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

merge сливает список аргумента со списком (предполагается, что оба сортированы). Слияние устойчиво, то есть для равных элементов в двух списках элементы списка всегда предшествуют элементам из списка аргумента. x пуст после слияния. Выполняется, самое большее, size() + x.size() - 1 сравнений.

reverse переставляет элементы в списке в обратном порядке. Операция линейного времени.

sort сортирует список согласно operator‹ или сравнивающему функциональному объекту. Она устойчива, то есть относительный порядок равных элементов сохраняется. Выполняется приблизительно NlogN сравнений, где N равно size().

Двусторонняя очередь (Deque)

deque - вид последовательности, которая, подобно вектору, поддерживает итераторы произвольного доступа. Кроме того она поддерживает операции вставки и стирания в начале или в конце за постоянное время; вставка и стирание в середине занимают линейное время. Как с векторами, управление памятью обрабатывается автоматически.

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

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

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

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