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?

回答1:

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

回答2:

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!

回答3:

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

回答4:

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

回答5:

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.