Почему неупорядоченные ассоциативные контейнеры реализуют меньше оператора?

У неупорядоченных ассоциативных контейнеров unordered_set, unordered_map и т.д. не меньше оператора operator<, не как функция-член, а как свободная функция. Зачем? Специализации less нет. SGI STL hash_* также не имеют этой функции.

Если исключить понятие базовых типов, все типы контейнеров удовлетворяют требованиям обычных типов, как определено, например. в Элементах программирования Степанова и Макджона. Единственным исключением являются неупорядоченные ассоциативные типы, которым не хватает operator<.

Я не мог придумать эффективную реализацию такого оператора, который бы соответствовал данному определению равенства, так что может быть причиной эффективности? С другой стороны, operator== для неупорядоченных ассоциативных контейнеров в некоторых случаях требует перефразировать каждый элемент одного контейнера и искать его в другом - O (N) среднем, но в худшем случае O (N²).

Ответ 1

Концептуально это не имеет большого смысла. Рассмотрим мешок из разных цветных мраморов. И скажем, у вас есть два мешка из мрамора:

Содержит красный, синий, зеленый.
Содержит фиолетовый, красный, желтый.

Является ли мешок 1 < мешок 2?

Даже если вы связываете порядок с цветами, скажите:

red < yellow < purple < blue < green

По-прежнему трудно сказать, не мешает ли один мешок другому, потому что внутри мешок не привязывает к мрамору никакого порядка. То есть сумка 1 может выводиться в любом из 6 форматов, которые эквивалентны:

красный, синий, зеленый
красный, зеленый, синий
синий, красный, зеленый
синий, зеленый, красный
зеленый, красный, синий
зеленый, синий, красный

Ни один из этих шести не меньше, чем любой другой. Действительно, все они равны, независимо от того, синий или синий < красный. Сумка не является последовательностью... это неупорядоченная последовательность.

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

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf