From Jason Turner

[unord.multimap]

C++17 → C++20 12.4 KB 143 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/tmpzqkepx6x/{from.md → to.md} +75 -60
tmp/tmpzqkepx6x/{from.md → to.md} RENAMED
@@ -1,38 +1,38 @@
1
  ### Class template `unordered_multimap` <a id="unord.multimap">[[unord.multimap]]</a>
2
 
3
- #### Class template `unordered_multimap` overview <a id="unord.multimap.overview">[[unord.multimap.overview]]</a>
4
 
5
  An `unordered_multimap` is an unordered associative container that
6
  supports equivalent keys (an instance of `unordered_multimap` may
7
  contain multiple copies of each key value) and that associates values of
8
  another type `mapped_type` with the keys. The `unordered_multimap` class
9
  supports forward iterators.
10
 
11
- An `unordered_multimap` satisfies all of the requirements of a
12
- container, of an unordered associative container, and of an
13
- allocator-aware container (Table  [[tab:containers.allocatoraware]]). It
14
- provides the operations described in the preceding requirements table
15
- for equivalent keys; that is, an `unordered_multimap` supports the
16
- `a_eq` operations in that table, not the `a_uniq` operations. For an
17
- `unordered_multimap<Key, T>` the `key type` is `Key`, the mapped type is
18
- `T`, and the value type is `pair<const Key, T>`.
19
 
20
- This section only describes operations on `unordered_multimap` that are
21
- not 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 T,
28
  class Hash = hash<Key>,
29
  class Pred = equal_to<Key>,
30
  class Allocator = allocator<pair<const Key, T>>>
31
  class unordered_multimap {
32
  public:
33
- // types:
34
  using key_type = Key;
35
  using mapped_type = T;
36
  using value_type = pair<const Key, T>;
37
  using hasher = Hash;
38
  using key_equal = Pred;
@@ -95,20 +95,20 @@ namespace std {
95
  is_nothrow_move_assignable_v<Hash> &&
96
  is_nothrow_move_assignable_v<Pred>);
97
  unordered_multimap& operator=(initializer_list<value_type>);
98
  allocator_type get_allocator() const noexcept;
99
 
100
- // iterators:
101
  iterator begin() noexcept;
102
  const_iterator begin() const noexcept;
103
  iterator end() noexcept;
104
  const_iterator end() const noexcept;
105
  const_iterator cbegin() const noexcept;
106
  const_iterator cend() const noexcept;
107
 
108
- // capacity:
109
- bool empty() const noexcept;
110
  size_type size() const noexcept;
111
  size_type max_size() const noexcept;
112
 
113
  // [unord.multimap.modifiers], modifiers
114
  template<class... Args> iterator emplace(Args&&... args);
@@ -144,22 +144,35 @@ namespace std {
144
  template<class H2, class P2>
145
  void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
146
  template<class H2, class P2>
147
  void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
148
 
149
- // observers:
150
  hasher hash_function() const;
151
  key_equal key_eq() const;
152
 
153
- // map operations:
154
  iterator find(const key_type& k);
155
  const_iterator find(const key_type& k) const;
 
 
 
 
156
  size_type count(const key_type& k) const;
 
 
 
 
 
157
  pair<iterator, iterator> equal_range(const key_type& k);
158
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
 
 
 
159
 
160
- // bucket interface:
161
  size_type bucket_count() const noexcept;
162
  size_type max_bucket_count() const noexcept;
163
  size_type bucket_size(size_type n) const;
164
  size_type bucket(const key_type& k) const;
165
  local_iterator begin(size_type n);
@@ -176,66 +189,59 @@ namespace std {
176
  void rehash(size_type n);
177
  void reserve(size_type n);
178
  };
179
 
180
  template<class InputIterator,
181
- class Hash = hash<iter_key_t<InputIterator>>,
182
- class Pred = equal_to<iter_key_t<InputIterator>>,
183
- class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
184
  unordered_multimap(InputIterator, InputIterator,
185
  typename see below::size_type = see below,
186
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
187
- -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
188
- Allocator>;
189
 
190
  template<class Key, class T, class Hash = hash<Key>,
191
  class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
192
- unordered_multimap(initializer_list<pair<const Key, T>>,
193
  typename see below::size_type = see below,
194
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
195
  -> unordered_multimap<Key, T, Hash, Pred, Allocator>;
196
 
197
  template<class InputIterator, class Allocator>
198
  unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)
199
- -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
200
- hash<iter_key_t<InputIterator>>,
201
- equal_to<iter_key_t<InputIterator>>, Allocator>;
202
 
203
  template<class InputIterator, class Allocator>
204
  unordered_multimap(InputIterator, InputIterator, Allocator)
205
- -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
206
- hash<iter_key_t<InputIterator>>,
207
- equal_to<iter_key_t<InputIterator>>, Allocator>;
208
 
209
  template<class InputIterator, class Hash, class Allocator>
210
  unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash,
211
  Allocator)
212
- -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
213
- equal_to<iter_key_t<InputIterator>>, Allocator>;
214
 
215
- template<class Key, class T, typename Allocator>
216
- unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type,
217
  Allocator)
218
  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
219
 
220
- template<class Key, class T, typename Allocator>
221
- unordered_multimap(initializer_list<pair<const Key, T>>, Allocator)
222
  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
223
 
224
  template<class Key, class T, class Hash, class Allocator>
225
- unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type,
226
  Hash, Allocator)
