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

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

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

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

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

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

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

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

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

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

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

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

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