На этом шаге мы приведем общие сведения по алгоритмам упорядоченных интервалов.
Алгоритмы упорядоченных интервалов требуют, чтобы элементы исходных интервалов были упорядочены по своим критериям сортировки. Обычно эти алгоритмы работают гораздо эффективнее своих аналогов для неупорядоченных интервалов (как правило, они обладают логарифмической, а не линейной сложностью). Алгоритмы упорядоченных интервалов могут использоваться с итераторами, которые не являются итераторами произвольного доступа, но в этом случае сложность оказывается линейной, поскольку им приходится последовательно перебирать элемент за элементом. Впрочем, количество сравнений все равно может остаться логарифмическим.
Согласно стандарту, вызов этих алгоритмов для неупорядоченных интервалов приводит к непредсказуемым последствиям. Хотя в большинстве реализаций алгоритмы успешно работают с неупорядоченными последовательностями, использовать их в программе нельзя - это нарушит ее переносимость.
В ассоциативных контейнерах определены специальные функции, аналогичные по назначению представленным в следующих шагах алгоритмам. При поиске по заданному значению или ключу следует использовать эти функции вместо алгоритмов.
На следующем шаге мы рассмотрим поиск элементов в упорядоченных интервалах.
