From Jason Turner

[list.ops]

C++17 → C++20 8.0 KB 84 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp701gph5q/{from.md → to.md} +41 -35
tmp/tmp701gph5q/{from.md → to.md} RENAMED
@@ -1,9 +1,13 @@
1
- #### `list` operations <a id="list.ops">[[list.ops]]</a>
2
 
3
  Since lists allow fast insertion and erasing from the middle of a list,
4
- certain operations are provided specifically for them.[^3]
 
 
 
 
5
 
6
  `list` provides three splice operations that destructively move elements
7
  from one list to another. The behavior of splice operations is undefined
8
  if `get_allocator() !=
9
  x.get_allocator()`.
@@ -11,11 +15,11 @@ x.get_allocator()`.
11
  ``` cpp
12
  void splice(const_iterator position, list& x);
13
  void splice(const_iterator position, list&& x);
14
  ```
15
 
16
- *Requires:* `&x != this`.
17
 
18
  *Effects:* Inserts the contents of `x` before `position` and `x` becomes
19
  empty. Pointers and references to the moved elements of `x` now refer to
20
  those same elements but as members of `*this`. Iterators referring to
21
  the moved elements will continue to refer to their elements, but they
@@ -28,11 +32,11 @@ now behave as iterators into `*this`, not into `x`.
28
  ``` cpp
29
  void splice(const_iterator position, list& x, const_iterator i);
30
  void splice(const_iterator position, list&& x, const_iterator i);
31
  ```
32
 
33
- *Requires:* `i` is a valid dereferenceable iterator of `x`.
34
 
35
  *Effects:* Inserts an element pointed to by `i` from list `x` before
36
  `position` and removes the element from `x`. The result is unchanged if
37
  `position == i` or `position == ++i`. Pointers and references to `*i`
38
  continue to refer to this same element but as a member of `*this`.
@@ -48,55 +52,59 @@ void splice(const_iterator position, list& x, const_iterator first,
48
  const_iterator last);
49
  void splice(const_iterator position, list&& x, const_iterator first,
50
  const_iterator last);
51
  ```
52
 
53
- *Requires:* `[first, last)` is a valid range in `x`. The program has
54
- undefined behavior if `position` is an iterator in the range \[`first`,
55
- `last`).
56
 
57
  *Effects:* Inserts elements in the range \[`first`, `last`) before
58
  `position` and removes the elements from `x`. Pointers and references to
59
  the moved elements of `x` now refer to those same elements but as
60
  members of `*this`. Iterators referring to the moved elements will
61
  continue to refer to their elements, but they now behave as iterators
62
  into `*this`, not into `x`.
63
 
64
  *Throws:* Nothing.
65
 
66
- *Complexity:* Constant time if `&x == this`; otherwise, linear time.
 
67
 
68
  ``` cpp
69
- void remove(const T& value);
70
- template <class Predicate> void remove_if(Predicate pred);
71
  ```
72
 
73
- *Effects:* Erases all the elements in the list referred by a list
74
- iterator `i` for which the following conditions hold:
75
- `*i == value, pred(*i) != false`. Invalidates only the iterators and
76
- references to the erased elements.
 
 
77
 
78
  *Throws:* Nothing unless an exception is thrown by `*i == value` or
79
  `pred(*i) != false`.
80
 
81
- *Remarks:* Stable ([[algorithm.stable]]).
82
 
83
  *Complexity:* Exactly `size()` applications of the corresponding
84
  predicate.
85
 
86
  ``` cpp
87
- void unique();
88
- template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
89
  ```
90
 
91
  *Effects:* Erases all but the first element from every consecutive group
92
  of equal elements referred to by the iterator `i` in the range
93
  \[`first + 1`, `last`) for which `*i == *(i-1)` (for the version of
94
  `unique` with no arguments) or `pred(*i, *(i - 1))` (for the version of
95
  `unique` with a predicate argument) holds. Invalidates only the
96
  iterators and references to the erased elements.
97
 
 
 
98
  *Throws:* Nothing unless an exception is thrown by `*i == *(i-1)` or
99
  `pred(*i, *(i - 1))`
100
 
101
  *Complexity:* If the range `[first, last)` is not empty, exactly
102
  `(last - first) - 1` applications of the corresponding predicate,
@@ -107,33 +115,34 @@ void merge(list& x);
107
  void merge(list&& x);
