From Jason Turner

[unord.set]

C++17 → C++20 11.4 KB 121 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpg15_nw3x/{from.md → to.md} +65 -48
tmp/tmpg15_nw3x/{from.md → to.md} RENAMED
@@ -1,37 +1,37 @@
1
  ### Class template `unordered_set` <a id="unord.set">[[unord.set]]</a>
2
 
3
- #### Class template `unordered_set` overview <a id="unord.set.overview">[[unord.set.overview]]</a>
4
 
5
  An `unordered_set` is an unordered associative container that supports
6
  unique keys (an `unordered_set` contains at most one of each key value)
7
  and in which the elements’ keys are the elements themselves. The
8
  `unordered_set` class supports forward iterators.
9
 
10
- An `unordered_set` satisfies all of the requirements of a container, of
11
- an unordered associative container, and of an allocator-aware container
12
- (Table  [[tab:containers.allocatoraware]]). It provides the operations
13
- described in the preceding requirements table for unique keys; that is,
14
- an `unordered_set` supports the `a_uniq` operations in that table, not
15
- the `a_eq` operations. For an `unordered_set<Key>` the `key type` and
16
- the value type are both `Key`. The `iterator` and `const_iterator` types
17
- are both constant iterator types. It is unspecified whether they are the
18
  same type.
19
 
20
- This section only describes operations on `unordered_set` that are not
21
- described in one of the requirement tables, or for which there is
22
- additional semantic information.
23
 
