Введение в стандартную библиотеку шаблонов 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, используемый для сравнения элементов.