std :: map с ключами, которые не имеют порядка - PullRequest
Новая
       4

std :: map с ключами, которые не имеют порядка

0 голосов
/ 28 февраля 2020

Какой подход следует использовать, если я хочу, чтобы std::map использовал пользовательский объект в качестве ключа?

Давайте рассмотрим этот минимальный фиктивный код (который компилируется, но не работает правильно): 

#include <map>

class Object
{
public:
  int x, y;
  Object(int x, int y) : x(x), y(y) {};
  bool operator<(const Object& o) const { return 1;};   // bogus just to make compiler happy
};

int main()
{
  Object o1(1, 2), o2(3, 4);
  std::map<Object, int> objmap;
  objmap.insert(std::make_pair(o1, 11));
  objmap.insert(std::make_pair(o2, 22));
}

Чтобы использовать объект как ключ в std::map, нам нужен оператор <.

Пока все хорошо, но что можно сделать, если объекты нельзя сравнивать с точки зрения «меньше» или «больше», а только с точки зрения «другое»?

Ответы [ 3 ]

2 голосов
/ 28 февраля 2020

Ваши объекты должны уважать строгий общий порядок . Это означает, что самое главное, ваше < отношение должно быть нерефлексивным и переходным. В вашем случае рассмотрите возможность использования std :: tuple, который уже обеспечивает функционирование operator< с лексикографическим упорядочением.

Это будет «правильное» упорядочение, но, скорее всего, совсем не то, что вы хотели бы: 

friend bool operator<(Object const& a, Object const& b) {
  return a.x < b.x; // probably not what you want, but legal
}

Поскольку это будет означать, что Object{1,100} и Object{1,101} приведут к std::map, если они будут одним и тем же ключом (если вы не хотите именно этого).

Однако, Вы можете фактически сломать карту, если предоставите следующее: 

friend bool operator<(Object const& a, Object const& b) {
  return a.x <= b.x; // this will break map
}

, потому что оно не является рефлексивным (т. е. x

В общем, вы должны рассмотреть все свойства вашего объекта, чтобы избежать совмещения имен (т. е. карта считает два разных объекта равными). Если вы не покажете нам свой Object, нет способа показать вам, как реализовать правильный operator<.

В большинстве случаев std::unordered_map - лучший (и более эффективный) выбор.

1 голос
/ 28 февраля 2020

Поскольку здесь нет общей последовательности заказов между Object с, одна возможность - использовать unorded_map вместо map.

Поэтому классу object требуется как минимум перегруженный == оператор и пользовательская функция ha sh: 

#include <unordered_map>
#include <iostream>

class Object
{
public:
  int x, y;
  Object(int x, int y) : x(x), y(y) {};

  bool operator==(const Object& o) const
  {
    std::cout << "equal hashes, using == operator on (" << x << "," << y << ")\n";
    auto isequal = x == o.x && y == o.y;
    std::cout << "objects are " << (isequal ? "" : "not ") << "equal\n";
    return isequal;
  };

  friend std::ostream& operator<<(std::ostream& os, const Object& o);
};

std::ostream& operator<<(std::ostream& os, const Object & o)
{
  os << "(" << o.x << "," << o.y << ")";
  return os;
}

struct ObjectHash {
  size_t operator()(const Object& o) const
  {
    std::cout << "hashing (" << o.x << "," << o.y << ")\n";;
    return o.x + o.y;  // purposly bad hash function, so we get collisions
                       // (o.x * 127) ^ o.y  would be better, still not ideal
  }
};


int main()
{
  Object o1(1, 2);
  Object o2(3, 4);  // different from o1, o3 and o4
  Object o3(1, 2);  // equal to o1
  Object o4(2, 1);  // different from o1, o2 and o3 but same hash as o1

  std::unordered_map<Object, int, ObjectHash> objmap;
  std::cout << "Inserting " << o1 << "\n"; objmap.insert(std::make_pair(o1, 11));
  std::cout << "Inserting " << o2 << "\n"; objmap.insert(std::make_pair(o2, 22));
  std::cout << "Inserting " << o3 << "\n"; objmap.insert(std::make_pair(o3, 33));
  std::cout << "Inserting " << o4 << "\n"; objmap.insert(std::make_pair(o4, 33));
}

* * * * * * * * * * * * * * * * * * * * * * * std::cout * * * * * * * * * * * * * * * * * *1011*

* 

Inserting (1,2)
hashing (1,2)
Inserting (3,4)
hashing (3,4)
Inserting (1,2)
hashing (1,2)
equal hashes, using == operator on (1,2)
objects are equal
Inserting (2,1)
hashing (2,1)
equal hashes, using == operator on (2,1)
objects are not equal
*
1 голос
/ 28 февраля 2020

Пока все хорошо, но что можно сделать, если объекты нельзя сравнивать с точки зрения «меньше» или «больше», а только с точки зрения «другого»?

Как правило, вы можете синтезировать и порядок, например, 

bool operator<(const Object& o) const { return std::tie(a, b) < std::tie(o.a, o.b); }

Кстати, именно эту конструкцию будет использовать сравнение по умолчанию в C ++ 20. 

auto operator<=>(const Object& o) const = default;
...