упорядочение stl - строгое слабое упорядочение

Question

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

Answer 1

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

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).

Если вы использовали <= чтобы реализовать оператор less-than, тогда приведенный выше вернет false, когда a == b.Неправильная проверка на равенство приведет к сбою почти любой алгоритм.

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

Весь смысл ограничения библиотеки оператором less-than заключается в том что все логические операторы могут быть реализованы в терминах it:

• <(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

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