FrozenHeart FrozenHeart - 1 month ago 5
C++ Question

How does std:map check whether two objects are equal?

Why does the following code print

1
, even though I insert two elements into the map?

#include <iostream>
#include <map>
#include <string>
#include <utility>

struct Foo
{
Foo(int bar, const std::string& baz)
: bar(bar)
, baz(baz)
{}

int bar;
std::string baz;

bool operator<(const Foo& rhs) const
{
if (bar < rhs.bar && baz < rhs.baz)
{
return true;
}
else
{
return false;
}
}
};

int main()
{
Foo first(0, "test");
Foo second(1, "test");
std::map<Foo, std::string> m;
m.insert(std::make_pair(first, "test"));
m.insert(std::make_pair(second, "test1"));
std::cout << m.size() << std::endl;
}


The second call to
insert()
says that we already have that item in the map. Why?

My previous question was mistakenly closed because of the typo. I know that
insert
will tell you whether that item is already in the container.

Answer

The map's insert() uses the operator< you provided to decide equivalence between elements. If a < b and b < a are both false, then the two elements are considered equal.

Your operator<() is inconsistent because it doesn't define the necessary strict weak ordering. For example, consider a.bar < b.bar and b.baz < a.baz; then a < b is false and b < a is false, so the map believes a == b.

In your specific case, when comparing first and second, then first.baz and second.baz are both "test", so both comparisons return false, and the elements are considered equal.

You need something like:

bool operator<(const Foo& rhs) const
{
    return std::tie(bar, baz) < std::tie(rhs.bar, rhs.baz);
}
Comments