Invalid operator< using std::equal_to

Question

Without going into much details why I´m doing what I´m doing let me describe the issue.

Im using a std::set for storing unique objects of a struct called VertexTypePos3Normal.

The struct is defined as following:

struct VertexTypePos3Normal {
 // ctor, dtor ..
 friend bool operator==(const VertexTypePos3Normal& v1, const VertexTypePos3Normal& v2);
 friend bool operator<(const VertexTypePos3Normal& v1, const VertexTypePos3Normal& v2);
 glm::vec3 pos;
 glm::vec3 normal;

};

bool operator<(const VertexTypePos3Normal& v1, const VertexTypePos3Normal& v2) {
    return (v1.pos.x < v2.pos.x) && (v1.pos.y < v2.pos.y) && (v1.pos.z < v2.pos.z) && (v1.normal.x < v2.normal.x) && (v1.normal.y < v2.normal.y) && (v1.normal.z < v2.normal.z); 
}

// operator == ommited

Per default std::set uses std::less as comparison function. So I first declared my set as std::set<VertexTypePos3Normal> set; The elements inserted into the set are stored in a std::vector that is not containing unique values (looping over the vector). Using std::less called my operator< but the result was not correct as the set contained mostly only 1 value although the vector contained about 15 different ones.

Here is the method inserting into the set:

void createUniqueVertices(const std::vector<const VertexTypePos3Normal>& verticesIn,
                                  std::vector<const VertexTypePos3Normal>& verticesOut,
                                  std::vector<unsigned short>& indicesOut)
        {

            //std::map<VertexTypePos3Normal, int, std::equal_to<VertexTypePos3Normal> > map;
            std::set<const VertexTypePos3Normal, std::equal_to<const VertexTypePos3Normal> > set;

            int indexCounter = 0;

            for (auto c_it = verticesIn.cbegin(); c_it != verticesIn.cend(); ++c_it) {

                //bool newlyAdded = map.insert(std::pair<VertexTypePos3Normal, int>(*c_it, indexCounter)).second;

                bool newlyAdded = set.insert(*c_it).second;

                //if (newlyAdded) {
                    //verticesOut.push_back(*c_it);
                    //map.insert(std::pair<VertexTypePos3Normal, int>(*c_it, indexCounter));
                    //++indexCounter;
                //}

                //indicesOut.push_back(map[*c_it]);
            }
        }

So I was about to try out std::equal_to instead of std::less and wrote operator==. Now the weird stuff started:

Although I´m not calling std::less anymore and therefore also not operator<, there is an assertion error in STL (using VC compiler) _DEBUG_ERROR2("invalid operator<", _File, _Line);

So actually i got two questions:

1.) Why is my operator < not working with std::less as it is supposed to.

2.) How can operator< trigger an assertion when it is not even called.

EDIT: Thanks for all information. Looks like I totally missunderstood strict weak ordering. Using std::tie taking care of it solved my problem. Here is the updated code:

void createUniqueVertices(const std::vector<const VertexTypePos3Normal>& verticesIn,
                                  std::vector<const VertexTypePos3Normal>& verticesOut,
                                  std::vector<unsigned short>& indicesOut)
        {

            std::map<VertexTypePos3Normal, int> map;

            int indexCounter = 0;

            for (auto c_it = verticesIn.cbegin(); c_it != verticesIn.cend(); ++c_it) {

                bool newlyAdded = map.insert(std::pair<VertexTypePos3Normal, int>(*c_it, indexCounter)).second;

                if (newlyAdded) {
                    verticesOut.push_back(*c_it);
                    //map.insert(std::pair<VertexTypePos3Normal, int>(*c_it, indexCounter));
                    ++indexCounter;
                }

                indicesOut.push_back(map[*c_it]);
            }
        }

Im using a map in the final version as the set is obsolete.

Here is my new operator<

bool operator<(const VertexTypePos3Normal& v1, const VertexTypePos3Normal& v2) {
            return (std::tie(v1.pos.x, v1.pos.y, v1.pos.z, v1.normal.x, v1.normal.y, v1.normal.z) < std::tie(v2.pos.x, v2.pos.y, v2.pos.z, v2.normal.x, v2.normal.y, v2.normal.z));
        }

