Язык программирования C++. Пятое издание - Стенли Липпман

А.2. Краткий обзор алгоритмов

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

• beg и end — итераторы, обозначающие диапазон элементов (см. раздел 9.2.1). Почти все алгоритмы работают с последовательностями, обозначенными итераторами beg и end.

• beg2 — итератор, обозначающий начало второй исходной последовательности. Если итератор end2 присутствует, он обозначает конец второй последовательности. Если итератора end2 нет, подразумевается, что обозначенная итератором beg2 последовательность такого же размера, что и исходная, обозначенная итераторами beg и end. Типы итераторов beg и beg2 не обязаны совпадать. Но должна существовать возможность применить указанную операцию или заданный вызываемый объект к элементам этих двух последовательностей.

• dest — итератор, обозначающий назначение. Последовательность назначения должна быть способна содержать столько элементов, сколько необходимо для исходной последовательности.

• unaryPred и binaryPred — унарные и бинарные предикаты (см. раздел 10.3.1), возвращающие применимый в условии тип и получающие соответственно один и два аргумента, являющиеся элементами исходного диапазона.

• comp — бинарный предикат, отвечающий требованиям упорядочивания по ключу в ассоциативном контейнере (см. раздел 11.2.2).

• unaryOp и binaryOp — вызываемые объекты (см. раздел 10.3.2), которые могут быть вызваны с одним и двумя аргументами из исходного диапазона соответственно.

А.2.1. Алгоритмы поиска объекта

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

Каждый алгоритм предоставляет две перегруженных версии. Первая версия для сравнения элементов использует оператор равенства (==) базового типа, а вторая использует предоставленные пользователем предикаты unaryPred или binaryPred.

Для поиска этим алгоритмам требуются итераторы ввода.

find(beg, end, val)

find_if(beg, end, unaryPred)

find_if_not(beg, end, unaryPred)

count(beg, end, val)

count_if(beg, end, unaryPred)

Функция find() возвращает итератор на первый элемент в исходном диапазоне, равный значению val. Функция find_if() возвращает итератор на первый элемент, для которого выполняется предикат unaryPred. Функция find_if_not() возвращает итератор на первый элемент, для которого предикат unaryPred возвращает значение false. Все три функции возвращают итератор end, если искомый элемент не существует.

Функция count() возвращает количество вхождений значения val. Функция count_if() подсчитает количество элементов, для которых предикат unaryPred возвращает значение true.

all_of(beg, end, unaryPred)

any_of(beg, end, unaryPred)

none_of(beg, end, unaryPred)

Возвращают логическое значение, указывающее, выполняется ли предикат unaryPred для всех элементов, какого-нибудь элемента или ни одного элемента соответственно. Если последовательность пуста, функция any_of() возвращает значение false, а функции all_of() и none_of() — true.

Этим алгоритмам требуются прямые итераторы. Они ищут в исходной последовательности повторяющиеся элементы.

adjacent_find(beg, end)

adjacent_find(beg, end, binaryPred)

Возвращает итератор на первую пару смежных совпадающих элементов. Возвращает итератор end, если смежных совпадающих элементов нет.

search_n(beg, end, count, val)

search_n(beg, end, count, val, binaryPred)

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

За исключением алгоритма find_first_of() этим алгоритмам требуются две пары прямых итераторов. Для обозначения первой своей последовательности алгоритм find_first_of() использует итераторы ввода и прямые итераторы для второй. Эти алгоритмы ищут последовательность, а не одиночный элемент.

search(beg1, end1, beg2, end2)

search(beg1, end1, beg2, end2, binaryPred)

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

find_first_of(beg1, end1, beg2, end2)

find_first_of(beg1, end1, beg2, end2, binaryPred)

Возвращает итератор на первое вхождение в первом диапазоне любого элемента из второго диапазона. Возвращает итератор endl, если искомое соответствие отсутствует.

find_end(beg1, end1, beg2, end2)

find_end(beg1, end1, beg2, end2, binaryPred)

Подобен алгоритму search(), но возвращает итератор на последнюю позицию в исходном диапазоне, в которой второй диапазон встречается как внутренняя последовательность. Возвращает итератор end1, если вторая последовательность пуста или не найдена.

А.2.2. Другие алгоритмы, осуществляющие только чтение

Для первых двух аргументов этим алгоритмам требуются итераторы ввода.

Алгоритмы equal() и mismatch() получают также дополнительный итератор ввода, обозначающий начало второго диапазона. Они также предоставляют две перегруженных версии. Первая версия для сравнения элементов использует оператор равенства (==) базового типа, а вторая сравнивает элементы используя предоставленный пользователем предикат unaryPred или binaryPred.

for_each(beg, end, unaryOp)

Вызываемый объект (см. раздел 10.3.2) unaryOp применяется к каждому элементу в исходном диапазоне. Возвращаемое значение объекта unaryOp (если оно есть) игнорируется. Если итераторы позволяют запись в элементы при помощи оператора обращения к значению, то вызываемый объект unaryOp способен изменять элементы.

mismatch(beg1, end1, beg2)

mismatch(beg1, end1, beg2, binaryPred)

Сравнивает элементы в двух последовательностях. Возвращает пару (см. раздел 11.2.3) итераторов, обозначающих первые элементы в каждой не совпадающей последовательности. Если все элементы соответствуют друг другу, первый итератор возвращенной пары окажется равным end1, а итератор beg2 — смещению, равному размеру первой последовательности.

equal(beg1, end1, beg2)

equal(beg1, end1, beg2, binaryPred)

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

А.2.3. Алгоритмы бинарного поиска

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

Этим алгоритмам требуются прямые итераторы, но они оптимизированы так, что выполняются намного быстрее, если вызываются с итераторами прямого доступа. С технической точки зрения, независимо от типа итератора, эти алгоритмы выполняют логарифмическое количество сравнений. Но при использовании с прямыми итераторами они должны выполнить линейное количество операций с итераторами для перебора элементов последовательности.

Эти алгоритмы требуют, чтобы элементы в исходной последовательности уже были упорядочены. Эти алгоритмы ведут себя подобно одноименным функциям-членам ассоциативных контейнеров (см. раздел 11.3.5).

Алгоритмы equal_range(), lower_bound() и upper_bound() возвращают итераторы на позиции последовательности, куда мог бы быть вставлен заданный элемент при сохранении существующего порядка в последовательности. Если элемент больше всех остальных в последовательности, то возвращаемый итератор будет итератором после конца.

Каждый алгоритм предоставлен в двух версиях: первая использует для проверки элементов оператор меньше (<) типа элемента, а вторая использует заданную функцию сравнения. В следующих алгоритмах "x меньше, чем y" означает, что выражения x<y и comp(x, y) истинны:

lower_bound(beg, end, val)

lower_bound(beg, end, val, comp)

Возвращает итератор, обозначающий первый элемент, значение которого больше или равно значению val, или итератор end, если такого элемента нет.