From Jason Turner

[forward.list.ops]

C++20 → C++23 6.8 KB 173 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp0ez9bcnc/{from.md → to.md} +170 -0
tmp/tmp0ez9bcnc/{from.md → to.md} RENAMED
@@ -0,0 +1,170 @@
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
+ #### Operations <a id="forward.list.ops">[[forward.list.ops]]</a>
2
+
3
+ In this subclause, arguments for a template parameter named `Predicate`
4
+ or `BinaryPredicate` shall meet the corresponding requirements in
5
+ [[algorithms.requirements]]. The semantics of `i + n`, where `i` is an
6
+ iterator into the list and `n` is an integer, are the same as those of
7
+ `next(i, n)`. The expression `i - n`, where `i` is an iterator into the
8
+ list and `n` is an integer, means an iterator `j` such that `j + n == i`
9
+ is `true`. For `merge` and `sort`, the definitions and requirements in
10
+ [[alg.sorting]] apply.
11
+
12
+ ``` cpp
13
+ void splice_after(const_iterator position, forward_list& x);
14
+ void splice_after(const_iterator position, forward_list&& x);
15
+ ```
16
+
17
+ *Preconditions:* `position` is `before_begin()` or is a dereferenceable
18
+ iterator in the range \[`begin()`, `end()`).
19
+ `get_allocator() == x.get_allocator()` is `true`. `addressof(x) != this`
20
+ is `true`.
21
+
22
+ *Effects:* Inserts the contents of `x` after `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
26
+ now behave as iterators into `*this`, not into `x`.
27
+
28
+ *Throws:* Nothing.
29
+
30
+ *Complexity:* 𝑂(`distance(x.begin(), x.end())`)
31
+
32
+ ``` cpp
33
+ void splice_after(const_iterator position, forward_list& x, const_iterator i);
34
+ void splice_after(const_iterator position, forward_list&& x, const_iterator i);
35
+ ```
36
+
37
+ *Preconditions:* `position` is `before_begin()` or is a dereferenceable
38
+ iterator in the range \[`begin()`, `end()`). The iterator following `i`
39
+ is a dereferenceable iterator in `x`.
40
+ `get_allocator() == x.get_allocator()` is `true`.
41
+
42
+ *Effects:* Inserts the element following `i` into `*this`, following
43
+ `position`, and removes it from `x`. The result is unchanged if
44
+ `position == i` or `position == ++i`. Pointers and references to `*++i`
45
+ continue to refer to the same element but as a member of `*this`.
46
+ Iterators to `*++i` continue to refer to the same element, but now
47
+ behave as iterators into `*this`, not into `x`.
48
+
49
+ *Throws:* Nothing.
50
+
51
+ *Complexity:* 𝑂(1)
52
+
53
+ ``` cpp
54
+ void splice_after(const_iterator position, forward_list& x,
55
+ const_iterator first, const_iterator last);
56
+ void splice_after(const_iterator position, forward_list&& x,
57
+ const_iterator first, const_iterator last);
58
+ ```
59
+
60
+ *Preconditions:* `position` is `before_begin()` or is a dereferenceable
61
+ iterator in the range \[`begin()`, `end()`). (`first`, `last`) is a
62
+ valid range in `x`, and all iterators in the range (`first`, `last`) are
63
+ dereferenceable. `position` is not an iterator in the range (`first`,
64
+ `last`). `get_allocator() == x.get_allocator()` is `true`.
65
+
66
+ *Effects:* Inserts elements in the range (`first`, `last`) after
67
+ `position` and removes the elements from `x`. Pointers and references to
68
+ the moved elements of `x` now refer to those same elements but as
69
+ members of `*this`. Iterators referring to the moved elements will
70
+ continue to refer to their elements, but they now behave as iterators
71
+ into `*this`, not into `x`.
72
+
73
+ *Complexity:* 𝑂(`distance(first, last)`)
74
+
75
+ ``` cpp
76
+ size_type remove(const T& value);
77
+ template<class Predicate> size_type remove_if(Predicate pred);
78
+ ```
79
+
80
+ *Effects:* Erases all the elements in the list referred to by a list
81
+ iterator `i` for which the following conditions hold: `*i == value` (for
82
+ `remove()`), `pred(*i)` is `true` (for `remove_if()`). Invalidates only
83
+ the iterators and references to the erased elements.
84
+
85
+ *Returns:* The number of elements erased.
86
+
87
+ *Throws:* Nothing unless an exception is thrown by the equality
88
+ comparison or the predicate.
89
+
90
+ *Complexity:* Exactly `distance(begin(), end())` applications of the
91
+ corresponding predicate.
92
+
93
+ *Remarks:* Stable [[algorithm.stable]].
94
+
95
+ ``` cpp
96
+ size_type unique();
97
+ template<class BinaryPredicate> size_type unique(BinaryPredicate binary_pred);
98
+ ```
99
+
100
+ Let `binary_pred` be `equal_to<>{}` for the first overload.
101
+
102
+ *Preconditions:* `binary_pred` is an equivalence relation.
103
+
104
+ *Effects:* Erases all but the first element from every consecutive group
105
+ of equivalent elements. That is, for a nonempty list, erases all
106
+ elements referred to by the iterator `i` in the range \[`begin() + 1`,
107
+ `end()`) for which `binary_pred(*i, *(i - 1))` is `true`. Invalidates
108
+ only the iterators and references to the erased elements.
109
+
110
+ *Returns:* The number of elements erased.
111
+
112
+ *Throws:* Nothing unless an exception is thrown by the predicate.
113
+
114
+ *Complexity:* If `empty()` is `false`, exactly
115
+ `distance(begin(), end()) - 1` applications of the corresponding
116
+ predicate, otherwise no applications of the predicate.
117
+
118
+ ``` cpp
119
+ void merge(forward_list& x);
120
+ void merge(forward_list&& x);
121
+ template<class Compare> void merge(forward_list& x, Compare comp);
122
+ template<class Compare> void merge(forward_list&& x, Compare comp);
123
+ ```
124
+
125
+ Let `comp` be `less<>` for the first two overloads.
126
+
127
+ *Preconditions:* `*this` and `x` are both sorted with respect to the
128
+ comparator `comp`, and `get_allocator() == x.get_allocator()` is `true`.
129
+
130
+ *Effects:* If `addressof(x) == this`, there are no effects. Otherwise,
131
+ merges the two sorted ranges \[`begin()`, `end()`) and \[`x.begin()`,
132
+ `x.end()`). The result is a range that is sorted with respect to the
133
+ comparator `comp`. Pointers and references to the moved elements of `x`
134
+ now refer to those same elements but as members of `*this`. Iterators
135
+ referring to the moved elements will continue to refer to their
136
+ elements, but they now behave as iterators into `*this`, not into `x`.
137
+
138
+ *Complexity:* At most
139
+ `distance(begin(), end()) + distance(x.begin(), x.end()) - 1`
140
+ comparisons if `addressof(x) != this`; otherwise, no comparisons are
141
+ performed.
142
+
143
+ *Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, `x`
144
+ is empty after the merge. No elements are copied by this operation. If
145
+ an exception is thrown other than by a comparison, there are no effects.
146
+
147
+ ``` cpp
148
+ void sort();
149
+ template<class Compare> void sort(Compare comp);
150
+ ```
151
+
152
+ *Effects:* Sorts the list according to the `operator<` or the `comp`
153
+ function object. If an exception is thrown, the order of the elements in
154
+ `*this` is unspecified. Does not affect the validity of iterators and
155
+ references.
156
+
157
+ *Complexity:* Approximately N log N comparisons, where N is
158
+ `distance(begin(), end())`.
159
+
160
+ *Remarks:* Stable [[algorithm.stable]].
161
+
162
+ ``` cpp
163
+ void reverse() noexcept;
164
+ ```
165
+
166
+ *Effects:* Reverses the order of the elements in the list. Does not
167
+ affect the validity of iterators and references.
168
+
169
+ *Complexity:* Linear time.
170
+