stl ordering - строгий слабый порядок

Question

Почему STL работает с функцией сравнения со строгим слабым порядком? Почему это не может быть частичным заказом?

Answer 1

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

Answer 2

Просто строгий слабый порядок определяется как порядок, который определяет (вычислимое) отношение эквивалентности. Классы эквивалентности упорядочены строгим слабым порядком: строгий слабый порядок является строгим порядком классов эквивалентности.

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

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

Дано

• математический набор S
• частичный заказ < над S
• ценность x в S

Вы можете определить раздел S (каждый элемент S либо в L(x), I(x) или же G(x)):

L(x) = { y in S | y<x }
I(x) = { y in S | not(y<x) and not(x<y) }
G(x) = { y in S | x<y }

 L(x) : set of elements less than x
 I(x) : set of elements incomparable with x
 G(x) : set of elements greater than x

Последовательность отсортирована в соответствии с < если для каждого x в последовательности, элементы L(x) появляются сначала в последовательности, затем следуют элементы I(x)с последующими элементами G(x),

Последовательность топологически отсортирована, если для каждого элемента y который появляется после другого элемента x в последовательности, y не менее чем x, Это более слабое ограничение, чем сортировка.

Тривиально доказать, что каждый элемент L(x) меньше любого элемента G(x), Там нет общего отношения между элементами L(x) и элементы I(x)или между элементами I(x) и элементы G(x), Однако если < это строгий слабый порядок, чем каждый элемент L(x) меньше любого элемента I(x), а чем любой элемент I(x) меньше любого элемента G(x),

Если < это строгий слабый порядок, и x<y тогда любой элемент L(x) U I(x) меньше любого элемента I(y) U G(y): любой элемент не больше чем x меньше любого элемента не меньше y, Это не обязательно верно для частичного заказа.

Answer 3

Цитирую ответ, приведенный здесь:

Потому что внутренне эти алгоритмы реализуют "равно" как !(a < b) && !(b < a),

Если вы использовали <= чтобы реализовать оператор меньше чем, то выше будет возвращать ложь, когда a == b, Сломанная проверка на равенство испортит практически любой алгоритм.

Точно так же они реализуют "не равно", как (a < b) || (b < a) и еще раз, если вы реализовали < оператор, использующий <=тогда он вернет истину, когда они равны друг другу, а на самом деле они не равны. Таким образом, проверка на равенство нарушена в обоих направлениях.

Весь смысл ограничения библиотеки оператором "меньше" состоит в том, что все логические операторы могут быть реализованы в терминах этого:

• <(a, b): (a < b)
• <=(a, b): !(b < a)
• ==(a, b): !(a < b) && !(b < a)
• !=(a, b): (a < b) || (b < a)
• >(a, b): (b < a)
• >=(a, b): !(a < b)

Это работает до тех пор, пока ваш оператор отвечает условиям строгого слабого заказа. Стандарт <= а также >= операторы нет.

Answer 4

Вы не можете выполнить бинарный поиск с частичным упорядочением. Вы не можете создать двоичное дерево поиска с частичным упорядочением. Какие функции / типы данных из алгоритма требуют упорядочения и могут работать с частичным упорядочением?

Answer 5

Вы можете реализовать это, например, комбинируя std::multimap/multiset с собственным предикатом, переопределяя std::less.