Имеет ли std :: equal_range строгий слабый порядок?

Question

Я вижу документацию для более старой, нестандартной equal_range, которая явно вызывает строгий слабый порядок (старые документы SGI) и некоторые более новые, стандартные equal_range, которые не выполняют (cppreference, libstdC++ docs).

Была ли функция изменена так, что она требовала строгого слабого упорядочения, и теперь она требует ... своего рода раздела без имени?

Answer 1

std::equal_range требует, чтобы последовательность рассматривается должна быть распределял выражения pr(value, N) и pr(N, value) где pr является предикатом, value значения, для которого вы хотите найти равный диапазон и N является элементом последовательности.

Для последовательности это более слабое условие, чем требование упорядочения последовательности со строгим слабым порядком. Для этого требуется только точка разделения P, где pr(N, value) возвращает true для всех элементов N в последовательности до P, pr(value, N) возвращает false для всех элементов в последовательности после или после P. Так, например, последовательность [2, 1, 5, 4] разбивается < и значение 3, точка разбиения быть на элементе со значением 5.

Для самого предиката, equal_range требует асимметрии по отношению к value , то есть pr(N, value) подразумевает ! pr(value, N) для всех N последовательности. В частности, это означает, что pr(X, X) может вернуть true, что не соответствует строгому упорядоченному порядку. Требования/свойства для строгого слабого упорядочении:

• асимметрия: pr(x, y) подразумевает ! pr(y, x)
• irreflexivity: pr(x, x) == false
• транзитивность: pr(x, y) && pr(y, z) подразумевает pr(x, z)
• ! pr(x, y) && ! pr(y, z) предполагает ! pr(x, z) (в элементах программирования, это заявлено через дополнительное отношение эквивалентности)

Обратите внимание, что эти точки применяются для всех элементов x, y последовательности. Однако требование по pr в equal_range не является общим требованием к предикату, а является специфическим требованием для предиката и для этого конкретного значения.