Зачем использовать std:: less в качестве функтора по умолчанию для сравнения ключей в std:: map и std:: set?

Мне интересно, почему std::map и std::set используют std::less как функтор по умолчанию для сравнения ключей. Почему бы не использовать функтор, который работает аналогично strcmp? Что-то вроде:

Скажите, что map имеет в нем два объекта с ключами key1 и key2. Теперь мы хотим вставить другой объект с ключом key3.

При использовании std::less функция insert должна сначала вызвать std::less::operator() с помощью key1 и key3. Предположим, что std::less::operator()(key1, key3) возвращает false. Он должен снова вызвать std::less::operator() с помощью переключаемых клавиш std::less::operator()(key3, key1), чтобы решить, равен ли key1 key3 или key3 больше, чем key1. Для принятия решения, если первый вызов возвращает false, есть два вызова std::less::operator().

Если бы std::map::insert использовал compare, то было бы достаточно информации, чтобы принять правильное решение, используя только один вызов.

В зависимости от типа ключа на карте std::less::operator()(key1, key2) может быть дорогостоящим.

Если мне не хватает чего-то очень простого, не следует std::map и std::set использовать вместо std::less что-то вроде compare как функтор по умолчанию для сравнения ключей?

Ответы

Ответ 1

Я решил попросить об этом Александра Степанова (конструктора STL). Мне разрешено процитировать его следующим образом:

Первоначально я предложил трехсторонние сравнения. Стандартный комитет попросил мне перейти на стандартные операторы сравнения. Я сделал то, что мне сказали. Я выступал за добавление 3-сторонних компонентов к стандарту для более 20 лет.

Но обратите внимание, что, возможно, неинтуитивно, 2-way - это не огромные накладные расходы. Вам не нужно делать в два раза больше сравнений. Это только одно сравнение на node по пути вниз (без проверки равенства). Стоимость не может вернуться раньше (когда ключ находится в нелисте) и одно дополнительное сравнение в конце (свопинг аргументов для проверки равенства). Если я не ошибаюсь, это делает

1 + 1/2*1 + 1/4*2 + 1/8*3 + ...
= 1 + 1/2+1/4+1/8+... + 1/4+1/8+... + ...
-> 3  (depth -> infty)

дополнительные сравнения в среднем на сбалансированном дереве, содержащем запрошенный элемент.

С другой стороны, трехстороннее сравнение не имеет ужасных накладных расходов: Непрерывное трехстороннее сравнение целых чисел. Теперь, нужна ли дополнительная ветвь для проверки результата сравнения против 0 (равенство) в каждом node меньше накладных расходов, чем оплата 3 дополнительных сравнений в конце - это еще один вопрос. Наверное, не имеет большого значения. Но я думаю, что само сравнение должно было быть 3-значным, поэтому можно было бы изменить решение о том, использовать ли все 3 результата.

Обновление: см. комментарии ниже, почему я думаю, что трехстороннее сравнение лучше в деревьях, но не обязательно в плоских массивах.

Ответ 2

Контейнеры на основе дерева требуют только строгого полного заказа.

См. https://www.sgi.com/tech/stl/StrictWeakOrdering.html

доступ на запись

Точка вставки для карт и множеств определяется исключительно одним бинарным поиском, например. lower_bound или upper_bound. Сложность двоичного поиска во время выполнения O(log n)
доступ для чтения

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

Результат состоит в том, что информация equality не требуется. Просто эти элементы могут иметь эквивалентный порядок.

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