void splice(iterator position, list‹T, Allocator›& x, iterator first, iterator last) вставляет элементы из диапазона [first, last) перед position и удаляет элементы из x. Требуется постоянное время, если &x==this; иначе требуется линейное время. [first, last) - допустимый диапазон в x. Результат не определён, если position - итератор в диапазоне [first, last).
remove стирает все элементы в списке, указанном итератором списка i, для которого выполняются следующие условия: *i==value, pred(*i)==true. remove устойчиво, то есть относительный порядок элементов, которые не удалены, тот же самый, как их относительный порядок в первоначальном списке. Соответствующий предикат применяется точно size() раз.
unique стирает все, кроме первого элемента, из каждой последовательной группы равных элементов в списке. Соответствующий бинарный предикат применяется точно size() - 1 раз.
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. То есть двусторонняя очередь особенно оптимизирована для помещения и извлечения элементов в начале и в конце.