std :: map, пользовательские ограничения дизайна компаратора

Я пытался определить пользовательский компаратор для контейнера std :: map.

Вопрос в том, могу ли я включить операторы == и! = Или это нарушит строгий слабый порядок? Я вынужден использовать оператор < ?

(Один и два класса имеют операторы! = И оператор == определены правильно)

typedef std::pair<One, Two> MapKey_t;
class cmp
{
bool operator()(const MapKey_t& left, const MapKey_t& right) const
{ return left.first != right.first && right.first == right.second; }
}

typedef std::map<MapKey_t, Three*, cmp> MyMap_t;

Поскольку переключение влево и вправо не приведет к изменению возвращаемого значения компаратора, будет ли это работать?

Меня не волнует, как элементы сортируются в контейнере, но я не хочу, чтобы дубликаты были частью этого.

Обновить :

можно использовать адрес памяти для получения строгого слабого порядка?

class cmp
{
bool operator()(const MapKey_t& left, const MapKey_t& right) const
{
if(left.first == right.first)
if(left.second != right.second)
return false; // This represents for me, functionally, a duplicate
else
// Can't use operator < there since left.second equals right.second but
// functionally for me, this is not a duplicate and should be stored
// what about memory address strict weak ordering ?
return &left < &right;
else
return left.first < right.first; // There I can use operator <
}

1

Решение

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

Это очень важно, что A < B верно, то B < A ложно Кроме того, если A < B а также B < C оба верны, то A < C тоже верно.

Если вы не хотите или не можете установить строгий слабый порядок для ваших типов, тогда вы можете использовать карту, которая не требует этого: std::unordered_map1, которая является хэш-картой. Однако для этого потребуется предоставить хеш-функцию и сравнение на равенство. Это также требует, чтобы ваш компилятор имел поддержку C ++ 11.

1 Как @JohnDibling указывает в комментариях, std::unordered_map к сожалению назван. Это должно было быть std::hash_map но, видимо, это имя могло конфликтовать с hash_maps из других библиотек. В любом случае, цель состоит не в том, чтобы иметь карту, которая не упорядочена, а в том, чтобы иметь карту с постоянным временем поиска.

5

Другие решения

Вам может быть все равно, как все упорядочено на карте, но карта это делает. Код, который вы предоставили выше, похоже, неправильно реализует строгий слабый порядок. Как вы уже заметили, переключение влево и вправо не изменит результат operator() во всех случаях ваша функция не реализует строгое слабое упорядочение.

Вы не обязательно должны реализовывать компаратор с точки зрения operator< напрямую, но вы должны убедиться, что если operator()(A,B) возвращается true, затем operator()(B,A) также не возвращается true,

5

Это недопустимо, слабый порядок строк означает, что A < B а также B < A не должно быть правдой одновременно. std::map опирается на это, чтобы установить и порядок и равенство ключей

0