24
  ``` cpp
25
  namespace std {
26
  template<class Key,
27
  class Hash = hash<Key>,
28
  class Pred = equal_to<Key>,
29
  class Allocator = allocator<Key>>
30
  class unordered_set {
31
  public:
32
- // types:
33
  using key_type = Key;
34
  using value_type = Key;
35
  using hasher = Hash;
36
  using key_equal = Pred;
37
  using allocator_type = Allocator;
@@ -45,11 +45,11 @@ namespace std {
45
  using iterator = implementation-defined // type of unordered_set::iterator; // see [container.requirements]
46
  using const_iterator = implementation-defined // type of unordered_set::const_iterator; // see [container.requirements]
47
  using local_iterator = implementation-defined // type of unordered_set::local_iterator; // see [container.requirements]
48
  using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
49
  using node_type = unspecified;
50
- using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
51
 
52
  // [unord.set.cnstr], construct/copy/destroy
53
  unordered_set();
54
  explicit unordered_set(size_type n,
55
  const hasher& hf = hasher(),
@@ -94,24 +94,24 @@ namespace std {
94
  is_nothrow_move_assignable_v<Hash> &&
95
  is_nothrow_move_assignable_v<Pred>);
96
  unordered_set& operator=(initializer_list<value_type>);
97
  allocator_type get_allocator() const noexcept;
98
 
99
- // iterators:
100
  iterator begin() noexcept;
101
  const_iterator begin() const noexcept;
102
  iterator end() noexcept;
103
  const_iterator end() const noexcept;
104
  const_iterator cbegin() const noexcept;
105
  const_iterator cend() const noexcept;
106
 
107
- // capacity:
108
- bool empty() const noexcept;
109
  size_type size() const noexcept;
110
  size_type max_size() const noexcept;
111
 
112
- // modifiers:
113
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
114
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
115
  pair<iterator, bool> insert(const value_type& obj);
116
  pair<iterator, bool> insert(value_type&& obj);
117
  iterator insert(const_iterator hint, const value_type& obj);
@@ -141,22 +141,35 @@ namespace std {
141
  template<class H2, class P2>
142
  void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
143
  template<class H2, class P2>
144
  void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
145
 
146
- // observers:
147
  hasher hash_function() const;
148
  key_equal key_eq() const;
149
 
150
- // set operations:
151
  iterator find(const key_type& k);
152
  const_iterator find(const key_type& k) const;
 
 
 
 
153
  size_type count(const key_type& k) const;
 
 
 
 
 
154
  pair<iterator, iterator> equal_range(const key_type& k);
155
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
 
 
 
156
 
157
- // bucket interface:
158
  size_type bucket_count() const noexcept;
159
  size_type max_bucket_count() const noexcept;
160
  size_type bucket_size(size_type n) const;
161
  size_type bucket(const key_type& k) const;
162
  local_iterator begin(size_type n);
@@ -164,75 +177,68 @@ namespace std {
164
  local_iterator end(size_type n);
165
  const_local_iterator end(size_type n) const;
166
  const_local_iterator cbegin(size_type n) const;
167
  const_local_iterator cend(size_type n) const;
168
 
169
- // hash policy:
170
  float load_factor() const noexcept;
171
  float max_load_factor() const noexcept;
172
  void max_load_factor(float z);
173
  void rehash(size_type n);
174
  void reserve(size_type n);
175
  };
176
 
177
  template<class InputIterator,
178
- class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
179
- class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
180
- class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
181
  unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
182
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
183
- -> unordered_set<typename iterator_traits<InputIterator>::value_type,
184
  Hash, Pred, Allocator>;
185
 
186
  template<class T, class Hash = hash<T>,
187
  class Pred = equal_to<T>, class Allocator = allocator<T>>
188
  unordered_set(initializer_list<T>, typename see below::size_type = see below,
189
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
190
  -> unordered_set<T, Hash, Pred, Allocator>;
191
 
192
  template<class InputIterator, class Allocator>
193
  unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
194
- -> unordered_set<typename iterator_traits<InputIterator>::value_type,
195
- hash<typename iterator_traits<InputIterator>::value_type>,
196
- equal_to<typename iterator_traits<InputIterator>::value_type>,
197
  Allocator>;
198
 
199
  template<class InputIterator, class Hash, class Allocator>
200
  unordered_set(InputIterator, InputIterator, typename see below::size_type,
201
  Hash, Allocator)
202
- -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
203
- equal_to<typename iterator_traits<InputIterator>::value_type>,
204
  Allocator>;
205
 
206
  template<class T, class Allocator>
207
  unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
208
  -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
209
 
210
  template<class T, class Hash, class Allocator>
211
  unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
212
  -> unordered_set<T, Hash, equal_to<T>, Allocator>;
213
 
214
- template <class Key, class Hash, class Pred, class Alloc>
215
- bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
216
- const unordered_set<Key, Hash, Pred, Alloc>& b);
217
- template <class Key, class Hash, class Pred, class Alloc>
218
- bool operator!=(const unordered_set<Key, Hash, Pred, Alloc>& a,
219
- const unordered_set<Key, Hash, Pred, Alloc>& b);
220
-
221
- // [unord.set.swap], swap
222
  template<class Key, class Hash, class Pred, class Alloc>
223
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
224
  unordered_set<Key, Hash, Pred, Alloc>& y)
225
  noexcept(noexcept(x.swap(y)));
226
  }
227
  ```
228
 
229
  A `size_type` parameter type in an `unordered_set` deduction guide
230
- refers to the `size_type` member type of the primary `unordered_set`
231
- template.
232
 
233
- #### `unordered_set` constructors <a id="unord.set.cnstr">[[unord.set.cnstr]]</a>
234
 
235
  ``` cpp
236
  unordered_set() : unordered_set(size_type(see below)) { }
237
  explicit unordered_set(size_type n,
238
  const hasher& hf = hasher(),
@@ -268,16 +274,27 @@ buckets. If `n` is not provided, the number of buckets is
268
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
269
  for the second form. `max_load_factor()` returns `1.0`.
270
 
271
  *Complexity:* Average case linear, worst case quadratic.
272
 
273
- #### `unordered_set` swap <a id="unord.set.swap">[[unord.set.swap]]</a>
274
 
275
  ``` cpp
