FrozenHeart FrozenHeart - 1 year ago 96
C++ Question

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

Why does the following code print

, 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 < && baz < rhs.baz)
return true;
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
says that we already have that item in the map. Why?

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

Answer Source

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 < 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.baz);
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download