[deque] - C++17 → C++20

Files changed (1) hide show

tmp/tmpz8a52aa_/{from.md → to.md} +67 -59

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

@@ -1,31 +1,30 @@
 ### Class template `deque` <a id="deque">[[deque]]</a>
-#### Class template `deque` overview <a id="deque.overview">[[deque.overview]]</a>
 A `deque` is a sequence container that supports random access iterators
-([[random.access.iterators]]). In addition, it supports constant time
 insert and erase operations at the beginning or the end; insert and
 erase in the middle take linear time. That is, a deque is especially
 optimized for pushing and popping elements at the beginning and end.
 Storage management is handled automatically.
-A `deque` satisfies all of the requirements of a container, of a
-reversible container (given in tables in  [[container.requirements]]),
-of a sequence container, including the optional sequence container
-requirements ([[sequence.reqmts]]), and of an allocator-aware container
-(Table  [[tab:containers.allocatoraware]]). Descriptions are provided
-here only for operations on `deque` that are not described in one of
-these tables or for operations where there is additional semantic
-information.
 ``` cpp
 namespace std {
   template<class T, class Allocator = allocator<T>>
   class deque {
   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&;
@@ -59,11 +58,11 @@ namespace std {
       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;
@@ -75,18 +74,18 @@ namespace std {
     const_iterator         cend() const noexcept;
     const_reverse_iterator crbegin() const noexcept;
     const_reverse_iterator crend() const noexcept;
     // [deque.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);
     void      shrink_to_fit();
-    // element access:
     reference       operator[](size_type n);
     const_reference operator[](size_type n) const;
     reference       at(size_type n);
     const_reference at(size_type n) const;
     reference       front();
@@ -119,36 +118,22 @@ namespace std {
     void     swap(deque&)
       noexcept(allocator_traits<Allocator>::is_always_equal::value);
     void     clear() noexcept;
   };
-  template<class InputIterator,
-           class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
     deque(InputIterator, InputIterator, Allocator = Allocator())
-      -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;
- template <class T, class Allocator>
-    bool operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
-  template <class T, class Allocator>
-    bool operator< (const deque<T, Allocator>& x, const deque<T, Allocator>& y);
-  template <class T, class Allocator>
-    bool operator!=(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
-  template <class T, class Allocator>
-    bool operator> (const deque<T, Allocator>& x, const deque<T, Allocator>& y);
-  template <class T, class Allocator>
-    bool operator>=(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
-  template <class T, class Allocator>
-    bool operator<=(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
-  // [deque.special], specialized algorithms
   template<class T, class Allocator>
     void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
       noexcept(noexcept(x.swap(y)));
 }
 ```
-#### `deque` constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
 ``` cpp
 explicit deque(const Allocator&);
 ```
@@ -161,22 +146,22 @@ explicit deque(size_type n, const Allocator& = Allocator());
 ```
 *Effects:* Constructs a `deque` with `n` default-inserted elements using
 the specified allocator.
-*Requires:* `T` shall be `DefaultInsertable` into `*this`.
 *Complexity:* Linear in `n`.
 ``` cpp
 deque(size_type n, const T& value, const Allocator& = Allocator());
 ```
 *Effects:* Constructs a `deque` with `n` copies of `value`, using the
 specified allocator.
-*Requires:* `T` shall be `CopyInsertable` into `*this`.
 *Complexity:* Linear in `n`.
 ``` cpp
 template<class InputIterator>
@@ -186,55 +171,57 @@ template <class InputIterator>
 *Effects:* Constructs a `deque` equal to the range \[`first`, `last`),
 using the specified allocator.
 *Complexity:* Linear in `distance(first, last)`.
-#### `deque` capacity <a id="deque.capacity">[[deque.capacity]]</a>
 ``` cpp
 void resize(size_type sz);
 ```
 *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
 the sequence. Otherwise, appends `sz - size()` default-inserted elements
 to the sequence.
-*Requires:* `T` shall be `MoveInsertable` and `DefaultInsertable` into
-`*this`.
 ``` cpp
 void resize(size_type sz, const T& c);
 ```
 *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
 the sequence. Otherwise, appends `sz - size()` copies of `c` to the
 sequence.
