Что я могу использовать в качестве ключей std :: map?

Question

Расширяет .

У меня есть:

struct Coord
{
  int row, col ;

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

Я пытаюсь создать map<Coord, Node*>, где вы можете найти Node* на Coord.

Проблема в том, что в ней есть ошибки. Поиски в map<Coord, Node*> на Coord возвращают неправильные.

Мне трудно понять, подходит ли это или нет.

Википедия говорит: карта [ключи] требует строгого слабого порядка . Я сделал это неправильно? Есть ли способ заставить его работать, или ключи карты должны быть простыми значениями, которые можно «строго упорядочить»?

В основном вопрос заключается в том, что требуется для пользовательского struct для работы в качестве ключа для моего std :: map?

Answer 1

Да, у вас вполне могут быть проблемы со строго-слабым порядком. Скорее всего, он не работает, как вы ожидаете. Рассмотрим:

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

obj1 (это) ряд: 2 col: 3

obj2 ряд: 3 col: 2

obj1 ложь

хорошо, тогда:

obj2 false

Единственный вывод - они должны быть равны (в зависимости от вашего оператора <). Поскольку это карта, а ключи уникальны, оба ключа находятся в одном месте. Такое поведение может или не может быть то, что вы ожидаете, но похоже, что это не так. </p>

Вам нужно сделать приоритет между строкой / столбцом, чтобы <действительно работал так, как вы ожидаете: </p>

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

Answer 2

Вы, вероятно, хотите:

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

или наоборот. Этот тоже меня укусил несколько раз!

Answer 3

попробуйте это:

struct Coord
{
  int row, col ;

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

    return col < other.col ;
  }
} ;

Answer 4

Чтобы функция сравнения наложила строгий слабый порядок на набор значений для вашего объекта, одно из условий состоит в том, что эквивалентность должна быть транзитивной. a и b называются эквивалентными, если (в синтаксисе C ++) !(a < b) && !(b < a) имеет значение true.

Ваш operator< не соответствует этому требованию. Рассмотрим a = {1, 3}, b = {3, 2}, c = {2, 1}. В этом случае ни a Coord для использования в качестве ключа в std::map.

Answer 5

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