From Jason Turner

[set]

C++20 → C++23 8.7 KB 87 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpbn2zt_lp/{from.md → to.md} +53 -26
tmp/tmpbn2zt_lp/{from.md → to.md} RENAMED
@@ -1,23 +1,25 @@
1
  ### Class template `set` <a id="set">[[set]]</a>
2
 
3
  #### Overview <a id="set.overview">[[set.overview]]</a>
4
 
5
- A `set` is an associative container that supports unique keys (contains
6
- at most one of each key value) and provides for fast retrieval of the
7
- keys themselves. The `set` class supports bidirectional iterators.
 
8
 
9
- A `set` meets all of the requirements of a container, of a reversible
10
- container [[container.requirements]], of an associative container
11
- [[associative.reqmts]], and of an allocator-aware container (
12
- [[container.alloc.req]]). A `set` also provides most operations
13
- described in  [[associative.reqmts]] for unique keys. This means that a
14
- `set` supports the `a_uniq` operations in  [[associative.reqmts]] but
15
- not the `a_eq` operations. For a `set<Key>` both the `key_type` and
16
- `value_type` are `Key`. Descriptions are provided here only for
17
- operations on `set` that are not described in one of these tables and
18
- for operations where there is additional semantic information.
 
19
 
20
  ``` cpp
21
  namespace std {
22
  template<class Key, class Compare = less<Key>,
23
  class Allocator = allocator<Key>>
@@ -31,12 +33,12 @@ namespace std {
31
  using allocator_type = Allocator;
32
  using pointer = typename allocator_traits<Allocator>::pointer;
33
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
34
  using reference = value_type&;
35
  using const_reference = const value_type&;
36
- using size_type = implementation-defined; // see [container.requirements]
37
- using difference_type = implementation-defined; // see [container.requirements]
38
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
39
  using const_iterator = implementation-defined // type of set::const_iterator; // see [container.requirements]
40
  using reverse_iterator = std::reverse_iterator<iterator>;
41
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
42
  using node_type = unspecified;
@@ -46,20 +48,25 @@ namespace std {
46
  set() : set(Compare()) { }
47
  explicit set(const Compare& comp, const Allocator& = Allocator());
48
  template<class InputIterator>
49
  set(InputIterator first, InputIterator last,
50
  const Compare& comp = Compare(), const Allocator& = Allocator());
 
 
51
  set(const set& x);
52
  set(set&& x);
53
  explicit set(const Allocator&);
54
- set(const set&, const Allocator&);
55
- set(set&&, const Allocator&);
56
  set(initializer_list<value_type>, const Compare& = Compare(),
57
  const Allocator& = Allocator());
58
  template<class InputIterator>
59
  set(InputIterator first, InputIterator last, const Allocator& a)
60
  : set(first, last, Compare(), a) { }
 
 
 
61
  set(initializer_list<value_type> il, const Allocator& a)
62
  : set(il, Compare(), a) { }
63
  ~set();
64
  set& operator=(const set& x);
65
  set& operator=(set&& x)
@@ -96,20 +103,25 @@ namespace std {
96
  pair<iterator,bool> insert(value_type&& x);
97
  iterator insert(const_iterator position, const value_type& x);
98
  iterator insert(const_iterator position, value_type&& x);
99
  template<class InputIterator>
100
  void insert(InputIterator first, InputIterator last);
 
 
101
  void insert(initializer_list<value_type>);
102
 
103
  node_type extract(const_iterator position);
104
  node_type extract(const key_type& x);
 
105
  insert_return_type insert(node_type&& nh);
106
  iterator insert(const_iterator hint, node_type&& nh);
107
 
108
- iterator erase(iterator position);
 
109
  iterator erase(const_iterator position);
110
  size_type erase(const key_type& x);
 
111
  iterator erase(const_iterator first, const_iterator last);
112
  void swap(set&)
113
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
114
  is_nothrow_swappable_v<Compare>);
115
  void clear() noexcept;
@@ -162,38 +174,41 @@ namespace std {
162
  class Allocator = allocator<iter-value-type<InputIterator>>>
163
  set(InputIterator, InputIterator,
164
  Compare = Compare(), Allocator = Allocator())
165
  -> set<iter-value-type<InputIterator>, Compare, Allocator>;
166
 
 
 
 
 
 
167
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
168
  set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
169
  -> set<Key, Compare, Allocator>;
170
 
171
  template<class InputIterator, class Allocator>
172
  set(InputIterator, InputIterator, Allocator)
173
  -> set<iter-value-type<InputIterator>,
174
  less<iter-value-type<InputIterator>>, Allocator>;
175
 
 
 
 
 
176
  template<class Key, class Allocator>
177
  set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>;
178
-
179
- // swap
180
- template<class Key, class Compare, class Allocator>
181
- void swap(set<Key, Compare, Allocator>& x,
182
- set<Key, Compare, Allocator>& y)
183
- noexcept(noexcept(x.swap(y)));
184
  }
185
  ```
