Введение в стандартную библиотеку шаблонов C++. Описание, примеры использования, учебные задачи - страница 24

Во всех алгоритмах, связанных с копированием или перемещением данных, предполагается, что в результирующей последовательности зарезервировано достаточно места для размещения всех получаемых элементов.

Всюду при указании сложности алгоритма под N понимается разность итераторов distance(first, last) (если N имеет индекс, то подразумевается, что итераторы имеют такой же номер, например N_>1 = distance(first1, last1)). Если сложность алгоритма является постоянной, т. е. не зависит от размера обрабатываемой последовательности, то она не указывается.

Алгоритмы, описываемые в данном пункте, определены в заголовочном файле .

Находит первую пару соседних элементов из диапазона [first, last), которые равны (или, при наличии предиката pred(^>*p, ^>*(p + 1)), для которых данный предикат возвращает true). Возвращает итератор, связанный с первым элементом найденной пары, или last, если пара не найдена.

Сложность линейная (не более N + 1 вызовов pred).

Возвращает true, если все элементы диапазона [first, last) удовлетворяют предикату pred. В случае пустого диапазона также возвращается true.

Сложность линейная (не более N вызовов pred).

Возвращает true, если хотя бы один элемент диапазона [first, last) удовлетворяет предикату pred. В случае пустого диапазона возвращается false.

Сложность линейная (не более N вызовов pred).

Использует двоичный поиск для проверки того, содержится ли в диапазоне [first, last) значение value (если значение найдено, то возвращает true, иначе false). Содержимое диапазона должно быть предварительно отсортировано в соответствии с порядком, задаваемым предикатом comp(^>*p1, ^>*p2) или (по умолчанию) операцией <.

Сложность логарифмическая (не более log N + 2 сравнений).

Копирует элементы из [first, last) в диапазон, начинающийся с result, и возвращает позицию за последним скопированным элементом в полученном диапазоне. Итератор result не может находиться в исходном диапазоне [first, last), но другие части выходного диапазона могут накладываться на исходный диапазон. Таким образом, данный алгоритм можно применять для «копирования влево», т. е. копирования в ситуации, когда левая граница выходного диапазона находится слева от исходного диапазона.

Сложность линейная (N присваиваний).