Введение в стандартную библиотеку шаблонов C++. Описание, примеры использования, учебные задачи
Шрифт:
Имеются дополнительные функции-члены, связанные с удалением: это 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).
Контейнеры-адаптеры реализуют ограниченный набор действий. Стек позволяет добавлять новый элемент в вершину, получать значение верхнего элемента и удалять верхний элемент. Очередь позволяет добавлять новый элемент в конец, получать значение начального и конечного элемента и удалять начальный элемент. Очередь с приоритетом позволяет добавлять новый элемент, получать значение наибольшего элемента и удалять наибольший элемент.
Во всех контейнерах-адаптерах используются одинаковые имена для функций-членов, связанных с добавлением и удалением элементов. Эти функции-члены описаны в таблице 4.