108
  template<class Compare> void merge(list& x, Compare comp);
109
  template<class Compare> void merge(list&& x, Compare comp);
110
  ```
111
 
112
- *Requires:* `comp` shall define a strict weak
113
- ordering ([[alg.sorting]]), and both the list and the argument list
114
- shall be sorted according to this ordering.
 
115
 
116
- *Effects:* If `(&x == this)` does nothing; otherwise, merges the two
117
- sorted ranges `[begin(), end())` and `[x.begin(), x.end())`. The result
118
- is a range in which the elements will be sorted in non-decreasing order
119
- according to the ordering defined by `comp`; that is, for every iterator
120
- `i`, in the range other than the first, the condition
121
  `comp(*i, *(i - 1))` will be `false`. Pointers and references to the
122
  moved elements of `x` now refer to those same elements but as members of
123
  `*this`. Iterators referring to the moved elements will continue to
124
  refer to their elements, but they now behave as iterators into `*this`,
125
  not into `x`.
126
 
127
- *Remarks:* Stable ([[algorithm.stable]]). If `(&x != this)` the range
128
- `[x.begin(), x.end())` is empty after the merge. No elements are copied
129
- by this operation. The behavior is undefined if
130
- `get_allocator() != x.get_allocator()`.
131
 
132
  *Complexity:* At most `size() + x.size() - 1` applications of `comp` if
133
- `(&x != this)`; otherwise, no applications of `comp` are performed. If
134
- an exception is thrown other than by a comparison there are no effects.
 
135
 
136
  ``` cpp
137
  void reverse() noexcept;
138
  ```
139
 
@@ -145,17 +154,14 @@ affect the validity of iterators and references.
145
  ``` cpp
146
  void sort();
147
  template<class Compare> void sort(Compare comp);
148
  ```
149
 
150
- *Requires:* `operator<` (for the first version) or `comp` (for the
151
- second version) shall define a strict weak ordering ([[alg.sorting]]).
152
-
153
  *Effects:* Sorts the list according to the `operator<` or a `Compare`
154
  function object. If an exception is thrown, the order of the elements in
155
  `*this` is unspecified. Does not affect the validity of iterators and
156
  references.
157
 
158
- *Remarks:* Stable ([[algorithm.stable]]).
159
 
160
  *Complexity:* Approximately N log N comparisons, where `N == size()`.
161
 
 
1
+ #### Operations <a id="list.ops">[[list.ops]]</a>
2
 
3
  Since lists allow fast insertion and erasing from the middle of a list,
4
+ certain operations are provided specifically for them.[^3] In this
5
+ subclause, arguments for a template parameter named `Predicate` or
6
+ `BinaryPredicate` shall meet the corresponding requirements in
7
+ [[algorithms.requirements]]. For `merge` and `sort`, the definitions and
8
+ requirements in [[alg.sorting]] apply.
9
 
10
  `list` provides three splice operations that destructively move elements
11
  from one list to another. The behavior of splice operations is undefined
12
  if `get_allocator() !=
13
  x.get_allocator()`.
 
15
  ``` cpp
16
  void splice(const_iterator position, list& x);
17
  void splice(const_iterator position, list&& x);
18
  ```
19
 
20
+ *Preconditions:* `addressof(x) != this` is `true`.
21
 
22
  *Effects:* Inserts the contents of `x` before `position` and `x` becomes
23
  empty. Pointers and references to the moved elements of `x` now refer to
24
  those same elements but as members of `*this`. Iterators referring to
25
  the moved elements will continue to refer to their elements, but they
 
32
  ``` cpp
33
  void splice(const_iterator position, list& x, const_iterator i);
34
  void splice(const_iterator position, list&& x, const_iterator i);
35
  ```
36
 
37
+ *Preconditions:* `i` is a valid dereferenceable iterator of `x`.
38
 
39
  *Effects:* Inserts an element pointed to by `i` from list `x` before
40
  `position` and removes the element from `x`. The result is unchanged if
41
  `position == i` or `position == ++i`. Pointers and references to `*i`
42
  continue to refer to this same element but as a member of `*this`.
 
52
  const_iterator last);
53
  void splice(const_iterator position, list&& x, const_iterator first,
54
  const_iterator last);
55
  ```
56
 
57
+ *Preconditions:* `[first, last)` is a valid range in `x`. `position` is
58
+ not an iterator in the range \[`first`, `last`).
 
59
 
