Требования к использованию структуры в качестве ключа карты STL?

Question

Я использую карту STL с ключом struct. Это определение карты: std::map<Coord2<uint8_t>, MapTile> tile_;

Определение struct:

template <typename T> 
struct Coord2 
{ 
    T x; 
    T y; 

    bool operator<(const Coord2<T> &coord) const { return (x < coord.x || y < coord.y); } 
    bool operator>(const Coord2<T> &coord) const { return (x > coord.x || y > coord.y); } 
} 

Будет ли возникнуть проблемы с картой, так как сравнение?

Answer 1

Этот operator< непригоден для использования с ассоциативными контейнерами стандартной библиотеки C++.

Компаратор должен предоставить strict weak ordering, которого нет у вас. Рассмотрим следующие операнды, которые демонстрируют свою несостоятельность:

a = { x = 1, y = 0 } 
b = { x = 0, y = 1 } 

Учитывая эти входы, a < b == true и b < a == true, но b != a.

Правильное сравнение для этого типа может быть:

if (x < coord.x) 
    return true; 

if (coord.x < x) 
    return false; 

return y < coord.y; 

(Это, конечно, можно написать этот правильный код в более компактном виде, однако я отлажена достаточно ошибок, вызванных неправильно выполненных строгими слабыми порядками, что Я настоятельно рекомендую быть очень явным в сравнении, так что ясно, что это правильно. С этой реализацией очень ясно, что мы сравниваем только значения y, если значения x сравниваются одинаковыми, что мы и хотим.)

Answer 2

Первое замечание: вам не нужно operator>, так как std::map будет использовать только operator<.

Однако ваш operator< является не подходит для std::map ключа, поскольку он не определяет строгий слабый порядок. На самом деле, это даже и не осуществлять строгий частичный порядок, так как он нарушает как транзитивность и антисимметрию: Рассмотрим следующие определения:

coord p = { 2, 2 }; 
coord q = { 0, 4 }; 
coord r = { 1, 1 }; 

Нор p < q возвращается true потому 2 < 4, q < r возвращает true потому что 0 < 1, но p < r возвращается false , Таким образом, транзитивность нарушается.

Кроме того, не только p < q возвращение true, но так же q < p, т.к. 0 < 2. Другими словами, согласно вашему оператору, каждый из p и q будет считаться меньшим, чем другой.

Answer 3

Для двух значений ответа Джеймс идеально подходит для нескольких членов это становится сложнее, поэтому простым способом реализовать строгий слабый порядок в течение нескольких значений для создания кортежей этих значений и сравнить кортежи:

return boost::tie(x, y, z) < boost::tie(coord.x, coord.y, coord.z); 

Все, что вам нужно сделать для этого, - это для каждого члена быть LessThanComparable, затем #include <boost/tuple/tuple_comparison.hpp> и перечислить членов в том же порядке в каждом выражении tie.

В C++ 11 вы можете #include <tuple> и использовать вместо этого std::tie.

Сравнение для кортежей определяется как лексикографическое сравнение, поэтому сравниваются первые элементы, и если результат верен, сравнение завершено и возвращается истина, в противном случае сравниваются следующие элементы таким же образом, для каждой пары элементов. Это гарантирует правильный строгий слабый порядок, если каждый тип элемента имеет правильно заданный operator<.