186
 
187
  #### Constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
188
 
189
  ``` cpp
190
  explicit set(const Compare& comp, const Allocator& = Allocator());
191
  ```
192
 
193
  *Effects:* Constructs an empty `set` using the specified comparison
194
- objects and allocator.
195
 
196
  *Complexity:* Constant.
197
 
198
  ``` cpp
199
  template<class InputIterator>
@@ -204,11 +219,23 @@ template<class InputIterator>
204
  *Effects:* Constructs an empty `set` using the specified comparison
205
  object and allocator, and inserts elements from the range \[`first`,
206
  `last`).
207
 
208
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
209
- sorted using `comp` and otherwise N log N, where N is `last - first`.
 
 
 
 
 
 
 
 
 
 
 
 
210
 
211
  #### Erasure <a id="set.erasure">[[set.erasure]]</a>
212
 
213
  ``` cpp
214
  template<class Key, class Compare, class Allocator, class Predicate>
 
1
  ### Class template `set` <a id="set">[[set]]</a>
2
 
3
  #### Overview <a id="set.overview">[[set.overview]]</a>
4
 
5
+ A `set` is an associative container that supports unique keys (i.e.,
6
+ contains at most one of each key value) and provides for fast retrieval
7
+ 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>>
 
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]
41
  using const_iterator = implementation-defined // type of set::const_iterator; // see [container.requirements]
42
  using reverse_iterator = std::reverse_iterator<iterator>;
43
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
44
  using node_type = unspecified;
 
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)
 
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;
 
174
  class Allocator = allocator<iter-value-type<InputIterator>>>
175
  set(InputIterator, InputIterator,
176
  Compare = Compare(), Allocator = Allocator())
177
  -> set<iter-value-type<InputIterator>, Compare, Allocator>;
178
 
179
+ template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
180
+ class Allocator = allocator<ranges::range_value_t<R>>>
181
+ set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
182
+ -> set<ranges::range_value_t<R>, Compare, Allocator>;
183
+
184
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
185
  set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
186
  -> set<Key, Compare, Allocator>;
187
 
188
  template<class InputIterator, class Allocator>
189
  set(InputIterator, InputIterator, Allocator)
190
  -> set<iter-value-type<InputIterator>,
191
  less<iter-value-type<InputIterator>>, Allocator>;
192
 
193
+ template<ranges::input_range R, class Allocator>
194
+ set(from_range_t, R&&, Allocator)
195
+ -> set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>;
196
+
197
  template<class Key, class Allocator>
198
  set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>;
 
 
 
 
 
 
199
  }
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>
 
219
  *Effects:* Constructs an empty `set` using the specified comparison
220
  object and allocator, and inserts elements from the range \[`first`,
221
  `last`).
222
 
223
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
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
+
235
+ *Complexity:* Linear in N if `rg` is already sorted with respect to
236
+ `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
237
 
238
  #### Erasure <a id="set.erasure">[[set.erasure]]</a>
239
 
240
  ``` cpp
241
  template<class Key, class Compare, class Allocator, class Predicate>