276
- template <class Key, class Hash, class Pred, class Alloc>
277
- void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
278
- unordered_set<Key, Hash, Pred, Alloc>& y)
279
- noexcept(noexcept(x.swap(y)));
280
  ```
281
 
282
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
283
 
 
1
  ### Class template `unordered_set` <a id="unord.set">[[unord.set]]</a>
2
 
3
+ #### Overview <a id="unord.set.overview">[[unord.set.overview]]</a>
4
 
5
  An `unordered_set` is an unordered associative container that supports
6
  unique keys (an `unordered_set` contains at most one of each key value)
7
  and in which the elements’ keys are the elements themselves. The
8
  `unordered_set` class supports forward iterators.
9
 
10
+ An `unordered_set` meets all of the requirements of a container, of an
11
+ unordered associative container, and of an allocator-aware container (
12
+ [[container.alloc.req]]). It provides the operations described in the
13
+ preceding requirements table for unique keys; that is, an
14
+ `unordered_set` supports the `a_uniq` operations in that table, not the
15
+ `a_eq` operations. For an `unordered_set<Key>` the `key type` and the
16
+ value type are both `Key`. The `iterator` and `const_iterator` types are
17
+ both constant iterator types. It is unspecified whether they are the
18
  same type.
19
 
20
+ Subclause  [[unord.set]] only describes operations on `unordered_set`
21
+ that are not described in one of the requirement tables, or for which
22
+ there is additional semantic information.
23
 
24
  ``` cpp
25
  namespace std {
26
  template<class Key,
27
  class Hash = hash<Key>,
28
  class Pred = equal_to<Key>,
29
  class Allocator = allocator<Key>>
30
  class unordered_set {
31
  public:
32
+ // types
33
  using key_type = Key;
34
  using value_type = Key;
35
  using hasher = Hash;
36
  using key_equal = Pred;
37
  using allocator_type = Allocator;
 
45
  using iterator = implementation-defined // type of unordered_set::iterator; // see [container.requirements]
46
  using const_iterator = implementation-defined // type of unordered_set::const_iterator; // see [container.requirements]
47
  using local_iterator = implementation-defined // type of unordered_set::local_iterator; // see [container.requirements]
48
  using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
49
  using node_type = unspecified;
50
+ using insert_return_type = insert-return-type<iterator, node_type>;
51
 
52
  // [unord.set.cnstr], construct/copy/destroy
53
  unordered_set();
54
  explicit unordered_set(size_type n,
55
  const hasher& hf = hasher(),
 
94
  is_nothrow_move_assignable_v<Hash> &&
95
  is_nothrow_move_assignable_v<Pred>);
96
  unordered_set& operator=(initializer_list<value_type>);
97
  allocator_type get_allocator() const noexcept;
98
 
99
+ // iterators
100
  iterator begin() noexcept;
101
  const_iterator begin() const noexcept;
102
  iterator end() noexcept;
103
  const_iterator end() const noexcept;
104
  const_iterator cbegin() const noexcept;
105
  const_iterator cend() const noexcept;
106
 
107
+ // capacity
108
+ [[nodiscard]] bool empty() const noexcept;
109
  size_type size() const noexcept;
110
  size_type max_size() const noexcept;
111
 
112
+ // modifiers
113
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
114
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
115
  pair<iterator, bool> insert(const value_type& obj);
116
  pair<iterator, bool> insert(value_type&& obj);
117
  iterator insert(const_iterator hint, const value_type& obj);
 
141
  template<class H2, class P2>
142
  void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
143
  template<class H2, class P2>
144
  void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
145
 
146
+ // observers
147
  hasher hash_function() const;
148
  key_equal key_eq() const;
149
 
150
+ // set operations
151
  iterator find(const key_type& k);
152
  const_iterator find(const key_type& k) const;
153
+ template<class K>
154
+ iterator find(const K& k);
155
+ template<class K>
156
+ const_iterator find(const K& k) const;
157
  size_type count(const key_type& k) const;
158
+ template<class K>
159
+ size_type count(const K& k) const;
160
+ bool contains(const key_type& k) const;
161
+ template<class K>
162
+ bool contains(const K& k) const;
163
  pair<iterator, iterator> equal_range(const key_type& k);
164
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
165
+ template<class K>
166
+ pair<iterator, iterator> equal_range(const K& k);
167
+ template<class K>
168
+ pair<const_iterator, const_iterator> equal_range(const K& k) const;
169
 
170
+ // bucket interface
171
  size_type bucket_count() const noexcept;
172
  size_type max_bucket_count() const noexcept;
173
  size_type bucket_size(size_type n) const;
174
  size_type bucket(const key_type& k) const;
175
  local_iterator begin(size_type n);
 
177
  local_iterator end(size_type n);
178
  const_local_iterator end(size_type n) const;
179
  const_local_iterator cbegin(size_type n) const;
180
  const_local_iterator cend(size_type n) const;
181
 
182
+ // hash policy
183
  float load_factor() const noexcept;
184
  float max_load_factor() const noexcept;
185
  void max_load_factor(float z);
186
  void rehash(size_type n);
187
  void reserve(size_type n);
188
  };
189
 
190
  template<class InputIterator,
191
+ class Hash = hash<iter-value-type<InputIterator>>,
192
+ class Pred = equal_to<iter-value-type<InputIterator>>,
193
+ class Allocator = allocator<iter-value-type<InputIterator>>>
194
  unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
195
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
196
+ -> unordered_set<iter-value-type<InputIterator>,
197
  Hash, Pred, Allocator>;
198
 
199
  template<class T, class Hash = hash<T>,
200
  class Pred = equal_to<T>, class Allocator = allocator<T>>
201
  unordered_set(initializer_list<T>, typename see below::size_type = see below,
202
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
203
  -> unordered_set<T, Hash, Pred, Allocator>;
204
 
205
  template<class InputIterator, class Allocator>
206
  unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
207
+ -> unordered_set<iter-value-type<InputIterator>,
208
+ hash<iter-value-type<InputIterator>>,
209
+ equal_to<iter-value-type<InputIterator>>,
210
  Allocator>;
211
 
212
  template<class InputIterator, class Hash, class Allocator>
213
  unordered_set(InputIterator, InputIterator, typename see below::size_type,
214
  Hash, Allocator)
215
+ -> unordered_set<iter-value-type<InputIterator>, Hash,
216
+ equal_to<iter-value-type<InputIterator>>,
217
  Allocator>;
218
 
219
  template<class T, class Allocator>
220
  unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
221
  -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
222
 
223
  template<class T, class Hash, class Allocator>
224
  unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
225
  -> unordered_set<T, Hash, equal_to<T>, Allocator>;
226
 
227
+ // swap
 
 
 
 
 
 
 
228
  template<class Key, class Hash, class Pred, class Alloc>
229
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
230
  unordered_set<Key, Hash, Pred, Alloc>& y)
231
  noexcept(noexcept(x.swap(y)));
232
  }
