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

template ‹class T, template ‹class U› class Allocator = allocator›
class list {
public:

 // определения типов:
 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_reverse_iterator;

 // размещение/удаление:
 list()
 list(size_type n, const T& value = T());
 template ‹class InputIterator›
 list(InputIterator first, InputIterator last);
 list(const list‹T, Allocator›& x);
 ~list();
 list‹T, Allocator›& operator=(const list‹T,Allocator›& x);
 void swap(list‹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();
 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 ‹class InputIterator›
 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‹T, Allocator›& x);
 void splice(iterator position, list‹T, Allocator›& x, iterator i);
 void splice(iterator position, list‹T, Allocator›& x, iterator first, iterator last);
 void remove(const T& value);
 template ‹class Predicate›
 void remove_if(Predicate pred);
 void unique();
 template ‹class BinaryPredicate›
 void unique(BinaryPredicate binary_pred);
 void merge(list‹T, Allocator›& x);
 template ‹class Compare›
 void merge(list‹T,Allocator›& x, Compare comp);
 void reverse();
 void sort();
 template ‹class Compare› void sort(Compare comp);
};

template ‹class T, class Allocator›
bool operator==(const list‹T, Allocator›& x, const list‹T, Allocator›& y);

template ‹class T, class Allocator›
bool operator‹(const list‹T, Allocator›& x, const list‹T, 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‹T, Allocator›& x) вставляет содержимое x перед position, и x становится пустым. Требуется постоянное время. Результат не определён, если &x==this.

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

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 раз.