Руководство по стандартной библиотеке шаблонов (STL)

 void insert(iterator position, InputIterator first, InputIterator last);

 void pop_front();

 void pop_back();

 void erase(iterator position);

 void erase(iterator first, iterator last);

};

template ‹class T, class Allocator›

bool operator==(const deque‹T, Allocator›& x, const deque‹T, Allocator›& y);

template ‹class T, class Allocator›

bool operator‹(const deque‹T, Allocator›& x, const deque‹T, Allocator›& y);

iterator - итератор произвольного доступа, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.

const_iterator - постоянный итератор произвольного доступа, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.

difference_type - знаковый целочисленный тип. Точный зависит от исполнения и определяется в Allocator.

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

erase (стирание) в середине двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. erase и pop (извлечение) с обоих концов двусторонней очереди делают недействительными только итераторы и ссылки на стёртый элемент. Число вызовов деструктора равно числу стёртых элементов, а число вызовов оператора присваивания равно минимуму из числа элементов перед стёртыми элементами и числа элементов после стёртых элементов.

Ассоциативные контейнеры (Associative containers)

Ассоциативные контейнеры обеспечивают быстрый поиск данных, основанных на ключах. Библиотека предоставляет четыре основных вида ассоциативных контейнеров: set (множество), multiset (множество с дубликатами), map (словарь) и multimap (словарь с дубликатами).

Все они берут в качестве параметров Key (ключ) и упорядочивающее отношение Compare, которое вызывает полное упорядочение по элементам Key. Кроме того, map и multimap ассоциируют произвольный тип T с Key. Объект типа Compare называется сравнивающим объектом (comparison object) контейнера.

В этом разделе, когда мы говорим о равенстве ключей, мы подразумеваем отношение эквивалентности, обусловленное сравнением и не (not) operator== для ключей. То есть считается, что два ключа k1 и k2 являются равными, если для сравнивающего объекта comp истинно comp(k1, k2)==false && comp(k2, k1)==false.

Ассоциативный контейнер поддерживает уникальные ключи (unique keys), если он может содержать, самое большее, один элемент для каждого значения ключа. Иначе он поддерживает равные ключи (equal keys). set и map поддерживают уникальные ключи. multiset и multimap поддерживают равные ключи.

Для set и multiset значимый тип - тот же самый, что и тип ключа. Для map и multimap он равен pair‹const Key, T›.

iterator ассоциативного контейнера относится к категории двунаправленного итератора. insert не влияет на действительность итераторов и ссылок контейнера, а erase делает недействительными только итераторы и ссылки на стёртые элементы.

В следующей таблице обозначается: X - класс ассоциативного контейнера, a - значение X, a_uniq - значение X, когда X поддерживает уникальные ключи, a a_eq - значение X, когда X поддерживает многократные ключи, i и j удовлетворяют требованиям итераторов ввода и указывают на элементы value_type, [i, j) - допустимый диапазон, p - допустимый итератор для a, q - разыменовываемый итератор для a, [q1, q2) - допустимый диапазон в a, t - значение X::value_type и k - значение X::key_type.

Таблица 12. Требования ассоциативных контейнеров (в дополнение к контейнерам)