Debian Codegraph @

libcxx/include/__cxx03/unordered_map

raw
1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _LIBCPP___CXX03_UNORDERED_MAP
11 #define _LIBCPP___CXX03_UNORDERED_MAP
12
13 /*
14
15 unordered_map synopsis
16
17 #include <__cxx03/initializer_list>
18
19 namespace std
20 {
21
22 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
23 class Alloc = allocator<pair<const Key, T>>>
24 class unordered_map
25 {
26 public:
27 // types
28 typedef Key key_type;
29 typedef T mapped_type;
30 typedef Hash hasher;
31 typedef Pred key_equal;
32 typedef Alloc allocator_type;
33 typedef pair<const key_type, mapped_type> value_type;
34 typedef value_type& reference;
35 typedef const value_type& const_reference;
36 typedef typename allocator_traits<allocator_type>::pointer pointer;
37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
38 typedef typename allocator_traits<allocator_type>::size_type size_type;
39 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
40
41 typedef /unspecified/ iterator;
42 typedef /unspecified/ const_iterator;
43 typedef /unspecified/ local_iterator;
44 typedef /unspecified/ const_local_iterator;
45
46 typedef unspecified node_type; // C++17
47 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
48
49 unordered_map()
50 noexcept(
51 is_nothrow_default_constructible<hasher>::value &&
52 is_nothrow_default_constructible<key_equal>::value &&
53 is_nothrow_default_constructible<allocator_type>::value);
54 explicit unordered_map(size_type n, const hasher& hf = hasher(),
55 const key_equal& eql = key_equal(),
56 const allocator_type& a = allocator_type());
57 template <class InputIterator>
58 unordered_map(InputIterator f, InputIterator l,
59 size_type n = 0, const hasher& hf = hasher(),
60 const key_equal& eql = key_equal(),
61 const allocator_type& a = allocator_type());
62 template<container-compatible-range<value_type> R>
63 unordered_map(from_range_t, R&& rg, size_type n = see below,
64 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
65 const allocator_type& a = allocator_type()); // C++23
66
67 explicit unordered_map(const allocator_type&);
68 unordered_map(const unordered_map&);
69 unordered_map(const unordered_map&, const Allocator&);
70 unordered_map(unordered_map&&)
71 noexcept(
72 is_nothrow_move_constructible<hasher>::value &&
73 is_nothrow_move_constructible<key_equal>::value &&
74 is_nothrow_move_constructible<allocator_type>::value);
75 unordered_map(unordered_map&&, const Allocator&);
76 unordered_map(initializer_list<value_type>, size_type n = 0,
77 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
78 const allocator_type& a = allocator_type());
79 unordered_map(size_type n, const allocator_type& a)
80 : unordered_map(n, hasher(), key_equal(), a) {} // C++14
81 unordered_map(size_type n, const hasher& hf, const allocator_type& a)
82 : unordered_map(n, hf, key_equal(), a) {} // C++14
83 template <class InputIterator>
84 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
85 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14
86 template <class InputIterator>
87 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
88 const allocator_type& a)
89 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14
90 template<container-compatible-range<value_type> R>
91 unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a)
92 : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
93 template<container-compatible-range<value_type> R>
94 unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
95 : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
96 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)
97 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14
98 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
99 const allocator_type& a)
100 : unordered_map(il, n, hf, key_equal(), a) {} // C++14
101 ~unordered_map();
102 unordered_map& operator=(const unordered_map&);
103 unordered_map& operator=(unordered_map&&)
104 noexcept(
105 allocator_type::propagate_on_container_move_assignment::value &&
106 is_nothrow_move_assignable<allocator_type>::value &&
107 is_nothrow_move_assignable<hasher>::value &&
108 is_nothrow_move_assignable<key_equal>::value);
109 unordered_map& operator=(initializer_list<value_type>);
110
111 allocator_type get_allocator() const noexcept;
112
113 bool empty() const noexcept;
114 size_type size() const noexcept;
115 size_type max_size() const noexcept;
116
117 iterator begin() noexcept;
118 iterator end() noexcept;
119 const_iterator begin() const noexcept;
120 const_iterator end() const noexcept;
121 const_iterator cbegin() const noexcept;
122 const_iterator cend() const noexcept;
123
124 template <class... Args>
125 pair<iterator, bool> emplace(Args&&... args);
126 template <class... Args>
127 iterator emplace_hint(const_iterator position, Args&&... args);
128 pair<iterator, bool> insert(const value_type& obj);
129 template <class P>
130 pair<iterator, bool> insert(P&& obj);
131 iterator insert(const_iterator hint, const value_type& obj);
132 template <class P>
133 iterator insert(const_iterator hint, P&& obj);
134 template <class InputIterator>
135 void insert(InputIterator first, InputIterator last);
136 template<container-compatible-range<value_type> R>
137 void insert_range(R&& rg); // C++23
138 void insert(initializer_list<value_type>);
139
140 node_type extract(const_iterator position); // C++17
141 node_type extract(const key_type& x); // C++17
142 insert_return_type insert(node_type&& nh); // C++17
143 iterator insert(const_iterator hint, node_type&& nh); // C++17
144
145 template <class... Args>
146 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
147 template <class... Args>
148 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
149 template <class... Args>
150 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
151 template <class... Args>
152 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
153 template <class M>
154 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
155 template <class M>
156 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
157 template <class M>
158 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
159 template <class M>
160 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
161
162 iterator erase(const_iterator position);
163 iterator erase(iterator position); // C++14
164 size_type erase(const key_type& k);
165 iterator erase(const_iterator first, const_iterator last);
166 void clear() noexcept;
167
168 template<class H2, class P2>
169 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17
170 template<class H2, class P2>
171 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17
172 template<class H2, class P2>
173 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17
174 template<class H2, class P2>
175 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17
176
177 void swap(unordered_map&)
178 noexcept(
179 (!allocator_type::propagate_on_container_swap::value ||
180 __is_nothrow_swappable<allocator_type>::value) &&
181 __is_nothrow_swappable<hasher>::value &&
182 __is_nothrow_swappable<key_equal>::value);
183
184 hasher hash_function() const;
185 key_equal key_eq() const;
186
187 iterator find(const key_type& k);
188 const_iterator find(const key_type& k) const;
189 template<typename K>
190 iterator find(const K& x); // C++20
191 template<typename K>
192 const_iterator find(const K& x) const; // C++20
193 size_type count(const key_type& k) const;
194 template<typename K>
195 size_type count(const K& k) const; // C++20
196 bool contains(const key_type& k) const; // C++20
197 template<typename K>
198 bool contains(const K& k) const; // C++20
199 pair<iterator, iterator> equal_range(const key_type& k);
200 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
201 template<typename K>
202 pair<iterator, iterator> equal_range(const K& k); // C++20
203 template<typename K>
204 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
205
206 mapped_type& operator[](const key_type& k);
207 mapped_type& operator[](key_type&& k);
208
209 mapped_type& at(const key_type& k);
210 const mapped_type& at(const key_type& k) const;
211
212 size_type bucket_count() const noexcept;
213 size_type max_bucket_count() const noexcept;
214
215 size_type bucket_size(size_type n) const;
216 size_type bucket(const key_type& k) const;
217
218 local_iterator begin(size_type n);
219 local_iterator end(size_type n);
220 const_local_iterator begin(size_type n) const;
221 const_local_iterator end(size_type n) const;
222 const_local_iterator cbegin(size_type n) const;
223 const_local_iterator cend(size_type n) const;
224
225 float load_factor() const noexcept;
226 float max_load_factor() const noexcept;
227 void max_load_factor(float z);
228 void rehash(size_type n);
229 void reserve(size_type n);
230 };
231
232 template<class InputIterator,
233 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,
234 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
235 unordered_map(InputIterator, InputIterator, typename see below::size_type = see below,
236 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
237 -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
238 Allocator>; // C++17
239
240 template<ranges::input_range R, class Hash = hash<range-key-type<R>>,
241 class Pred = equal_to<range-key-type<R>>,
242 class Allocator = allocator<range-to-alloc-type<R>>>
243 unordered_map(from_range_t, R&&, typename see below::size_type = see below,
244 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
245 -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23
246
247 template<class Key, class T, class Hash = hash<Key>,
248 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
249 unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,
250 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
251 -> unordered_map<Key, T, Hash, Pred, Allocator>; // C++17
252
253 template<class InputIterator, class Allocator>
254 unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)
255 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
256 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
257
258 template<class InputIterator, class Allocator>
259 unordered_map(InputIterator, InputIterator, Allocator)
260 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
261 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
262
263 template<class InputIterator, class Hash, class Allocator>
264 unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
265 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
266 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
267
268 template<ranges::input_range R, class Allocator>
269 unordered_map(from_range_t, R&&, typename see below::size_type, Allocator)
270 -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
271 equal_to<range-key-type<R>>, Allocator>; // C++23
272
273 template<ranges::input_range R, class Allocator>
274 unordered_map(from_range_t, R&&, Allocator)
275 -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
276 equal_to<range-key-type<R>>, Allocator>; // C++23
277
278 template<ranges::input_range R, class Hash, class Allocator>
279 unordered_map(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
280 -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash,
281 equal_to<range-key-type<R>>, Allocator>; // C++23
282
283 template<class Key, class T, typename Allocator>
284 unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)
285 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
286
287 template<class Key, class T, typename Allocator>
288 unordered_map(initializer_list<pair<const Key, T>>, Allocator)
289 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
290
291 template<class Key, class T, class Hash, class Allocator>
292 unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, Allocator)
293 -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>; // C++17
294
295 template <class Key, class T, class Hash, class Pred, class Alloc>
296 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
297 unordered_map<Key, T, Hash, Pred, Alloc>& y)
298 noexcept(noexcept(x.swap(y)));
299
300 template <class Key, class T, class Hash, class Pred, class Alloc>
301 bool
302 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
303 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
304
305 template <class Key, class T, class Hash, class Pred, class Alloc>
306 bool
307 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
308 const unordered_map<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20
309
310 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
311 class Alloc = allocator<pair<const Key, T>>>
312 class unordered_multimap
313 {
314 public:
315 // types
316 typedef Key key_type;
317 typedef T mapped_type;
318 typedef Hash hasher;
319 typedef Pred key_equal;
320 typedef Alloc allocator_type;
321 typedef pair<const key_type, mapped_type> value_type;
322 typedef value_type& reference;
323 typedef const value_type& const_reference;
324 typedef typename allocator_traits<allocator_type>::pointer pointer;
325 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
326 typedef typename allocator_traits<allocator_type>::size_type size_type;
327 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
328
329 typedef /unspecified/ iterator;
330 typedef /unspecified/ const_iterator;
331 typedef /unspecified/ local_iterator;
332 typedef /unspecified/ const_local_iterator;
333
334 typedef unspecified node_type; // C++17
335
336 unordered_multimap()
337 noexcept(
338 is_nothrow_default_constructible<hasher>::value &&
339 is_nothrow_default_constructible<key_equal>::value &&
340 is_nothrow_default_constructible<allocator_type>::value);
341 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
342 const key_equal& eql = key_equal(),
343 const allocator_type& a = allocator_type());
344 template <class InputIterator>
345 unordered_multimap(InputIterator f, InputIterator l,
346 size_type n = 0, const hasher& hf = hasher(),
347 const key_equal& eql = key_equal(),
348 const allocator_type& a = allocator_type());
349 template<container-compatible-range<value_type> R>
350 unordered_multimap(from_range_t, R&& rg, size_type n = see below,
351 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
352 const allocator_type& a = allocator_type()); // C++23
353 explicit unordered_multimap(const allocator_type&);
354 unordered_multimap(const unordered_multimap&);
355 unordered_multimap(const unordered_multimap&, const Allocator&);
356 unordered_multimap(unordered_multimap&&)
357 noexcept(
358 is_nothrow_move_constructible<hasher>::value &&
359 is_nothrow_move_constructible<key_equal>::value &&
360 is_nothrow_move_constructible<allocator_type>::value);
361 unordered_multimap(unordered_multimap&&, const Allocator&);
362 unordered_multimap(initializer_list<value_type>, size_type n = 0,
363 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
364 const allocator_type& a = allocator_type());
365 unordered_multimap(size_type n, const allocator_type& a)
366 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14
367 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
368 : unordered_multimap(n, hf, key_equal(), a) {} // C++14
369 template <class InputIterator>
370 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
371 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14
372 template <class InputIterator>
373 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
374 const allocator_type& a)
375 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14
376 template<container-compatible-range<value_type> R>
377 unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a)
378 : unordered_multimap(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
379 template<container-compatible-range<value_type> R>
380 unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
381 : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
382 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)
383 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14
384 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
385 const allocator_type& a)
386 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14
387 ~unordered_multimap();
388 unordered_multimap& operator=(const unordered_multimap&);
389 unordered_multimap& operator=(unordered_multimap&&)
390 noexcept(
391 allocator_type::propagate_on_container_move_assignment::value &&
392 is_nothrow_move_assignable<allocator_type>::value &&
393 is_nothrow_move_assignable<hasher>::value &&
394 is_nothrow_move_assignable<key_equal>::value);
395 unordered_multimap& operator=(initializer_list<value_type>);
396
397 allocator_type get_allocator() const noexcept;
398
399 bool empty() const noexcept;
400 size_type size() const noexcept;
401 size_type max_size() const noexcept;
402
403 iterator begin() noexcept;
404 iterator end() noexcept;
405 const_iterator begin() const noexcept;
406 const_iterator end() const noexcept;
407 const_iterator cbegin() const noexcept;
408 const_iterator cend() const noexcept;
409
410 template <class... Args>
411 iterator emplace(Args&&... args);
412 template <class... Args>
413 iterator emplace_hint(const_iterator position, Args&&... args);
414 iterator insert(const value_type& obj);
415 template <class P>
416 iterator insert(P&& obj);
417 iterator insert(const_iterator hint, const value_type& obj);
418 template <class P>
419 iterator insert(const_iterator hint, P&& obj);
420 template <class InputIterator>
421 void insert(InputIterator first, InputIterator last);
422 template<container-compatible-range<value_type> R>
423 void insert_range(R&& rg); // C++23
424 void insert(initializer_list<value_type>);
425
426 node_type extract(const_iterator position); // C++17
427 node_type extract(const key_type& x); // C++17
428 iterator insert(node_type&& nh); // C++17
429 iterator insert(const_iterator hint, node_type&& nh); // C++17
430
431 iterator erase(const_iterator position);
432 iterator erase(iterator position); // C++14
433 size_type erase(const key_type& k);
434 iterator erase(const_iterator first, const_iterator last);
435 void clear() noexcept;
436
437 template<class H2, class P2>
438 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17
439 template<class H2, class P2>
440 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17
441 template<class H2, class P2>
442 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17
443 template<class H2, class P2>
444 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17
445
446 void swap(unordered_multimap&)
447 noexcept(
448 (!allocator_type::propagate_on_container_swap::value ||
449 __is_nothrow_swappable<allocator_type>::value) &&
450 __is_nothrow_swappable<hasher>::value &&
451 __is_nothrow_swappable<key_equal>::value);
452
453 hasher hash_function() const;
454 key_equal key_eq() const;
455
456 iterator find(const key_type& k);
457 const_iterator find(const key_type& k) const;
458 template<typename K>
459 iterator find(const K& x); // C++20
460 template<typename K>
461 const_iterator find(const K& x) const; // C++20
462 size_type count(const key_type& k) const;
463 template<typename K>
464 size_type count(const K& k) const; // C++20
465 bool contains(const key_type& k) const; // C++20
466 template<typename K>
467 bool contains(const K& k) const; // C++20
468 pair<iterator, iterator> equal_range(const key_type& k);
469 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
470 template<typename K>
471 pair<iterator, iterator> equal_range(const K& k); // C++20
472 template<typename K>
473 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
474
475 size_type bucket_count() const noexcept;
476 size_type max_bucket_count() const noexcept;
477
478 size_type bucket_size(size_type n) const;
479 size_type bucket(const key_type& k) const;
480
481 local_iterator begin(size_type n);
482 local_iterator end(size_type n);
483 const_local_iterator begin(size_type n) const;
484 const_local_iterator end(size_type n) const;
485 const_local_iterator cbegin(size_type n) const;
486 const_local_iterator cend(size_type n) const;
487
488 float load_factor() const noexcept;
489 float max_load_factor() const noexcept;
490 void max_load_factor(float z);
491 void rehash(size_type n);
492 void reserve(size_type n);
493 };
494
495 template<class InputIterator,
496 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,
497 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
498 unordered_multimap(InputIterator, InputIterator, typename see below::size_type = see below,
499 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
500 -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
501 Allocator>; // C++17
502
503 template<ranges::input_range R, class Hash = hash<range-key-type<R>>,
504 class Pred = equal_to<range-key-type<R>>,
505 class Allocator = allocator<range-to-alloc-type<R>>>
506 unordered_multimap(from_range_t, R&&, typename see below::size_type = see below,
507 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
508 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23
509
510 template<class Key, class T, class Hash = hash<Key>,
511 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
512 unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,
513 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
514 -> unordered_multimap<Key, T, Hash, Pred, Allocator>; // C++17
515
516 template<class InputIterator, class Allocator>
517 unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)
518 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
519 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
520
521 template<class InputIterator, class Allocator>
522 unordered_multimap(InputIterator, InputIterator, Allocator)
523 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
524 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
525
526 template<class InputIterator, class Hash, class Allocator>
527 unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
528 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
529 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
530
531 template<ranges::input_range R, class Allocator>
532 unordered_multimap(from_range_t, R&&, typename see below::size_type, Allocator)
533 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
534 equal_to<range-key-type<R>>, Allocator>; // C++23
535
536 template<ranges::input_range R, class Allocator>
537 unordered_multimap(from_range_t, R&&, Allocator)
538 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
539 equal_to<range-key-type<R>>, Allocator>; // C++23
540
541 template<ranges::input_range R, class Hash, class Allocator>
542 unordered_multimap(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
543 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash,
544 equal_to<range-key-type<R>>, Allocator>; // C++23
545
546 template<class Key, class T, typename Allocator>
547 unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)
548 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
549
550 template<class Key, class T, typename Allocator>
551 unordered_multimap(initializer_list<pair<const Key, T>>, Allocator)
552 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
553
554 template<class Key, class T, class Hash, class Allocator>
555 unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash,
556 Allocator)
557 -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>; // C++17
558
559 template <class Key, class T, class Hash, class Pred, class Alloc>
560 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
561 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
562 noexcept(noexcept(x.swap(y)));
563
564 template <class K, class T, class H, class P, class A, class Predicate>
565 typename unordered_map<K, T, H, P, A>::size_type
566 erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred); // C++20
567
568 template <class K, class T, class H, class P, class A, class Predicate>
569 typename unordered_multimap<K, T, H, P, A>::size_type
570 erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred); // C++20
571
572 template <class Key, class T, class Hash, class Pred, class Alloc>
573 bool
574 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
575 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
576
577 template <class Key, class T, class Hash, class Pred, class Alloc>
578 bool
579 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
580 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20
581
582 } // std
583
584 */
585
586 #include <__cxx03/__algorithm/is_permutation.h>
587 #include <__cxx03/__assert>
588 #include <__cxx03/__config>
589 #include <__cxx03/__functional/operations.h>
590 #include <__cxx03/__hash_table>
591 #include <__cxx03/__iterator/distance.h>
592 #include <__cxx03/__iterator/erase_if_container.h>
593 #include <__cxx03/__iterator/iterator_traits.h>
594 #include <__cxx03/__memory/addressof.h>
595 #include <__cxx03/__memory/allocator.h>
596 #include <__cxx03/__type_traits/is_allocator.h>
597 #include <__cxx03/__type_traits/type_identity.h>
598 #include <__cxx03/__utility/forward.h>
599 #include <__cxx03/stdexcept>
600 #include <__cxx03/version>
601
602 // standard-mandated includes
603
604 // [iterator.range]
605 #include <__cxx03/__iterator/access.h>
606
607 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
608 # pragma GCC system_header
609 #endif
610
611 _LIBCPP_PUSH_MACROS
612 #include <__cxx03/__undef_macros>
613
614 _LIBCPP_BEGIN_NAMESPACE_STD
615
616 template <class _Key,
617 class _Cp,
618 class _Hash,
619 class _Pred,
620 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
621 class __unordered_map_hasher : private _Hash {
622 public:
623 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() : _Hash() {}
624 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) : _Hash(__h) {}
625 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return *this; }
626 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const {
627 return static_cast<const _Hash&>(*this)(__x.__get_value().first);
628 }
629 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return static_cast<const _Hash&>(*this)(__x); }
630 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) {
631 using std::swap;
632 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
633 }
634 };
635
636 template <class _Key, class _Cp, class _Hash, class _Pred>
637 class __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> {
638 _Hash __hash_;
639
640 public:
641 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() : __hash_() {}
642 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) : __hash_(__h) {}
643 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; }
644 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.__get_value().first); }
645 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); }
646 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) {
647 using std::swap;
648 swap(__hash_, __y.__hash_);
649 }
650 };
651
652 template <class _Key, class _Cp, class _Hash, class _Pred, bool __b>
653 inline _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x,
654 __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) {
655 __x.swap(__y);
656 }
657
658 template <class _Key,
659 class _Cp,
660 class _Pred,
661 class _Hash,
662 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>
663 class __unordered_map_equal : private _Pred {
664 public:
665 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() : _Pred() {}
666 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) : _Pred(__p) {}
667 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return *this; }
668 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {
669 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);
670 }
671 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {
672 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);
673 }
674 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {
675 return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);
676 }
677 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) {
678 using std::swap;
679 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
680 }
681 };
682
683 template <class _Key, class _Cp, class _Pred, class _Hash>
684 class __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> {
685 _Pred __pred_;
686
687 public:
688 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() : __pred_() {}
689 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) : __pred_(__p) {}
690 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; }
691 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {
692 return __pred_(__x.__get_value().first, __y.__get_value().first);
693 }
694 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {
695 return __pred_(__x.__get_value().first, __y);
696 }
697 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {
698 return __pred_(__x, __y.__get_value().first);
699 }
700 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) {
701 using std::swap;
702 swap(__pred_, __y.__pred_);
703 }
704 };
705
706 template <class _Key, class _Cp, class _Pred, class _Hash, bool __b>
707 inline _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x,
708 __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y) {
709 __x.swap(__y);
710 }
711
712 template <class _Alloc>
713 class __hash_map_node_destructor {
714 typedef _Alloc allocator_type;
715 typedef allocator_traits<allocator_type> __alloc_traits;
716
717 public:
718 typedef typename __alloc_traits::pointer pointer;
719
720 private:
721 allocator_type& __na_;
722
723 public:
724 bool __first_constructed;
725 bool __second_constructed;
726
727 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;
728
729 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
730 : __na_(__na),
731 __first_constructed(false),
732 __second_constructed(false) {}
733
734 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
735 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
736 const_cast<bool&>(__x.__value_constructed) = false;
737 }
738
739 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
740 if (__second_constructed)
741 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().second));
742 if (__first_constructed)
743 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().first));
744 if (__p)
745 __alloc_traits::deallocate(__na_, __p, 1);
746 }
747 };
748
749 template <class _Key, class _Tp>
750 struct __hash_value_type {
751 typedef _Key key_type;
752 typedef _Tp mapped_type;
753 typedef pair<const key_type, mapped_type> value_type;
754
755 private:
756 value_type __cc_;
757
758 public:
759 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }
760 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }
761
762 ~__hash_value_type() = delete;
763 };
764
765 template <class _HashIterator>
766 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator {
767 _HashIterator __i_;
768
769 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
770
771 public:
772 typedef forward_iterator_tag iterator_category;
773 typedef typename _NodeTypes::__map_value_type value_type;
774 typedef typename _NodeTypes::difference_type difference_type;
775 typedef value_type& reference;
776 typedef typename _NodeTypes::__map_value_type_pointer pointer;
777
778 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {}
779
780 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
781
782 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
783 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
784
785 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {
786 ++__i_;
787 return *this;
788 }
789 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {
790 __hash_map_iterator __t(*this);
791 ++(*this);
792 return __t;
793 }
794
795 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
796 return __x.__i_ == __y.__i_;
797 }
798 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
799 return __x.__i_ != __y.__i_;
800 }
801
802 template <class, class, class, class, class>
803 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
804 template <class, class, class, class, class>
805 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
806 template <class>
807 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
808 template <class>
809 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
810 template <class>
811 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
812 };
813
814 template <class _HashIterator>
815 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator {
816 _HashIterator __i_;
817
818 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
819
820 public:
821 typedef forward_iterator_tag iterator_category;
822 typedef typename _NodeTypes::__map_value_type value_type;
823 typedef typename _NodeTypes::difference_type difference_type;
824 typedef const value_type& reference;
825 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
826
827 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {}
828
829 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
830 _LIBCPP_HIDE_FROM_ABI
831 __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT
832 : __i_(__i.__i_) {}
833
834 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
835 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
836
837 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {
838 ++__i_;
839 return *this;
840 }
841 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {
842 __hash_map_const_iterator __t(*this);
843 ++(*this);
844 return __t;
845 }
846
847 friend _LIBCPP_HIDE_FROM_ABI bool
848 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
849 return __x.__i_ == __y.__i_;
850 }
851 friend _LIBCPP_HIDE_FROM_ABI bool
852 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
853 return __x.__i_ != __y.__i_;
854 }
855
856 template <class, class, class, class, class>
857 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
858 template <class, class, class, class, class>
859 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
860 template <class>
861 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
862 template <class>
863 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
864 };
865
866 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
867 class unordered_multimap;
868
869 template <class _Key,
870 class _Tp,
871 class _Hash = hash<_Key>,
872 class _Pred = equal_to<_Key>,
873 class _Alloc = allocator<pair<const _Key, _Tp> > >
874 class _LIBCPP_TEMPLATE_VIS unordered_map {
875 public:
876 // types
877 typedef _Key key_type;
878 typedef _Tp mapped_type;
879 typedef __type_identity_t<_Hash> hasher;
880 typedef __type_identity_t<_Pred> key_equal;
881 typedef __type_identity_t<_Alloc> allocator_type;
882 typedef pair<const key_type, mapped_type> value_type;
883 typedef value_type& reference;
884 typedef const value_type& const_reference;
885 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
886 "Allocator::value_type must be same type as value_type");
887
888 private:
889 typedef __hash_value_type<key_type, mapped_type> __value_type;
890 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
891 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
892 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
893
894 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
895
896 __table __table_;
897
898 typedef typename __table::_NodeTypes _NodeTypes;
899 typedef typename __table::__node_pointer __node_pointer;
900 typedef typename __table::__node_const_pointer __node_const_pointer;
901 typedef typename __table::__node_traits __node_traits;
902 typedef typename __table::__node_allocator __node_allocator;
903 typedef typename __table::__node __node;
904 typedef __hash_map_node_destructor<__node_allocator> _Dp;
905 typedef unique_ptr<__node, _Dp> __node_holder;
906 typedef allocator_traits<allocator_type> __alloc_traits;
907
908 static_assert(__check_valid_allocator<allocator_type>::value, "");
909
910 static_assert(is_same<typename __table::__container_value_type, value_type>::value, "");
911 static_assert(is_same<typename __table::__node_value_type, __value_type>::value, "");
912
913 public:
914 typedef typename __alloc_traits::pointer pointer;
915 typedef typename __alloc_traits::const_pointer const_pointer;
916 typedef typename __table::size_type size_type;
917 typedef typename __table::difference_type difference_type;
918
919 typedef __hash_map_iterator<typename __table::iterator> iterator;
920 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
921 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
922 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
923
924 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
925 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
926 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
927 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
928
929 _LIBCPP_HIDE_FROM_ABI unordered_map() {}
930 explicit _LIBCPP_HIDE_FROM_ABI
931 unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
932 _LIBCPP_HIDE_FROM_ABI
933 unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
934 template <class _InputIterator>
935 _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last);
936 template <class _InputIterator>
937 _LIBCPP_HIDE_FROM_ABI
938 unordered_map(_InputIterator __first,
939 _InputIterator __last,
940 size_type __n,
941 const hasher& __hf = hasher(),
942 const key_equal& __eql = key_equal());
943 template <class _InputIterator>
944 _LIBCPP_HIDE_FROM_ABI unordered_map(
945 _InputIterator __first,
946 _InputIterator __last,
947 size_type __n,
948 const hasher& __hf,
949 const key_equal& __eql,
950 const allocator_type& __a);
951
952 _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a);
953 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u);
954 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a);
955
956 _LIBCPP_HIDE_FROM_ABI ~unordered_map() {
957 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
958 }
959
960 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) {
961 if (this != std::addressof(__u)) {
962 __table_.clear();
963 __table_.hash_function() = __u.__table_.hash_function();
964 __table_.key_eq() = __u.__table_.key_eq();
965 __table_.max_load_factor() = __u.__table_.max_load_factor();
966 __table_.__copy_assign_alloc(__u.__table_);
967 insert(__u.begin(), __u.end());
968 }
969 return *this;
970 }
971
972 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
973 return allocator_type(__table_.__node_alloc());
974 }
975
976 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
977 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
978 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
979
980 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
981 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
982 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
983 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
984 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
985 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
986
987 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
988
989 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
990
991 template <class _InputIterator>
992 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
993
994 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
995 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
996 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
997 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
998 return __table_.erase(__first.__i_, __last.__i_);
999 }
1000 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
1001
1002 _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) { __table_.swap(__u.__table_); }
1003
1004 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
1005 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
1006
1007 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1008 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
1009
1010 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
1011
1012 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1013 return __table_.__equal_range_unique(__k);
1014 }
1015 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1016 return __table_.__equal_range_unique(__k);
1017 }
1018
1019 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
1020
1021 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
1022 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
1023
1024 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1025 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
1026
1027 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1028 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
1029
1030 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1031 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1032 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1033 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1034 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1035 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
1036
1037 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1038 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1039 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1040 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
1041 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
1042
1043 private:
1044 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1045 };
1046
1047 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1048 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql)
1049 : __table_(__hf, __eql) {
1050 __table_.__rehash_unique(__n);
1051 }
1052
1053 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1054 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1055 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1056 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1057 __table_.__rehash_unique(__n);
1058 }
1059
1060 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1061 inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a)
1062 : __table_(typename __table::allocator_type(__a)) {}
1063
1064 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1065 template <class _InputIterator>
1066 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) {
1067 insert(__first, __last);
1068 }
1069
1070 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1071 template <class _InputIterator>
1072 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1073 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1074 : __table_(__hf, __eql) {
1075 __table_.__rehash_unique(__n);
1076 insert(__first, __last);
1077 }
1078
1079 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1080 template <class _InputIterator>
1081 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1082 _InputIterator __first,
1083 _InputIterator __last,
1084 size_type __n,
1085 const hasher& __hf,
1086 const key_equal& __eql,
1087 const allocator_type& __a)
1088 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1089 __table_.__rehash_unique(__n);
1090 insert(__first, __last);
1091 }
1092
1093 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1094 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u) : __table_(__u.__table_) {
1095 __table_.__rehash_unique(__u.bucket_count());
1096 insert(__u.begin(), __u.end());
1097 }
1098
1099 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1100 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a)
1101 : __table_(__u.__table_, typename __table::allocator_type(__a)) {
1102 __table_.__rehash_unique(__u.bucket_count());
1103 insert(__u.begin(), __u.end());
1104 }
1105
1106 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1107 template <class _InputIterator>
1108 inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1109 for (; __first != __last; ++__first)
1110 __table_.__insert_unique(*__first);
1111 }
1112
1113 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1114 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1115 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) {
1116 __node_allocator& __na = __table_.__node_alloc();
1117 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1118 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().first), __k);
1119 __h.get_deleter().__first_constructed = true;
1120 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().second));
1121 __h.get_deleter().__second_constructed = true;
1122 return __h;
1123 }
1124
1125 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1126 _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
1127 iterator __i = find(__k);
1128 if (__i != end())
1129 return __i->second;
1130 __node_holder __h = __construct_node_with_key(__k);
1131 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1132 __h.release();
1133 return __r.first->second;
1134 }
1135
1136 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1137 _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) {
1138 iterator __i = find(__k);
1139 if (__i == end())
1140 __throw_out_of_range("unordered_map::at: key not found");
1141 return __i->second;
1142 }
1143
1144 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1145 const _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const {
1146 const_iterator __i = find(__k);
1147 if (__i == end())
1148 __throw_out_of_range("unordered_map::at: key not found");
1149 return __i->second;
1150 }
1151
1152 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1153 inline _LIBCPP_HIDE_FROM_ABI void
1154 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1155 __x.swap(__y);
1156 }
1157
1158 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1159 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1160 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1161 if (__x.size() != __y.size())
1162 return false;
1163 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1164 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
1165 const_iterator __j = __y.find(__i->first);
1166 if (__j == __ey || !(*__i == *__j))
1167 return false;
1168 }
1169 return true;
1170 }
1171
1172 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1173 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1174 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1175 return !(__x == __y);
1176 }
1177
1178 template <class _Key,
1179 class _Tp,
1180 class _Hash = hash<_Key>,
1181 class _Pred = equal_to<_Key>,
1182 class _Alloc = allocator<pair<const _Key, _Tp> > >
1183 class _LIBCPP_TEMPLATE_VIS unordered_multimap {
1184 public:
1185 // types
1186 typedef _Key key_type;
1187 typedef _Tp mapped_type;
1188 typedef __type_identity_t<_Hash> hasher;
1189 typedef __type_identity_t<_Pred> key_equal;
1190 typedef __type_identity_t<_Alloc> allocator_type;
1191 typedef pair<const key_type, mapped_type> value_type;
1192 typedef value_type& reference;
1193 typedef const value_type& const_reference;
1194 static_assert(__check_valid_allocator<allocator_type>::value, "");
1195 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1196 "Allocator::value_type must be same type as value_type");
1197
1198 private:
1199 typedef __hash_value_type<key_type, mapped_type> __value_type;
1200 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
1201 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
1202 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1203
1204 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
1205
1206 __table __table_;
1207
1208 typedef typename __table::_NodeTypes _NodeTypes;
1209 typedef typename __table::__node_traits __node_traits;
1210 typedef typename __table::__node_allocator __node_allocator;
1211 typedef typename __table::__node __node;
1212 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1213 typedef unique_ptr<__node, _Dp> __node_holder;
1214 typedef allocator_traits<allocator_type> __alloc_traits;
1215 static_assert(is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value,
1216 "Allocator uses different size_type for different types");
1217
1218 public:
1219 typedef typename __alloc_traits::pointer pointer;
1220 typedef typename __alloc_traits::const_pointer const_pointer;
1221 typedef typename __table::size_type size_type;
1222 typedef typename __table::difference_type difference_type;
1223
1224 typedef __hash_map_iterator<typename __table::iterator> iterator;
1225 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1226 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1227 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1228
1229 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1230 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1231 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1232 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1233
1234 _LIBCPP_HIDE_FROM_ABI unordered_multimap() {}
1235 explicit _LIBCPP_HIDE_FROM_ABI
1236 unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1237 _LIBCPP_HIDE_FROM_ABI
1238 unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1239 template <class _InputIterator>
1240 _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last);
1241 template <class _InputIterator>
1242 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1243 _InputIterator __first,
1244 _InputIterator __last,
1245 size_type __n,
1246 const hasher& __hf = hasher(),
1247 const key_equal& __eql = key_equal());
1248 template <class _InputIterator>
1249 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1250 _InputIterator __first,
1251 _InputIterator __last,
1252 size_type __n,
1253 const hasher& __hf,
1254 const key_equal& __eql,
1255 const allocator_type& __a);
1256
1257 _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a);
1258 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u);
1259 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1260
1261 _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() {
1262 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
1263 }
1264
1265 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) {
1266 if (this != std::addressof(__u)) {
1267 __table_.clear();
1268 __table_.hash_function() = __u.__table_.hash_function();
1269 __table_.key_eq() = __u.__table_.key_eq();
1270 __table_.max_load_factor() = __u.__table_.max_load_factor();
1271 __table_.__copy_assign_alloc(__u.__table_);
1272 insert(__u.begin(), __u.end());
1273 }
1274 return *this;
1275 }
1276
1277 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1278 return allocator_type(__table_.__node_alloc());
1279 }
1280
1281 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1282 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1283 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1284
1285 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1286 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1287 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1288 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1289 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1290 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1291
1292 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
1293
1294 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
1295 return __table_.__insert_multi(__p.__i_, __x);
1296 }
1297
1298 template <class _InputIterator>
1299 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
1300
1301 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
1302 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
1303 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
1304 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1305 return __table_.erase(__first.__i_, __last.__i_);
1306 }
1307 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
1308
1309 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) { __table_.swap(__u.__table_); }
1310
1311 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
1312 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
1313
1314 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1315 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
1316
1317 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
1318
1319 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1320 return __table_.__equal_range_multi(__k);
1321 }
1322 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1323 return __table_.__equal_range_multi(__k);
1324 }
1325
1326 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1327 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
1328
1329 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1330 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
1331
1332 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1333 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1334 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1335 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1336 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1337 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
1338
1339 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1340 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1341 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1342 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
1343 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
1344 };
1345
1346 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1347 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1348 size_type __n, const hasher& __hf, const key_equal& __eql)
1349 : __table_(__hf, __eql) {
1350 __table_.__rehash_multi(__n);
1351 }
1352
1353 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1354 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1355 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1356 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1357 __table_.__rehash_multi(__n);
1358 }
1359
1360 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1361 template <class _InputIterator>
1362 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) {
1363 insert(__first, __last);
1364 }
1365
1366 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1367 template <class _InputIterator>
1368 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1369 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1370 : __table_(__hf, __eql) {
1371 __table_.__rehash_multi(__n);
1372 insert(__first, __last);
1373 }
1374
1375 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1376 template <class _InputIterator>
1377 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1378 _InputIterator __first,
1379 _InputIterator __last,
1380 size_type __n,
1381 const hasher& __hf,
1382 const key_equal& __eql,
1383 const allocator_type& __a)
1384 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1385 __table_.__rehash_multi(__n);
1386 insert(__first, __last);
1387 }
1388
1389 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1390 inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a)
1391 : __table_(typename __table::allocator_type(__a)) {}
1392
1393 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1394 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const unordered_multimap& __u)
1395 : __table_(__u.__table_) {
1396 __table_.__rehash_multi(__u.bucket_count());
1397 insert(__u.begin(), __u.end());
1398 }
1399
1400 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1401 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1402 const unordered_multimap& __u, const allocator_type& __a)
1403 : __table_(__u.__table_, typename __table::allocator_type(__a)) {
1404 __table_.__rehash_multi(__u.bucket_count());
1405 insert(__u.begin(), __u.end());
1406 }
1407
1408 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1409 template <class _InputIterator>
1410 inline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1411 for (; __first != __last; ++__first)
1412 __table_.__insert_multi(*__first);
1413 }
1414
1415 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1416 inline _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1417 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1418 __x.swap(__y);
1419 }
1420
1421 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1422 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1423 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1424 if (__x.size() != __y.size())
1425 return false;
1426 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1427 typedef pair<const_iterator, const_iterator> _EqRng;
1428 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
1429 _EqRng __xeq = __x.equal_range(__i->first);
1430 _EqRng __yeq = __y.equal_range(__i->first);
1431 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
1432 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1433 return false;
1434 __i = __xeq.second;
1435 }
1436 return true;
1437 }
1438
1439 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1440 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1441 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1442 return !(__x == __y);
1443 }
1444
1445 _LIBCPP_END_NAMESPACE_STD
1446
1447 _LIBCPP_POP_MACROS
1448
1449 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)
1450 # include <__cxx03/algorithm>
1451 # include <__cxx03/cstdlib>
1452 # include <__cxx03/iterator>
1453 # include <__cxx03/type_traits>
1454 #endif
1455
1456 #endif // _LIBCPP___CXX03_UNORDERED_MAP