-*Requires:* `T` shall be `CopyInsertable` into `*this`.
 ``` cpp
 void shrink_to_fit();
 ```
-*Requires:* `T` shall be `MoveInsertable` into `*this`.
 *Effects:* `shrink_to_fit` is a non-binding request to reduce memory use
 but does not change the size of the sequence.
 [*Note 1*: The request is non-binding to allow latitude for
 implementation-specific optimizations. — *end note*]
-If an exception is thrown other than by the move constructor of a
-non-`CopyInsertable` `T` there are no effects.
-*Complexity:* Linear in the size of the sequence.
-*Remarks:* `shrink_to_fit` invalidates all the references, pointers, and
-iterators referring to the elements in the sequence as well as the
-past-the-end iterator.
-#### `deque` modifiers <a id="deque.modifiers">[[deque.modifiers]]</a>
 ``` cpp
 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);
@@ -259,16 +246,16 @@ has no effect on the validity of references to elements of the deque.
 *Remarks:* If an exception is thrown other than by the copy constructor,
 move constructor, assignment operator, or move assignment operator of
 `T` there are no effects. If an exception is thrown while inserting a
 single element at either end, there are no effects. Otherwise, if an
-exception is thrown by the move constructor of a non-`CopyInsertable`
-`T`, the effects are unspecified.
 *Complexity:* The complexity is linear in the number of elements
 inserted plus the lesser of the distances to the beginning and end of
-the deque. Inserting a single element either at the beginning or end of
 a deque always takes constant time and causes a single call to a
 constructor of `T`.
 ``` cpp
 iterator erase(const_iterator position);
@@ -293,19 +280,40 @@ operations. — *end note*]
 as the number of elements erased, but the number of calls to the
 assignment operator of `T` is no more than the lesser of the number of
 elements before the erased elements and the number of elements after the
 erased elements.
-*Throws:* Nothing unless an exception is thrown by the copy constructor,
-move constructor, assignment operator, or move assignment operator of
-`T`.
-#### `deque` specialized algorithms <a id="deque.special">[[deque.special]]</a>
 ``` cpp
-template <class T, class Allocator>
- void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
- noexcept(noexcept(x.swap(y)));
 ```
-*Effects:* As if by `x.swap(y)`.

 ### Class template `deque` <a id="deque">[[deque]]</a>
+#### Overview <a id="deque.overview">[[deque.overview]]</a>
 A `deque` is a sequence container that supports random access iterators
+[[random.access.iterators]]. In addition, it supports constant time
 insert and erase operations at the beginning or the end; insert and
 erase in the middle take linear time. That is, a deque is especially
 optimized for pushing and popping elements at the beginning and end.
 Storage management is handled automatically.
+A `deque` meets all of the requirements of a container, of a reversible
+container (given in tables in  [[container.requirements]]), of a
+sequence container, including the optional sequence container
+requirements [[sequence.reqmts]], and of an allocator-aware container (
+[[container.alloc.req]]). Descriptions are provided here only for
+operations on `deque` that are not described in one of these tables or
+for operations where there is additional semantic information.
 ``` cpp
 namespace std {
   template<class T, class Allocator = allocator<T>>
   class deque {
   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&;
       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_iterator         cend() const noexcept;
     const_reverse_iterator crbegin() const noexcept;
     const_reverse_iterator crend() const noexcept;
     // [deque.capacity], capacity
+ [[nodiscard]] 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);
     void      shrink_to_fit();
+    // element access
     reference       operator[](size_type n);
     const_reference operator[](size_type n) const;
     reference       at(size_type n);
     const_reference at(size_type n) const;
     reference       front();
     void     swap(deque&)
       noexcept(allocator_traits<Allocator>::is_always_equal::value);
     void     clear() noexcept;
   };
+  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
     deque(InputIterator, InputIterator, Allocator = Allocator())
+      -> deque<iter-value-type<InputIterator>, Allocator>;
+ // swap
   template<class T, class Allocator>
     void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
       noexcept(noexcept(x.swap(y)));
 }
 ```
