From Jason Turner

[set]

C++23 → Trunk 16.1 KB 222 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpd02346w9/{from.md → to.md} +124 -89
tmp/tmpd02346w9/{from.md → to.md} RENAMED
@@ -8,19 +8,22 @@ of the keys themselves. The `set` class supports bidirectional
8
  iterators.
9
 
10
  A `set` meets all of the requirements of a container
11
  [[container.reqmts]], of a reversible container
12
  [[container.rev.reqmts]], of an allocator-aware container
13
- [[container.alloc.reqmts]]. and of an associative container
14
  [[associative.reqmts]]. A `set` also provides most operations described
15
  in  [[associative.reqmts]] for unique keys. This means that a `set`
16
  supports the `a_uniq` operations in  [[associative.reqmts]] but not the
17
  `a_eq` operations. For a `set<Key>` both the `key_type` and `value_type`
18
  are `Key`. Descriptions are provided here only for operations on `set`
19
  that are not described in one of these tables and for operations where
20
  there is additional semantic information.
21
 
 
 
 
22
  ``` cpp
23
  namespace std {
24
  template<class Key, class Compare = less<Key>,
25
  class Allocator = allocator<Key>>
26
  class set {
@@ -29,12 +32,12 @@ namespace std {
29
  using key_type = Key;
30
  using key_compare = Compare;
31
  using value_type = Key;
32
  using value_compare = Compare;
33
  using allocator_type = Allocator;
34
- using pointer = typename allocator_traits<Allocator>::pointer;
35
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
36
  using reference = value_type&;
37
  using const_reference = const value_type&;
38
  using size_type = implementation-defined // type of set::size_type; // see [container.requirements]
39
  using difference_type = implementation-defined // type of set::difference_type; // see [container.requirements]
40
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
@@ -43,132 +46,136 @@ namespace std {
43
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
44
  using node_type = unspecified;
45
  using insert_return_type = insert-return-type<iterator, node_type>;
46
 
47
  // [set.cons], construct/copy/destroy
48
- set() : set(Compare()) { }
49
- explicit set(const Compare& comp, const Allocator& = Allocator());
50
  template<class InputIterator>
51
- set(InputIterator first, InputIterator last,
52
  const Compare& comp = Compare(), const Allocator& = Allocator());
53
  template<container-compatible-range<value_type> R>
54
- set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
55
- set(const set& x);
56
- set(set&& x);
57
- explicit set(const Allocator&);
58
- set(const set&, const type_identity_t<Allocator>&);
59
- set(set&&, const type_identity_t<Allocator>&);
60
- set(initializer_list<value_type>, const Compare& = Compare(),
61
- const Allocator& = Allocator());
 
62
  template<class InputIterator>
63
- set(InputIterator first, InputIterator last, const Allocator& a)
64
  : set(first, last, Compare(), a) { }
65
  template<container-compatible-range<value_type> R>
66
- set(from_range_t, R&& rg, const Allocator& a))
67
  : set(from_range, std::forward<R>(rg), Compare(), a) { }
68
- set(initializer_list<value_type> il, const Allocator& a)
69
  : set(il, Compare(), a) { }
70
- ~set();
71
- set& operator=(const set& x);
72
- set& operator=(set&& x)
73
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
74
  is_nothrow_move_assignable_v<Compare>);
75
- set& operator=(initializer_list<value_type>);
76
- allocator_type get_allocator() const noexcept;
77
 
78
  // iterators
79
- iterator begin() noexcept;
80
- const_iterator begin() const noexcept;
81
- iterator end() noexcept;
82
- const_iterator end() const noexcept;
83
 
84
- reverse_iterator rbegin() noexcept;
85
- const_reverse_iterator rbegin() const noexcept;
86
- reverse_iterator rend() noexcept;
87
- const_reverse_iterator rend() const noexcept;
88
 
89
- const_iterator cbegin() const noexcept;
90
- const_iterator cend() const noexcept;
91
- const_reverse_iterator crbegin() const noexcept;
92
- const_reverse_iterator crend() const noexcept;
93
 
94
  // capacity
95
- [[nodiscard]] bool empty() const noexcept;
96
- size_type size() const noexcept;
97
- size_type max_size() const noexcept;
98
 
99
- // modifiers
100
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
101
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
102
- pair<iterator,bool> insert(const value_type& x);
103
- pair<iterator,bool> insert(value_type&& x);
104
- iterator insert(const_iterator position, const value_type& x);
105
- iterator insert(const_iterator position, value_type&& x);
 
 
 
106
  template<class InputIterator>
107
- void insert(InputIterator first, InputIterator last);
108
  template<container-compatible-range<value_type> R>
109
- void insert_range(R&& rg);
110
- void insert(initializer_list<value_type>);
111
 
112
- node_type extract(const_iterator position);
113
- node_type extract(const key_type& x);
114
- template<class K> node_type extract(K&& x);
115
- insert_return_type insert(node_type&& nh);
116
- iterator insert(const_iterator hint, node_type&& nh);
117
 
118
- iterator erase(iterator position)
119
  requires (!same_as<iterator, const_iterator>);
120
- iterator erase(const_iterator position);
121
- size_type erase(const key_type& x);
122
- template<class K> size_type erase(K&& x);
123
- iterator erase(const_iterator first, const_iterator last);
124
- void swap(set&)
125
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
126
  is_nothrow_swappable_v<Compare>);
127
- void clear() noexcept;
128
 
129
  template<class C2>
130
- void merge(set<Key, C2, Allocator>& source);
131
  template<class C2>
132
- void merge(set<Key, C2, Allocator>&& source);
133
  template<class C2>
134
- void merge(multiset<Key, C2, Allocator>& source);
135
  template<class C2>
136
- void merge(multiset<Key, C2, Allocator>&& source);
137
 
138
  // observers
139
- key_compare key_comp() const;
140
- value_compare value_comp() const;
141
 
142
  // set operations
143
- iterator find(const key_type& x);
144
- const_iterator find(const key_type& x) const;
145
- template<class K> iterator find(const K& x);
146
- template<class K> const_iterator find(const K& x) const;
147
 
148
- size_type count(const key_type& x) const;
149
- template<class K> size_type count(const K& x) const;
150
 
151
- bool contains(const key_type& x) const;
152
- template<class K> bool contains(const K& x) const;
153
 
154
- iterator lower_bound(const key_type& x);
155
- const_iterator lower_bound(const key_type& x) const;
156
- template<class K> iterator lower_bound(const K& x);
157
- template<class K> const_iterator lower_bound(const K& x) const;
158
 
159
- iterator upper_bound(const key_type& x);
160
- const_iterator upper_bound(const key_type& x) const;
161
- template<class K> iterator upper_bound(const K& x);
162
- template<class K> const_iterator upper_bound(const K& x) const;
163
 
164
- pair<iterator, iterator> equal_range(const key_type& x);
165
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
166
  template<class K>
167
- pair<iterator, iterator> equal_range(const K& x);
168
  template<class K>
169
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
170
  };
171
 
172
  template<class InputIterator,
173
  class Compare = less<iter-value-type<InputIterator>>,
174
  class Allocator = allocator<iter-value-type<InputIterator>>>
@@ -200,21 +207,21 @@ namespace std {
200
  ```
