From Jason Turner

[unord.multimap]

C++14 → C++17 16.4 KB 203 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game
C++ Weekly: Ep 193

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpmpa_qurq/{from.md → to.md} +140 -56
tmp/tmpmpa_qurq/{from.md → to.md} RENAMED
@@ -13,46 +13,46 @@ 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 `std::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 = std::equal_to<Key>,
30
- class Allocator = std::allocator<std::pair<const Key, T> > >
31
- class unordered_multimap
32
- {
33
  public:
34
- // types
35
- typedef Key key_type;
36
- typedef std::pair<const Key, T> value_type;
37
- typedef T mapped_type;
38
- typedef Hash hasher;
39
- typedef Pred key_equal;
40
- typedef Allocator allocator_type;
41
- typedef typename allocator_traits<Allocator>::pointer pointer;
42
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
43
- typedef value_type& reference;
44
- typedef const value_type& const_reference;
45
- typedef implementation-defined size_type;
46
- typedef implementation-defined difference_type;
47
 
48
- typedef implementation-defined iterator;
49
- typedef implementation-defined const_iterator;
50
- typedef implementation-defined local_iterator;
51
- typedef implementation-defined const_local_iterator;
 
52
 
53
- // construct/destroy/copy
54
  unordered_multimap();
55
  explicit unordered_multimap(size_type n,
56
  const hasher& hf = hasher(),
57
  const key_equal& eql = key_equal(),
58
  const allocator_type& a = allocator_type());
@@ -65,12 +65,12 @@ namespace std {
65
  unordered_multimap(const unordered_multimap&);
66
  unordered_multimap(unordered_multimap&&);
67
  explicit unordered_multimap(const Allocator&);
68
  unordered_multimap(const unordered_multimap&, const Allocator&);
69
  unordered_multimap(unordered_multimap&&, const Allocator&);
70
- unordered_multimap(initializer_list<value_type>,
71
- size_type = see below,
72
  const hasher& hf = hasher(),
73
  const key_equal& eql = key_equal(),
74
  const allocator_type& a = allocator_type());
75
  unordered_multimap(size_type n, const allocator_type& a)
76
  : unordered_multimap(n, hasher(), key_equal(), a) { }
@@ -88,56 +88,78 @@ namespace std {
88
  unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
89
  const allocator_type& a)
90
  : unordered_multimap(il, n, hf, key_equal(), a) { }
91
  ~unordered_multimap();
92
  unordered_multimap& operator=(const unordered_multimap&);
93
- unordered_multimap& operator=(unordered_multimap&&);
 
 
 
94
  unordered_multimap& operator=(initializer_list<value_type>);
95
  allocator_type get_allocator() const noexcept;
96
 
97
- // size and capacity
98
- bool empty() const noexcept;
99
- size_type size() const noexcept;
100
- size_type max_size() const noexcept;
101
-
102
- // iterators
103
  iterator begin() noexcept;
104
  const_iterator begin() const noexcept;
105
  iterator end() noexcept;
106
  const_iterator end() const noexcept;
107
  const_iterator cbegin() const noexcept;
108
  const_iterator cend() const noexcept;
109
 
110
- // modifiers
 
 
 
 
 
111
  template <class... Args> iterator emplace(Args&&... args);
112
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
113
  iterator insert(const value_type& obj);
 
114
  template <class P> iterator insert(P&& obj);
115
  iterator insert(const_iterator hint, const value_type& obj);
 
116
  template <class P> iterator insert(const_iterator hint, P&& obj);
117
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
118
  void insert(initializer_list<value_type>);
119
 
 
 
 
 
 
 
120
  iterator erase(const_iterator position);
121
  size_type erase(const key_type& k);
122
  iterator erase(const_iterator first, const_iterator last);
 
 
 
 
123
  void clear() noexcept;
124
 
125
- void swap(unordered_multimap&);
 
 
 
 
 
 
 
126
 
127
- // observers
128
  hasher hash_function() const;
129
  key_equal key_eq() const;
130
 
131
- // lookup
132
  iterator find(const key_type& k);
133
  const_iterator find(const key_type& k) const;
134
  size_type count(const key_type& k) const;
135
- std::pair<iterator, iterator> equal_range(const key_type& k);
136
- std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
137
 
138
- // bucket interface
139
  size_type bucket_count() const noexcept;
140
  size_type max_bucket_count() const noexcept;
141
  size_type bucket_size(size_type n) const;
142
  size_type bucket(const key_type& k) const;
143
  local_iterator begin(size_type n);
@@ -153,23 +175,78 @@ namespace std {
153
  void max_load_factor(float z);
154
  void rehash(size_type n);
155
  void reserve(size_type n);
156
  };
157
 
158
- template <class Key, class T, class Hash, class Pred, class Alloc>
159
- void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
160
- unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
161
 
162
  template <class Key, class T, class Hash, class Pred, class Alloc>
163
  bool operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
164
  const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
165
  template <class Key, class T, class Hash, class Pred, class Alloc>
166
  bool operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
167
  const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
 
 
 
 
 
 
168
  }
169
  ```