+#### Constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
 ``` cpp
 explicit deque(const Allocator&);
 ```
 ```
 *Effects:* Constructs a `deque` with `n` default-inserted elements using
 the specified allocator.
+*Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
 *Complexity:* Linear in `n`.
 ``` cpp
 deque(size_type n, const T& value, const Allocator& = Allocator());
 ```
 *Effects:* Constructs a `deque` with `n` copies of `value`, using the
 specified allocator.
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
 *Complexity:* Linear in `n`.
 ``` cpp
 template<class InputIterator>
 *Effects:* Constructs a `deque` equal to the range \[`first`, `last`),
 using the specified allocator.
 *Complexity:* Linear in `distance(first, last)`.
+#### Capacity <a id="deque.capacity">[[deque.capacity]]</a>
 ``` cpp
 void resize(size_type sz);
 ```
+*Preconditions:* `T` is *Cpp17MoveInsertable* and
+*Cpp17DefaultInsertable* into `*this`.
 *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
 the sequence. Otherwise, appends `sz - size()` default-inserted elements
 to the sequence.
 ``` cpp
 void resize(size_type sz, const T& c);
 ```
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
 *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
 the sequence. Otherwise, appends `sz - size()` copies of `c` to the
 sequence.
 ``` cpp
 void shrink_to_fit();
 ```
+*Preconditions:* `T` is *Cpp17MoveInsertable* into `*this`.
 *Effects:* `shrink_to_fit` is a non-binding request to reduce memory use
 but does not change the size of the sequence.
 [*Note 1*: The request is non-binding to allow latitude for
 implementation-specific optimizations. — *end note*]
+If the size is equal to the old capacity, or if an exception is thrown
+other than by the move constructor of a non-*Cpp17CopyInsertable* `T`,
+then there are no effects.
+*Complexity:* If the size is not equal to the old capacity, linear in
+the size of the sequence; otherwise constant.
+*Remarks:* If the size is not equal to the old capacity, then
+invalidates all the references, pointers, and iterators referring to the
+elements in the sequence, as well as the past-the-end iterator.
+#### Modifiers <a id="deque.modifiers">[[deque.modifiers]]</a>
 ``` cpp
 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);
 *Remarks:* If an exception is thrown other than by the copy constructor,
 move constructor, assignment operator, or move assignment operator of
 `T` there are no effects. If an exception is thrown while inserting a
 single element at either end, there are no effects. Otherwise, if an
+exception is thrown by the move constructor of a
+non-*Cpp17CopyInsertable* `T`, the effects are unspecified.
 *Complexity:* The complexity is linear in the number of elements
 inserted plus the lesser of the distances to the beginning and end of
+the deque. Inserting a single element at either the beginning or end of
 a deque always takes constant time and causes a single call to a
 constructor of `T`.
 ``` cpp
 iterator erase(const_iterator position);
 as the number of elements erased, but the number of calls to the
 assignment operator of `T` is no more than the lesser of the number of
 elements before the erased elements and the number of elements after the
 erased elements.
+*Throws:* Nothing unless an exception is thrown by the assignment
+operator of `T`.
+#### Erasure <a id="deque.erasure">[[deque.erasure]]</a>
 ``` cpp
+template<class T, class Allocator, class U>
+ typename deque<T, Allocator>::size_type
+ erase(deque<T, Allocator>& c, const U& value);
 ```
+*Effects:* Equivalent to:
+``` cpp
+auto it = remove(c.begin(), c.end(), value);
+auto r = distance(it, c.end());
+c.erase(it, c.end());
+return r;
+```
+``` cpp
+template<class T, class Allocator, class Predicate>
+  typename deque<T, Allocator>::size_type
+    erase_if(deque<T, Allocator>& c, Predicate pred);
+```
+*Effects:* Equivalent to:
+``` cpp
+auto it = remove_if(c.begin(), c.end(), pred);
+auto r = distance(it, c.end());
+c.erase(it, c.end());
+return r;
+```

Diff to HTML by rtfpessoa