201
 
202
  #### Constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
203
 
204
  ``` cpp
205
- explicit set(const Compare& comp, const Allocator& = Allocator());
206
  ```
207
 
208
  *Effects:* Constructs an empty `set` using the specified comparison
209
  object and allocator.
210
 
211
  *Complexity:* Constant.
212
 
213
  ``` cpp
214
  template<class InputIterator>
215
- set(InputIterator first, InputIterator last,
216
  const Compare& comp = Compare(), const Allocator& = Allocator());
217
  ```
218
 
219
  *Effects:* Constructs an empty `set` using the specified comparison
220
  object and allocator, and inserts elements from the range \[`first`,
@@ -224,11 +231,12 @@ object and allocator, and inserts elements from the range \[`first`,
224
  sorted with respect to `comp` and otherwise N log N, where N is
225
  `last - first`.
226
 
227
  ``` cpp
228
  template<container-compatible-range<value_type> R>
229
- set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
 
230
  ```
231
 
232
  *Effects:* Constructs an empty `set` using the specified comparison
233
  object and allocator, and inserts elements from the range `rg`.
234
 
@@ -237,11 +245,11 @@ object and allocator, and inserts elements from the range `rg`.
237
 
238
  #### Erasure <a id="set.erasure">[[set.erasure]]</a>
239
 
240
  ``` cpp
241
  template<class Key, class Compare, class Allocator, class Predicate>
242
- typename set<Key, Compare, Allocator>::size_type
243
  erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
244
  ```
245
 
246
  *Effects:* Equivalent to:
247
 
@@ -255,5 +263,32 @@ for (auto i = c.begin(), last = c.end(); i != last; ) {
255
  }
256
  }
257
  return original_size - c.size();
258
  ```
259
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
8
  iterators.
9
 
10
  A `set` meets all of the requirements of a container
11
  [[container.reqmts]], of a reversible container
12
  [[container.rev.reqmts]], of an allocator-aware container
13
+ [[container.alloc.reqmts]], and of an associative container
14
  [[associative.reqmts]]. A `set` also provides most operations described
15
  in  [[associative.reqmts]] for unique keys. This means that a `set`
16
  supports the `a_uniq` operations in  [[associative.reqmts]] but not the
17
  `a_eq` operations. For a `set<Key>` both the `key_type` and `value_type`
18
  are `Key`. Descriptions are provided here only for operations on `set`
19
  that are not described in one of these tables and for operations where
20
  there is additional semantic information.
21
 
22
+ The types `iterator` and `const_iterator` meet the constexpr iterator
23
+ requirements [[iterator.requirements.general]].
24
+
25
  ``` cpp
26
  namespace std {
27
  template<class Key, class Compare = less<Key>,
28
  class Allocator = allocator<Key>>
29
  class set {
 
32
  using key_type = Key;
33
  using key_compare = Compare;
34
  using value_type = Key;
35
  using value_compare = Compare;
36
  using allocator_type = Allocator;
37
+ using pointer = allocator_traits<Allocator>::pointer;
38
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
39
  using reference = value_type&;
40
  using const_reference = const value_type&;
41
  using size_type = implementation-defined // type of set::size_type; // see [container.requirements]
42
  using difference_type = implementation-defined // type of set::difference_type; // see [container.requirements]
43
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
 
46
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
47
  using node_type = unspecified;
48
  using insert_return_type = insert-return-type<iterator, node_type>;
49
 
50
  // [set.cons], construct/copy/destroy
51
+ constexpr set() : set(Compare()) { }
52
+ constexpr explicit set(const Compare& comp, const Allocator& = Allocator());
53
  template<class InputIterator>
54
+ constexpr set(InputIterator first, InputIterator last,
55
  const Compare& comp = Compare(), const Allocator& = Allocator());
56
  template<container-compatible-range<value_type> R>
57
+ constexpr set(from_range_t, R&& rg,
58
+ const Compare& comp = Compare(), const Allocator& = Allocator());
59
+ constexpr set(const set& x);
60
+ constexpr set(set&& x);
61
+ constexpr explicit set(const Allocator&);
62
+ constexpr set(const set&, const type_identity_t<Allocator>&);
63
+ constexpr set(set&&, const type_identity_t<Allocator>&);
64
+ constexpr set(initializer_list<value_type>,
65
+ const Compare& = Compare(), const Allocator& = Allocator());
66
  template<class InputIterator>
67
+ constexpr set(InputIterator first, InputIterator last, const Allocator& a)
68
  : set(first, last, Compare(), a) { }
69
  template<container-compatible-range<value_type> R>
70
+ constexpr set(from_range_t, R&& rg, const Allocator& a)
71
  : set(from_range, std::forward<R>(rg), Compare(), a) { }
72
+ constexpr set(initializer_list<value_type> il, const Allocator& a)
73
  : set(il, Compare(), a) { }
74
+ constexpr ~set();
75
+ constexpr set& operator=(const set& x);
76
+ constexpr set& operator=(set&& x)
77
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
78
  is_nothrow_move_assignable_v<Compare>);
79
+ constexpr set& operator=(initializer_list<value_type>);
80
+ constexpr allocator_type get_allocator() const noexcept;
81
 
82
  // iterators
83
+ constexpr iterator begin() noexcept;
84
+ constexpr const_iterator begin() const noexcept;
85
+ constexpr iterator end() noexcept;
86
+ constexpr const_iterator end() const noexcept;
87
 
88
+ constexpr reverse_iterator rbegin() noexcept;
89
+ constexpr const_reverse_iterator rbegin() const noexcept;
90
+ constexpr reverse_iterator rend() noexcept;
91
+ constexpr const_reverse_iterator rend() const noexcept;
92
 
93
+ constexpr const_iterator cbegin() const noexcept;
94
+ constexpr const_iterator cend() const noexcept;
95
+ constexpr const_reverse_iterator crbegin() const noexcept;
96
+ constexpr const_reverse_iterator crend() const noexcept;
97
 
98
  // capacity
99
+ constexpr bool empty() const noexcept;
100
+ constexpr size_type size() const noexcept;
101
+ constexpr size_type max_size() const noexcept;
102
 
103
+ // [set.modifiers], modifiers
104
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
105
+ template<class... Args>
106
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
107
+ constexpr pair<iterator,bool> insert(const value_type& x);
108
+ constexpr pair<iterator,bool> insert(value_type&& x);
109
+ template<class K> constexpr pair<iterator, bool> insert(K&& x);
110
+ constexpr iterator insert(const_iterator position, const value_type& x);
111
+ constexpr iterator insert(const_iterator position, value_type&& x);
112
+ template<class K> constexpr iterator insert(const_iterator position, K&& x);
113
  template<class InputIterator>
114
+ constexpr void insert(InputIterator first, InputIterator last);
115
  template<container-compatible-range<value_type> R>
116
+ constexpr void insert_range(R&& rg);
117
+ constexpr void insert(initializer_list<value_type>);
118
 
119
+ constexpr node_type extract(const_iterator position);
120
+ constexpr node_type extract(const key_type& x);
121
+ template<class K> constexpr node_type extract(K&& x);
122
+ constexpr insert_return_type insert(node_type&& nh);
123
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
124
 
125
+ constexpr iterator erase(iterator position)
126
  requires (!same_as<iterator, const_iterator>);
127
+ constexpr iterator erase(const_iterator position);
128
+ constexpr size_type erase(const key_type& x);
129
+ template<class K> constexpr size_type erase(K&& x);
130
+ constexpr iterator erase(const_iterator first, const_iterator last);
131
+ constexpr void swap(set&)
132
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
133
  is_nothrow_swappable_v<Compare>);
134
+ constexpr void clear() noexcept;
135
 
136
  template<class C2>
137
+ constexpr void merge(set<Key, C2, Allocator>& source);
138
  template<class C2>
139
+ constexpr void merge(set<Key, C2, Allocator>&& source);
140
  template<class C2>
141
+ constexpr void merge(multiset<Key, C2, Allocator>& source);
142
  template<class C2>
143
+ constexpr void merge(multiset<Key, C2, Allocator>&& source);
144
 
145
  // observers
146
+ constexpr key_compare key_comp() const;
147
+ constexpr value_compare value_comp() const;
148
 
149
  // set operations
150
+ constexpr iterator find(const key_type& x);
151
+ constexpr const_iterator find(const key_type& x) const;
152
+ template<class K> constexpr iterator find(const K& x);
153
+ template<class K> constexpr const_iterator find(const K& x) const;
154
 
155
+ constexpr size_type count(const key_type& x) const;
156
+ template<class K> constexpr size_type count(const K& x) const;
157
 
158
+ constexpr bool contains(const key_type& x) const;
159
+ template<class K> constexpr bool contains(const K& x) const;
160
 
161
+ constexpr iterator lower_bound(const key_type& x);
162
+ constexpr const_iterator lower_bound(const key_type& x) const;
163
+ template<class K> constexpr iterator lower_bound(const K& x);
164
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
165
 
166
+ constexpr iterator upper_bound(const key_type& x);
167
+ constexpr const_iterator upper_bound(const key_type& x) const;
168
+ template<class K> constexpr iterator upper_bound(const K& x);
169
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
170
 
171
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
172
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
173
  template<class K>
174
+ constexpr pair<iterator, iterator> equal_range(const K& x);
175
  template<class K>
176
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
177
  };