170
 
 
 
 
 
171
  #### `unordered_multimap` constructors <a id="unord.multimap.cnstr">[[unord.multimap.cnstr]]</a>
172
 
173
  ``` cpp
174
  unordered_multimap() : unordered_multimap(size_type(see below)) { }
175
  explicit unordered_multimap(size_type n,
@@ -177,61 +254,68 @@ explicit unordered_multimap(size_type n,
177
  const key_equal& eql = key_equal(),
178
  const allocator_type& a = allocator_type());
179
  ```
180
 
181
  *Effects:* Constructs an empty `unordered_multimap` using the specified
182
- hash function, key equality function, and allocator, and using at least
183
- *`n`* buckets. For the default constructor, the number of buckets is
184
- *implementation-defined*. `max_load_factor()` returns 1.0.
185
 
186
  *Complexity:* Constant.
187
 
188
  ``` cpp
189
  template <class InputIterator>
190
  unordered_multimap(InputIterator f, InputIterator l,
191
  size_type n = see below,
192
  const hasher& hf = hasher(),
193
  const key_equal& eql = key_equal(),
194
  const allocator_type& a = allocator_type());
 
 
 
 
 
195
  ```
196
 
197
  *Effects:* Constructs an empty `unordered_multimap` using the specified
198
- hash function, key equality function, and allocator, and using at least
199
- *`n`* buckets. If *`n`* is not provided, the number of buckets is
200
- *implementation-defined*. Then inserts elements from the range
201
- `[`*`f`*`, `*`l`*`)`. `max_load_factor()` returns 1.0.
 
202
 
203
  *Complexity:* Average case linear, worst case quadratic.
204
 
205
  #### `unordered_multimap` modifiers <a id="unord.multimap.modifiers">[[unord.multimap.modifiers]]</a>
206
 
207
  ``` cpp
208
  template <class P>
209
  iterator insert(P&& obj);
210
  ```
211
 
212
- *Effects:* Equivalent to `return emplace(std::forward<P>(obj))`.
213
 
214
  *Remarks:* This signature shall not participate in overload resolution
215
- unless `std::is_constructible<value_type, P&&>::value` is `true`.
216
 
217
  ``` cpp
218
  template <class P>
219
  iterator insert(const_iterator hint, P&& obj);
220
  ```
221
 
222
- *Effects:* Equivalent to
223
- `return emplace_hint(hint, std::forward<P>(obj))`.
224
 
225
  *Remarks:* This signature shall not participate in overload resolution
226
- unless `std::is_constructible<value_type, P&&>::value` is `true`.
227
 
228
  #### `unordered_multimap` swap <a id="unord.multimap.swap">[[unord.multimap.swap]]</a>
229
 
230
  ``` cpp
231
  template <class Key, class T, class Hash, class Pred, class Alloc>
232
  void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
233
- unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
234
  ```
235
 
236
- *Effects:* `x.swap(y)`.
237
 
 
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;
39
+ using allocator_type = Allocator;
40
+ using pointer = typename allocator_traits<Allocator>::pointer;
41
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
42
+ using reference = value_type&;
43
+ using const_reference = const value_type&;
44
+ using size_type = implementation-defined; // see [container.requirements]
45
+ using difference_type = implementation-defined; // see [container.requirements]
46
 