233
  ```
234
 
235
  A `size_type` parameter type in an `unordered_set` deduction guide
236
+ refers to the `size_type` member type of the type deduced by the
237
+ deduction guide.
238
 
239
+ #### Constructors <a id="unord.set.cnstr">[[unord.set.cnstr]]</a>
240
 
241
  ``` cpp
242
  unordered_set() : unordered_set(size_type(see below)) { }
243
  explicit unordered_set(size_type n,
244
  const hasher& hf = hasher(),
 
274
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
275
  for the second form. `max_load_factor()` returns `1.0`.
276
 
277
  *Complexity:* Average case linear, worst case quadratic.
278
 
279
+ #### Erasure <a id="unord.set.erasure">[[unord.set.erasure]]</a>
280
 
281
  ``` cpp
282
+ template<class K, class H, class P, class A, class Predicate>
283
+ typename unordered_set<K, H, P, A>::size_type
284
+ erase_if(unordered_set<K, H, P, A>& c, Predicate pred);
 
285
  ```
286
 
287
+ *Effects:* Equivalent to:
288
+
289
+ ``` cpp
290
+ auto original_size = c.size();
291
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
292
+ if (pred(*i)) {
293
+ i = c.erase(i);
294
+ } else {
295
+ ++i;
296
+ }
297
+ }
298
+ return original_size - c.size();
299
+ ```
300