178
 
179
  template<class InputIterator,
180
  class Compare = less<iter-value-type<InputIterator>>,
181
  class Allocator = allocator<iter-value-type<InputIterator>>>
 
207
  ```
208
 
209
  #### Constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
210
 
211
  ``` cpp
212
+ constexpr explicit set(const Compare& comp, const Allocator& = Allocator());
213
  ```
214
 
215
  *Effects:* Constructs an empty `set` using the specified comparison
216
  object and allocator.
217
 
218
  *Complexity:* Constant.
219
 
220
  ``` cpp
221
  template<class InputIterator>
222
+ constexpr set(InputIterator first, InputIterator last,
223
  const Compare& comp = Compare(), const Allocator& = Allocator());
224
  ```
225
 
226
  *Effects:* Constructs an empty `set` using the specified comparison
227
  object and allocator, and inserts elements from the range \[`first`,
 
231
  sorted with respect to `comp` and otherwise N log N, where N is
232
  `last - first`.
233
 
234
  ``` cpp
235
  template<container-compatible-range<value_type> R>
236
+ constexpr set(from_range_t, R&& rg, const Compare& comp = Compare(),
237
+ const Allocator& = Allocator());
238
  ```
239
 
240
  *Effects:* Constructs an empty `set` using the specified comparison
241
  object and allocator, and inserts elements from the range `rg`.
242
 
 
245
 
246
  #### Erasure <a id="set.erasure">[[set.erasure]]</a>
247
 
248
  ``` cpp
