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

Question

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.

`operator<` must define a strict weak ordering. Yours does not. — Pubby, Oct 11 '16 at 14:49
http://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering — Pubby, Oct 11 '16 at 14:51
Sorry the dupe was wrong. Your title does not match the problem — NathanOliver, Oct 11 '16 at 14:51
Define your operator as `return bar != rhs.bar ? bar < rhs.bar : baz < rhs.baz;` — Pubby, Oct 11 '16 at 14:51
@Pubby Can I just do `return bar < rhs.bar || baz < rhs.baz`? — FrozenHeart, Oct 11 '16 at 14:57
Think about putting two-letter words in alphabetical order. That is an example of strict weak ordering. Same thing here, just instead of two letters you have an `int` and a `string`. — Chris Drew, Oct 11 '16 at 15:22
Your question was not closed because of a typo. Read the duplicate. — juanchopanza, Oct 11 '16 at 18:18

Toby Speight · Accepted Answer · 2016-10-11T15:26:55.947

6

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);
}

edited Oct 11 '16 at 15:26

answered Oct 11 '16 at 15:03

Toby Speight

27,591
48
66
103

Can I just do `return bar < rhs.bar || baz < rhs.baz`? – FrozenHeart Oct 11 '16 at 15:05
4

@FrozenHeart: No. – Lightness Races in Orbit Oct 11 '16 at 15:06
1

@FrozenHeart you can do whatever you want, as complicated or as simple as you desire, but if it doesn't comply with [strict weak ordering restrictions](https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings) , it isn't going to work. That does not. In your case, `return bar < rhs.bar || (!(rhs.bar < bar) && (baz < rhs.baz))`, which `std::tie` couplings will give you (and thus why it is encouraged). – WhozCraig Oct 11 '16 at 15:06
If you don't like `std::tie()`, you could `return bar!=rhs.bar ? bar < rhs.bar : baz != rhs.baz ? baz < rhs.baz : /* more tests */ : false;`. But you won't get the necessary ordering by simply combining those two tests with boolean operators. I encourage you to work through the possibilities in your head or on paper to see why they won't work. – Toby Speight Oct 11 '16 at 15:12

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

1 Answers1