C++. Сборник рецептов

Когсуэлл Джефф

Стандартные алгоритмы также используют функциональные объекты, или функторы. Функциональный объект — это класс, который переопределяет

operator

так, что его можно вызвать как функцию. Функтор, который возвращает

bool

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

то бинарный предикат. Для краткости я при демонстрации объявлений функций использую сокращения, приведенные в табл. 7.2.

Табл. 7.2. Типы функторов

Имя типа	Описание
UnPred	Унарный предикат. Принимает один аргумент и возвращает bool
BinPred	Бинарный предикат. Принимает два аргумента и возвращает bool
UnFunc	Унарная функция. Принимает один аргумент и возвращает некое значение
BinFunc	Бинарная функция. Принимает два аргумента и возвращает некое значение

В большинстве случаев там, где требуется аргумент в виде функтора, может использоваться указатель на функцию. При использовании термина «функтор» я также подразумеваю указатель на функцию, если не указано иного.

7.1. Перебор элементов контейнера

Проблема

Имеется диапазон итераторов — скорее всего, из стандартного контейнера — и стандартные алгоритмы не удовлетворяют вашим требованиям, так что вам требуется выполнить итерации самостоятельно.

Решение

Для доступа к элементам контейнера и перехода от одного элемента к другому используйте

iterator

или

const_iterator

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

Пример 7.1. Использование итераторов с контейнерами

#include <iostream>

#include <list>

#include <algorithm>

#include <string>

using namespace std;

static const int ARRAY_SIZE = 5;

template<typename T, typename FwdIter>

FwdIter fixOutliersUBound(FwdIter p1,

 FwdIter p2, const T& oldVal, const T& newVal) {

 for ( ; p1 != p2; ++p1) {

if (greater<T>(*p1, oldVal)) {

*p1 = newVal;

}

 }

}

int main {

 list<string> lstStr;

 lstStr.push_back("Please");

 lstStr.push_back("leave");

 lstStr.push_back("a");

 lstStr.push_back("message");

 //

Создать итератор для последовательного перебора элементов списка

 for (list<string>::iterator p = lstStr.begin;

p != lstStr.end; ++p) {

cout << *p << endl;

 }

 // Или можно использовать reverse_iterator для перебора от конца

 // к началу, rbegin возвращает reverse_iterator, указывающий

 // на последний элемент, a rend возвращает reverse_iterator, указывающий

 // на один-перед-первым.

 for (list<string>::reverse_iterator p = lstStr.rbegin;

p != lstStr.rend; ++p) {

cout << *p << endl;

 }

 // Перебор диапазона элементов

 string arrStr[ARRAY_SIZE] = {"My", "cup", "cup", "runneth", "over"};

 for (string* p = &arrStr[0];

p != &arrStr[ARRAY_SIZE]; ++p) {

cout << *p << endl;

 }

 // Использование стандартных алгоритмов со стандартной последовательностью

 list<string> lstStrDest;

 unique_copy(&arrStr[0], &arrStr[ARRAY_SIZE],

back_inserter(lstStrDest));

}

Обсуждение

Итератор — это тип, который используется для ссылки на единственный объект в контейнере. Стандартные контейнеры используют итераторы как основной механизм для доступа к содержащимся в них элементам. Итератор ведет себя как указатель; для доступа к объекту, на который указывает итератор, вы его разыменовываете (с помощью операторов

*

или

– >

), а для перевода итератора вперед или назад используется синтаксис, аналогичный арифметике указателей. Однако есть несколько причин, по которым итератор — это не то же самое, что указатель. Однако перед тем, как я покажу их, давайте рассмотрим основы использования итераторов.

Использование итераторов

Итератор объявляется с помощью типа, элементы которого с его помощью будут перебираться. Например, в примере 7.1 используется

list<string>

, так что итератор объявляется вот так.

list<string>::iterator p = lstStr.begin;

Если вы не работали со стандартными контейнерами, то часть этого объявления

::iterator

может выглядеть несколько необычно. Это вложенный в шаблон класса

list typedef

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

list<int>

или для

set<MyClass>

, как здесь.