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

Ищет ключ k и возвращает итератор, указывающий на соответствующий элемент контейнера, или end(), если ключ не найден. В случае мультимножества и мультиотображения итератор может указывать на любой из элементов с ключом k.

Вставляет в контейнер новые данные. Если данные с указанным ключом уже имеются в контейнере, то в случае множества и отображения попытка вставки игнорируется. Во всех вариантах, кроме двух последних, функция возвращает позицию вставленного элемента, а также (в первом варианте, имеющемся только у множества и отображения) логическое значение, определяющее, была ли произведена вставка. Если вставка не была произведена из-за того, что в контейнере (множестве или отображении) уже существует элемент с таким же ключом, то возвращается позиция уже имеющегося элемента с этим ключом. Параметр hintpos является «подсказкой» для позиции вставки: элемент x вставляется максимально близко к позиции hintpos (в стандарте C++11 уточняется, что вставка выполняется перед позицией hintpos). Вариант с параметрами InIterFirst, InIterLast обеспечивает вставку всех элементов из диапазона [InIterFirst, InIterLast); эти элементы не обязаны быть упорядоченными по ключу, однако если они упорядочены, то время их вставки уменьшается. Вариант с параметром init_list (списком инициализации) вставляет в контейнер все элементы из указанного списка; этот вариант добавлен в стандарте C++11.

Возвращает функциональный объект, обеспечивающий сравнение ключей.

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

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

Возвращает функциональный объект, обеспечивающий сравнение элементов контейнера по их ключам. В случае (мульти)множества совпадает с объектом key_compare, в случае (мульти)отображения выполняет сравнение пар pair<const Key, T> по их первому компоненту Key.

1.2.7. Вставка и удаление в последовательных контейнерах

Функция-член insert реализована во всех последовательных контейнерах в трех вариантах (в стандарте С++11 добавлен еще один вариант). Первый параметр во всех вариантах – итератор pos, определяющий позицию вставки. Новые данные вставляются, начиная с указанной позиции pos; все прежние элементы, начиная с позиции pos и далее, смещаются вправо (по направлению к концу контейнера). Варианты различаются параметрами, определяющими, что именно вставляется: это либо (1) один параметр x типа T (вставляется единственное значение x), либо (2) параметры n и x (вставляются n значений x), либо (3) два итератора чтения InIterFirst и InIterLast (вставляются все элементы из диапазона [InIterFirst, InIterLast)), либо (4, в стандарте C++11) список инициализации init_list. До появления стандарта C++11 только вариант (1) функции insert возвращал значение, этим значением являлся итератор, указывающий на вставленный элемент. В стандарте С++11 варианты (3) и (4) также возвращают значение – итератор, указывающий на первый вставленный элемент, или исходное значение pos, если диапазон или список инциализации являются пустыми. Параметр-итератор pos и возвращаемый итератор всегда прямые (обычные) итераторы; обратные итераторы в качестве pos использовать нельзя.

Имеются дополнительные функции-члены, связанные со вставкой: это push_back(x) – вставка одного элемента в конец контейнера (реализована для всех последовательных контейнеров) и push_front(x) – вставка одного элемента в начало контейнера (реализована для дека и списка). Эти функции не возвращают значения.

Функция-член erase реализована во всех последовательных контейнерах в двух вариантах: (1) с параметром-итератором pos, определяющим позицию удаляемого элемента, и с двумя параметрами-итераторами first и last, определяющими диапазон [first, last) удаляемых элементов. В обоих вариантах возвращается итератор, который указывает на элемент, расположенный за удаленным элементом (или удаленным диапазоном).

Имеются дополнительные функции-члены, связанные с удалением: это pop_back() – удаление последнего элемента из контейнера (реализована для всех последовательных контейнеров; поддержка для строк string добавлена в стандарте C++11), pop_front() – удаление первого элемента из контейнера (реализована для дека и списка), clear() – удаление всех элементов из контейнера (реализована для всех контейнеров). Эти функции не возвращают значения.

Альтернативой функциям insert и erase для списков list являются три варианта функции-члена splice, позволяющие перемещать отдельные элементы или их диапазоны между различными списками или между различными позициями одного списка. Все варианты функции splice начинаются с параметров pos (итератора, определяющего место вставки) и lst (списка-источника вставляемых данных). Если других параметров нет, то список-источник lst целиком вставляется в позицию pos списка-приемника; если имеется один дополнительный параметр-итератор pos_lst, то из списка-источника в список-приемник перемещается единственный элемент, связанный с итератором pos_lst; если имеются два дополнительных параметра first_lst и last_lst, то перемещается диапазон элементов [first_lst, last_lst). Все перемещаемые элементы удаляются из списка-источника.

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

