26 Containers library [containers]

26.3 Sequence containers [sequences]

26.3.10 Class template list [list]

26.3.10.1 Class template list overview [list.overview]

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 ссылка на какой-либо член результирующей специализации .

Эти функции-члены предоставляются только контейнерами, итераторы которых являются итераторами с произвольным доступом.

26.3.10.2 list constructors, copy, and assignment [list.cons]

explicit list(const Allocator&);

Effects: Создает пустой список, используя указанный распределитель.

Complexity: Постоянный.

explicit list(size_type n, const Allocator& = Allocator());

Effects: Создаетlist со n вставленными по умолчанию элементами с использованием указанного распределителя.

Requires:T должен бытьDefaultInsertable в*this.

Complexity: Линейный вход n.

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

Effects: Создает list с n копиями value, используя указанный распределитель.

Requires:T должен бытьCopyInsertable в*this.

Complexity: Линейный вход n.

template <class InputIterator> list(InputIterator first, InputIterator last, const Allocator& = Allocator());

Effects: Создает list равный диапазону [first, last).

Complexity: Линейный вход distance(first, last).

26.3.10.3 list capacity [list.capacity]

void resize(size_type sz);

Effects: Еслиsize() < sz, добавляетsz - size() в последовательность элементы, вставленные по умолчанию. Еслиsz <= size()эквивалентно:

list<T>::iterator it = begin();
advance(it, sz);
erase(it, end());

Requires:T должен быть DefaultInsertable в*this.

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

Requires:T должен бытьCopyInsertable в*this.

26.3.10.4 list modifiers [list.modifiers]

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;

Effects: Делает недействительными только итераторы и ссылки на удаленные элементы.

Throws: Ничего такого.

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

26.3.10.5 list operations [list.ops]

Поскольку списки позволяют быстро вставлять и стирать из середины списка, определенные операции предусмотрены специально для них.259

list предоставляет три операции соединения, которые разрушающе перемещают элементы из одного списка в другой. Поведение операций соединения не определено, еслиget_­allocator() != x.get_­allocator().

void splice(const_iterator position, list& x); void splice(const_iterator position, list&& x);

Requires: &x != this.

Effects: Вставляет содержимое x до position и x становится пустым. Указатели и ссылки на перемещенные элементы x теперь относятся к тем же элементам, но как к членам *this. Итераторы, относящиеся к перемещенным элементам, будут продолжать ссылаться на свои элементы, но теперь они ведут себя как итераторы в *this, а не в x.

Throws: Ничего такого.

Complexity: Постоянное время.

void splice(const_iterator position, list& x, const_iterator i); void splice(const_iterator position, list&& x, const_iterator i);

Requires: i - допустимый разыменяемый итератор для x.

Effects: Вставляет элемент , на который указывает i из списка ,x прежде чемposition и удаляет элемент из x. Результат не меняется, если position == i или position == ++i. Указатели и ссылки, чтобы *i продолжать ссылаться на этот же элемент, но как на член *this. Итераторы *i (включая i себя) продолжают ссылаться на один и тот же элемент, но теперь ведут себя как итераторы в *this, а не в x.

Throws: Ничего такого.

Complexity: Постоянное время.

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.

Throws: Ничего такого.

Complexity: Постоянное время, если &x == this; в противном случае - линейное время.

void remove(const T& value); template <class Predicate> void remove_if(Predicate pred);

Effects: Удаляет все элементы в списке, на которые ссылается итератор списка,i для которого выполняются следующие условия:*i == value,pred(*i) != false. Делает недействительными только итераторы и ссылки на удаленные элементы.

Throws: Ничего, если исключение не вызвано *i == value или pred(*i) != false.

Remarks:Stable.

Complexity: Точно size() применения соответствующего предиката.

void unique(); template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);

Effects: Удаляет все элементы, кроме первого, из каждой последовательной группы равных элементов, на которую ссылается итераторi в диапазоне, [first + 1, last) для которого*i == *(i-1) (для версии unique без аргументов) илиpred(*i, *(i - 1)) (для версии unique с аргументом предиката) выполняется. Делает недействительными только итераторы и ссылки на удаленные элементы.

Throws: Ничего, если исключение не вызвано *i == *(i-1) или pred(*i, *(i - 1))

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.

Remarks:Stable. Если после слияния(&x != this) диапазон[x.begin(), x.end())пуст. Эта операция не копирует никакие элементы. Поведение не определено, если get_­allocator() != x.get_­allocator().

Complexity: В большинстве size() + x.size() - 1 приложенийcomp if (&x != this); в противном случае приложенияcomp не выполняются. Если исключение выбрасывается иначе, чем путем сравнения, нет никаких эффектов.

void reverse() noexcept;

Effects: Меняет порядок элементов в списке на обратный. Не влияет на валидность итераторов и ссылок.

Complexity: Линейное время.

void sort(); template <class Compare> void sort(Compare comp);

Requires: operator< (для первой версии) или comp (для второй версии) должен определять файлstrict weak ordering.

Effects: Сортирует список по объектуoperator< илиCompare функции. Если выбрасывается исключение, порядок элементов в нем*this не указан. Не влияет на валидность итераторов и ссылок.

Remarks:Stable.

Complexity: Примерно NlogN сравнения, где N == size().

Как указано в[allocator.requirements], требования этого пункта применяются только к спискам, распределители которых сравниваются одинаково.

26.3.10.6 list specialized algorithms [list.special]

template <class T, class Allocator> void swap(list<T, Allocator>& x, list<T, Allocator>& y) noexcept(noexcept(x.swap(y)));

Effects: Как будто мимоx.swap(y).