227
  -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>;
228
 
229
- template <class Key, class T, class Hash, class Pred, class Alloc>
230
- bool operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
231
- const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
232
- template <class Key, class T, class Hash, class Pred, class Alloc>
233
- bool operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
234
- const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
235
-
236
- // [unord.multimap.swap], swap
237
  template<class Key, class T, class Hash, class Pred, class Alloc>
238
  void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
239
  unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
240
  noexcept(noexcept(x.swap(y)));
241
  }
@@ -243,11 +249,11 @@ namespace std {
243
 
244
  A `size_type` parameter type in an `unordered_multimap` deduction guide
245
  refers to the `size_type` member type of the type deduced by the
246
  deduction guide.
247
 
248
- #### `unordered_multimap` constructors <a id="unord.multimap.cnstr">[[unord.multimap.cnstr]]</a>
249
 
250
  ``` cpp
251
  unordered_multimap() : unordered_multimap(size_type(see below)) { }
252
  explicit unordered_multimap(size_type n,
253
  const hasher& hf = hasher(),
@@ -283,39 +289,48 @@ hash function, key equality predicate, and allocator, and using at least
283
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
284
  for the second form. `max_load_factor()` returns `1.0`.
285
 
286
  *Complexity:* Average case linear, worst case quadratic.
287
 
288
- #### `unordered_multimap` modifiers <a id="unord.multimap.modifiers">[[unord.multimap.modifiers]]</a>
289
 
290
  ``` cpp
291
  template<class P>
292
  iterator insert(P&& obj);
293
  ```
294
 
 
 
295
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
296
 
297
- *Remarks:* This signature shall not participate in overload resolution
298
- unless `is_constructible_v<value_type, P&&>` is `true`.
299
-
300
  ``` cpp
301
  template<class P>
302
  iterator insert(const_iterator hint, P&& obj);
303
  ```
304
 
 
 
305
  *Effects:* Equivalent to:
306
  `return emplace_hint(hint, std::forward<P>(obj));`
307
 
308
- *Remarks:* This signature shall not participate in overload resolution
309
- unless `is_constructible_v<value_type, P&&>` is `true`.
310
-
311
- #### `unordered_multimap` swap <a id="unord.multimap.swap">[[unord.multimap.swap]]</a>
312
 
313
  ``` cpp
314
- template <class Key, class T, class Hash, class Pred, class Alloc>
315
- void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
316
- unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
317
- noexcept(noexcept(x.swap(y)));
318
  ```
319
 
320
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
321
 
 
1
  ### Class template `unordered_multimap` <a id="unord.multimap">[[unord.multimap]]</a>
2
 
3
+ #### Overview <a id="unord.multimap.overview">[[unord.multimap.overview]]</a>
4
 
5
  An `unordered_multimap` is an unordered associative container that
6
  supports equivalent keys (an instance of `unordered_multimap` may
7
  contain multiple copies of each key value) and that associates values of
8
  another type `mapped_type` with the keys. The `unordered_multimap` class
9
  supports forward iterators.
10
 
11
+ An `unordered_multimap` meets all of the requirements of a container, of
12
+ an unordered associative container, and of an allocator-aware container
13
+ ([[container.alloc.req]]). It provides the operations described in the
14
+ preceding requirements table for equivalent keys; that is, an
15
+ `unordered_multimap` supports the `a_eq` operations in that table, not
16
+ the `a_uniq` operations. For an `unordered_multimap<Key, T>` the
17
+ `key type` is `Key`, the mapped type is `T`, and the value type is
18
+ `pair<const Key, T>`.
19
 
20
+ Subclause  [[unord.multimap]] only describes operations on
21
+ `unordered_multimap` that are not described in one of the requirement
22
+ tables, or for which there is additional semantic information.
23
 
24
  ``` cpp
25
  namespace std {
26
  template<class Key,
27
  class T,
28
  class Hash = hash<Key>,
29
  class Pred = equal_to<Key>,
30
  class Allocator = allocator<pair<const Key, T>>>
31
  class unordered_multimap {
32
  public:
33
+ // types
34
  using key_type = Key;
35
  using mapped_type = T;
36
  using value_type = pair<const Key, T>;
37
  using hasher = Hash;
38
  using key_equal = Pred;
 
95
  is_nothrow_move_assignable_v<Hash> &&
96
  is_nothrow_move_assignable_v<Pred>);
97
  unordered_multimap& operator=(initializer_list<value_type>);
98
  allocator_type get_allocator() const noexcept;
99
 
100
+ // iterators
101
  iterator begin() noexcept;
102
  const_iterator begin() const noexcept;
103
  iterator end() noexcept;
104
  const_iterator end() const noexcept;
105
  const_iterator cbegin() const noexcept;
106
  const_iterator cend() const noexcept;
107
 
108
+ // capacity
109
+ [[nodiscard]] bool empty() const noexcept;
110
  size_type size() const noexcept;
111
  size_type max_size() const noexcept;
112
 
113
  // [unord.multimap.modifiers], modifiers
114
  template<class... Args> iterator emplace(Args&&... args);
 
144
  template<class H2, class P2>
145
  void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
146
  template<class H2, class P2>
147
  void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
148
 
149
+ // observers
150
  hasher hash_function() const;
151
  key_equal key_eq() const;
152
 
153
+ // map operations
154
  iterator find(const key_type& k);
155
  const_iterator find(const key_type& k) const;
156
+ template<class K>
157
+ iterator find(const K& k);
158
+ template<class K>
159
+ const_iterator find(const K& k) const;
160
  size_type count(const key_type& k) const;
161
+ template<class K>
162
+ size_type count(const K& k) const;
163
+ bool contains(const key_type& k) const;
164
+ template<class K>
165
+ bool contains(const K& k) const;
166
  pair<iterator, iterator> equal_range(const key_type& k);
167
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
168
+ template<class K>
169
+ pair<iterator, iterator> equal_range(const K& k);
170
+ template<class K>
171
+ pair<const_iterator, const_iterator> equal_range(const K& k) const;
172
 
173
+ // bucket interface
174
  size_type bucket_count() const noexcept;
175
  size_type max_bucket_count() const noexcept;
176
  size_type bucket_size(size_type n) const;
177
  size_type bucket(const key_type& k) const;
178
  local_iterator begin(size_type n);
 
189
  void rehash(size_type n);
190
  void reserve(size_type n);
191
  };
192
 
193
  template<class InputIterator,
194
+ class Hash = hash<iter-key-type<InputIterator>>,
195
+ class Pred = equal_to<iter-key-type<InputIterator>>,
196
+ class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
197
  unordered_multimap(InputIterator, InputIterator,
198
  typename see below::size_type = see below,
199
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
200
+ -> unordered_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
201
+ Hash, Pred, Allocator>;
202
 
203
  template<class Key, class T, class Hash = hash<Key>,
204
  class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
205
+ unordered_multimap(initializer_list<pair<Key, T>>,
206
  typename see below::size_type = see below,
207
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
208
  -> unordered_multimap<Key, T, Hash, Pred, Allocator>;
209
 
210
  template<class InputIterator, class Allocator>
211
  unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)
212
+ -> unordered_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
213
+ hash<iter-key-type<InputIterator>>,
214
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
215
 
216
  template<class InputIterator, class Allocator>
217
  unordered_multimap(InputIterator, InputIterator, Allocator)
218
+ -> unordered_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
219
+ hash<iter-key-type<InputIterator>>,
220
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
221
 
222
  template<class InputIterator, class Hash, class Allocator>
223
  unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash,
224
  Allocator)
225
+ -> unordered_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Hash,
226
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
227
 
228
+ template<class Key, class T, class Allocator>
229
+ unordered_multimap(initializer_list<pair<Key, T>>, typename see below::size_type,
230
  Allocator)
231
  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
232
 
233
+ template<class Key, class T, class Allocator>
234
+ unordered_multimap(initializer_list<pair<Key, T>>, Allocator)
235
  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
236
 
237
  template<class Key, class T, class Hash, class Allocator>
238
+ unordered_multimap(initializer_list<pair<Key, T>>, typename see below::size_type,
239
  Hash, Allocator)
240
  -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>;
241
 
242
+ // swap
 
 
 
 
 
 
 
243
  template<class Key, class T, class Hash, class Pred, class Alloc>
244
  void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
245
  unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
246
  noexcept(noexcept(x.swap(y)));
247
  }
 
