C++. Сборник рецептов - [96]

Представленные здесь рецепты в основном предназначены для работы со стандартными контейнерами, и тому есть две причины. Во-первых, стандартные контейнеры очень распространены, и лучше изучить стандарт, чем изобретать колесо. Во-вторых, реализация алгоритмов из стандартной библиотеки предоставляет хороший пример для подражания в смысле взаимодействия и производительности. Если вы посмотрите, как профессионалы выполнили код стандартной библиотеки, вы, скорее всего, узнаете много нового и полезного для себя.

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

Табл. 7.1. Сокращения категорий итераторов

Сокращение	Значение
In	Input iterator (Итератор ввода)
Out	Output iterator (Итератор вывода)
Fwd	Forward iterator (Однонаправленный итератор)
Bid	Bidirectional iterator (Двунаправленный итератор)
Rand	Random-access iterator (Итератор произвольного доступа)

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

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

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

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

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

Проблема

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

Решение

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

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

#include
#include
#include
#include

using namespace std;

static const int ARRAY_SIZE = 5;

template
FwdIter fixOutliersUBound(FwdIter p1,
 FwdIter p2, const T& oldVal, const T& newVal) {
 for ( ; p1 != p2; ++p1) {
  if (greater(*p1, oldVal)) {
   *p1 = newVal;
  }
 }
}

int main() {
 list lstStr;
 lstStr.push_back("Please");
 lstStr.push_back("leave");
 lstStr.push_back("a");
 lstStr.push_back("message");
 // Создать итератор для последовательного перебора элементов списка
 for (list::iterator p = lstStr.begin();
  p != lstStr.end(); ++p) {
  cout << *p << endl;
 }
 // Или можно использовать reverse_iterator для перебора от конца
 // к началу, rbegin возвращает reverse_iterator, указывающий
 // на последний элемент, a rend возвращает reverse_iterator, указывающий
 // на один-перед-первым.
 for (list::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 lstStrDest;
 unique_copy(&arrStr[0], &arrStr[ARRAY_SIZE],
  back_inserter(lstStrDest));
}

Обсуждение

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