What _can_ I use as std::map keys?

Extends.

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?

From stackoverflow

• 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!

  anon : Thanks for the acceptance, but I thought Doug T's answer was much better, and includes what I wrote.

  bobobobo : Well, yours answers the question, and was earlier. But I'll change it.

  Doug T. : thanks for the compliment.

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

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

  David Rodríguez - dribeas : or else `return row < other.row || (row == other.row && col < other.col)`

  Charles Bailey : 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`.

  avakar : +1, this is why professionals use `tie(col, row) < tie(other.col, other.row)` ;)

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

  GMan : It's more correct to not use the `==` operator. To compare two elements with `operator<`, they should only have to define `operator<`.

  anon : @GMan We are talking about comparing integer here.

  superoptimizer : How about parentheses to make it clear that && has higher precedence than ||?

  superoptimizer : @Neil In the abstract it's a very good point. You don't want your code to break because you change the underlying types.

  anon : @super Does that mean you never use the == operator? I doubt it somehow.

  superoptimizer : 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.

  MSalters : 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;`

• 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.