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