ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Category:

C++: сортировка ассоциативных контейнеров STL

Одно из отличий ассоциативных контейнеров от последовательных в том, что в ассоциативных контейнерах элементы всегда автоматически (без участия программиста) отсортированы в каком-то порядке (по умолчанию — по возрастанию).

Например, определим множество целых чисел:
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
Tags: Математика, Образование, Программирование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments