На этом шаге мы перечислим алгоритмы, предназначенные для работы с упорядоченными интервалами.
Алгоритмы упорядоченных интервалов требуют, чтобы интервалы, с которыми они работают, были изначально упорядочены по соответствующему критерию. В таблице 1 перечислены все алгоритмы стандартной библиотеки C++, предназначенные для упорядоченных интервалов. Достоинством этих алгоритмов является невысокая сложность.
| Название | Описание |
|---|---|
| binary_search() | Проверяет, содержит ли интервал заданный элемент |
| includes() | Проверяет, что каждый элемент интервала также является элементом другого интервала |
| lower_bound() | Находит первый элемент со значением, большим либо равным заданному |
| upper_bound() | Находит первый элемент со значением, большим заданного |
| equal_range() | Возвращает количество элементов в интервале, равных заданному значению |
| merge() | Выполняет слияние элементов двух интервалов |
| set_union() | Вычисляет упорядоченное объединение двух интервалов |
| set_intersection() | Вычисляет упорядоченное пересечение двух интервалов |
| set_difference() | Вычисляет упорядоченный интервал, который содержит все элементы интервала, не входящие в другой интервал |
| set_symmetric_difference() | Вычисляет упорядоченный интервал, содержащий все элементы, входящие только в один из двух интервалов |
| inplace_merge() | Выполняет слияние двух последовательных упорядоченных интервалов |
Первые пять алгоритмов упорядоченных интервалов, перечисленные в таблице, являются немодифицирующими, поскольку они ограничиваются поиском по заданному условию. Другие алгоритмы комбинируют два упорядоченных входных интервала и записывают результат в приемный интервал. Как правило, результат выполнения алгоритмов тоже упорядочен.
На следующем шаге мы рассмотрим численные алгоритмы.