249
 
250
  A `size_type` parameter type in an `unordered_multimap` deduction guide
251
  refers to the `size_type` member type of the type deduced by the
252
  deduction guide.
253
 
254
+ #### Constructors <a id="unord.multimap.cnstr">[[unord.multimap.cnstr]]</a>
255
 
256
  ``` cpp
257
  unordered_multimap() : unordered_multimap(size_type(see below)) { }
258
  explicit unordered_multimap(size_type n,
259
  const hasher& hf = hasher(),
 
289
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
290
  for the second form. `max_load_factor()` returns `1.0`.
291
 
292
  *Complexity:* Average case linear, worst case quadratic.
293
 
294
+ #### Modifiers <a id="unord.multimap.modifiers">[[unord.multimap.modifiers]]</a>
295
 
296
  ``` cpp
297
  template<class P>
298
  iterator insert(P&& obj);
299
  ```
300
 
301
+ *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
302
+
303
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
304
 
 
 
 
305
  ``` cpp
306
  template<class P>
307
  iterator insert(const_iterator hint, P&& obj);
308
  ```
309
 
310
+ *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
311
+
312
  *Effects:* Equivalent to:
313
  `return emplace_hint(hint, std::forward<P>(obj));`
314
 
315
+ #### Erasure <a id="unord.multimap.erasure">[[unord.multimap.erasure]]</a>
 
 
 
316
 
317
  ``` cpp
318
+ template<class K, class T, class H, class P, class A, class Predicate>
319
+ typename unordered_multimap<K, T, H, P, A>::size_type
320
+ erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);
 
321
  ```
322
 
323
+ *Effects:* Equivalent to:
324
+
325
+ ``` cpp
326
+ auto original_size = c.size();
327
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
328
+ if (pred(*i)) {
329
+ i = c.erase(i);
330
+ } else {
331
+ ++i;
332
+ }
333
+ }
334
+ return original_size - c.size();
335
+ ```
336