47
+ using iterator = implementation-defined // type of unordered_multimap::iterator; // see [container.requirements]
48
+ using const_iterator = implementation-defined // type of unordered_multimap::const_iterator; // see [container.requirements]
49
+ using local_iterator = implementation-defined // type of unordered_multimap::local_iterator; // see [container.requirements]
50
+ using const_local_iterator = implementation-defined // type of unordered_multimap::const_local_iterator; // see [container.requirements]
51
+ using node_type = unspecified;
52
 
53
+ // [unord.multimap.cnstr], construct/copy/destroy
54
  unordered_multimap();
55
  explicit unordered_multimap(size_type n,
56
  const hasher& hf = hasher(),
57
  const key_equal& eql = key_equal(),
58
  const allocator_type& a = allocator_type());
 
65
  unordered_multimap(const unordered_multimap&);
66
  unordered_multimap(unordered_multimap&&);
67
  explicit unordered_multimap(const Allocator&);
68
  unordered_multimap(const unordered_multimap&, const Allocator&);
69
  unordered_multimap(unordered_multimap&&, const Allocator&);
70
+ unordered_multimap(initializer_list<value_type> il,
71
+ size_type n = see below,
72
  const hasher& hf = hasher(),
73
  const key_equal& eql = key_equal(),
74
  const allocator_type& a = allocator_type());
75
  unordered_multimap(size_type n, const allocator_type& a)
76
  : unordered_multimap(n, hasher(), key_equal(), a) { }
 
88
  unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
89
  const allocator_type& a)
90
  : unordered_multimap(il, n, hf, key_equal(), a) { }
91
  ~unordered_multimap();
92
  unordered_multimap& operator=(const unordered_multimap&);
93
+ unordered_multimap& operator=(unordered_multimap&&)
94
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
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);
115
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
116
  iterator insert(const value_type& obj);
117
+ iterator insert(value_type&& obj);
118
  template <class P> iterator insert(P&& obj);
119
  iterator insert(const_iterator hint, const value_type& obj);
120
+ iterator insert(const_iterator hint, value_type&& obj);
121
  template <class P> iterator insert(const_iterator hint, P&& obj);
122
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
123
  void insert(initializer_list<value_type>);
124
 
125
+ node_type extract(const_iterator position);
126
+ node_type extract(const key_type& x);
127
+ iterator insert(node_type&& nh);
128
+ iterator insert(const_iterator hint, node_type&& nh);
129
+
130
+ iterator erase(iterator position);
131
  iterator erase(const_iterator position);
132
  size_type erase(const key_type& k);
133
  iterator erase(const_iterator first, const_iterator last);
134
+ void swap(unordered_multimap&)
135
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
136
+ is_nothrow_swappable_v<Hash> &&
137
+ is_nothrow_swappable_v<Pred>);
138
  void clear() noexcept;
139
 
140
+ template<class H2, class P2>
141
+ void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
142
+ template<class H2, class P2>
143
+ void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
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);
 
175
  void max_load_factor(float z);
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
  }
242
  ```
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,
 
254
  const key_equal& eql = key_equal(),
255
  const allocator_type& a = allocator_type());
256
  ```
257
 
258
  *Effects:* Constructs an empty `unordered_multimap` using the specified
259
+ hash function, key equality predicate, and allocator, and using at least
260
+ `n` buckets. For the default constructor, the number of buckets is
261
+ *implementation-defined*. `max_load_factor()` returns `1.0`.
262
 
263
  *Complexity:* Constant.
264
 
265
  ``` cpp
266
  template <class InputIterator>
267
  unordered_multimap(InputIterator f, InputIterator l,
268
  size_type n = see below,
269
  const hasher& hf = hasher(),
270
  const key_equal& eql = key_equal(),
271
  const allocator_type& a = allocator_type());
272
+ unordered_multimap(initializer_list<value_type> il,
273
+ size_type n = see below,
274
+ const hasher& hf = hasher(),
275
+ const key_equal& eql = key_equal(),
276
+ const allocator_type& a = allocator_type());
277
  ```
278
 
279
  *Effects:* Constructs an empty `unordered_multimap` using the specified
280
+ hash function, key equality predicate, and allocator, and using at least
281
+ `n` buckets. If `n` is not provided, the number of buckets is
282
+ *implementation-defined*. Then inserts elements from the range \[`f`,
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