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

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

Чтобы не создавать каждую из этих функций как член контейнера каждого типа, стандартная библиотека определяет набор обобщенных алгоритмов (generic algorithm). Алгоритмами они называются потому, что реализуют классические алгоритмы, такие как сортировка и поиск, а обобщенными — потому, что работают с контейнерами любых типов, включая массивы встроенных типов, и, как будет продемонстрировано далее, с последовательностями других видов, а не только с такими библиотечными типами, как vectorили list.

Большинство алгоритмов определено в заголовке algorithm. Библиотека определяет также набор обобщенных числовых алгоритмов в заголовке numeric.

Обычно алгоритмы воздействуют не на сам контейнер, а работают, перебирая диапазон элементов, заданный двумя итераторами (см. раздел 9.2.1). Перебирая диапазон, алгоритм, как правило, выполняет некое действие с каждым элементом. Предположим, например, что имеется вектор целых чисел и необходимо узнать, содержит ли этот вектор некое значение. Проще всего ответить на этот вопрос, воспользовавшись библиотечным алгоритмом find():

int val = 42; // искомое значение

// result обозначит искомый элемент, если он есть в векторе,

// или значение vec.cend(), если нет

auto result = find(vec.cbegin(), vec.cend(), val);

// отображение результата

cout << "The value " << val

<< (result == vec.cend()

? " is not present" : " is present") << endl;

Первые два аргумента функции find()являются итераторами, обозначающими диапазон элементов, а третий аргумент — это значение. Функция find()сравнивает каждый элемент указанного диапазона с заданным значением и возвращает итератор на первый элемент, соответствующий этому значению. При отсутствии соответствия функция find()возвращает свой второй итератор, означая неудачу поиска. Так, сравнив возвращаемое значение со вторым аргументом, можно определить, был ли найден элемент. Для проверки, свидетельствующей об успехе поиска значения, в операторе вывода используется условный оператор (см. раздел 4.7).

Поскольку функция find()работает с итераторами, ее можно использовать для поиска значения в любом контейнере. Рассмотрим пример применения функции find()для поиска значения в списке строк:

string val = "a value"; // искомое значение

// вызов, позволяющий найти строковый элемент в списке

auto result = find(lst.cbegin(), lst.cend(), val);

Аналогично, поскольку указатели действуют как итераторы встроенных массивов, функцию find()можно использовать для поиска в массиве:

int ia[] = {27, 210, 12, 47, 109, 83};

int val = 83;

int* result = find(begin(ia), end(ia), val);

Здесь для передачи указателей на первый и следующий после последнего элементы массива iaиспользуются библиотечные функции begin()и end()(см. раздел 3.5.3).

Искать также можно в диапазоне, заданном переданными итераторами (или указателями), на его первый и следующий после последнего элементы. Например, следующий вызов ищет соответствие в элементах iа[1], ia[2]и ia[3]:

// искать среди элементов, начиная с ia[1] и до, но не включая, ia[4]

auto result = find(ia +1, ia + 4, val);

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

1. Обратиться к первому элементу последовательности.

2. Сравнить этот элемент с искомым значением.

3. Если элемент соответствует искомому, функция find()возвращает значение, идентифицирующее этот элемент.

4. В противном случае функция find()переходит к следующему элементу и повторяет этапы 2 и 3.

5. По достижении конца последовательности функция find()должна остановиться.

6. Достигнув конца последовательности, функция find()должна возвратить значение, означающее неудачу поиска. Тип этого значения должен быть совместимым с типом значения, возвращенного на этапе 3.

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