set<string> s;
// Заполнить s данными...
log_[id] = s; // Скопировать s и добавить его копию в log_
Это приведет к огромному числу дополнительных нежелательных копирований. Следовательно, общее правило при использовании контейнеров из контейнеров — это использовать указатели на контейнеры.
Глава 7
Алгоритмы
7.0. Введение
Эта глава рассказывает, как работать со стандартными алгоритмами и как использовать их для стандартных контейнеров. Эти алгоритмы первоначально являлись частью того, что часто называется Standard Template Library (STL — стандартная библиотека шаблонов) и представляет собой набор алгоритмов, итераторов и контейнеров, которые теперь вошли в стандартную библиотеку (глава 6 содержит рецепты по работе со стандартными контейнерами). Я их буду называть просто стандартными алгоритмами, итераторами и контейнерами, но не забывайте, что это то же самое, что другие авторы называют частью STL. Одним из базовых элементов стандартной библиотеки являются итераторы, так что первый рецепт описывает, что они собой представляют и как их использовать. После этого идет несколько рецептов, которые объясняют, как использовать и расширять стандартные алгоритмы. Наконец, если вы не нашли ничего подходящего в стандартной библиотеке, то рецепт 7.10 расскажет, как написать собственный алгоритм.
Представленные здесь рецепты в основном предназначены для работы со стандартными контейнерами, и тому есть две причины. Во-первых, стандартные контейнеры очень распространены, и лучше изучить стандарт, чем изобретать колесо. Во-вторых, реализация алгоритмов из стандартной библиотеки предоставляет хороший пример для подражания в смысле взаимодействия и производительности. Если вы посмотрите, как профессионалы выполнили код стандартной библиотеки, вы, скорее всего, узнаете много нового и полезного для себя.
Все стандартные алгоритмы используют итераторы. Даже если вы знакомы с концепцией итераторов, которые рассматриваются в первом рецепте, посмотрите на табл. 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 <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>, как здесь.
list<int>::iterator p1;
set<MyClass>::iterator p2;
Возвращаясь обратно к нашему примеру, итератор о инициализируется первым элементом последовательности, который возвращается методом begin. Чтобы перейти к следующему элементу, используется operator++. Можно использовать как префиксный инкремент так и постфиксный инкремент (p++), аналогично указателям на элементы массивов, но префиксный инкремент не создает временного значения, так что он более эффективен и является предпочтительным. Постфиксный инкремент (p++) должен создавать временную переменную, так как он возвращает значение p до его инкрементирования. Однако он не может инкрементировать значение после того, как вернет его, так что он вынужден делать копию текущего значения, инкрементировать текущее значение, а затем возвращать временное значение. Создание таких временных переменных с течением времени требует все больших и больших затрат, так что если вам не требуется именно постфиксное поведение, используйте префиксный инкремент.
