What _can_ I use as std::map keys?

Question

I have:

struct Coord
{
  int row, col ;

  bool operator<( const Coord& other ) const
  {
    return row < other.row && col < other.col ;
  }
} ;

I'm trying to create a map<Coord, Node*>, where you can look up a Node* by Coord.

The problem is, it has bugs. Lookups into the map<Coord, Node*> by Coord are returning the wrong ones.

I'm having difficulty figuring out if this is appropriate or not.

Wikipedia says, map [keys] requires a strict weak ordering. Have I done this wrong? Is there a way to make it work, or should keys for a map be simple values that can be "strictly ordered"?

Basically the question is what is required for a custom struct to work as a key for my std::map?

Can you be more specific about "has bugs"? Does your code compile? Return the wrong results? Crash? — , Dec 06 '09 at 21:06
std::map does not have any bugs. At least in MS STL that i have seen. Also wikipedia is not the best source for RTFN. — Captain Comic, Dec 06 '09 at 21:09
What I mean by "has bugs" is just the following sentence: "Lookups into the map by Coord are returning the wrong ones." — bobobobo, Dec 06 '09 at 21:22

score 21 · Accepted Answer · answered Dec 06 '09 at 21:08

Yes you could very well have a problem with strict-weak ordering. Odds are its not working like you'd expect. Consider:

  bool operator<( const Coord& other ) const
  {
    return row < other.row && col < other.col ;
  }

obj1 (this) row: 2 col: 3

obj2 row: 3 col: 2

obj1 < obj2? => false

ok well then:

obj2 < obj1? => false

The only conclusion is that they must be equal (based on your < operator). Since this is a map, and keys are unique, both keys reselve to the same spot. This behavior may-or-may not be what you expect, but it sounds like it probably isn't.

What you need is to make a precedence between row/col so that < really works like you'd expect:

  bool operator<( const Coord& other ) const
  {
     // look at row first, if row is equal, check column.
     if (row < other.row)
     {
         return true;
     }
     else if (row == other.row)
     {
         return col < other.col ;
     }
     return false;
  }

or else `return row < other.row || (row == other.row && col < other.col)` — David Rodríguez - dribeas, Dec 06 '09 at 21:41
It isn't just the fact that the comparison may not do what is wanted that is the problem, it's the fact the equivalence under the original definition isn't an equivalence relation and this violates the requirements for use as a key in `std::map`. — CB Bailey, Dec 06 '09 at 21:47
+1, this is why professionals use `tie(col, row) < tie(other.col, other.row)` ;) — avakar, Dec 06 '09 at 22:05

score 6 · Answer 2 · 2009-12-06T21:14:17.060

6

You probably want:

 bool operator<( const Coord& other ) const
  {
    if ( row < other.row ) {
       return true;
    }
    else if ( row == other.row ) {
       return col < other.col;
    }
    else {
       return false ;
    }
  }

or vice versa. This one has bitten me a few times too!

edited Dec 06 '09 at 21:14

answered Dec 06 '09 at 21:06

Thanks for the acceptance, but I thought Doug T's answer was much better, and includes what I wrote. – Dec 06 '09 at 21:28
Well, yours answers the question, and was earlier. But I'll change it. – bobobobo Dec 06 '09 at 21:30

score 1 · Answer 3 · answered Dec 06 '09 at 21:08

1

try this:

struct Coord
{
  int row, col ;

  bool operator<( const Coord& other ) const
  {
    if (row != other.row)
      return row < other.row;

    return col < other.col ;
  }
} ;

answered Dec 06 '09 at 21:08

dcp

54,410
22
144
164

score 0 · Answer 4 · answered Dec 06 '09 at 21:12

0

bool operator<(const Coord& other) const
{
    return row < other.row
        || row ==other.row
        && col < other.col;
}

answered Dec 06 '09 at 21:12

Fred

101
2

It's more correct to not use the `==` operator. To compare two elements with `operator<`, they should only have to define `operator<`. – GManNickG Dec 06 '09 at 21:19
@GMan We are talking about comparing integer here. – Dec 06 '09 at 21:20
2

How about parentheses to make it clear that && has higher precedence than ||? – Dec 06 '09 at 21:20
@Neil In the abstract it's a very good point. You don't want your code to break because you change the underlying types. – Dec 06 '09 at 21:22
@super Does that mean you never use the == operator? I doubt it somehow. – Dec 06 '09 at 21:33
1

No, it doesn't, but I do make an attempt to make the requirements of underlying types minimal. If you only use < here, then the underlying types only have to define an operator<, not both operator< and operator==. Also, although it may seem unnatural to avoid == here, it seems satisfying that operator< only be defined in terms of operator< of the types it's comparing. – Dec 06 '09 at 21:38
I'd also argue for using < only, because that gives you the canonical form. E.g. `if (row < other.row) return true; if (other.row < row) return false; return col < other.col;` – MSalters Dec 07 '09 at 11:10

score 0 · Answer 5 · answered Dec 06 '09 at 21:42

For a comparison function to impose a strict weak ordering on the set of values for your object, one of the conditions is that equivalence must be transitive. a and b are said to be equivalent if (in C++ syntax) !(a < b) && !(b < a) is true.

Your operator< fails this requirement. Consider a = { 1, 3 }, b = { 3, 2 }, c = { 2, 1 }. In this case neither of a < b, b < a are true and neither of a < c, c < a are true. This means that a and b are equivalent and a and c are equivalent, however clearly c < b so b and c are not equivalent, thus showing that equivalence isn't transitive. This is why your operator< is not suitable for Coord to be used as a key in a std::map.

What _can_ I use as std::map keys?

5 Answers5

Linked