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

Итератор после конца (off-the-end iterator). Итератор, обозначающий (несуществующий) следующий элемент после последнего в диапазоне. Обычно называемый "конечным итератором" (end iterator).

Итератор после начала (off-the-beginning iterator). Итератор, обозначающий (несуществующий) элемент непосредственно перед началом контейнера forward_list. Возвращается функцией before_begin() контейнера forward_list. Подобно итератору, возвращенному функцией end(), к значению данного итератора обратиться нельзя.

Контейнер array (массив). Последовательный контейнер фиксированного размера. Чтобы определить массив, кроме определения типа элемента следует указать его размер. К элементам массива можно обратиться по их позиционному индексу. Обеспечивает быстрый произвольный доступ к элементам.

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

Контейнер forward_list (односвязный список). Последовательный контейнер, представляющий односвязный список. К элементам контейнера forward_list можно обращаться только последовательно; начиная с данного элемента, можно добраться до другого элемента, только перебрав каждый элемент между ними. Итераторы класса forward_list не поддерживают декремент (--). Обеспечивает быструю вставку (или удаление) в любой позиции. В отличие от других контейнеров, вставка и удаление происходят после указанной позиции итератора. Как следствие, у контейнера forward_list есть итератор перед началом, для согласованности с обычным итератором после конца. При добавлении новых элементов итераторы остаются допустимыми. Когда элемент удаляется, некорректным становится лишь итератор удаленного элемента.

Контейнер list (список). Последовательный контейнер, к элементам которого можно обратиться только последовательно, т.е. начиная с одного элемента, можно перейти к другому, увеличивая или уменьшая итератор. Итераторы контейнера list поддерживают как инкремент (++), так и декремент (--). Обеспечивает быструю вставку (и удаление) в любой позиции. Добавление новых элементов никак не влияет ни на другие элементы, ни на существующие итераторы. Когда элемент удаляется, некорректным становится лишь итератор удаленного элемента.

Контейнер vector (вектор). Последовательный контейнер, к элементам которого можно обратиться по индексу (позиции). Эффективно добавить или удалить элементы вектора можно только с конца. Добавление элементов в вектор может привести к его перераспределению в памяти, что сделает некорректными все созданные ранее итераторы. При добавлении (или удалении) элемента в середину вектора итераторы всех расположенных далее элементов становятся некорректными.

Контейнер (container). Тип (класс), который содержит коллекцию объектов определенного типа. Каждый библиотечный контейнер является шаблоном класса. Чтобы создать контейнер, необходимо указать тип хранимых в нем элементов. За исключением массивов, библиотечные контейнеры имеют переменный размер.

Последовательный контейнер (sequential container). Контейнер, позволяющий содержать упорядоченную коллекцию объектов одинакового типа. К элементам последовательного контейнера обращаются по позиции.

Функция begin(). Функция контейнера, возвращающая итератор на первый элемент в контейнере (если он есть), или итератор после конца, если контейнер пуст. Будет ли возвращенный итератор константным, зависит от типа контейнера.

Функция cbegin(). Функция контейнера, возвращающая итератор const_iterator на первый элемент в контейнере (если он есть), или итератор после конца (off-the-end iterator), если контейнер пуст.

Функция cend(). Функция контейнера, возвращающая итератор const_iterator на (несуществующий) элемент после последнего элемента контейнера.

Функция end(). Функция контейнера, возвращающая итератор на (несуществующий) элемент после последнего элемента контейнера. Будет ли возвращенный итератор константным, зависит от типа контейнера.

Глава 10

Обобщенные алгоритмы

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

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

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

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

Чтобы не создавать каждую из этих функций как член контейнера каждого типа, стандартная библиотека определяет набор обобщенных алгоритмов (generic algorithm). Алгоритмами они называются потому, что реализуют классические алгоритмы, такие как сортировка и поиск, а обобщенными — потому, что работают с контейнерами любых типов, включая массивы встроенных типов, и, как будет продемонстрировано далее, с последовательностями других видов, а не только с такими библиотечными типами, как vector или list.

10.1. Краткий обзор

Большинство алгоритмов определено в заголовке algorithm. Библиотека определяет также набор обобщенных числовых алгоритмов в заголовке numeric.

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

int val = 42; // искомое значение

// result обозначит искомый элемент, если он есть в векторе,

// или значение vec.cend(), если нет

auto result = find(vec.cbegin(), vec.cend(), val);

// отображение результата

cout << "The value " << val

     << (result == vec.cend()

         ? " is not present" : " is present") << endl;

Первые два аргумента функции find() являются итераторами, обозначающими диапазон элементов, а третий аргумент — это значение. Функция find() сравнивает каждый элемент указанного диапазона с заданным значением и возвращает итератор на первый элемент, соответствующий этому значению. При отсутствии соответствия функция find() возвращает свой второй итератор, означая неудачу поиска. Так, сравнив возвращаемое значение со вторым аргументом, можно определить, был ли найден элемент. Для проверки, свидетельствующей об успехе поиска значения, в операторе вывода используется условный оператор (см. раздел 4.7).

Поскольку функция find() работает с итераторами, ее можно использовать для поиска значения в любом контейнере. Рассмотрим пример применения функции find() для поиска значения в списке строк:

string val = "a value"; // искомое значение

// вызов, позволяющий найти строковый элемент в списке

auto result = find(lst.cbegin(), lst.cend(), val);

Аналогично, поскольку указатели действуют как итераторы встроенных массивов, функцию find() можно использовать для поиска в массиве:

int ia[] = {27, 210, 12, 47, 109, 83};

int val = 83;

int* result = find(begin(ia), end(ia), val);

Здесь для передачи указателей на первый и следующий после последнего элементы массива ia используются библиотечные функции begin() и end() (см. раздел 3.5.3).

Искать также можно в диапазоне, заданном переданными итераторами (или указателями), на его первый и следующий после последнего элементы. Например, следующий вызов ищет соответствие в элементах iа[1], ia[2] и ia[3]:

// искать среди элементов, начиная с ia[1] и до, но не включая, ia[4]