Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

class deque {

public:

// typedefs:

typedef iterator;

typedef const_iterator;

typedef Allocator‹T›::pointer pointer;

typedef Allocator‹T›::reference reference;

typedef Allocator‹T›::const_reference const_reference;

typedef size_type;

typedef difference_type;

typedef Т value_type;

typedef reverse_iterator;

typedef const_revcrse_iterator;

// размещение/удаление:

deque();

deque(size_type n, const T& value = T());

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

template ‹class InputIterator›

deque(InputIterator first, InputIterator last);

~deque();

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

void swap(deque‹T, Allocator›& x);

// средства доступа:

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

reverse_iterator rbegin();

const_reverse_iterator rbegin();

reverse_iterator rend();

const_reverse_iterator rend();

size_type size() const;

size_type max_size() const;

bool empty() const;

reference operator[](size_type n);

const_reference operator[](size_type n) const;

reference front();

const_reference front() const;

reference back();

const_reference back() const;

// вставка/стирание:

void push_front(const T& x);

void push_back(const T& x);

iterator insert(iterator position, const T& x = T());

void insert(iterator position, size_type n, const T& x);

template

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 (извлечение) с обоих концов двусторонней очереди делают недействительными только итераторы и ссылки на стёртый элемент. Число вызовов деструктора равно числу стёртых элементов, а число вызовов оператора присваивания равно минимуму из числа элементов перед стёртыми элементами и числа элементов после стёртых элементов.

Ассоциативные контейнеры обеспечивают быстрый поиск данных, основанных на ключах. Библиотека предоставляет четыре основных вида ассоциативных контейнеров: 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 поддерживают равные ключи.