C++ Map<>.find() overloading for different class

Question

I try to use a map which is defined as :

    map<Vertex,unsigned int> _addedVertices;

now when I use the find function to check if a vertex is already inside I get an iterator to a wrong vertex with different information, so I have tried the following :

    map<Vertex,unsigned int,cmpByVertexFields> _addedVertices;

which didn't help.

also I have the following overloaded functions inside the Vertex class.

    bool operator<(const Vertex &otherV)const{
        return(_x<otherV._x && _y<otherV._y && _z<otherV._z);
    }
    bool operator==(const Vertex &otherV)const{
        return _x==otherV._x && _y==otherV._y && _z==otherV._z;
    }

but nothing works. Example: I've inserted a vertex containing (0.2,0.1,0.4) and next thing I use is the find function with (0.2,0.15,0.41) the iterator I get is of the first vertex instead of map.end().

What did I forget to define? Thanks

edit: cmpByVertexFields :

struct cmpByVertexFields {
    bool operator()(const Vertex& a, const Vertex& b) const {
        return a.getX()==b.getX() &&
            a.getY()==b.getY() &&
            a.getZ()==b.getZ();
    }
};

Your less-than `operator<` does not implement a [strict weak ordering](http://www.sgi.com/tech/stl/StrictWeakOrdering.html). This is a requirement for an `std::map` to function correctly. — juanchopanza, Jul 20 '13 at 11:43
I advise you to read about lexicographical ordering. Basically a struct with N fields is a bit like a string with N characters, now compare "ab" and "ba", with your operator: `"ab" < "ba"` `<=>` `'a' < 'b' and 'b' < 'a'` <=> `true and false` <=> `false`, and yet we know that "ab" IS less then "ba" :) — Matthieu M., Jul 20 '13 at 12:14

score 5 · Accepted Answer · answered Jul 20 '13 at 11:47

This is your culprit

bool operator<(const Vertex &otherV)const{
        return(_x<otherV._x && _y<otherV._y && _z<otherV._z);
    }

This doesn't yield strict weak ordering.

You need something like this

bool operator<(const Vertex &otherV)const{
        if(_x != otherV.x)
               return _x < otherV.x;
        if(_y != otherV.y)
               return _y < otherV.y;
        return _z < otherV.z;
    }

Or, equivalently and more conveniently, compare them as tuples, using std::tie

bool operator<(const Vertex &otherV)const{
       return std::tie(x_, y_, z_) < std::tie(OtherV.x_, OtherV.y_, OtherV.z_);
}

score 4 · Answer 2 · edited May 23 '17 at 10:25

4

As Juan said in a comment, your operator < implementation is semantically incorrect. Since you’re talking about vertices, you actually need to implement a lexicographical comparison across _x, _y and _z.

The easiest way is to use the std::tuple built-in comparison:

bool operator<(const Vertex &otherV)const{
    return std::tie(_x, _y, _z) < std::tie(otherV._x, otherV._y, otherV._z);
}

Using std::tie in this way is now the established way of implementing a lexicographical comparison across (member) variable (and you can actually use the same for the operator== implementation).

edited May 23 '17 at 10:25

Community

1
1

answered Jul 20 '13 at 11:47

Konrad Rudolph

530,221
131
937
1,214

Thanks to all of you guys, took me a while to understand the mistake but now I see why its not a good comparison function. Cheers – Despair Jul 20 '13 at 11:52

score 4 · Answer 3 · answered Jul 20 '13 at 11:48

The comparison functor or less than operator< must implement a strict weak ordering. This is a requirement for an std::map. Yours does not. There is no obvious and natural way to order 3D vertices, but if you want to order lexicographically by x, y and then z coordinate, then the easiest way is to use std::tie (or boost::tie or std::tr1::tie if you do not have C++11 support):

bool operator<(const Vertex &otherV)const{
    return std::tie(_x, _y, _z) < std::tie(otherV._x, otherV._y, otherV._z);
}

Note that this ordering is completely arbitrary: why would x take precedence over y? It is up to you to implement the ordering that suits the problem you are trying to solve. On the other hand, if you don't care about the actual ordering of the elements of the map, any strict weak ordering will do.

C++ Map<>.find() overloading for different class

3 Answers3