Вектор

Вставка:

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

• если перераспределения памяти не производится, то итераторы и ссылки до позиции вставки остаются корректными, а прочие – недействительными.

Удаление:

• все итераторы и ссылки до позиции удаления остаются корректными, а прочие – недействительными.

Дек

Вставка:

• все итераторы делаются недействительными;

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

Удаление:

• все итераторы делаются недействительными;

• ссылки на оставшиеся элементы делаются недействительными при удалении элементов из середины дека и остаются корректными при удалении начальных или конечных элементов дека.

Список

Вставка:

• все итераторы и ссылки остаются корректными.

Удаление:

• все итераторы и ссылки на оставшиеся элементы списка остаются корректными.

1.2.8. Контейнеры-адаптеры и контейнеры, добавленные в стандарт C++11

В данном пункте, как и в пунктах 1.2.2–1.2.7, посвященных основным видам контейнеров, при описании конструкторов и функций-членов контейнеров не указывается дополнительный тип Alloc, который обычно устанавливается по умолчанию. Все рассматриваемые в данном пункте контейнеры определены в пространстве имен std.

Начнем с описания контейнеров-адаптеров: стека (stack), очереди (queue) и очереди с приоритетом (priority_queue).

Особенностью контейнеров-адаптеров является то, что они основаны на одном из «настоящих» контейнеров, который хранится в качестве внутреннего контейнера (underlying container) с именем c – защищенного члена контейнера-адаптера. Для очереди с приоритетом используется еще один защищенный член – функциональный объект comp, используемый для сравнения элементов.

Реализация функций-членов контейнеров-адаптеров сводится к вызову соответствующих функций-членов «внутреннего» контейнера c. При этом набор средств, доступных для контейнеров-адаптеров, существенно сокращен по сравнению со средствами внутреннего контейнера. В частности, с контейнерами-адаптерами не связываются итераторы, что не позволяет их использовать совместно со стандартными алгоритмами.

В таблице 3 приводится описание шаблонов контейнеров-адаптеров.

Таблица 3

Контейнеры-адаптеры

Для всех контейнеров-адаптеров можно использовать конструктор без параметров и конструктор копии с параметром other того же типа, что и создаваемый адаптер; в стандарте С++11 добавлен конструктор перемещения, в котором параметр other является ссылкой на r-значение.

Кроме того, для стека и очереди можно использовать конструктор с явно указанным контейнером cont типа const Container& (в стандарте C++11 добавлен вариант с типом Container&&), содержимое которого копируется (или, соответственно, перемещается) во внутренний контейнер c адаптера.

Для очереди с приоритетом предусмотрены также конструкторы со следующими параметрами (в квадратных скобках, как обычно, указаны необязательные параметры):

Здесь параметр comp имеет тип const Compare& и определяет операцию сравнения для очереди с приоритетом, параметр cont имеет тип const Container& или Container&& (C++11) и определяет начальное содержимое, которое копируется или, соответственно, перемещается во внутренний контейнер c адаптера. При наличии параметров-итераторов чтения first и last после первоначального заполнения внутреннего контейнера с помощью параметра cont (или, по умолчанию, создания пустого внутреннего контейнера) для него вызывается функция-член c.insert(c.end(), first, last). На завершающем этапе формирования очереди с приоритетом с использованием данных вариантов конструктора для ее внутреннего контейнера вызывается алгоритм make_heap(c.begin(), c.end(), comp).

Для всех контейнеров-адаптеров определена операция =, обеспечивающая копирование (а в стандарте C++11 и перемещение) элементов из одного адаптера в другой того же типа.

Кроме того, для всех контейнеров-адаптеров (как и для всех других контейнеров) определены функции-члены bool empty() const и size_type size() const (выполнение которых сводится к вызову одноименных функций-членов внутренних контейнеров: c.empty() и c.size()), а также функция-член void swap(other), обеспечивающая обмен содержимым между двумя адаптерами одинакового типа (для этого выполняется вызов алгоритма swap(c, other.c), а в случае очереди с приоритетом дополнительно вызывается алгоритм swap(comp, other.comp)).

Для доступа к элементам контейнеров-адаптеров предусмотрены следующие функции-члены:

• стек: reference top() – доступ к верхнему элементу стека (возвращает c.back());

• очередь: reference front() – доступ к начальному элементу очереди (возвращает c.front()) и reference back() – доступ к конечному элементу очереди (возвращает c.back());

• очередь с приоритетом: reference front() – доступ к наибольшему элементу очереди (возвращает c.front()).

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