60
  *Effects:* Inserts elements in the range \[`first`, `last`) before
61
  `position` and removes the elements from `x`. Pointers and references to
62
  the moved elements of `x` now refer to those same elements but as
63
  members of `*this`. Iterators referring to the moved elements will
64
  continue to refer to their elements, but they now behave as iterators
65
  into `*this`, not into `x`.
66
 
67
  *Throws:* Nothing.
68
 
69
+ *Complexity:* Constant time if `addressof(x) == this`; otherwise, linear
70
+ time.
71
 
72
  ``` cpp
73
+ size_type remove(const T& value);
74
+ template<class Predicate> size_type remove_if(Predicate pred);
75
  ```
76
 
77
+ *Effects:* Erases all the elements in the list referred to by a list
78
+ iterator `i` for which the following conditions hold: `*i == value`,
79
+ `pred(*i) != false`. Invalidates only the iterators and references to
80
+ the erased elements.
81
+
82
+ *Returns:* The number of elements erased.
83
 
84
  *Throws:* Nothing unless an exception is thrown by `*i == value` or
85
  `pred(*i) != false`.
86
 
87
+ *Remarks:* Stable [[algorithm.stable]].
88
 
89
  *Complexity:* Exactly `size()` applications of the corresponding
90
  predicate.
91
 
92
  ``` cpp
93
+ size_type unique();
94
+ template<class BinaryPredicate> size_type unique(BinaryPredicate binary_pred);
95
  ```
96
 
97
  *Effects:* Erases all but the first element from every consecutive group
98
  of equal elements referred to by the iterator `i` in the range
99
  \[`first + 1`, `last`) for which `*i == *(i-1)` (for the version of
100
  `unique` with no arguments) or `pred(*i, *(i - 1))` (for the version of
101
  `unique` with a predicate argument) holds. Invalidates only the
102
  iterators and references to the erased elements.
103
 
104
+ *Returns:* The number of elements erased.
105
+
106
  *Throws:* Nothing unless an exception is thrown by `*i == *(i-1)` or
107
  `pred(*i, *(i - 1))`
108
 
109
  *Complexity:* If the range `[first, last)` is not empty, exactly
110
  `(last - first) - 1` applications of the corresponding predicate,
 
115
  void merge(list&& x);
116
  template<class Compare> void merge(list& x, Compare comp);
117
  template<class Compare> void merge(list&& x, Compare comp);
118
  ```
119
 
120
+ *Preconditions:* Both the list and the argument list shall be sorted
121
+ with respect to the comparator `operator<` (for the first two overloads)
122
+ or `comp` (for the last two overloads), and
123
+ `get_allocator() == x.get_allocator()` is `true`.
124
 
125
+ *Effects:* If `addressof(x) == this`, does nothing; otherwise, merges
126
+ the two sorted ranges `[begin(), end())` and `[x.begin(), x.end())`. The
127
+ result is a range in which the elements will be sorted in non-decreasing
128
+ order according to the ordering defined by `comp`; that is, for every
129
+ iterator `i`, in the range other than the first, the condition
130
  `comp(*i, *(i - 1))` will be `false`. Pointers and references to the
131
  moved elements of `x` now refer to those same elements but as members of
132
  `*this`. Iterators referring to the moved elements will continue to
133
  refer to their elements, but they now behave as iterators into `*this`,
134
  not into `x`.
135
 
136
+ *Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, the
137
+ range `[x.begin(), x.end())` is empty after the merge. No elements are
138
+ copied by this operation.
 
139
 
140
  *Complexity:* At most `size() + x.size() - 1` applications of `comp` if
141
+ `addressof(x) != this`; otherwise, no applications of `comp` are
142
+ performed. If an exception is thrown other than by a comparison there
143
+ are no effects.
144
 
145
  ``` cpp
146
  void reverse() noexcept;
147
  ```
148
 
 
154
  ``` cpp
155
  void sort();
156
  template<class Compare> void sort(Compare comp);
157
  ```
158
 
 
 
 
159
  *Effects:* Sorts the list according to the `operator<` or a `Compare`
160
  function object. If an exception is thrown, the order of the elements in
161
  `*this` is unspecified. Does not affect the validity of iterators and
162
  references.
163
 
164
+ *Remarks:* Stable [[algorithm.stable]].
165
 
166
  *Complexity:* Approximately N log N comparisons, where `N == size()`.
167