249
  template<class Key, class Compare, class Allocator, class Predicate>
250
+ constexpr typename set<Key, Compare, Allocator>::size_type
251
  erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
252
  ```
253
 
254
  *Effects:* Equivalent to:
255
 
 
263
  }
264
  }
265
  return original_size - c.size();
266
  ```
267
 
268
+ #### Modifiers <a id="set.modifiers">[[set.modifiers]]</a>
269
+
270
+ ``` cpp
271
+ template<class K> constexpr pair<iterator, bool> insert(K&& x);
272
+ template<class K> constexpr iterator insert(const_iterator hint, K&& x);
273
+ ```
274
+
275
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
276
+ denotes a type. For the second overload,
277
+ `is_convertible_v<K&&, const_iterator>` and
278
+ `is_convertible_v<K&&, iterator>` are both `false`.
279
+
280
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `set`
281
+ from `std::forward<K>(x)`.
282
+
283
+ *Effects:* If the set already contains an element that is equivalent to
284
+ `x`, there is no effect. Otherwise, let `r` be `equal_range(x)`.
285
+ Constructs an object `u` of type `value_type` with `std::forward<K>(x)`.
286
+ If `equal_range(u) == r` is `false`, the behavior is undefined. Inserts
287
+ `u` into `*this`.
288
+
289
+ *Returns:* For the first overload, the `bool` component of the returned
290
+ pair is `true` if and only if the insertion took place. The returned
291
+ iterator points to the set element that is equivalent to `x`.
292
+
293
+ *Complexity:* Logarithmic.
294
+