[forward.list] - C++20 → C++23

Files changed (1) hide show

tmp/tmpog733j7g/{from.md → to.md} +620 -0

tmp/tmpog733j7g/{from.md → to.md} RENAMED Viewed

	@@ -0,0 +1,620 @@

+### Class template `forward_list` <a id="forward.list">[[forward.list]]</a>
+#### Overview <a id="forward.list.overview">[[forward.list.overview]]</a>
+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 1*: 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*]
+A `forward_list` meets all of the requirements of a container
+[[container.reqmts]], except that the `size()` member function is not
+provided and `operator==` has linear complexity, A `forward_list` also
+meets all of the requirements for an allocator-aware container
+[[container.alloc.reqmts]]. In addition, a `forward_list` provides the
+`assign` member functions and several of the optional sequence container
+requirements [[sequence.reqmts]]. 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.
+[*Note 2*: 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,
+`erase_after` and `splice_after` take fully-open ranges, not semi-open
+ranges. — *end note*]
+``` cpp
+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  // type of forward_list::size_type; // see [container.requirements]
+    using difference_type = implementation-defined  // type of forward_list::difference_type; // see [container.requirements]
+    using iterator        = implementation-defined  // type of forward_list::iterator; // see [container.requirements]
+    using const_iterator  = implementation-defined  // type of forward_list::const_iterator; // see [container.requirements]
+    // [forward.list.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());
+    template<container-compatible-range<T> R>
+      forward_list(from_range_t, R&& rg, const Allocator& = Allocator());
+    forward_list(const forward_list& x);
+    forward_list(forward_list&& x);
+    forward_list(const forward_list& x, const type_identity_t<Allocator>&);
+    forward_list(forward_list&& x, const type_identity_t<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);
+    template<container-compatible-range<T> R>
+      void assign_range(R&& rg);
+    void assign(size_type n, const T& t);
+    void assign(initializer_list<T>);
+    allocator_type get_allocator() const noexcept;
+    // [forward.list.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
+    [[nodiscard]] bool empty() const noexcept;
+    size_type max_size() const noexcept;
+    // [forward.list.access], element access
+    reference front();
+    const_reference front() const;
+    // [forward.list.modifiers], modifiers
+    template<class... Args> reference emplace_front(Args&&... args);
+    void push_front(const T& x);
+    void push_front(T&& x);
+    template<container-compatible-range<T> R>
+      void prepend_range(R&& rg);
+    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);
+    template<container-compatible-range<T> R>
+      iterator insert_range_after(const_iterator position, R&& rg);
+    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;
+    // [forward.list.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);
+    size_type remove(const T& value);
+    template<class Predicate> size_type remove_if(Predicate pred);
+    size_type unique();
+    template<class BinaryPredicate> size_type 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<iter-value-type<InputIterator>>>
+    forward_list(InputIterator, InputIterator, Allocator = Allocator())
+      -> forward_list<iter-value-type<InputIterator>, Allocator>;
+  template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
+    forward_list(from_range_t, R&&, Allocator = Allocator())
+      -> forward_list<ranges::range_value_t<R>, Allocator>;
+}
+```
+An incomplete type `T` may be used when instantiating `forward_list` if
+the allocator meets the allocator completeness requirements
+[[allocator.requirements.completeness]]. `T` shall be complete before
+any member of the resulting specialization of `forward_list` is
+referenced.
+#### Constructors, copy, and assignment <a id="forward.list.cons">[[forward.list.cons]]</a>
+``` cpp
+explicit forward_list(const Allocator&);
+```
+*Effects:* Constructs an empty `forward_list` object using the specified
+allocator.
+*Complexity:* Constant.
+``` cpp
+explicit forward_list(size_type n, const Allocator& = Allocator());
+```
+*Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
+*Effects:* Constructs a `forward_list` object with `n` default-inserted
+elements using the specified allocator.
+*Complexity:* Linear in `n`.
+``` cpp
+forward_list(size_type n, const T& value, const Allocator& = Allocator());
+```
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
+*Effects:* Constructs a `forward_list` object with `n` copies of `value`
+using the specified allocator.
+*Complexity:* Linear in `n`.
+``` cpp
+template<class InputIterator>
+  forward_list(InputIterator first, InputIterator last, const Allocator& = Allocator());
+```
+*Effects:* Constructs a `forward_list` object equal to the range
+\[`first`, `last`).
+*Complexity:* Linear in `distance(first, last)`.
+``` cpp
+template<container-compatible-range<T> R>
+  forward_list(from_range_t, R&& rg, const Allocator& = Allocator());
+```
+*Effects:* Constructs a `forward_list` object with the elements of the
+range `rg`.
+*Complexity:* Linear in `ranges::distance(rg)`.
+#### Iterators <a id="forward.list.iter">[[forward.list.iter]]</a>
+``` cpp
+iterator before_begin() noexcept;
+const_iterator before_begin() const noexcept;
+const_iterator cbefore_begin() const noexcept;
+```
+*Effects:* `cbefore_begin()` is equivalent to
+`const_cast<forward_list const&>(*this).before_begin()`.
+*Returns:* A non-dereferenceable iterator that, when incremented, is
+equal to the iterator returned by `begin()`.
+*Remarks:* `before_begin() == end()` shall equal `false`.
+#### Element access <a id="forward.list.access">[[forward.list.access]]</a>
+``` cpp
+reference front();
+const_reference front() const;
+```
+*Returns:* `*begin()`
+#### Modifiers <a id="forward.list.modifiers">[[forward.list.modifiers]]</a>
+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`.
+``` cpp
+template<class... Args> reference emplace_front(Args&&... args);
+```
+*Effects:* Inserts an object of type `value_type` constructed with
+`value_type(std::forward<Args>(args)...)` at the beginning of the list.
+``` cpp
+void push_front(const T& x);
+void push_front(T&& x);
+```
+*Effects:* Inserts a copy of `x` at the beginning of the list.
+``` cpp
+template<container-compatible-range<T> R>
+  void prepend_range(R&& rg);
+```
+*Effects:* Inserts a copy of each element of `rg` at the beginning of
+the list.
+[*Note 1*: The order of elements is not reversed. — *end note*]
+``` cpp
+void pop_front();
+```
+*Effects:* As if by `erase_after(before_begin())`.
+``` cpp
+iterator insert_after(const_iterator position, const T& x);
+```
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `forward_list`.
+`position` is `before_begin()` or is a dereferenceable iterator in the
+range \[`begin()`, `end()`).
+*Effects:* Inserts a copy of `x` after `position`.
+*Returns:* An iterator pointing to the copy of `x`.
+``` cpp
+iterator insert_after(const_iterator position, T&& x);
+```
+*Preconditions:* `T` is *Cpp17MoveInsertable* into `forward_list`.
+`position` is `before_begin()` or is a dereferenceable iterator in the
+range \[`begin()`, `end()`).
+*Effects:* Inserts a copy of `x` after `position`.
+*Returns:* An iterator pointing to the copy of `x`.
+``` cpp
+iterator insert_after(const_iterator position, size_type n, const T& x);
+```
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `forward_list`.
+`position` is `before_begin()` or is a dereferenceable iterator in the
+range \[`begin()`, `end()`).
+*Effects:* Inserts `n` copies of `x` after `position`.
+*Returns:* An iterator pointing to the last inserted copy of `x`, or
+`position` if `n == 0` is `true`.
+``` cpp
+template<class InputIterator>
+  iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
+```
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `forward_list`
+from `*first`. `position` is `before_begin()` or is a dereferenceable
+iterator in the range \[`begin()`, `end()`). Neither `first` nor `last`
+are iterators in `*this`.
+*Effects:* Inserts copies of elements in \[`first`, `last`) after
+`position`.
+*Returns:* An iterator pointing to the last inserted element, or
+`position` if `first == last` is `true`.
+``` cpp
+template<container-compatible-range<T> R>
+  iterator insert_range_after(const_iterator position, R&& rg);
+```
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `forward_list`
+from `*ranges::begin(rg)`. `position` is `before_begin()` or is a
+dereferenceable iterator in the range \[`begin()`, `end()`). `rg` and
+`*this` do not overlap.
+*Effects:* Inserts copies of elements in the range `rg` after
+`position`.
+*Returns:* An iterator pointing to the last inserted element, or
+`position` if `rg` is empty.
+``` cpp
+iterator insert_after(const_iterator position, initializer_list<T> il);
+```
+*Effects:* Equivalent to:
+`return insert_after(position, il.begin(), il.end());`
+``` cpp
+template<class... Args>
+  iterator emplace_after(const_iterator position, Args&&... args);
+```
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `forward_list`
+from `std::forward<Args>(args)...`. `position` is `before_begin()` or is
+a dereferenceable iterator in the range \[`begin()`, `end()`).
+*Effects:* Inserts an object of type `value_type`
+direct-non-list-initialized with `std::forward<Args>(args)...` after
+`position`.
+*Returns:* An iterator pointing to the new object.
+``` cpp
+iterator erase_after(const_iterator position);
+```
+*Preconditions:* The iterator following `position` is dereferenceable.
+*Effects:* Erases the element pointed to by the iterator following
+`position`.
+*Returns:* An iterator pointing to the element following the one that
+was erased, or `end()` if no such element exists.
+*Throws:* Nothing.
+``` cpp
+iterator erase_after(const_iterator position, const_iterator last);
+```
+*Preconditions:* All iterators in the range (`position`, `last`) are
+dereferenceable.
+*Effects:* Erases the elements in the range (`position`, `last`).
+*Returns:* `last`.
+*Throws:* Nothing.
+``` cpp
+void resize(size_type sz);
+```
+*Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
+*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.
+``` cpp
+void resize(size_type sz, const value_type& c);
+```
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
+*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.
+``` cpp
+void clear() noexcept;
+```
+*Effects:* Erases all elements in the range \[`begin()`, `end()`).
+*Remarks:* Does not invalidate past-the-end iterators.
+#### Operations <a id="forward.list.ops">[[forward.list.ops]]</a>
+In this subclause, arguments for a template parameter named `Predicate`
+or `BinaryPredicate` shall meet the corresponding requirements in
+[[algorithms.requirements]]. The semantics of `i + n`, where `i` is an
+iterator into the list and `n` is an integer, are the same as those of
+`next(i, n)`. The expression `i - n`, where `i` is an iterator into the
+list and `n` is an integer, means an iterator `j` such that `j + n == i`
+is `true`. For `merge` and `sort`, the definitions and requirements in
+[[alg.sorting]] apply.
+``` cpp
+void splice_after(const_iterator position, forward_list& x);
+void splice_after(const_iterator position, forward_list&& x);
+```
+*Preconditions:* `position` is `before_begin()` or is a dereferenceable
+iterator in the range \[`begin()`, `end()`).
+`get_allocator() == x.get_allocator()` is `true`. `addressof(x) != this`
+is `true`.
+*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`.
+*Throws:* Nothing.
+*Complexity:* 𝑂(`distance(x.begin(), x.end())`)
+``` cpp
+void splice_after(const_iterator position, forward_list& x, const_iterator i);
+void splice_after(const_iterator position, forward_list&& x, const_iterator i);
+```
+*Preconditions:* `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()` is `true`.
+*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`.
+*Throws:* Nothing.
+*Complexity:* 𝑂(1)
+``` cpp
+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);
+```
+*Preconditions:* `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()` is `true`.
+*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`.
+*Complexity:* 𝑂(`distance(first, last)`)
+``` cpp
+size_type remove(const T& value);
+template<class Predicate> size_type remove_if(Predicate pred);
+```
+*Effects:* Erases all the elements in the list referred to 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.
+*Returns:* The number of elements erased.
+*Throws:* Nothing unless an exception is thrown by the equality
+comparison or the predicate.
+*Complexity:* Exactly `distance(begin(), end())` applications of the
+corresponding predicate.
+*Remarks:* Stable [[algorithm.stable]].
+``` cpp
+size_type unique();
+template<class BinaryPredicate> size_type unique(BinaryPredicate binary_pred);
+```
+Let `binary_pred` be `equal_to<>{}` for the first overload.
+*Preconditions:* `binary_pred` is an equivalence relation.
+*Effects:* Erases all but the first element from every consecutive group
+of equivalent elements. That is, for a nonempty list, erases all
+elements referred to by the iterator `i` in the range \[`begin() + 1`,
+`end()`) for which `binary_pred(*i, *(i - 1))` is `true`. Invalidates
+only the iterators and references to the erased elements.
+*Returns:* The number of elements erased.
+*Throws:* Nothing unless an exception is thrown by the predicate.
+*Complexity:* If `empty()` is `false`, exactly
+`distance(begin(), end()) - 1` applications of the corresponding
+predicate, otherwise no applications of the predicate.
+``` cpp
+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);
+```
+Let `comp` be `less<>` for the first two overloads.
+*Preconditions:* `*this` and `x` are both sorted with respect to the
+comparator `comp`, and `get_allocator() == x.get_allocator()` is `true`.
+*Effects:* If `addressof(x) == this`, there are no effects. Otherwise,
+merges the two sorted ranges \[`begin()`, `end()`) and \[`x.begin()`,
+`x.end()`). The result is a range that is sorted with respect to the
+comparator `comp`. 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`.
+*Complexity:* At most
+`distance(begin(), end()) + distance(x.begin(), x.end()) - 1`
+comparisons if `addressof(x) != this`; otherwise, no comparisons are
+performed.
+*Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, `x`
+is empty after the merge. No elements are copied by this operation. If
+an exception is thrown other than by a comparison, there are no effects.
+``` cpp
+void sort();
+template<class Compare> void sort(Compare comp);
+```
+*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.
+*Complexity:* Approximately N log N comparisons, where N is
+`distance(begin(), end())`.
+*Remarks:* Stable [[algorithm.stable]].
+``` cpp
+void reverse() noexcept;
+```
+*Effects:* Reverses the order of the elements in the list. Does not
+affect the validity of iterators and references.
+*Complexity:* Linear time.
+#### Erasure <a id="forward.list.erasure">[[forward.list.erasure]]</a>
+``` cpp
+template<class T, class Allocator, class U>
+  typename forward_list<T, Allocator>::size_type
+    erase(forward_list<T, Allocator>& c, const U& value);
+```
+*Effects:* Equivalent to:
+`return erase_if(c, [&](auto& elem) { return elem == value; });`
+``` cpp
+template<class T, class Allocator, class Predicate>
+  typename forward_list<T, Allocator>::size_type
+    erase_if(forward_list<T, Allocator>& c, Predicate pred);
+```
+*Effects:* Equivalent to: `return c.remove_if(pred);`

Diff to HTML by rtfpessoa