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]

1
#
A forward_­list is a container that supports forward iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically.
Fast random access to list elements is not supported.
[ Note
:
It is intended that forward_­list have zero space or time overhead relative to a hand-written C-style singly linked list.
Features that would conflict with that goal have been omitted.
— end note
 ]
2
#
A forward_­list satisfies all of the requirements of a container (Table 78), except that the size() member function is not provided and operator== has linear complexity.
A forward_­list also satisfies all of the requirements for an allocator-aware container (Table 81).
In addition, a forward_­list provides the assign member functions (Table 82) and several of the optional container requirements (Table 83).
Descriptions are provided here only for operations on forward_­list that are not described in that table or for operations where there is additional semantic information.
3
#
[ Note
:
Modifying any list requires access to the element preceding the first element of interest, but in a forward_­list there is no constant-time way to access a preceding element.
For this reason, ranges that are modified, such as those supplied to erase and splice, must be open at the beginning.
— 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)));
}
4
#
An incomplete type T may be used when instantiating forward_­list if the allocator satisfies the allocator completeness requirements ([allocator.requirements.completeness]).
T shall be complete before any member of the resulting specialization of forward_­list is referenced.

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

explicit forward_list(const Allocator&);
1
#
Effects: Constructs an empty forward_­list object using the specified allocator.
2
#
Complexity: Constant.
explicit forward_list(size_type n, const Allocator& = Allocator());
3
#
Effects: Constructs a forward_­list object with n default-inserted elements using the specified allocator.
4
#
Requires: T shall be DefaultInsertable into *this.
5
#
Complexity: Linear in n.
forward_list(size_type n, const T& value, const Allocator& = Allocator());
6
#
Effects: Constructs a forward_­list object with n copies of value using the specified allocator.
7
#
Requires: T shall be CopyInsertable into *this.
8
#
Complexity: Linear in n.
template <class InputIterator> forward_list(InputIterator first, InputIterator last, const Allocator& = Allocator());
9
#
Effects: Constructs a forward_­list object equal to the range [first, last).
10
#
Complexity: Linear in 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;
1
#
Returns: A non-dereferenceable iterator that, when incremented, is equal to the iterator returned by begin().
2
#
Effects: cbefore_­begin() is equivalent to const_­cast<forward_­list const&>(*this).before_­begin().
3
#
Remarks: before_­begin() == end() shall equal false.

26.3.9.4 forward_­list element access [forwardlist.access]

reference front(); const_reference front() const;
1
#
Returns: *begin()

26.3.9.5 forward_­list modifiers [forwardlist.modifiers]