[Can't reproduce](http://coliru.stacked-crooked.com/a/a3694a760aa309c3) (this is the example I was able to pull off from the small amount of informations you are giving us). — Shoe, Feb 02 '14 at 16:24
The problem occurs at runtime when insering into the set. Sorry if my information provided was not enough. I added the method that is inserting into the set. Please redo the downvote if the question is more informative now. — Chris, Feb 02 '14 at 16:29
The assertion isn't necessarily being triggered by your `operator<`, I think that's a generic message indicating that your comparison predicate is somehow invalid, probably because your `operator==` doesn't meet [strict weak ordering](https://en.wikipedia.org/wiki/Strict_weak_ordering#Strict_weak_orderings) requirements (irreflexivity). — Praetorian, Feb 02 '14 at 16:49

score 4 · Answer 1 · answered Feb 02 '14 at 16:29

4

Ordered associative containers require a strict weak ordering relation. Among the required properties is antisymmetry, that is, cmp(x,y) implies !cmp(y,x). Your definition of operator< does not satisfy this property.

Also, equality (or equivalence) may be defined as !(cmp(x,y)||cmp(y,x)), and often this is used instead of x==y. That is, operator< may be called even if you don't use it explicitly.

answered Feb 02 '14 at 16:29

iavr

7,547
1
18
53

Thanks for that at first. I know about the strict weak ordering rule but was not able to see any rule I am not satisfying. And I know that operator< may be called but I set a breakpoint inside that is not triggered (but it is in operator==). – Chris Feb 02 '14 at 16:31
In any case, using `std::equal_to` is probably even worse than your incorrect `operator<`. – iavr Feb 02 '14 at 16:43
@Chris `operator==` is being called because you've defined your set with the comparison predicate as `std::equal_to`, what do you expect it to do in that case? You haven't shown us how your `operator==` is defined, but in all likelihood it violates `cmp(x,x) == false`, which is a requirement of strict weak ordering. – Praetorian Feb 02 '14 at 16:44
std::equal_to is calling operator< not operator== that is my confusion. I know it is supposed to call operator== like it does. – Chris Feb 02 '14 at 16:47
@Chris I don't understand why you keep saying that. You've proven it isn't being called by placing a breakpoint that is never hit. Look at my explanation in the comments below the question. And addressing your comment below the other answer, `std::tie` doesn't care what elements you give it, so if you want both `pos` and `normal` to be in the comparison, just add those too. `return std::tie(v1.pos.x, v1.pos.y, v1.pos.z, v1.normal.x, v1.normal.y, v1.normal.z) < std::tie(...);` – Praetorian Feb 02 '14 at 16:56
I updated my code above. Thanks for all your help. The output Expression: operator< just confused me. It should not be called opeator< when it is for a generic purpose I guess. – Chris Feb 02 '14 at 17:07

score 1 · Answer 2 · 2014-02-02T16:41:34.927

Your operator < is plain wrong.

You might want:

bool operator<(const VertexTypePos3Normal& v1, const VertexTypePos3Normal& v2) {
    if(v1.pos.x < v2.pos.x) return true;
    else if(v1.pos.x == v2.pos.x) {
        if(v1.pos.y < v2.pos.y) return true;
        else if(v1.pos.y == v2.pos.y) {
            if(v1.pos.z < v2.pos.z) return true;
            else if(v1.pos.z < v2.pos.z) {
                if(v1.normal.x < v2.normal.x) return true;
                else if(v1.normal.x == v2.normal.x) {
                    if(v1.normal.y < v2.normal.y) return true;
                    else if(v1.normal.y < v2.normal.y) {
                        if(v1.normal.z < v2.normal.z) return true;
                    }
                }
            }
        }
    }
    return false;
}

Note: That should be split into two less function calls for glm::vec3 (having bool less(const glm::vec3&, const glm::vec3&);)

Or simply `return std::tie(v1.pos.x, v1.pos.y, v1.pos.z) < std::tie(v2.pos.x, v2.pos.y, v2.pos.z);` — Praetorian, Feb 02 '14 at 16:35

Invalid operator< using std::equal_to

2 Answers2