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

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

10.2. Первый взгляд на алгоритмы

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

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

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

10.2.1. Алгоритмы только для чтения

Много алгоритмов только читают значения элементов в исходном диапазоне, но никогда не записывают их. Функция find() и функция count(), использованная в упражнениях раздела 10.1, являются примерами таких алгоритмов.

Другим предназначенным только для чтения алгоритмом является accumulate(), который определен в заголовке numeric. Функция accumulate() получает три аргумента. Первые два определяют диапазон суммируемых элементов, а третий — исходное значение для суммы. Предположим, что vec — это последовательность целых чисел.

// суммирует элементы вектора vec, начиная со значения 0

int sum = accumulate(vec.cbegin(), vec.cend(), 0);

Приведенный выше код суммирует значения элементов вектора vec, используя 0 как начальное значение суммы.

Тип третьего аргумента функции accumulate() определяет, какой именно оператор суммы будет использован и каков будет тип возвращаемого значения функции accumulate().

Алгоритмы и типы элементов

У того факта, что функция accumulate() использует свой третий аргумент как отправную точку для суммирования, есть важное последствие: он позволяет добавить тип элемента к типу суммы. Таким образом, тип элементов последовательности должен соответствовать или быть приводим к типу третьего аргумента. В этом примере элементами вектора vec могли бы быть целые числа, или числа типа double, или long long, или любого другого типа, который может быть добавлен к значению типа int.

Например, поскольку тип string имеет оператор +, функцию accumulate() можно использовать для конкатенации элементов вектора строк:

string sum = accumulate(v.cbegin(), v.cend(), string(""));

Этот вызов добавляет каждый элемент вектора v к первоначально пустой строке sum. Обратите внимание: третий параметр здесь явно указан как объект класса string. Передача строки как символьного литерала привела бы к ошибке при компиляции.

// ошибка: no + on const char*

string sum = accumulate(v.cbegin(), v.cend(), "");

Если бы был передан строковый литерал, типом суммируемых значений оказался бы const char*. Этот тип и определяет используемый оператор +. Поскольку тип const char* не имеет оператора +, этот вызов не будет компилироваться.

С алгоритмами, которые читают, но не пишут в элементы, обычно лучше использовать функции cbegin() и cend() (см. раздел 9.2.3). Но если возвращенный алгоритмом итератор планируется использовать для изменения значения элемента, то следует использовать функции begin() и end().

Алгоритмы, работающие с двумя последовательностями

Еще один алгоритм только для чтения, equal(), позволяет определять, содержат ли две последовательности одинаковые значения. Он сравнивает каждый элемент первой последовательности с соответствующим элементом второй. Алгоритм возвращает значение true, если соответствующие элементы равны, и значение false в противном случае. Он получает три итератора: первые два (как обычно) обозначают диапазон элементов первой последовательности, а третий — первый элемент второй последовательности:

// roster2 должен иметь по крайней мере столько же элементов,

// сколько и roster1

equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());