1
#
None of the overloads of insert_­after shall affect the validity of iterators and references, and erase_­after shall invalidate only iterators and references to the erased elements.
If an exception is thrown during insert_­after there shall be no effect.
Inserting n elements into a forward_­list is linear in n, and the number of calls to the copy or move constructor of T is exactly equal to n.
Erasing n elements from a forward_­list is linear in n and the number of calls to the destructor of type T is exactly equal to n.
template <class... Args> reference emplace_front(Args&&... args);
2
#
Effects: Inserts an object of type value_­type constructed with value_­type(std​::​forward<Args>(​args)...) at the beginning of the list.
void push_front(const T& x); void push_front(T&& x);
3
#
Effects: Inserts a copy of x at the beginning of the list.
void pop_front();
4
#
Effects: As if by erase_­after(before_­begin()).
iterator insert_after(const_iterator position, const T& x); iterator insert_after(const_iterator position, T&& x);
5
#
Requires: position is before_­begin() or is a dereferenceable iterator in the range [begin(), end()).
6
#
Effects: Inserts a copy of x after position.
7
#
Returns: An iterator pointing to the copy of x.
iterator insert_after(const_iterator position, size_type n, const T& x);
8
#
Requires: position is before_­begin() or is a dereferenceable iterator in the range [begin(), end()).
9
#
Effects: Inserts n copies of x after position.
10
#
Returns: An iterator pointing to the last inserted copy of x or position if n == 0.
template <class InputIterator> iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
11
#
Requires: position is before_­begin() or is a dereferenceable iterator in the range [begin(), end()).
first and last are not iterators in *this.
12
#
Effects: Inserts copies of elements in [first, last) after position.
13
#
Returns: An iterator pointing to the last inserted element or position if first == last.
iterator insert_after(const_iterator position, initializer_list<T> il);
14
#
Effects: insert_­after(p, il.begin(), il.end()).
15
#
Returns: An iterator pointing to the last inserted element or position if il is empty.
template <class... Args> iterator emplace_after(const_iterator position, Args&&... args);
16
#
Requires: position is before_­begin() or is a dereferenceable iterator in the range [begin(), end()).
17
#
Effects: Inserts an object of type value_­type constructed with value_­type(std​::​forward<Args>(​args)...) after position.
18
#
Returns: An iterator pointing to the new object.
iterator erase_after(const_iterator position);
19
#
Requires: The iterator following position is dereferenceable.
20
#
Effects: Erases the element pointed to by the iterator following position.
21
#
Returns: An iterator pointing to the element following the one that was erased, or end() if no such element exists.
22
#
Throws: Nothing.
iterator erase_after(const_iterator position, const_iterator last);
23
#
Requires: All iterators in the range (position, last) are dereferenceable.
24
#
Effects: Erases the elements in the range (position, last).
25
#
Returns: last.
26
#
Throws: Nothing.
void resize(size_type sz);
27
#
Effects: If sz < distance(begin(), end()), erases the last distance(begin(), end()) - sz elements from the list.
Otherwise, inserts sz - distance(begin(), end()) default-inserted elements at the end of the list.
28
#
Requires: T shall be DefaultInsertable into *this.
void resize(size_type sz, const value_type& c);
29
#
Effects: If sz < distance(begin(), end()), erases the last distance(begin(), end()) - sz elements from the list.
Otherwise, inserts sz - distance(begin(), end()) copies of c at the end of the list.
30
#
Requires: T shall be CopyInsertable into *this.
void clear() noexcept;
31
#
Effects: Erases all elements in the range [begin(), end()).
32
#
Remarks: Does not invalidate past-the-end iterators.

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);
1
#
Requires: position is before_­begin() or is a dereferenceable iterator in the range [begin(), end()).
get_­allocator() == x.get_­allocator().
&x != this.
2
#
Effects: Inserts the contents of x after position, and x becomes empty.
Pointers and references to the moved elements of x now refer to those same elements but as members of *this.
Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.
3
#
Throws: Nothing.
4
#
Complexity:
void splice_after(const_iterator position, forward_list& x, const_iterator i); void splice_after(const_iterator position, forward_list&& x, const_iterator i);
5
#
Requires: position is before_­begin() or is a dereferenceable iterator in the range [begin(), end()).
The iterator following i is a dereferenceable iterator in x.
get_­allocator() == x.get_­allocator().
6
#
Effects: Inserts the element following i into *this, following position, and removes it from x.
The result is unchanged if position == i or position == ++i.
Pointers and references to *++i continue to refer to the same element but as a member of *this.
Iterators to *++i continue to refer to the same element, but now behave as iterators into *this, not into x.
7
#
Throws: Nothing.
8
#
Complexity:
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);
9
#
Requires: position is before_­begin() or is a dereferenceable iterator in the range [begin(), end()).
(first, last) is a valid range in x, and all iterators in the range (first, last) are dereferenceable.
position is not an iterator in the range (first, last).
get_­allocator() == x.get_­allocator().
10
#
Effects: Inserts elements in the range (first, last) after position and removes the elements from x.
Pointers and references to the moved elements of x now refer to those same elements but as members of *this.
Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.
11
#
Complexity:
void remove(const T& value); template <class Predicate> void remove_if(Predicate pred);
12
#
Effects: Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value (for remove()), pred(*i) is true (for remove_­if()).
Invalidates only the iterators and references to the erased elements.
13
#
Throws: Nothing unless an exception is thrown by the equality comparison or the predicate.
14
#
Remarks: Stable ([algorithm.stable]).
15
#
Complexity: Exactly distance(begin(), end()) applications of the corresponding predicate.
void unique(); template <class BinaryPredicate> void unique(BinaryPredicate pred);
16
#
Effects: Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version with no arguments) or pred(*i, *(i - 1)) (for the version with a predicate argument) holds.
Invalidates only the iterators and references to the erased elements.
17
#
Throws: Nothing unless an exception is thrown by the equality comparison or the predicate.
18
#
Complexity: If the range [first, last) is not empty, exactly (last - first) - 1 applications of the corresponding predicate, otherwise no applications of the predicate.
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);
19
#
Requires: comp defines a strict weak ordering ([alg.sorting]), and *this and x are both sorted according to this ordering.
get_­allocator() == x.get_­allocator().
20
#
Effects: Merges the two sorted ranges [begin(), end()) and [x.begin(), x.end()).
x is empty after the merge.
If an exception is thrown other than by a comparison there are no effects.
Pointers and references to the moved elements of x now refer to those same elements but as members of *this.
Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.
21
#
Remarks: Stable ([algorithm.stable]).
The behavior is undefined if get_­allocator() != x.get_­allocator().
22
#
Complexity: At most distance(begin(), end()) + distance(x.begin(), x.end()) - 1 comparisons.
void sort(); template <class Compare> void sort(Compare comp);
23
#
Requires: operator< (for the version with no arguments) or comp (for the version with a comparison argument) defines a strict weak ordering ([alg.sorting]).
24
#
Effects: Sorts the list according to the operator< or the comp function object.
If an exception is thrown, the order of the elements in *this is unspecified.
Does not affect the validity of iterators and references.
25
#
Remarks: Stable ([algorithm.stable]).
26
#
Complexity: Approximately comparisons, where N is distance(begin(), end()).
void reverse() noexcept;
27
#
Effects: Reverses the order of the elements in the list.
Does not affect the validity of iterators and references.
28
#
Complexity: Linear time.

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)));
1
#
Effects: As if by x.swap(y).