Введение в стандартную библиотеку шаблонов C++. Описание, примеры использования, учебные задачи

Абрамян Михаил

В качестве итераторов чтения и итераторов записи можно использовать итераторы всех остальных видов (однонаправленные, двунаправленные, произвольного доступа); следует лишь учитывать, что итераторы записи можно инкрементировать неограниченно, тогда как итераторы других видов всегда связываются с некоторым диапазоном допустимых элементов. В качестве однонаправленных итераторов можно использовать двунаправленные итераторы и итераторы произвольного доступа, а в качестве двунаправленных итераторов – итераторы произвольного доступа.

Для всех видов итераторов определены их модификации – константные итераторы, отличающиеся от обычных тем, что их разыменование дает константное значение.

Особыми итераторами являются итераторы потоков ввода–вывода (см. п. 1.1.2), обратные итераторы (см. п. 1.2.9) и итераторы

вставки (см. п. 1.3.4).

1.1.2. Итераторы потоков ввода-вывода

Стандартные потоковые итераторы istream_iterator<T> и ostream_iterator<T> (шаблонные классы) определены в заголовочном файле <iterator>.

Имеются два варианта конструктора для итератора потокового чтения istream_iterator: вариант с параметром-потоком stream создает итератор для чтения из данного потока, вариант без параметров создает итератор, обозначающий конец потока (все итераторы, обозначающие конец потока, считаются равными друг другу и не равными никаким другим итераторам потокового чтения).

Ниже перечислены свойства потоковых итераторов чтения:

• тип T определяет тип элементов данных, которые считываются из потока;

• чтение элемента из потока выполняется в начальный момент работы с итератором, а затем при каждой операции инкремента ++;

• имеются два варианта операции ++: префиксный инкремент (++p) и постфиксный инкремент (p++);

• операция ^* (и ее вариант ->) возвращает последнее прочитанное значение, причем эту операцию можно использовать неоднократно для получения того же самого значения;

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

Для итератора потоковой записи ostream_iterator<T> также определены два конструктора: первый конструктор содержит единственный параметр stream, задающий поток вывода, а второй конструктор дополнительно к параметру stream содержит второй параметр delim, задающий разделитель, который добавляется в поток вывода после каждого выведенного элемента (если параметр delim не указан, то между выводимыми элементами никакой разделитель не добавляется).

Ниже перечислены свойства потоковых итераторов записи:

• специальный конструктор для создания итератора конца потока вывода не предусмотрен;

• операции ^* и ++ не выполняют никаких действий и просто возвращают сам итератор;

• операция присваивания p = выражение (где p – имя итератора записи) записывает значение выражения в поток вывода.

1.2. Контейнеры

1.2.1. Общее описание

Данный раздел посвящен контейнерам, входящим в стандартную библиотеку шаблонов C++. Подробно описываются те основные виды последовательных и ассоциативных контейнеров, с которыми связаны задания, приводимые в книге: это векторы (vector), деки (deque), списки (list), множества (set), мультимножества (multiset), отображения (map) и мультиотображения (multimap), а также текстовые строки (string), которые относят к псевдоконтейнерам. Другие виды контейнеров кратко описываются в п. 1.2.8: это контейнеры-адаптеры стек (stack), очередь (queue) и очередь с приоритетом (priority_queue), а также контейнеры, добавленные в библиотеку STL в стандарте C++11 (array, forward_list и ассоциативные контейнеры на базе хеш-функций). Все контейнеры определены в пространстве имен std.

В таблицах 1 и 2 перечислены характеристики основных видов последовательных и ассоциативных контейнеров.

Таблица 1

Последовательные контейнеры

Таблица 2

Ассоциативные контейнеры

В описаниях шаблонов контейнеров, приводимых в таблицах 1 и 2, и далее при описании конструкторов и функций-членов этих контейнеров (см. п. 1.2.2–1.2.6) не указывается дополнительный тип Alloc, который

обычно устанавливается по умолчанию. Необязательные параметры заключаются в квадратные скобки, набранные полужирным шрифтом: [ ]. В частности, если в шаблоне ассоциативного контейнера не указывается операция сравнения Compare, то она считается равной less<Key>.

