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

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. В заголовке algorithmопределена функция count(), подобная функции find(). Она получает два итератора и значение, а возвращает количество обнаруженных в диапазоне элементов, обладающих искомым значением. Организуйте чтение в вектор последовательности целых чисел. Осуществите подсчет элементов с указанным значением.

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

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

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

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

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