Например, определим множество целых чисел:
set<int> iSet;это то же самое, что и
set<int, less<int>> iSet;
Код
set<int> iSet {2, 1, 5, 4, 3, 5}; set<int>::iterator iter; for (iter = iSet.begin(); iter != iSet.end(); iter++) cout << *iter << ' ';выдаст на экран следующее:
1 2 3 4 5
Порядок сортировки элементов в ассоциативном контейнере задается функциональным объектом (в примере выше —
less<int>
). То есть сортировка элементов в определенном выше множестве производится посредством сравнения элементов с помощью единственной операции — «меньше».Множество в C++ по определению не может включать одинаковые элементы (в отличие от мультимножества). Это видно в приведенном выше примере: при определении множества ему на вход задается последовательность из 6 элементов: 2, 1, 5, 4, 3, 5, а в итоге множество содержит последовательность из 5 элементов: 1, 2, 3, 4, 5. Второе число 5 не было включено во множество.
И вот тут я задумался: каким образом программа определяет равенство элементов, если ей при сравнении доступна только операция «меньше»? Если один элемент меньше другого, тут всё понятно, они не равны. А если один элемент не меньше другого? Тут два варианта: либо они равны, либо первый больше второго — неясно, есть ли равенство.
(При использовании множеств с элементами базовых типов у меня этот вопрос не возникал, так как я понимал, что для базовых типов в принципе доступны все операции сравнения. Но когда я стал использовать множество с элементами-объектами написанного мною класса и при этом для этого класса я перегрузил только операцию «меньше», а программа работала всё так же прекрасно, этот вопрос и возник. Текст этой программы можно посмотреть тут.)
Тут нужно понимать, что функциональный объект возвращает значение логического типа (
bool
), а это значит, что программа кроме операции «меньше», применяемой к элементам множества, может использовать еще и логические операции, применяя их к результату, возвращаемому функциональным объектом.Как оказалось, элементы
а
и б
считаются равными, если для функционального объекта comp
выражение!comp(а, б) && !comp(б, а)
принимает значение
истина
.В приведенном выше примере у нас есть функциональный объект «меньше» (
less<int>
). Предположим, нужно сравнить на равенство элементы со значениями 1 и 4, а затем элементы со значениями 5 и 5. Тогда:!(1 < 4) && !(4 < 1)
то же, что и!(истина) && !(ложь)
то же, что иложь && истина
то же, что иложь
,то есть 1 и 4 не равны.
!(5 < 5) && !(5 < 5)
то же, что и!(ложь) && !(ложь)
то же, что иистина && истина
то же, что иистина
,то есть 5 и 5 равны.
То есть два элемента равны, если первый не меньше второго и одновременно второй не меньше первого.
В математике это называют асимметричным отношением (по-английски asymmetric relation). Вернее, выделенное жирным выше правило вытекает из асимметричности операций сравнения «меньше» и «больше» и симметричности операции «равно». Асимметричность (по-английски asymmetry) — одно из условий (свойств) отношения строгого частичного порядка (по-английски strict weak ordering) на множестве. Эти термины мне встретились, пока я читал источники (см. ниже).
Асимметричность операций «меньше» и «больше» выражается в том, что:
при а < б не может быть, что б < а
при а > б не может быть, что б > а
Симметричность операции «равно» выражается в том, что:
при а == б также верно, что б == а
https://en.cppreference.com/w/cpp/container/set
https://en.cppreference.com/w/cpp/named_req/Compare