Контейнеры могут содержать данные только тех типов T, которые удовлятворяют некоторым естественным условиям (например, в стандарте C++98 требуется, чтобы для типа T был определен конструктор копирования и операция присваивания).

Все рассматриваемые последовательные контейнеры допускают вставку новых элементов в любую позицию и удаление элементов из любой позиции. Векторы оптимизированы для быстрого (за константное время) выполнения операций вставки и удаления, связанных с концом последовательности элементов (функции-члены push_back и pop_back), а деки – для операций, связанных как с началом, так и с концом последовательности (функции-члены push_back и pop_back, push_front и pop_front). В то же время, векторы обладают рядом особенностей, отсутствующих у деков; в частности, они имеют такую характеристику, как емкость, которая доступна и для чтения (функция-член capacity) и для изменения (функция-член reserve). Текстовые строки string обладают возможностями, аналогичными возможностям векторов с символьными элементами. Списки позволяют выполнять быструю вставку и удаление элементов для любой позиции, однако доступ к элементу списка по его номеру требует линейного времени (т. е. зависит от текущего размера списка). По этой причине для списков не реализована операция индексирования, а связанные со списками итераторы являются двунаправленными (а не итераторами произвольного доступа, как для всех остальных последовательных контейнеров). Еще одной особенностью списка является то, что операции вставки и удаления не влияют на корректность итераторов и ссылок, связанных с другими его элементами, в то время как для векторов и деков вставка или удаление элементов может приводить к тому, что некоторые (или все) итераторы и/или ссылки окажутся недействительными (подробности приведены в п. 1.2.7). Кроме того, для списков предусмотрен набор дополнительных функций-членов, отсутствующих у других последовательных контейнеров и представляющих собой оптимизированные реализации соответствующих алгоритмов (см. п. 1.2.5).

Все рассматриваемые ассоциативные контейнеры хранят последовательности своих элементов в отсортированном виде. Сортировка выполняется по ключу, причем для множеств и мультимножеств ключами выступают сами элементы (типа T), а в отображениях и мультиотображениях хранятся пары типа pair<Key, T>, первый компонент которых считается ключом (key), а второй – значением (value). По умолчанию порядок определяется операцией < для типа ключа Key, однако его можно явно указать в шаблоне контейнера в виде функционального объекта, реализующего бинарный предикат с параметрами типа Key и со свойствами операции сравнения «меньше». Мультимножества и мультиотображения, в отличие от множеств и отображений, позволяют хранить набор элементов с эквивалентными ключами (ключи считаются эквивалентными, если ни один из них не является меньшим, чем другой). Для отображения определена операция индексирования с дополнительными возможностями (см. п. 1.2.6). Вставка новых элементов в любой ассоциативный контейнер сохраняет его упорядоченность. И операция вставки, и операция удаления для ассоциативных контейнеров требует логарифмического времени, если для этих операций указывается параметр-ключ. За это же время выполняется и поиск элементов по ключу, для реализации которого в ассоциативных контейнерах предусмотрен целый набор функций-членов. Указанные свойства ассоциативных контейнеров делают их удобным механизмом для группировки и объединения наборов данных по ключу.

Поскольку контейнеры, перечисленные в таблицах 1 и 2, имеют много одинаковых функций-членов, все они далее рассматриваются совместно: в п. 1.2.2 перечисляются типы, связанные с контейнерами, и описываются варианты конструкторов, в п. 1.2.3 приводятся функции-члены, имеющиеся у всех контейнеров, в п. 1.2.4 – функции-члены последовательных контейнеров, в п. 1.2.5 – дополнительные функции-члены списков, в п. 1.2.6 – функции-члены ассоциативных контейнеров. В каждом пункте все функции-члены приводятся в алфавитном порядке их имен. Если некоторые функции-члены имеются не у всех рассматриваемых типов контейнеров, то это явно указывается; кроме того, специальным образом помечаются функции-члены, добавленные в стандарте C++11 (например, текст vector(C++11), string означает, что соответствующая функция-член доступна только для классов vector и string, причем для класса vector – только начиная со стандарта C++11). Если один из прежних вариантов функции-члена отсутствует в стандарте С++11, то он помечается текстом C++98.