Список (List)
list - вид последовательности, которая поддерживает двунаправленные итераторы и позволяет операции вставки и стирания с постоянным временем в любом месте последовательности, с управлением памятью, обрабатываемым автоматически. В отличие от векторов и двусторонних очередей, быстрый произвольный доступ к элементам списка не поддерживается, но многим алгоритмам, во всяком случае, только и нужен последовательный доступ.
template class Allocator = allocator> 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 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& y); template bool operator& x, const list& 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().
