26 Containers library [containers]

26.3 Sequence containers [sequences]

26.3.9 Class template forward_­list [forwardlist]

26.3.9.1 Class template forward_­list overview [forwardlist.overview]

Aforward_­list - это контейнер, который поддерживает прямые итераторы и позволяет выполнять операции вставки и стирания с постоянным временем в любом месте последовательности с автоматическим управлением хранилищем. Быстрый произвольный доступ к элементам списка не поддерживается. [ Note: Предполагается, чтоforward_­list у него нулевые объемные или временные накладные расходы по сравнению с рукописным односвязным списком в стиле C. Функции, которые противоречили бы этой цели, были опущены. ]end note

Aforward_­list удовлетворяет всем требованиям a container, за исключением того, чтоsize() функция-член не предоставляется иoperator== имеет линейную сложность. Aforward_­list также удовлетворяет всем требованиям для allocator-aware container. Кроме того, aforward_­list предоставляетassign функции-члены (таблица87) и некоторые из optional container requirements. Здесь приведены описания только для операций forward_­list , не описанных в этой таблице, или для операций, для которых имеется дополнительная семантическая информация.

[ Note: Изменение любого списка требует доступа к элементу, предшествующему первому интересующему элементу, но в aforward_­list нет постоянного способа доступа к предыдущему элементу. По этой причине изменяемые диапазоны, например диапазоны, предоставленные для erase иsplice, должны быть открыты в начале. ]end note

