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

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

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

(У одного и двух classов есть оператор! = И правильный оператор ==)

typedef std::pair 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 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 < } 

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

Очень важно, что A < B истинно, тогда B < A является ложным. Более того, если A < B и B < C истинны, то A < C также верно.

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

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

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

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

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