A list - это контейнер последовательности, который поддерживает двунаправленные итераторы и позволяет выполнять операции вставки и стирания с постоянным временем в любом месте последовательности с автоматическим управлением хранением. В отличие отvectors иdeques, быстрый произвольный доступ к элементам списка не поддерживается, но многим алгоритмам в любом случае нужен только последовательный доступ.
Alist удовлетворяет всем требованиям контейнера, обратимого контейнера (приведенного в двух таблицах [container.requirements]), контейнера последовательности, включая большую часть optional sequence container requirements, и файла allocator-aware container. Исключением являются функции-членыoperator[] и at, которые не предусмотрены.258 Здесь описаны только операции list , не описанные в одной из этих таблиц, или операции, в которых есть дополнительная семантическая информация.
namespace std { template <class T, class Allocator = allocator<T>> class list { public: // types: using value_type = T; using allocator_type = Allocator; using pointer = typename allocator_traits<Allocator>::pointer; using const_pointer = typename allocator_traits<Allocator>::const_pointer; using reference = value_type&; using const_reference = const value_type&; using size_type = implementation-defined; // see [container.requirements] using difference_type = implementation-defined; // see [container.requirements] using iterator = implementation-defined; // see [container.requirements] using const_iterator = implementation-defined; // see [container.requirements] using reverse_iterator = std::reverse_iterator<iterator>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; // [list.cons], construct/copy/destroy list() : list(Allocator()) { } explicit list(const Allocator&); explicit list(size_type n, const Allocator& = Allocator()); list(size_type n, const T& value, const Allocator& = Allocator()); template <class InputIterator> list(InputIterator first, InputIterator last, const Allocator& = Allocator()); list(const list& x); list(list&& x); list(const list&, const Allocator&); list(list&&, const Allocator&); list(initializer_list<T>, const Allocator& = Allocator()); ~list(); list& operator=(const list& x); list& operator=(list&& x) noexcept(allocator_traits<Allocator>::is_always_equal::value); list& operator=(initializer_list<T>); template <class InputIterator> void assign(InputIterator first, InputIterator last); void assign(size_type n, const T& t); void assign(initializer_list<T>); allocator_type get_allocator() const noexcept; // iterators: iterator begin() noexcept; const_iterator begin() const noexcept; iterator end() noexcept; const_iterator end() const noexcept; reverse_iterator rbegin() noexcept; const_reverse_iterator rbegin() const noexcept; reverse_iterator rend() noexcept; const_reverse_iterator rend() const noexcept; const_iterator cbegin() const noexcept; const_iterator cend() const noexcept; const_reverse_iterator crbegin() const noexcept; const_reverse_iterator crend() const noexcept; // [list.capacity], capacity bool empty() const noexcept; size_type size() const noexcept; size_type max_size() const noexcept; void resize(size_type sz); void resize(size_type sz, const T& c); // element access: reference front(); const_reference front() const; reference back(); const_reference back() const; // [list.modifiers], modifiers template <class... Args> reference emplace_front(Args&&... args); template <class... Args> reference emplace_back(Args&&... args); void push_front(const T& x); void push_front(T&& x); void pop_front(); void push_back(const T& x); void push_back(T&& x); void pop_back(); template <class... Args> iterator emplace(const_iterator position, Args&&... args); iterator insert(const_iterator position, const T& x); iterator insert(const_iterator position, T&& x); iterator insert(const_iterator position, size_type n, const T& x); template <class InputIterator> iterator insert(const_iterator position, InputIterator first, InputIterator last); iterator insert(const_iterator position, initializer_list<T> il); iterator erase(const_iterator position); iterator erase(const_iterator position, const_iterator last); void swap(list&) noexcept(allocator_traits<Allocator>::is_always_equal::value); void clear() noexcept; // [list.ops], list operations void splice(const_iterator position, list& x); void splice(const_iterator position, list&& x); void splice(const_iterator position, list& x, const_iterator i); void splice(const_iterator position, list&& x, const_iterator i); void splice(const_iterator position, list& x, const_iterator first, const_iterator last); void splice(const_iterator position, list&& x, const_iterator first, const_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& x); void merge(list&& x); template <class Compare> void merge(list& x, Compare comp); template <class Compare> void merge(list&& x, Compare comp); void sort(); template <class Compare> void sort(Compare comp); void reverse() noexcept; }; template<class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> list(InputIterator, InputIterator, Allocator = Allocator()) -> list<typename iterator_traits<InputIterator>::value_type, Allocator>; 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); 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); 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); // [list.special], specialized algorithms template <class T, class Allocator> void swap(list<T, Allocator>& x, list<T, Allocator>& y) noexcept(noexcept(x.swap(y))); }
Неполный типT может использоваться приlist создании экземпляра, если распределитель удовлетворяет требованиям allocator completeness requirements. T заполняется до того, как будет сделанаlist ссылка на какой-либо член результирующей специализации .
Эти функции-члены предоставляются только контейнерами, итераторы которых являются итераторами с произвольным доступом.
explicit list(const Allocator&);
explicit list(size_type n, const Allocator& = Allocator());
Effects: Создаетlist со n вставленными по умолчанию элементами с использованием указанного распределителя.
list(size_type n, const T& value, const Allocator& = Allocator());
template <class InputIterator>
list(InputIterator first, InputIterator last, const Allocator& = Allocator());
void resize(size_type sz);
Effects: Еслиsize() < sz, добавляетsz - size() в последовательность элементы, вставленные по умолчанию. Еслиsz <= size()эквивалентно:
list<T>::iterator it = begin(); advance(it, sz); erase(it, end());
void resize(size_type sz, const T& c);
Effects: Как будто по:
if (sz > size())
insert(end(), sz-size(), c);
else if (sz < size()) {
iterator i = begin();
advance(i, sz);
erase(i, end());
}
else
; // do nothing
iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);
iterator insert(const_iterator position, size_type n, const T& x);
template <class InputIterator>
iterator insert(const_iterator position, InputIterator first,
InputIterator last);
iterator insert(const_iterator position, initializer_list<T>);
template <class... Args> reference emplace_front(Args&&... args);
template <class... Args> reference emplace_back(Args&&... args);
template <class... Args> iterator emplace(const_iterator position, Args&&... args);
void push_front(const T& x);
void push_front(T&& x);
void push_back(const T& x);
void push_back(T&& x);
Remarks: Не влияет на валидность итераторов и ссылок. Если выбрано исключение, никаких эффектов нет.
Complexity: Вставка одного элемента в список занимает постоянное время и ровно один вызов конструктора T. Вставка нескольких элементов в список линейна по количеству вставленных элементов, а количество вызовов конструктора копирования или конструктора перемещенияT точно равно количеству вставленных элементов.
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
void pop_front();
void pop_back();
void clear() noexcept;
Поскольку списки позволяют быстро вставлять и стирать из середины списка, определенные операции предусмотрены специально для них.259
list предоставляет три операции соединения, которые разрушающе перемещают элементы из одного списка в другой. Поведение операций соединения не определено, еслиget_allocator() != x.get_allocator().
void splice(const_iterator position, list& x);
void splice(const_iterator position, list&& x);
Effects: Вставляет содержимое x до position и x становится пустым. Указатели и ссылки на перемещенные элементы x теперь относятся к тем же элементам, но как к членам *this. Итераторы, относящиеся к перемещенным элементам, будут продолжать ссылаться на свои элементы, но теперь они ведут себя как итераторы в *this, а не в x.
void splice(const_iterator position, list& x, const_iterator i);
void splice(const_iterator position, list&& x, const_iterator i);
Effects: Вставляет элемент , на который указывает i из списка ,x прежде чемposition и удаляет элемент из x. Результат не меняется, если position == i или position == ++i. Указатели и ссылки, чтобы *i продолжать ссылаться на этот же элемент, но как на член *this. Итераторы *i (включая i себя) продолжают ссылаться на один и тот же элемент, но теперь ведут себя как итераторы в *this, а не в x.
void splice(const_iterator position, list& x, const_iterator first,
const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first,
const_iterator last);
Requires: [first, last) допустимый диапазон в x. Программа имеет неопределенное поведение, если position является итератором в диапазоне [first, last).
Effects: Вставляет элементы в диапазон [first, last) до position и удаляет элементы из x. Указатели и ссылки на перемещенные элементы x теперь относятся к тем же элементам, но как к членам *this. Итераторы, относящиеся к перемещенным элементам, будут продолжать ссылаться на свои элементы, но теперь они ведут себя как итераторы в *this, а не в x.
void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);
Effects: Удаляет все элементы в списке, на которые ссылается итератор списка,i для которого выполняются следующие условия:*i == value,pred(*i) != false. Делает недействительными только итераторы и ссылки на удаленные элементы.
void unique();
template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
Effects: Удаляет все элементы, кроме первого, из каждой последовательной группы равных элементов, на которую ссылается итераторi в диапазоне, [first + 1, last) для которого*i == *(i-1) (для версии unique без аргументов) илиpred(*i, *(i - 1)) (для версии unique с аргументом предиката) выполняется. Делает недействительными только итераторы и ссылки на удаленные элементы.
Complexity: Если диапазон [first, last) не пуст, то это точно (last - first) - 1 применения соответствующего предиката, в противном случае - никакие применения предиката.
void merge(list& x);
void merge(list&& x);
template <class Compare> void merge(list& x, Compare comp);
template <class Compare> void merge(list&& x, Compare comp);
Requires: comp должен определять astrict weak ordering, и как список, так и список аргументов должны быть отсортированы в соответствии с этим порядком.
Effects: Если(&x == this) ничего не делает; в противном случае объединяет два отсортированных диапазона[begin(), end()) и[x.begin(), x.end()). Результатом является диапазон, в котором элементы будут отсортированы в неубывающем порядке в соответствии с порядком, определенным с помощьюcomp; то есть для каждого итератораiв диапазоне, отличном от первого, условие comp(*i, *(i - 1)) будетfalse. Указатели и ссылки на перемещенные элементыx теперь относятся к тем же элементам, но как к членам*this. Итераторы, относящиеся к перемещенным элементам, будут продолжать ссылаться на свои элементы, но теперь они ведут себя как итераторы в*this, а не в x.
Complexity: В большинстве size() + x.size() - 1 приложенийcomp if (&x != this); в противном случае приложенияcomp не выполняются. Если исключение выбрасывается иначе, чем путем сравнения, нет никаких эффектов.
void reverse() noexcept;
Effects: Меняет порядок элементов в списке на обратный. Не влияет на валидность итераторов и ссылок.
void sort();
template <class Compare> void sort(Compare comp);
Requires: operator< (для первой версии) или comp (для второй версии) должен определять файлstrict weak ordering.
Effects: Сортирует список по объектуoperator< илиCompare функции. Если выбрасывается исключение, порядок элементов в нем*this не указан. Не влияет на валидность итераторов и ссылок.
Как указано в[allocator.requirements], требования этого пункта применяются только к спискам, распределители которых сравниваются одинаково.
template <class T, class Allocator>
void swap(list<T, Allocator>& x, list<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));