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

Ответ 1

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

Ответ 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

Последовательность сортируется в соответствии с < iff для каждого 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, меньше любого элемента, t216 > . Это не обязательно для частичного упорядочения.

Ответ 3

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

Ответ 4

Цитируя ответ, указанный здесь:

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

Если вы использовали <= для реализации оператора меньшего размера, то приведенное выше вернет false, когда 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)

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

Ответ 5

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