Когда два элемента набора STL считаются идентичными?

Question

От cplusplus.com:

template < class Key, class Compare = less<Key>,
       class Allocator = allocator<Key> > class set;

"Compare: класс сравнения: класс, который принимает два аргумента того же типа, что и элементы контейнера, и возвращает bool. Выражение comp (a, b), где comp является объектом этого класса сравнения, а a и b являются элементами контейнера, должны возвращать true, если a должен быть помещен в более раннюю позицию, чем b, в операции строгого слабого упорядочения. Это может быть либо класс, реализующий оператор вызова функции, либо указатель на функцию (см. конструктор для пример). По умолчанию используется значение less, которое возвращает то же самое, что и применение оператора less-than (a < b). Объект set использует это выражение для определения положения элементов в контейнере. Все элементы в контейнере набора всегда упорядочены в соответствии с этим правилом. "

Учитывая, что класс сравнения используется для определения того, какой из двух объектов является «меньшим» или «меньшим», как класс проверяет, равны ли два элемента (например, чтобы предотвратить вставку одного и того же элемента дважды)?

Я могу представить здесь два подхода: один будет вызывать (a == b) в фоновом режиме, но не предоставит возможность переопределить это сравнение (как со значением по умолчанию less <Key>), не кажется слишком STL- для меня. Другим было бы предположение, что (a == b) ==! (A Так как это на самом деле делается?

Answer 1

Не точный дубликат, но первый ответ здесь отвечает на ваш вопрос

Ваше второе предположение о поведении правильное

Answer 2

Ассоциативные контейнеры в стандартной библиотеке определены в терминах эквивалентности ключей , а не равенства как таковых .

Поскольку не все экземпляры set и map используют less, но могут использовать универсальный оператор сравнения, необходимо определить эквивалентность в терминах этой одной функции сравнения, а не пытаться ввести отдельное понятие равенства.

Как правило, две клавиши (k1 и k2) в ассоциативном контейнере с использованием функции сравнения comp эквивалентны тогда и только тогда, когда:

comp( k1, k2 ) == false && comp( k2, k1 ) == false

В контейнере, использующем std::less для типов, которые не имеют определенной специализации std :: less, это означает то же самое, что и:

!(k1 < k2) && !(k2 < k1)

Answer 3

Ваша ошибка - предположение, что «сравнение может быть сколь угодно сложным функтором bool». Не может.

std::set требует частичного упорядочения, поэтому a<b подразумевает !(b<a). Это исключает большинство бинарных булевых функторов. Из-за этого мы можем говорить об относительном положении a и b в этом порядке. Если a<b, то предшествует b. Если b<a, b предшествует a. Если ни a<b, ни b<a, то a и b занимают одну и ту же позицию в порядке и, следовательно, эквивалентны.

Answer 4

Ваш второй вариант правильный. Почему не чувствует это правильно? Что бы вы сделали, если бы тест на равенство не соответствовал уравнению, которое вы дали?