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 ссылка на какой-либо член результирующей специализации .
explicit forward_list(const Allocator&);
explicit forward_list(size_type n, const Allocator& = Allocator());
Effects: Создаетforward_list объект соn вставленными по умолчанию элементами, используя указанный распределитель.
forward_list(size_type n, const T& value, const Allocator& = Allocator());
template <class InputIterator>
forward_list(InputIterator first, InputIterator last, const Allocator& = Allocator());
iterator before_begin() noexcept;
const_iterator before_begin() const noexcept;
const_iterator cbefore_begin() const noexcept;
Returns: Итератор без разыменования, который при увеличении равен итератору, возвращаемомуbegin().
reference front();
const_reference front() const;
Ни одна из перегрузок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);
void pop_front();
iterator insert_after(const_iterator position, const T& x);
iterator insert_after(const_iterator position, T&& x);
Requires:position являетсяbefore_begin() или является разыменяемым итератором в диапазоне[begin(), end()).
iterator insert_after(const_iterator position, size_type n, const T& x);
Requires:position являетсяbefore_begin() или является разыменяемым итератором в диапазоне[begin(), end()).
template <class InputIterator>
iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
Requires:position являетсяbefore_begin() или является разыменяемым итератором в диапазоне[begin(), end()). first иlast не являются итераторами в*this.
iterator insert_after(const_iterator position, initializer_list<T> 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.
iterator erase_after(const_iterator position);
Returns: Итератор, указывающий на элемент, следующий за тем, который был удален, илиend() если такой элемент не существует.
iterator erase_after(const_iterator position, const_iterator last);
void resize(size_type sz);
Effects: Еслиsz < distance(begin(), end()), стирает последниеdistance(begin(), end()) - sz элементы из списка. В противном случаеsz - distance(begin(), end()) вставляет элементы, вставленные по умолчанию, в конец списка.
void resize(size_type sz, const value_type& c);
Effects: Еслиsz < distance(begin(), end()), стирает последниеdistance(begin(), end()) - sz элементы из списка. В противном случае вставляетsz - distance(begin(), end()) копииc в конец списка.
void clear() noexcept;
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.
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.
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.
void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);
Effects: Удаляет все элементы в списке, на которые ссылается итератор списка,i для которых выполняются следующие условия:*i == value (forremove()), pred(*i) istrue (forremove_if()). Делает недействительными только итераторы и ссылки на удаленные элементы.
void unique();
template <class BinaryPredicate> void unique(BinaryPredicate pred);
Effects: Удаляет все элементы, кроме первого, из каждой последовательной группы равных элементов, на которую ссылается итераторi в диапазоне,[first + 1, last) для которого*i == *(i-1) (для версии без аргументов) илиpred(*i, *(i - 1)) (для версии с аргументом предиката) выполняется. Делает недействительными только итераторы и ссылки на удаленные элементы.
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.
void sort();
template <class Compare> void sort(Compare comp);
Requires:operator< (для версии без аргументов) илиcomp (для версии с аргументом сравнения) определяетstrict weak ordering.
Effects: Сортирует список по объекту функцииoperator< илиcomp . Если выбрасывается исключение, порядок элементов в нем*this не указан. Не влияет на валидность итераторов и ссылок.
void reverse() noexcept;
Effects: Меняет порядок элементов в списке на обратный. Не влияет на валидность итераторов и ссылок.
template <class T, class Allocator>
void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
noexcept(noexcept(x.swap(y)));