List. 
Стандартная библиотека шаблонов

list — вид последовательности, которая поддерживает двунаправленные итераторы и позволяет операции вставки и стирания с постоянным временем в любом месте последовательности, с управлением памятью, обрабатываемым автоматически. В отличие от векторов и двусторонних очередей, быстрый произвольный доступ к элементам списка не поддерживается, но многим алгоритмам, во всяком случае, только и нужен последовательный доступ.

template.

class list {.

public:

// определения типов:

typedef iterator;

typedef const_iterator;

typedef Allocator: pointer pointer;

typedef Allocator: reference reference;

typedef Allocator: const_reference const_reference;

typedef size_type;

typedef difference_type;

typedef Т value_type;

typedef reverse_iterator;

typedef const_reverse_iterator;

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

list ().

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

template.

list (InputIterator first, InputIterator last);

list (const list& x);

~list ();

list& operator=(const list& x);

void swap (list.

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

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 ();

bool empty () const;

size_type size () const;

size_type max_size () 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);

// специальные модифицирующие операции cо списком:

void splice (iterator position, list& x);

void splice (iterator position, list& x,.

iterator i);

void splice (iterator position, list& x,.

iterator first, iterator last);

void remove (const T& value);

template void remove_if (Predicate pred);

void unique ();

template void unique (BinaryPredicate binary_pred);

void merge (list& x);

template void merge (list& x, Compare comp);

void reverse ();

void sort ();

template void sort (Compare comp);

};

template.

bool operator==(const list& x, const list.

Allocator>& y);

template.

bool operator<(const list& x, const list.

Allocator>& y);

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

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

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

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

insert не влияет на действительность итераторов и ссылок. Вставка единственного элемента в список занимает постоянное время, и ровно один раз вызывается конструктор копирования T. Вставка множественных элементов в список зависит линейно от числа вставленных элементов, а число вызовов конструктора копирования T точно равно числу вставленных элементов.

erase делает недействительными только итераторы и ссылки для стёртых элементов. Стирание единственного элемента — операция постоянного времени с единственным вызовом деструктора T. Стирание диапазона в списке занимает линейное время от размера диапазона, а число вызовов деструктора типа T точно равно размеру диапазона.

Так как списки позволяют быструю вставку и стирание в середине списка, то некоторые операции определяются специально для них:

list обеспечивает три операции стыковки, которые разрушительно перемещают элементы из одного списка в другой:

void splice (iterator position, list& x) вставляет содержимое x перед position, и x становится пустым. Требуется постоянное время. Результат не определён, если &x == this.

void splice (iterator position, list& x, iterator i) вставляет элемент, указываемый i, из списка x перед position и удаляет элемент из x. Требуется постоянное время. i — допустимый разыменовываемый итератор списка x. Результат не изменяется, если position == i или position == ++i.

void splice (iterator position, list& 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 ().