namespace std {
  template <class T, class Allocator = allocator<T>>
  class forward_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]

    // [forwardlist.cons], construct/copy/destroy
    forward_list() : forward_list(Allocator()) { }
    explicit forward_list(const Allocator&);
    explicit forward_list(size_type n, const Allocator& = Allocator());
    forward_list(size_type n, const T& value,
                 const Allocator& = Allocator());
    template <class InputIterator>
      forward_list(InputIterator first, InputIterator last,
                   const Allocator& = Allocator());
    forward_list(const forward_list& x);
    forward_list(forward_list&& x);
    forward_list(const forward_list& x, const Allocator&);
    forward_list(forward_list&& x, const Allocator&);
    forward_list(initializer_list<T>, const Allocator& = Allocator());
    ~forward_list();
    forward_list& operator=(const forward_list& x);
    forward_list& operator=(forward_list&& x)
      noexcept(allocator_traits<Allocator>::is_always_equal::value);
    forward_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;

    // [forwardlist.iter], iterators
    iterator before_begin() noexcept;
    const_iterator before_begin() const noexcept;
    iterator begin() noexcept;
    const_iterator begin() const noexcept;
    iterator end() noexcept;
    const_iterator end() const noexcept;

    const_iterator cbegin() const noexcept;
    const_iterator cbefore_begin() const noexcept;
    const_iterator cend() const noexcept;

    // capacity:
    bool      empty() const noexcept;
    size_type max_size() const noexcept;

    // [forwardlist.access], element access
    reference front();
    const_reference front() const;

    // [forwardlist.modifiers], modifiers
    template <class... Args> reference emplace_front(Args&&... args);
    void push_front(const T& x);
    void push_front(T&& x);
    void pop_front();

    template <class... Args> iterator emplace_after(const_iterator position, Args&&... args);
    iterator insert_after(const_iterator position, const T& x);
    iterator insert_after(const_iterator position, T&& x);

    iterator insert_after(const_iterator position, size_type n, const T& x);
    template <class InputIterator>
      iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
    iterator insert_after(const_iterator position, initializer_list<T> il);

    iterator erase_after(const_iterator position);
    iterator erase_after(const_iterator position, const_iterator last);
    void swap(forward_list&)
      noexcept(allocator_traits<Allocator>::is_always_equal::value);

    void resize(size_type sz);
    void resize(size_type sz, const value_type& c);
    void clear() noexcept;

    // [forwardlist.ops], forward_­list operations
    void splice_after(const_iterator position, forward_list& x);
    void splice_after(const_iterator position, forward_list&& x);
    void splice_after(const_iterator position, forward_list& x,
                      const_iterator i);
    void splice_after(const_iterator position, forward_list&& x,
                      const_iterator i);
    void splice_after(const_iterator position, forward_list& x,
                      const_iterator first, const_iterator last);
    void splice_after(const_iterator position, forward_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(forward_list& x);
    void merge(forward_list&& x);
    template <class Compare> void merge(forward_list& x, Compare comp);
    template <class Compare> void merge(forward_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>>
    forward_list(InputIterator, InputIterator, Allocator = Allocator())
      -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>;

  template <class T, class Allocator>
    bool operator==(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator< (const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator!=(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator> (const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator>=(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
  template <class T, class Allocator>
    bool operator<=(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);

  // [forwardlist.spec], specialized algorithms
  template <class T, class Allocator>
    void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
      noexcept(noexcept(x.swap(y)));
}

Неполный типT может использоваться приforward_­list создании экземпляра, если распределитель удовлетворяет требованиям allocator completeness requirements. T заполняется до того, как будет сделанаforward_­list ссылка на какой-либо член результирующей специализации .

26.3.9.2 forward_­list constructors, copy, assignment [forwardlist.cons]

explicit forward_list(const Allocator&);

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

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

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

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

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

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

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

Effects: Создаетforward_­list объект сn копиями сvalue использованием указанного распределителя.

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

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

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

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

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

26.3.9.3 forward_­list iterators [forwardlist.iter]

iterator before_begin() noexcept; const_iterator before_begin() const noexcept; const_iterator cbefore_begin() const noexcept;

Returns: Итератор без разыменования, который при увеличении равен итератору, возвращаемомуbegin().

Effects:cbefore_­begin() эквивалентно const_­cast<forward_­list const&>(*this).before_­begin().

Remarks:before_­begin() == end() равныfalse.

26.3.9.4 forward_­list element access [forwardlist.access]

reference front(); const_reference front() const;

Returns:*begin()

26.3.9.5 forward_­list modifiers [forwardlist.modifiers]

Ни одна из перегрузокinsert_­after не должна влиять на действительность итераторов и ссылок, иerase_­after должна делать недействительными только итераторы и ссылки на стертые элементы. Если во время сгенерировано исключениеinsert_­after , никакого эффекта не будет. Вставкаn элементов в aforward_­list линейна по n, а количество вызовов конструктора копирования или перемещенияT точно равноn. Стираниеn элементов из aforward_­list линейно по,n и количество вызовов деструктора типаT точно равноn.

template <class... Args> reference emplace_front(Args&&... args);

Effects: Вставляет объект типа, созданногоvalue_­type с помощью, value_­type(std​::​forward<Args>(​args)...) в начало списка.

void push_front(const T& x); void push_front(T&& x);

Effects: Вставляет копиюx в начало списка.

void pop_front();

Effects: Как будто мимоerase_­after(before_­begin()).

iterator insert_after(const_iterator position, const T& x); iterator insert_after(const_iterator position, T&& x);

Requires:position являетсяbefore_­begin() или является разыменяемым итератором в диапазоне[begin(), end()).

Effects: Вставляет копиюx послеposition.

Returns: Итератор, указывающий на копиюx.

iterator insert_after(const_iterator position, size_type n, const T& x);

Requires:position являетсяbefore_­begin() или является разыменяемым итератором в диапазоне[begin(), end()).

Effects: Вставляетn копииx послеposition.

Returns: Итератор, указывающий на последнюю вставленную копиюx илиposition ifn == 0.

template <class InputIterator> iterator insert_after(const_iterator position, InputIterator first, InputIterator last);

Requires:position являетсяbefore_­begin() или является разыменяемым итератором в диапазоне[begin(), end()). first иlast не являются итераторами в*this.

Effects: Вставляет копии элементов в[first, last) afterposition.

Returns: Итератор, указывающий на последний вставленный элемент илиposition iffirst == last.

iterator insert_after(const_iterator position, initializer_list<T> il);

Effects:insert_­after(p, il.begin(), il.end()).

Returns: Итератор, указывающий на последний вставленный элемент илиposition еслиil он пуст.

template <class... Args> iterator emplace_after(const_iterator position, Args&&... args);

Requires:position являетсяbefore_­begin() или является разыменяемым итератором в диапазоне[begin(), end()).

Effects: Вставляет объект типа, созданногоvalue_­type с помощью value_­type(std​::​forward<Args>(​args)...) afterposition.

Returns: Итератор, указывающий на новый объект.

iterator erase_after(const_iterator position);

Requires: Следующий итераторposition можно разыменовать.

Effects: Удаляет элемент, на который указывает следующий итераторposition.

Returns: Итератор, указывающий на элемент, следующий за тем, который был удален, илиend() если такой элемент не существует.

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

iterator erase_after(const_iterator position, const_iterator last);

Requires: Все итераторы в диапазоне(position, last) можно разыменовать.

Effects: Стирает элементы в диапазоне(position, last).

Returns:last.

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

void resize(size_type sz);

Effects: Еслиsz < distance(begin(), end()), стирает последниеdistance(begin(), end()) - sz элементы из списка. В противном случаеsz - distance(begin(), end()) вставляет элементы, вставленные по умолчанию, в конец списка.

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

void resize(size_type sz, const value_type& c);

Effects: Еслиsz < distance(begin(), end()), стирает последниеdistance(begin(), end()) - sz элементы из списка. В противном случае вставляетsz - distance(begin(), end()) копииc в конец списка.

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

void clear() noexcept;

Effects: Удаляет все элементы в диапазоне[begin(), end()).

Remarks: Не делает недействительными итераторы, прошедшие мимо конца.

26.3.9.6 forward_­list operations [forwardlist.ops]

void splice_after(const_iterator position, forward_list& x); void splice_after(const_iterator position, forward_list&& x);

Requires:position являетсяbefore_­begin() или является разыменяемым итератором в диапазоне[begin(), end()). get_­allocator() == x.get_­allocator(). &x != this.

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

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

Complexity:O(distance(x.begin(), x.end()))

void splice_after(const_iterator position, forward_list& x, const_iterator i); void splice_after(const_iterator position, forward_list&& x, const_iterator i);

Requires:position являетсяbefore_­begin() или является разыменяемым итератором в диапазоне[begin(), end()). Следующий итераторi - это итератор с возможностью разыменования вx. get_­allocator() == x.get_­allocator().

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

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

Complexity:O(1)

void splice_after(const_iterator position, forward_list& x, const_iterator first, const_iterator last); void splice_after(const_iterator position, forward_list&& x, const_iterator first, const_iterator last);

Requires:position являетсяbefore_­begin() или является разыменяемым итератором в диапазоне[begin(), end()).(first, last) - допустимый диапазон вx, и все итераторы в этом диапазоне(first, last) можно разыменовать.position не является итератором в диапазоне(first, last). get_­allocator() == x.get_­allocator().

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

Complexity:O(distance(first, last))

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

Effects: Удаляет все элементы в списке, на которые ссылается итератор списка,i для которых выполняются следующие условия:*i == value (forremove()), pred(*i) istrue (forremove_­if()). Делает недействительными только итераторы и ссылки на удаленные элементы.

Throws: Ничего, если сравнение равенства или предикат не вызывает исключения.

Remarks:Stable.

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

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

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

Throws: Ничего, если сравнение равенства или предикат не вызывает исключения.

Complexity: Если диапазон[first, last) не пуст, то это точно(last - first) - 1 применения соответствующего предиката, в противном случае - никакие применения предиката.

void merge(forward_list& x); void merge(forward_list&& x); template <class Compare> void merge(forward_list& x, Compare comp); template <class Compare> void merge(forward_list&& x, Compare comp);

Requires:comp определяетstrict weak orderingи*this иx оба сортируются в соответствии с этим порядком. get_­allocator() == x.get_­allocator().

Effects: Объединяет два отсортированных диапазона[begin(), end()) и [x.begin(), x.end()).x после слияния пусто. Если исключение выбрасывается иначе, чем путем сравнения, нет никаких эффектов. Указатели и ссылки на перемещенные элементыx теперь относятся к тем же элементам, но как к членам*this. Итераторы, относящиеся к перемещенным элементам, будут продолжать ссылаться на свои элементы, но теперь они ведут себя как итераторы в*this, а не в x.

Remarks:Stable. Поведение не определено, если get_­allocator() != x.get_­allocator().

Complexity: Максимумdistance(begin(), end()) + distance(x.begin(), x.end()) - 1 сравнений.

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

Requires:operator< (для версии без аргументов) илиcomp (для версии с аргументом сравнения) определяетstrict weak ordering.

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

Remarks:Stable.

Complexity: ПримерноNlogN сравнения, гдеN естьdistance(begin(), end()).

void reverse() noexcept;

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

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

26.3.9.7 forward_­list specialized algorithms [forwardlist.spec]

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

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