10.1. Краткий обзор

Большинство алгоритмов определено в заголовке 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() в любом случае не зависит от типа контейнера (или даже хранимых в контейнере элементов).

Итераторы делают алгоритмы независимыми от типа контейнера…

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

…но алгоритмы зависят от типа элементов

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

Другие алгоритмы требуют, чтобы тип элемента имел оператор <. Но, как будет продемонстрировано, большинство алгоритмов позволяют предоставить собственную функцию для использования вместо оператора, заданного по умолчанию.

Упражнения раздела 10.1

Упражнение 10.1. В заголовке algorithm определена функция count(), подобная функции find(). Она получает два итератора и значение, а возвращает количество обнаруженных в диапазоне элементов, обладающих искомым значением. Организуйте чтение в вектор последовательности целых чисел. Осуществите подсчет элементов с указанным значением.

Упражнение 10.2. Повторите предыдущую программу, но чтение значений организуйте в список (list) строк.

Ключевая концепция. Алгоритмы никогда не используют функции контейнеров

Общие алгоритмы никогда не используют функции контейнеров. Они работают исключительно с итераторами. Тот факт, что алгоритмы оперируют итераторами, а не функциями контейнера, возможно, удивителен, но он имеет глубокий смысл: когда используются "обычные" итераторы, алгоритмы не способны изменить размер исходного контейнера. Как будет продемонстрировано далее, алгоритмы способны изменять значения хранимых в контейнере элементов и перемещать их в контейнер. Однако они не способны ни добавлять, ни удалять сами элементы.

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