2 //===-------------------------- unordered_map -----------------------------===//
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
8 //===----------------------------------------------------------------------===//
10 #ifndef _LIBCPP_UNORDERED_MAP
11 #define _LIBCPP_UNORDERED_MAP
15 unordered_map synopsis
17 #include <initializer_list>
22 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
23 class Alloc = allocator<pair<const Key, T>>>
29 typedef T mapped_type;
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;
41 typedef /unspecified/ iterator;
42 typedef /unspecified/ const_iterator;
43 typedef /unspecified/ local_iterator;
44 typedef /unspecified/ const_local_iterator;
46 typedef unspecified node_type; // C++17
47 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
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 explicit unordered_map(const allocator_type&);
63 unordered_map(const unordered_map&);
64 unordered_map(const unordered_map&, const Allocator&);
65 unordered_map(unordered_map&&)
67 is_nothrow_move_constructible<hasher>::value &&
68 is_nothrow_move_constructible<key_equal>::value &&
69 is_nothrow_move_constructible<allocator_type>::value);
70 unordered_map(unordered_map&&, const Allocator&);
71 unordered_map(initializer_list<value_type>, size_type n = 0,
72 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
73 const allocator_type& a = allocator_type());
74 unordered_map(size_type n, const allocator_type& a)
75 : unordered_map(n, hasher(), key_equal(), a) {} // C++14
76 unordered_map(size_type n, const hasher& hf, const allocator_type& a)
77 : unordered_map(n, hf, key_equal(), a) {} // C++14
78 template <class InputIterator>
79 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
80 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14
81 template <class InputIterator>
82 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
83 const allocator_type& a)
84 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14
85 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)
86 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14
87 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
88 const allocator_type& a)
89 : unordered_map(il, n, hf, key_equal(), a) {} // C++14
91 unordered_map& operator=(const unordered_map&);
92 unordered_map& operator=(unordered_map&&)
94 allocator_type::propagate_on_container_move_assignment::value &&
95 is_nothrow_move_assignable<allocator_type>::value &&
96 is_nothrow_move_assignable<hasher>::value &&
97 is_nothrow_move_assignable<key_equal>::value);
98 unordered_map& operator=(initializer_list<value_type>);
100 allocator_type get_allocator() const noexcept;
102 bool empty() const noexcept;
103 size_type size() const noexcept;
104 size_type max_size() const noexcept;
106 iterator begin() noexcept;
107 iterator end() noexcept;
108 const_iterator begin() const noexcept;
109 const_iterator end() const noexcept;
110 const_iterator cbegin() const noexcept;
111 const_iterator cend() const noexcept;
113 template <class... Args>
114 pair<iterator, bool> emplace(Args&&... args);
115 template <class... Args>
116 iterator emplace_hint(const_iterator position, Args&&... args);
117 pair<iterator, bool> insert(const value_type& obj);
119 pair<iterator, bool> insert(P&& obj);
120 iterator insert(const_iterator hint, const value_type& obj);
122 iterator insert(const_iterator hint, P&& obj);
123 template <class InputIterator>
124 void insert(InputIterator first, InputIterator last);
125 void insert(initializer_list<value_type>);
127 node_type extract(const_iterator position); // C++17
128 node_type extract(const key_type& x); // C++17
129 insert_return_type insert(node_type&& nh); // C++17
130 iterator insert(const_iterator hint, node_type&& nh); // C++17
132 template <class... Args>
133 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
134 template <class... Args>
135 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
136 template <class... Args>
137 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
138 template <class... Args>
139 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
141 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
143 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
145 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
147 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
149 iterator erase(const_iterator position);
150 iterator erase(iterator position); // C++14
151 size_type erase(const key_type& k);
152 iterator erase(const_iterator first, const_iterator last);
153 void clear() noexcept;
155 template<class H2, class P2>
156 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17
157 template<class H2, class P2>
158 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17
159 template<class H2, class P2>
160 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17
161 template<class H2, class P2>
162 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17
164 void swap(unordered_map&)
166 (!allocator_type::propagate_on_container_swap::value ||
167 __is_nothrow_swappable<allocator_type>::value) &&
168 __is_nothrow_swappable<hasher>::value &&
169 __is_nothrow_swappable<key_equal>::value);
171 hasher hash_function() const;
172 key_equal key_eq() const;
174 iterator find(const key_type& k);
175 const_iterator find(const key_type& k) const;
176 size_type count(const key_type& k) const;
177 bool contains(const key_type& k) const; // C++20
178 pair<iterator, iterator> equal_range(const key_type& k);
179 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
181 mapped_type& operator[](const key_type& k);
182 mapped_type& operator[](key_type&& k);
184 mapped_type& at(const key_type& k);
185 const mapped_type& at(const key_type& k) const;
187 size_type bucket_count() const noexcept;
188 size_type max_bucket_count() const noexcept;
190 size_type bucket_size(size_type n) const;
191 size_type bucket(const key_type& k) const;
193 local_iterator begin(size_type n);
194 local_iterator end(size_type n);
195 const_local_iterator begin(size_type n) const;
196 const_local_iterator end(size_type n) const;
197 const_local_iterator cbegin(size_type n) const;
198 const_local_iterator cend(size_type n) const;
200 float load_factor() const noexcept;
201 float max_load_factor() const noexcept;
202 void max_load_factor(float z);
203 void rehash(size_type n);
204 void reserve(size_type n);
207 template <class Key, class T, class Hash, class Pred, class Alloc>
208 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
209 unordered_map<Key, T, Hash, Pred, Alloc>& y)
210 noexcept(noexcept(x.swap(y)));
212 template <class Key, class T, class Hash, class Pred, class Alloc>
214 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
215 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
217 template <class Key, class T, class Hash, class Pred, class Alloc>
219 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
220 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
222 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
223 class Alloc = allocator<pair<const Key, T>>>
224 class unordered_multimap
228 typedef Key key_type;
229 typedef T mapped_type;
231 typedef Pred key_equal;
232 typedef Alloc allocator_type;
233 typedef pair<const key_type, mapped_type> value_type;
234 typedef value_type& reference;
235 typedef const value_type& const_reference;
236 typedef typename allocator_traits<allocator_type>::pointer pointer;
237 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
238 typedef typename allocator_traits<allocator_type>::size_type size_type;
239 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
241 typedef /unspecified/ iterator;
242 typedef /unspecified/ const_iterator;
243 typedef /unspecified/ local_iterator;
244 typedef /unspecified/ const_local_iterator;
246 typedef unspecified node_type; // C++17
250 is_nothrow_default_constructible<hasher>::value &&
251 is_nothrow_default_constructible<key_equal>::value &&
252 is_nothrow_default_constructible<allocator_type>::value);
253 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
254 const key_equal& eql = key_equal(),
255 const allocator_type& a = allocator_type());
256 template <class InputIterator>
257 unordered_multimap(InputIterator f, InputIterator l,
258 size_type n = 0, const hasher& hf = hasher(),
259 const key_equal& eql = key_equal(),
260 const allocator_type& a = allocator_type());
261 explicit unordered_multimap(const allocator_type&);
262 unordered_multimap(const unordered_multimap&);
263 unordered_multimap(const unordered_multimap&, const Allocator&);
264 unordered_multimap(unordered_multimap&&)
266 is_nothrow_move_constructible<hasher>::value &&
267 is_nothrow_move_constructible<key_equal>::value &&
268 is_nothrow_move_constructible<allocator_type>::value);
269 unordered_multimap(unordered_multimap&&, const Allocator&);
270 unordered_multimap(initializer_list<value_type>, size_type n = 0,
271 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
272 const allocator_type& a = allocator_type());
273 unordered_multimap(size_type n, const allocator_type& a)
274 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14
275 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
276 : unordered_multimap(n, hf, key_equal(), a) {} // C++14
277 template <class InputIterator>
278 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
279 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14
280 template <class InputIterator>
281 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
282 const allocator_type& a)
283 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14
284 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)
285 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14
286 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
287 const allocator_type& a)
288 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14
289 ~unordered_multimap();
290 unordered_multimap& operator=(const unordered_multimap&);
291 unordered_multimap& operator=(unordered_multimap&&)
293 allocator_type::propagate_on_container_move_assignment::value &&
294 is_nothrow_move_assignable<allocator_type>::value &&
295 is_nothrow_move_assignable<hasher>::value &&
296 is_nothrow_move_assignable<key_equal>::value);
297 unordered_multimap& operator=(initializer_list<value_type>);
299 allocator_type get_allocator() const noexcept;
301 bool empty() const noexcept;
302 size_type size() const noexcept;
303 size_type max_size() const noexcept;
305 iterator begin() noexcept;
306 iterator end() noexcept;
307 const_iterator begin() const noexcept;
308 const_iterator end() const noexcept;
309 const_iterator cbegin() const noexcept;
310 const_iterator cend() const noexcept;
312 template <class... Args>
313 iterator emplace(Args&&... args);
314 template <class... Args>
315 iterator emplace_hint(const_iterator position, Args&&... args);
316 iterator insert(const value_type& obj);
318 iterator insert(P&& obj);
319 iterator insert(const_iterator hint, const value_type& obj);
321 iterator insert(const_iterator hint, P&& obj);
322 template <class InputIterator>
323 void insert(InputIterator first, InputIterator last);
324 void insert(initializer_list<value_type>);
326 node_type extract(const_iterator position); // C++17
327 node_type extract(const key_type& x); // C++17
328 iterator insert(node_type&& nh); // C++17
329 iterator insert(const_iterator hint, node_type&& nh); // C++17
331 iterator erase(const_iterator position);
332 iterator erase(iterator position); // C++14
333 size_type erase(const key_type& k);
334 iterator erase(const_iterator first, const_iterator last);
335 void clear() noexcept;
337 template<class H2, class P2>
338 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17
339 template<class H2, class P2>
340 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17
341 template<class H2, class P2>
342 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17
343 template<class H2, class P2>
344 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17
346 void swap(unordered_multimap&)
348 (!allocator_type::propagate_on_container_swap::value ||
349 __is_nothrow_swappable<allocator_type>::value) &&
350 __is_nothrow_swappable<hasher>::value &&
351 __is_nothrow_swappable<key_equal>::value);
353 hasher hash_function() const;
354 key_equal key_eq() const;
356 iterator find(const key_type& k);
357 const_iterator find(const key_type& k) const;
358 size_type count(const key_type& k) const;
359 bool contains(const key_type& k) const; // C++20
360 pair<iterator, iterator> equal_range(const key_type& k);
361 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
363 size_type bucket_count() const noexcept;
364 size_type max_bucket_count() const noexcept;
366 size_type bucket_size(size_type n) const;
367 size_type bucket(const key_type& k) const;
369 local_iterator begin(size_type n);
370 local_iterator end(size_type n);
371 const_local_iterator begin(size_type n) const;
372 const_local_iterator end(size_type n) const;
373 const_local_iterator cbegin(size_type n) const;
374 const_local_iterator cend(size_type n) const;
376 float load_factor() const noexcept;
377 float max_load_factor() const noexcept;
378 void max_load_factor(float z);
379 void rehash(size_type n);
380 void reserve(size_type n);
383 template <class Key, class T, class Hash, class Pred, class Alloc>
384 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
385 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
386 noexcept(noexcept(x.swap(y)));
388 template <class K, class T, class H, class P, class A, class Predicate>
389 void erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20
391 template <class K, class T, class H, class P, class A, class Predicate>
392 void erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20
394 template <class Key, class T, class Hash, class Pred, class Alloc>
396 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
397 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
399 template <class Key, class T, class Hash, class Pred, class Alloc>
401 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
402 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
409 #include <__hash_table>
410 #include <__node_handle>
411 #include <functional>
418 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
419 #pragma GCC system_header
422 _LIBCPP_BEGIN_NAMESPACE_STD
424 template <class _Key, class _Cp, class _Hash,
425 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
426 class __unordered_map_hasher
430 _LIBCPP_INLINE_VISIBILITY
431 __unordered_map_hasher()
432 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
434 _LIBCPP_INLINE_VISIBILITY
435 __unordered_map_hasher(const _Hash& __h)
436 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
438 _LIBCPP_INLINE_VISIBILITY
439 const _Hash& hash_function() const _NOEXCEPT {return *this;}
440 _LIBCPP_INLINE_VISIBILITY
441 size_t operator()(const _Cp& __x) const
442 {return static_cast<const _Hash&>(*this)(__x.__get_value().first);}
443 _LIBCPP_INLINE_VISIBILITY
444 size_t operator()(const _Key& __x) const
445 {return static_cast<const _Hash&>(*this)(__x);}
446 void swap(__unordered_map_hasher&__y)
447 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
450 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
454 template <class _Key, class _Cp, class _Hash>
455 class __unordered_map_hasher<_Key, _Cp, _Hash, false>
459 _LIBCPP_INLINE_VISIBILITY
460 __unordered_map_hasher()
461 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
463 _LIBCPP_INLINE_VISIBILITY
464 __unordered_map_hasher(const _Hash& __h)
465 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
467 _LIBCPP_INLINE_VISIBILITY
468 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
469 _LIBCPP_INLINE_VISIBILITY
470 size_t operator()(const _Cp& __x) const
471 {return __hash_(__x.__get_value().first);}
472 _LIBCPP_INLINE_VISIBILITY
473 size_t operator()(const _Key& __x) const
474 {return __hash_(__x);}
475 void swap(__unordered_map_hasher&__y)
476 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
479 swap(__hash_, __y.__hash_);
483 template <class _Key, class _Cp, class _Hash, bool __b>
484 inline _LIBCPP_INLINE_VISIBILITY
486 swap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x,
487 __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y)
488 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
493 template <class _Key, class _Cp, class _Pred,
494 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>
495 class __unordered_map_equal
499 _LIBCPP_INLINE_VISIBILITY
500 __unordered_map_equal()
501 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
503 _LIBCPP_INLINE_VISIBILITY
504 __unordered_map_equal(const _Pred& __p)
505 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
507 _LIBCPP_INLINE_VISIBILITY
508 const _Pred& key_eq() const _NOEXCEPT {return *this;}
509 _LIBCPP_INLINE_VISIBILITY
510 bool operator()(const _Cp& __x, const _Cp& __y) const
511 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);}
512 _LIBCPP_INLINE_VISIBILITY
513 bool operator()(const _Cp& __x, const _Key& __y) const
514 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);}
515 _LIBCPP_INLINE_VISIBILITY
516 bool operator()(const _Key& __x, const _Cp& __y) const
517 {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);}
518 void swap(__unordered_map_equal&__y)
519 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
522 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
526 template <class _Key, class _Cp, class _Pred>
527 class __unordered_map_equal<_Key, _Cp, _Pred, false>
531 _LIBCPP_INLINE_VISIBILITY
532 __unordered_map_equal()
533 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
535 _LIBCPP_INLINE_VISIBILITY
536 __unordered_map_equal(const _Pred& __p)
537 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
539 _LIBCPP_INLINE_VISIBILITY
540 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
541 _LIBCPP_INLINE_VISIBILITY
542 bool operator()(const _Cp& __x, const _Cp& __y) const
543 {return __pred_(__x.__get_value().first, __y.__get_value().first);}
544 _LIBCPP_INLINE_VISIBILITY
545 bool operator()(const _Cp& __x, const _Key& __y) const
546 {return __pred_(__x.__get_value().first, __y);}
547 _LIBCPP_INLINE_VISIBILITY
548 bool operator()(const _Key& __x, const _Cp& __y) const
549 {return __pred_(__x, __y.__get_value().first);}
550 void swap(__unordered_map_equal&__y)
551 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
554 swap(__pred_, __y.__pred_);
558 template <class _Key, class _Cp, class _Pred, bool __b>
559 inline _LIBCPP_INLINE_VISIBILITY
561 swap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x,
562 __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y)
563 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
568 template <class _Alloc>
569 class __hash_map_node_destructor
571 typedef _Alloc allocator_type;
572 typedef allocator_traits<allocator_type> __alloc_traits;
576 typedef typename __alloc_traits::pointer pointer;
579 allocator_type& __na_;
581 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
584 bool __first_constructed;
585 bool __second_constructed;
587 _LIBCPP_INLINE_VISIBILITY
588 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
590 __first_constructed(false),
591 __second_constructed(false)
594 #ifndef _LIBCPP_CXX03_LANG
595 _LIBCPP_INLINE_VISIBILITY
596 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
599 __first_constructed(__x.__value_constructed),
600 __second_constructed(__x.__value_constructed)
602 __x.__value_constructed = false;
604 #else // _LIBCPP_CXX03_LANG
605 _LIBCPP_INLINE_VISIBILITY
606 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
608 __first_constructed(__x.__value_constructed),
609 __second_constructed(__x.__value_constructed)
611 const_cast<bool&>(__x.__value_constructed) = false;
613 #endif // _LIBCPP_CXX03_LANG
615 _LIBCPP_INLINE_VISIBILITY
616 void operator()(pointer __p) _NOEXCEPT
618 if (__second_constructed)
619 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
620 if (__first_constructed)
621 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
623 __alloc_traits::deallocate(__na_, __p, 1);
627 #ifndef _LIBCPP_CXX03_LANG
628 template <class _Key, class _Tp>
629 struct __hash_value_type
631 typedef _Key key_type;
632 typedef _Tp mapped_type;
633 typedef pair<const key_type, mapped_type> value_type;
634 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
635 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
641 _LIBCPP_INLINE_VISIBILITY
642 value_type& __get_value()
644 #if _LIBCPP_STD_VER > 14
645 return *_VSTD::launder(_VSTD::addressof(__cc));
651 _LIBCPP_INLINE_VISIBILITY
652 const value_type& __get_value() const
654 #if _LIBCPP_STD_VER > 14
655 return *_VSTD::launder(_VSTD::addressof(__cc));
661 _LIBCPP_INLINE_VISIBILITY
662 __nc_ref_pair_type __ref()
664 value_type& __v = __get_value();
665 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
668 _LIBCPP_INLINE_VISIBILITY
669 __nc_rref_pair_type __move()
671 value_type& __v = __get_value();
672 return __nc_rref_pair_type(
673 _VSTD::move(const_cast<key_type&>(__v.first)),
674 _VSTD::move(__v.second));
677 _LIBCPP_INLINE_VISIBILITY
678 __hash_value_type& operator=(const __hash_value_type& __v)
680 __ref() = __v.__get_value();
684 _LIBCPP_INLINE_VISIBILITY
685 __hash_value_type& operator=(__hash_value_type&& __v)
687 __ref() = __v.__move();
691 template <class _ValueTp,
692 class = typename enable_if<
693 __is_same_uncvref<_ValueTp, value_type>::value
696 _LIBCPP_INLINE_VISIBILITY
697 __hash_value_type& operator=(_ValueTp&& __v)
699 __ref() = _VSTD::forward<_ValueTp>(__v);
704 __hash_value_type(const __hash_value_type& __v) = delete;
705 __hash_value_type(__hash_value_type&& __v) = delete;
706 template <class ..._Args>
707 explicit __hash_value_type(_Args&& ...__args) = delete;
709 ~__hash_value_type() = delete;
714 template <class _Key, class _Tp>
715 struct __hash_value_type
717 typedef _Key key_type;
718 typedef _Tp mapped_type;
719 typedef pair<const key_type, mapped_type> value_type;
725 _LIBCPP_INLINE_VISIBILITY
726 value_type& __get_value() { return __cc; }
727 _LIBCPP_INLINE_VISIBILITY
728 const value_type& __get_value() const { return __cc; }
731 ~__hash_value_type();
736 template <class _HashIterator>
737 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator
741 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
744 typedef forward_iterator_tag iterator_category;
745 typedef typename _NodeTypes::__map_value_type value_type;
746 typedef typename _NodeTypes::difference_type difference_type;
747 typedef value_type& reference;
748 typedef typename _NodeTypes::__map_value_type_pointer pointer;
750 _LIBCPP_INLINE_VISIBILITY
751 __hash_map_iterator() _NOEXCEPT {}
753 _LIBCPP_INLINE_VISIBILITY
754 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
756 _LIBCPP_INLINE_VISIBILITY
757 reference operator*() const {return __i_->__get_value();}
758 _LIBCPP_INLINE_VISIBILITY
759 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
761 _LIBCPP_INLINE_VISIBILITY
762 __hash_map_iterator& operator++() {++__i_; return *this;}
763 _LIBCPP_INLINE_VISIBILITY
764 __hash_map_iterator operator++(int)
766 __hash_map_iterator __t(*this);
771 friend _LIBCPP_INLINE_VISIBILITY
772 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
773 {return __x.__i_ == __y.__i_;}
774 friend _LIBCPP_INLINE_VISIBILITY
775 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
776 {return __x.__i_ != __y.__i_;}
778 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
779 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
780 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
781 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
782 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
785 template <class _HashIterator>
786 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator
790 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
793 typedef forward_iterator_tag iterator_category;
794 typedef typename _NodeTypes::__map_value_type value_type;
795 typedef typename _NodeTypes::difference_type difference_type;
796 typedef const value_type& reference;
797 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
799 _LIBCPP_INLINE_VISIBILITY
800 __hash_map_const_iterator() _NOEXCEPT {}
802 _LIBCPP_INLINE_VISIBILITY
803 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
804 _LIBCPP_INLINE_VISIBILITY
805 __hash_map_const_iterator(
806 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
810 _LIBCPP_INLINE_VISIBILITY
811 reference operator*() const {return __i_->__get_value();}
812 _LIBCPP_INLINE_VISIBILITY
813 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
815 _LIBCPP_INLINE_VISIBILITY
816 __hash_map_const_iterator& operator++() {++__i_; return *this;}
817 _LIBCPP_INLINE_VISIBILITY
818 __hash_map_const_iterator operator++(int)
820 __hash_map_const_iterator __t(*this);
825 friend _LIBCPP_INLINE_VISIBILITY
826 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
827 {return __x.__i_ == __y.__i_;}
828 friend _LIBCPP_INLINE_VISIBILITY
829 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
830 {return __x.__i_ != __y.__i_;}
832 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
833 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
834 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
835 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
838 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
839 class unordered_multimap;
841 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
842 class _Alloc = allocator<pair<const _Key, _Tp> > >
843 class _LIBCPP_TEMPLATE_VIS unordered_map
847 typedef _Key key_type;
848 typedef _Tp mapped_type;
849 typedef typename __identity<_Hash>::type hasher;
850 typedef typename __identity<_Pred>::type key_equal;
851 typedef typename __identity<_Alloc>::type allocator_type;
852 typedef pair<const key_type, mapped_type> value_type;
853 typedef value_type& reference;
854 typedef const value_type& const_reference;
855 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
856 "Invalid allocator::value_type");
859 typedef __hash_value_type<key_type, mapped_type> __value_type;
860 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
861 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
862 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
863 __value_type>::type __allocator_type;
865 typedef __hash_table<__value_type, __hasher,
866 __key_equal, __allocator_type> __table;
870 typedef typename __table::_NodeTypes _NodeTypes;
871 typedef typename __table::__node_pointer __node_pointer;
872 typedef typename __table::__node_const_pointer __node_const_pointer;
873 typedef typename __table::__node_traits __node_traits;
874 typedef typename __table::__node_allocator __node_allocator;
875 typedef typename __table::__node __node;
876 typedef __hash_map_node_destructor<__node_allocator> _Dp;
877 typedef unique_ptr<__node, _Dp> __node_holder;
878 typedef allocator_traits<allocator_type> __alloc_traits;
880 static_assert((is_same<typename __table::__container_value_type, value_type>::value), "");
881 static_assert((is_same<typename __table::__node_value_type, __value_type>::value), "");
883 typedef typename __alloc_traits::pointer pointer;
884 typedef typename __alloc_traits::const_pointer const_pointer;
885 typedef typename __table::size_type size_type;
886 typedef typename __table::difference_type difference_type;
888 typedef __hash_map_iterator<typename __table::iterator> iterator;
889 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
890 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
891 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
893 #if _LIBCPP_STD_VER > 14
894 typedef __map_node_handle<__node, allocator_type> node_type;
895 typedef __insert_return_type<iterator, node_type> insert_return_type;
898 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
899 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
900 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
901 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
903 _LIBCPP_INLINE_VISIBILITY
905 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
907 #if _LIBCPP_DEBUG_LEVEL >= 2
908 __get_db()->__insert_c(this);
911 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
912 const key_equal& __eql = key_equal());
913 unordered_map(size_type __n, const hasher& __hf,
914 const key_equal& __eql,
915 const allocator_type& __a);
916 template <class _InputIterator>
917 unordered_map(_InputIterator __first, _InputIterator __last);
918 template <class _InputIterator>
919 unordered_map(_InputIterator __first, _InputIterator __last,
920 size_type __n, const hasher& __hf = hasher(),
921 const key_equal& __eql = key_equal());
922 template <class _InputIterator>
923 unordered_map(_InputIterator __first, _InputIterator __last,
924 size_type __n, const hasher& __hf,
925 const key_equal& __eql,
926 const allocator_type& __a);
927 _LIBCPP_INLINE_VISIBILITY
928 explicit unordered_map(const allocator_type& __a);
929 unordered_map(const unordered_map& __u);
930 unordered_map(const unordered_map& __u, const allocator_type& __a);
931 #ifndef _LIBCPP_CXX03_LANG
932 _LIBCPP_INLINE_VISIBILITY
933 unordered_map(unordered_map&& __u)
934 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
935 unordered_map(unordered_map&& __u, const allocator_type& __a);
936 unordered_map(initializer_list<value_type> __il);
937 unordered_map(initializer_list<value_type> __il, size_type __n,
938 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
939 unordered_map(initializer_list<value_type> __il, size_type __n,
940 const hasher& __hf, const key_equal& __eql,
941 const allocator_type& __a);
942 #endif // _LIBCPP_CXX03_LANG
943 #if _LIBCPP_STD_VER > 11
944 _LIBCPP_INLINE_VISIBILITY
945 unordered_map(size_type __n, const allocator_type& __a)
946 : unordered_map(__n, hasher(), key_equal(), __a) {}
947 _LIBCPP_INLINE_VISIBILITY
948 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
949 : unordered_map(__n, __hf, key_equal(), __a) {}
950 template <class _InputIterator>
951 _LIBCPP_INLINE_VISIBILITY
952 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
953 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
954 template <class _InputIterator>
955 _LIBCPP_INLINE_VISIBILITY
956 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
957 const allocator_type& __a)
958 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
959 _LIBCPP_INLINE_VISIBILITY
960 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
961 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
962 _LIBCPP_INLINE_VISIBILITY
963 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
964 const allocator_type& __a)
965 : unordered_map(__il, __n, __hf, key_equal(), __a) {}
967 _LIBCPP_INLINE_VISIBILITY
969 static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
972 _LIBCPP_INLINE_VISIBILITY
973 unordered_map& operator=(const unordered_map& __u)
975 #ifndef _LIBCPP_CXX03_LANG
976 __table_ = __u.__table_;
980 __table_.hash_function() = __u.__table_.hash_function();
981 __table_.key_eq() = __u.__table_.key_eq();
982 __table_.max_load_factor() = __u.__table_.max_load_factor();
983 __table_.__copy_assign_alloc(__u.__table_);
984 insert(__u.begin(), __u.end());
989 #ifndef _LIBCPP_CXX03_LANG
990 _LIBCPP_INLINE_VISIBILITY
991 unordered_map& operator=(unordered_map&& __u)
992 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
993 _LIBCPP_INLINE_VISIBILITY
994 unordered_map& operator=(initializer_list<value_type> __il);
995 #endif // _LIBCPP_CXX03_LANG
997 _LIBCPP_INLINE_VISIBILITY
998 allocator_type get_allocator() const _NOEXCEPT
999 {return allocator_type(__table_.__node_alloc());}
1001 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1002 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1003 _LIBCPP_INLINE_VISIBILITY
1004 size_type size() const _NOEXCEPT {return __table_.size();}
1005 _LIBCPP_INLINE_VISIBILITY
1006 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1008 _LIBCPP_INLINE_VISIBILITY
1009 iterator begin() _NOEXCEPT {return __table_.begin();}
1010 _LIBCPP_INLINE_VISIBILITY
1011 iterator end() _NOEXCEPT {return __table_.end();}
1012 _LIBCPP_INLINE_VISIBILITY
1013 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1014 _LIBCPP_INLINE_VISIBILITY
1015 const_iterator end() const _NOEXCEPT {return __table_.end();}
1016 _LIBCPP_INLINE_VISIBILITY
1017 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1018 _LIBCPP_INLINE_VISIBILITY
1019 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1021 _LIBCPP_INLINE_VISIBILITY
1022 pair<iterator, bool> insert(const value_type& __x)
1023 {return __table_.__insert_unique(__x);}
1025 iterator insert(const_iterator __p, const value_type& __x) {
1026 #if _LIBCPP_DEBUG_LEVEL >= 2
1027 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1028 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
1029 " referring to this unordered_map");
1033 return insert(__x).first;
1036 template <class _InputIterator>
1037 _LIBCPP_INLINE_VISIBILITY
1038 void insert(_InputIterator __first, _InputIterator __last);
1040 #ifndef _LIBCPP_CXX03_LANG
1041 _LIBCPP_INLINE_VISIBILITY
1042 void insert(initializer_list<value_type> __il)
1043 {insert(__il.begin(), __il.end());}
1045 _LIBCPP_INLINE_VISIBILITY
1046 pair<iterator, bool> insert(value_type&& __x)
1047 {return __table_.__insert_unique(_VSTD::move(__x));}
1049 iterator insert(const_iterator __p, value_type&& __x) {
1050 #if _LIBCPP_DEBUG_LEVEL >= 2
1051 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1052 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
1053 " referring to this unordered_map");
1057 return __table_.__insert_unique(_VSTD::move(__x)).first;
1060 template <class _Pp,
1061 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1062 _LIBCPP_INLINE_VISIBILITY
1063 pair<iterator, bool> insert(_Pp&& __x)
1064 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
1066 template <class _Pp,
1067 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1068 _LIBCPP_INLINE_VISIBILITY
1069 iterator insert(const_iterator __p, _Pp&& __x)
1071 #if _LIBCPP_DEBUG_LEVEL >= 2
1072 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1073 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
1074 " referring to this unordered_map");
1078 return insert(_VSTD::forward<_Pp>(__x)).first;
1081 template <class... _Args>
1082 _LIBCPP_INLINE_VISIBILITY
1083 pair<iterator, bool> emplace(_Args&&... __args) {
1084 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1087 template <class... _Args>
1088 _LIBCPP_INLINE_VISIBILITY
1089 iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1090 #if _LIBCPP_DEBUG_LEVEL >= 2
1091 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1092 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
1093 " referring to this unordered_map");
1097 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
1100 #endif // _LIBCPP_CXX03_LANG
1102 #if _LIBCPP_STD_VER > 14
1103 template <class... _Args>
1104 _LIBCPP_INLINE_VISIBILITY
1105 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1107 return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
1108 _VSTD::forward_as_tuple(__k),
1109 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1112 template <class... _Args>
1113 _LIBCPP_INLINE_VISIBILITY
1114 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1116 return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
1117 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1118 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1121 template <class... _Args>
1122 _LIBCPP_INLINE_VISIBILITY
1123 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1125 #if _LIBCPP_DEBUG_LEVEL >= 2
1126 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
1127 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1128 " referring to this unordered_map");
1132 return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first;
1135 template <class... _Args>
1136 _LIBCPP_INLINE_VISIBILITY
1137 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1139 #if _LIBCPP_DEBUG_LEVEL >= 2
1140 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
1141 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1142 " referring to this unordered_map");
1146 return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first;
1149 template <class _Vp>
1150 _LIBCPP_INLINE_VISIBILITY
1151 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1153 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1154 __k, _VSTD::forward<_Vp>(__v));
1155 if (!__res.second) {
1156 __res.first->second = _VSTD::forward<_Vp>(__v);
1161 template <class _Vp>
1162 _LIBCPP_INLINE_VISIBILITY
1163 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1165 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1166 _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1167 if (!__res.second) {
1168 __res.first->second = _VSTD::forward<_Vp>(__v);
1173 template <class _Vp>
1174 _LIBCPP_INLINE_VISIBILITY
1175 iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v)
1177 // FIXME: Add debug mode checking for the iterator input
1178 return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first;
1181 template <class _Vp>
1182 _LIBCPP_INLINE_VISIBILITY
1183 iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v)
1185 // FIXME: Add debug mode checking for the iterator input
1186 return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first;
1188 #endif // _LIBCPP_STD_VER > 14
1190 _LIBCPP_INLINE_VISIBILITY
1191 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1192 _LIBCPP_INLINE_VISIBILITY
1193 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
1194 _LIBCPP_INLINE_VISIBILITY
1195 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
1196 _LIBCPP_INLINE_VISIBILITY
1197 iterator erase(const_iterator __first, const_iterator __last)
1198 {return __table_.erase(__first.__i_, __last.__i_);}
1199 _LIBCPP_INLINE_VISIBILITY
1200 void clear() _NOEXCEPT {__table_.clear();}
1202 #if _LIBCPP_STD_VER > 14
1203 _LIBCPP_INLINE_VISIBILITY
1204 insert_return_type insert(node_type&& __nh)
1206 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1207 "node_type with incompatible allocator passed to unordered_map::insert()");
1208 return __table_.template __node_handle_insert_unique<
1209 node_type, insert_return_type>(_VSTD::move(__nh));
1211 _LIBCPP_INLINE_VISIBILITY
1212 iterator insert(const_iterator __hint, node_type&& __nh)
1214 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1215 "node_type with incompatible allocator passed to unordered_map::insert()");
1216 return __table_.template __node_handle_insert_unique<node_type>(
1217 __hint.__i_, _VSTD::move(__nh));
1219 _LIBCPP_INLINE_VISIBILITY
1220 node_type extract(key_type const& __key)
1222 return __table_.template __node_handle_extract<node_type>(__key);
1224 _LIBCPP_INLINE_VISIBILITY
1225 node_type extract(const_iterator __it)
1227 return __table_.template __node_handle_extract<node_type>(
1231 template <class _H2, class _P2>
1232 _LIBCPP_INLINE_VISIBILITY
1233 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
1235 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1236 "merging container with incompatible allocator");
1237 return __table_.__node_handle_merge_unique(__source.__table_);
1239 template <class _H2, class _P2>
1240 _LIBCPP_INLINE_VISIBILITY
1241 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
1243 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1244 "merging container with incompatible allocator");
1245 return __table_.__node_handle_merge_unique(__source.__table_);
1247 template <class _H2, class _P2>
1248 _LIBCPP_INLINE_VISIBILITY
1249 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
1251 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1252 "merging container with incompatible allocator");
1253 return __table_.__node_handle_merge_unique(__source.__table_);
1255 template <class _H2, class _P2>
1256 _LIBCPP_INLINE_VISIBILITY
1257 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
1259 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1260 "merging container with incompatible allocator");
1261 return __table_.__node_handle_merge_unique(__source.__table_);
1265 _LIBCPP_INLINE_VISIBILITY
1266 void swap(unordered_map& __u)
1267 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1268 { __table_.swap(__u.__table_);}
1270 _LIBCPP_INLINE_VISIBILITY
1271 hasher hash_function() const
1272 {return __table_.hash_function().hash_function();}
1273 _LIBCPP_INLINE_VISIBILITY
1274 key_equal key_eq() const
1275 {return __table_.key_eq().key_eq();}
1277 _LIBCPP_INLINE_VISIBILITY
1278 iterator find(const key_type& __k) {return __table_.find(__k);}
1279 _LIBCPP_INLINE_VISIBILITY
1280 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1281 _LIBCPP_INLINE_VISIBILITY
1282 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
1283 #if _LIBCPP_STD_VER > 17
1284 _LIBCPP_INLINE_VISIBILITY
1285 bool contains(const key_type& __k) const {return find(__k) != end();}
1286 #endif // _LIBCPP_STD_VER > 17
1287 _LIBCPP_INLINE_VISIBILITY
1288 pair<iterator, iterator> equal_range(const key_type& __k)
1289 {return __table_.__equal_range_unique(__k);}
1290 _LIBCPP_INLINE_VISIBILITY
1291 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1292 {return __table_.__equal_range_unique(__k);}
1294 mapped_type& operator[](const key_type& __k);
1295 #ifndef _LIBCPP_CXX03_LANG
1296 mapped_type& operator[](key_type&& __k);
1299 mapped_type& at(const key_type& __k);
1300 const mapped_type& at(const key_type& __k) const;
1302 _LIBCPP_INLINE_VISIBILITY
1303 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1304 _LIBCPP_INLINE_VISIBILITY
1305 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1307 _LIBCPP_INLINE_VISIBILITY
1308 size_type bucket_size(size_type __n) const
1309 {return __table_.bucket_size(__n);}
1310 _LIBCPP_INLINE_VISIBILITY
1311 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1313 _LIBCPP_INLINE_VISIBILITY
1314 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1315 _LIBCPP_INLINE_VISIBILITY
1316 local_iterator end(size_type __n) {return __table_.end(__n);}
1317 _LIBCPP_INLINE_VISIBILITY
1318 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1319 _LIBCPP_INLINE_VISIBILITY
1320 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1321 _LIBCPP_INLINE_VISIBILITY
1322 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1323 _LIBCPP_INLINE_VISIBILITY
1324 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1326 _LIBCPP_INLINE_VISIBILITY
1327 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1328 _LIBCPP_INLINE_VISIBILITY
1329 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1330 _LIBCPP_INLINE_VISIBILITY
1331 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1332 _LIBCPP_INLINE_VISIBILITY
1333 void rehash(size_type __n) {__table_.rehash(__n);}
1334 _LIBCPP_INLINE_VISIBILITY
1335 void reserve(size_type __n) {__table_.reserve(__n);}
1337 #if _LIBCPP_DEBUG_LEVEL >= 2
1339 bool __dereferenceable(const const_iterator* __i) const
1340 {return __table_.__dereferenceable(&__i->__i_);}
1341 bool __decrementable(const const_iterator* __i) const
1342 {return __table_.__decrementable(&__i->__i_);}
1343 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1344 {return __table_.__addable(&__i->__i_, __n);}
1345 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1346 {return __table_.__addable(&__i->__i_, __n);}
1348 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1352 #ifdef _LIBCPP_CXX03_LANG
1353 __node_holder __construct_node_with_key(const key_type& __k);
1357 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1358 template<class _InputIterator,
1359 class _Hash = hash<__iter_key_type<_InputIterator>>,
1360 class _Pred = equal_to<__iter_key_type<_InputIterator>>,
1361 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1362 class = _EnableIf<!__is_allocator<_Hash>::value>,
1363 class = _EnableIf<!is_integral<_Hash>::value>,
1364 class = _EnableIf<!__is_allocator<_Pred>::value>,
1365 class = _EnableIf<__is_allocator<_Allocator>::value>>
1366 unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
1367 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1368 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1370 template<class _Key, class _Tp, class _Hash = hash<remove_const_t<_Key>>,
1371 class _Pred = equal_to<remove_const_t<_Key>>,
1372 class _Allocator = allocator<pair<const _Key, _Tp>>,
1373 class = _EnableIf<!__is_allocator<_Hash>::value>,
1374 class = _EnableIf<!is_integral<_Hash>::value>,
1375 class = _EnableIf<!__is_allocator<_Pred>::value>,
1376 class = _EnableIf<__is_allocator<_Allocator>::value>>
1377 unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type = 0,
1378 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1379 -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
1381 template<class _InputIterator, class _Allocator,
1382 class = _EnableIf<__is_allocator<_Allocator>::value>>
1383 unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1384 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1385 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
1387 template<class _InputIterator, class _Allocator,
1388 class = _EnableIf<__is_allocator<_Allocator>::value>>
1389 unordered_map(_InputIterator, _InputIterator, _Allocator)
1390 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1391 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
1393 template<class _InputIterator, class _Hash, class _Allocator,
1394 class = _EnableIf<!__is_allocator<_Hash>::value>,
1395 class = _EnableIf<!is_integral<_Hash>::value>,
1396 class = _EnableIf<__is_allocator<_Allocator>::value>>
1397 unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1398 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1399 _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
1401 template<class _Key, class _Tp, class _Allocator,
1402 class = _EnableIf<__is_allocator<_Allocator>::value>>
1403 unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1404 -> unordered_map<remove_const_t<_Key>, _Tp,
1405 hash<remove_const_t<_Key>>,
1406 equal_to<remove_const_t<_Key>>, _Allocator>;
1408 template<class _Key, class _Tp, class _Allocator,
1409 class = _EnableIf<__is_allocator<_Allocator>::value>>
1410 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1411 -> unordered_map<remove_const_t<_Key>, _Tp,
1412 hash<remove_const_t<_Key>>,
1413 equal_to<remove_const_t<_Key>>, _Allocator>;
1415 template<class _Key, class _Tp, class _Hash, class _Allocator,
1416 class = _EnableIf<!__is_allocator<_Hash>::value>,
1417 class = _EnableIf<!is_integral<_Hash>::value>,
1418 class = _EnableIf<__is_allocator<_Allocator>::value>>
1419 unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1420 -> unordered_map<remove_const_t<_Key>, _Tp, _Hash,
1421 equal_to<remove_const_t<_Key>>, _Allocator>;
1424 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1425 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1426 size_type __n, const hasher& __hf, const key_equal& __eql)
1427 : __table_(__hf, __eql)
1429 #if _LIBCPP_DEBUG_LEVEL >= 2
1430 __get_db()->__insert_c(this);
1432 __table_.rehash(__n);
1435 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1436 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1437 size_type __n, const hasher& __hf, const key_equal& __eql,
1438 const allocator_type& __a)
1439 : __table_(__hf, __eql, typename __table::allocator_type(__a))
1441 #if _LIBCPP_DEBUG_LEVEL >= 2
1442 __get_db()->__insert_c(this);
1444 __table_.rehash(__n);
1447 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1449 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1450 const allocator_type& __a)
1451 : __table_(typename __table::allocator_type(__a))
1453 #if _LIBCPP_DEBUG_LEVEL >= 2
1454 __get_db()->__insert_c(this);
1458 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1459 template <class _InputIterator>
1460 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1461 _InputIterator __first, _InputIterator __last)
1463 #if _LIBCPP_DEBUG_LEVEL >= 2
1464 __get_db()->__insert_c(this);
1466 insert(__first, __last);
1469 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1470 template <class _InputIterator>
1471 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1472 _InputIterator __first, _InputIterator __last, size_type __n,
1473 const hasher& __hf, const key_equal& __eql)
1474 : __table_(__hf, __eql)
1476 #if _LIBCPP_DEBUG_LEVEL >= 2
1477 __get_db()->__insert_c(this);
1479 __table_.rehash(__n);
1480 insert(__first, __last);
1483 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1484 template <class _InputIterator>
1485 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1486 _InputIterator __first, _InputIterator __last, size_type __n,
1487 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1488 : __table_(__hf, __eql, typename __table::allocator_type(__a))
1490 #if _LIBCPP_DEBUG_LEVEL >= 2
1491 __get_db()->__insert_c(this);
1493 __table_.rehash(__n);
1494 insert(__first, __last);
1497 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1498 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1499 const unordered_map& __u)
1500 : __table_(__u.__table_)
1502 #if _LIBCPP_DEBUG_LEVEL >= 2
1503 __get_db()->__insert_c(this);
1505 __table_.rehash(__u.bucket_count());
1506 insert(__u.begin(), __u.end());
1509 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1510 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1511 const unordered_map& __u, const allocator_type& __a)
1512 : __table_(__u.__table_, typename __table::allocator_type(__a))
1514 #if _LIBCPP_DEBUG_LEVEL >= 2
1515 __get_db()->__insert_c(this);
1517 __table_.rehash(__u.bucket_count());
1518 insert(__u.begin(), __u.end());
1521 #ifndef _LIBCPP_CXX03_LANG
1523 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1525 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1526 unordered_map&& __u)
1527 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1528 : __table_(_VSTD::move(__u.__table_))
1530 #if _LIBCPP_DEBUG_LEVEL >= 2
1531 __get_db()->__insert_c(this);
1532 __get_db()->swap(this, &__u);
1536 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1537 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1538 unordered_map&& __u, const allocator_type& __a)
1539 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
1541 #if _LIBCPP_DEBUG_LEVEL >= 2
1542 __get_db()->__insert_c(this);
1544 if (__a != __u.get_allocator())
1546 iterator __i = __u.begin();
1547 while (__u.size() != 0) {
1548 __table_.__emplace_unique(
1549 __u.__table_.remove((__i++).__i_)->__value_.__move());
1552 #if _LIBCPP_DEBUG_LEVEL >= 2
1554 __get_db()->swap(this, &__u);
1558 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1559 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1560 initializer_list<value_type> __il)
1562 #if _LIBCPP_DEBUG_LEVEL >= 2
1563 __get_db()->__insert_c(this);
1565 insert(__il.begin(), __il.end());
1568 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1569 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1570 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1571 const key_equal& __eql)
1572 : __table_(__hf, __eql)
1574 #if _LIBCPP_DEBUG_LEVEL >= 2
1575 __get_db()->__insert_c(this);
1577 __table_.rehash(__n);
1578 insert(__il.begin(), __il.end());
1581 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1582 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1583 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1584 const key_equal& __eql, const allocator_type& __a)
1585 : __table_(__hf, __eql, typename __table::allocator_type(__a))
1587 #if _LIBCPP_DEBUG_LEVEL >= 2
1588 __get_db()->__insert_c(this);
1590 __table_.rehash(__n);
1591 insert(__il.begin(), __il.end());
1594 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1596 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1597 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1598 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1600 __table_ = _VSTD::move(__u.__table_);
1604 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1606 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1607 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1608 initializer_list<value_type> __il)
1610 __table_.__assign_unique(__il.begin(), __il.end());
1614 #endif // _LIBCPP_CXX03_LANG
1616 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1617 template <class _InputIterator>
1620 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1621 _InputIterator __last)
1623 for (; __first != __last; ++__first)
1624 __table_.__insert_unique(*__first);
1627 #ifndef _LIBCPP_CXX03_LANG
1629 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1631 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1633 return __table_.__emplace_unique_key_args(__k,
1634 std::piecewise_construct, std::forward_as_tuple(__k),
1635 std::forward_as_tuple()).first->__get_value().second;
1638 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1640 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1642 return __table_.__emplace_unique_key_args(__k,
1643 std::piecewise_construct, std::forward_as_tuple(std::move(__k)),
1644 std::forward_as_tuple()).first->__get_value().second;
1646 #else // _LIBCPP_CXX03_LANG
1648 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1649 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1650 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1652 __node_allocator& __na = __table_.__node_alloc();
1653 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1654 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
1655 __h.get_deleter().__first_constructed = true;
1656 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
1657 __h.get_deleter().__second_constructed = true;
1658 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
1661 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1663 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1665 iterator __i = find(__k);
1668 __node_holder __h = __construct_node_with_key(__k);
1669 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1671 return __r.first->second;
1674 #endif // _LIBCPP_CXX03_MODE
1676 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1678 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1680 iterator __i = find(__k);
1682 __throw_out_of_range("unordered_map::at: key not found");
1686 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1688 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1690 const_iterator __i = find(__k);
1692 __throw_out_of_range("unordered_map::at: key not found");
1696 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1697 inline _LIBCPP_INLINE_VISIBILITY
1699 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1700 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1701 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1706 #if _LIBCPP_STD_VER > 17
1707 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
1708 inline _LIBCPP_INLINE_VISIBILITY
1709 void erase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
1710 { __libcpp_erase_if_container(__c, __pred); }
1713 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1715 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1716 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1718 if (__x.size() != __y.size())
1720 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1722 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1725 const_iterator __j = __y.find(__i->first);
1726 if (__j == __ey || !(*__i == *__j))
1732 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1733 inline _LIBCPP_INLINE_VISIBILITY
1735 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1736 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1738 return !(__x == __y);
1741 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1742 class _Alloc = allocator<pair<const _Key, _Tp> > >
1743 class _LIBCPP_TEMPLATE_VIS unordered_multimap
1747 typedef _Key key_type;
1748 typedef _Tp mapped_type;
1749 typedef typename __identity<_Hash>::type hasher;
1750 typedef typename __identity<_Pred>::type key_equal;
1751 typedef typename __identity<_Alloc>::type allocator_type;
1752 typedef pair<const key_type, mapped_type> value_type;
1753 typedef value_type& reference;
1754 typedef const value_type& const_reference;
1755 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1756 "Invalid allocator::value_type");
1759 typedef __hash_value_type<key_type, mapped_type> __value_type;
1760 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1761 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1762 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1763 __value_type>::type __allocator_type;
1765 typedef __hash_table<__value_type, __hasher,
1766 __key_equal, __allocator_type> __table;
1770 typedef typename __table::_NodeTypes _NodeTypes;
1771 typedef typename __table::__node_traits __node_traits;
1772 typedef typename __table::__node_allocator __node_allocator;
1773 typedef typename __table::__node __node;
1774 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1775 typedef unique_ptr<__node, _Dp> __node_holder;
1776 typedef allocator_traits<allocator_type> __alloc_traits;
1777 static_assert((is_same<typename __node_traits::size_type,
1778 typename __alloc_traits::size_type>::value),
1779 "Allocator uses different size_type for different types");
1781 typedef typename __alloc_traits::pointer pointer;
1782 typedef typename __alloc_traits::const_pointer const_pointer;
1783 typedef typename __table::size_type size_type;
1784 typedef typename __table::difference_type difference_type;
1786 typedef __hash_map_iterator<typename __table::iterator> iterator;
1787 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1788 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1789 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1791 #if _LIBCPP_STD_VER > 14
1792 typedef __map_node_handle<__node, allocator_type> node_type;
1795 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1796 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1797 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1798 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1800 _LIBCPP_INLINE_VISIBILITY
1801 unordered_multimap()
1802 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1804 #if _LIBCPP_DEBUG_LEVEL >= 2
1805 __get_db()->__insert_c(this);
1808 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1809 const key_equal& __eql = key_equal());
1810 unordered_multimap(size_type __n, const hasher& __hf,
1811 const key_equal& __eql,
1812 const allocator_type& __a);
1813 template <class _InputIterator>
1814 unordered_multimap(_InputIterator __first, _InputIterator __last);
1815 template <class _InputIterator>
1816 unordered_multimap(_InputIterator __first, _InputIterator __last,
1817 size_type __n, const hasher& __hf = hasher(),
1818 const key_equal& __eql = key_equal());
1819 template <class _InputIterator>
1820 unordered_multimap(_InputIterator __first, _InputIterator __last,
1821 size_type __n, const hasher& __hf,
1822 const key_equal& __eql,
1823 const allocator_type& __a);
1824 _LIBCPP_INLINE_VISIBILITY
1825 explicit unordered_multimap(const allocator_type& __a);
1826 unordered_multimap(const unordered_multimap& __u);
1827 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1828 #ifndef _LIBCPP_CXX03_LANG
1829 _LIBCPP_INLINE_VISIBILITY
1830 unordered_multimap(unordered_multimap&& __u)
1831 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1832 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1833 unordered_multimap(initializer_list<value_type> __il);
1834 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1835 const hasher& __hf = hasher(),
1836 const key_equal& __eql = key_equal());
1837 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1838 const hasher& __hf, const key_equal& __eql,
1839 const allocator_type& __a);
1840 #endif // _LIBCPP_CXX03_LANG
1841 #if _LIBCPP_STD_VER > 11
1842 _LIBCPP_INLINE_VISIBILITY
1843 unordered_multimap(size_type __n, const allocator_type& __a)
1844 : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1845 _LIBCPP_INLINE_VISIBILITY
1846 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1847 : unordered_multimap(__n, __hf, key_equal(), __a) {}
1848 template <class _InputIterator>
1849 _LIBCPP_INLINE_VISIBILITY
1850 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1851 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1852 template <class _InputIterator>
1853 _LIBCPP_INLINE_VISIBILITY
1854 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1855 const allocator_type& __a)
1856 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1857 _LIBCPP_INLINE_VISIBILITY
1858 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1859 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1860 _LIBCPP_INLINE_VISIBILITY
1861 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1862 const allocator_type& __a)
1863 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1865 _LIBCPP_INLINE_VISIBILITY
1866 ~unordered_multimap() {
1867 static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
1870 _LIBCPP_INLINE_VISIBILITY
1871 unordered_multimap& operator=(const unordered_multimap& __u)
1873 #ifndef _LIBCPP_CXX03_LANG
1874 __table_ = __u.__table_;
1878 __table_.hash_function() = __u.__table_.hash_function();
1879 __table_.key_eq() = __u.__table_.key_eq();
1880 __table_.max_load_factor() = __u.__table_.max_load_factor();
1881 __table_.__copy_assign_alloc(__u.__table_);
1882 insert(__u.begin(), __u.end());
1887 #ifndef _LIBCPP_CXX03_LANG
1888 _LIBCPP_INLINE_VISIBILITY
1889 unordered_multimap& operator=(unordered_multimap&& __u)
1890 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1891 _LIBCPP_INLINE_VISIBILITY
1892 unordered_multimap& operator=(initializer_list<value_type> __il);
1893 #endif // _LIBCPP_CXX03_LANG
1895 _LIBCPP_INLINE_VISIBILITY
1896 allocator_type get_allocator() const _NOEXCEPT
1897 {return allocator_type(__table_.__node_alloc());}
1899 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1900 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1901 _LIBCPP_INLINE_VISIBILITY
1902 size_type size() const _NOEXCEPT {return __table_.size();}
1903 _LIBCPP_INLINE_VISIBILITY
1904 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1906 _LIBCPP_INLINE_VISIBILITY
1907 iterator begin() _NOEXCEPT {return __table_.begin();}
1908 _LIBCPP_INLINE_VISIBILITY
1909 iterator end() _NOEXCEPT {return __table_.end();}
1910 _LIBCPP_INLINE_VISIBILITY
1911 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1912 _LIBCPP_INLINE_VISIBILITY
1913 const_iterator end() const _NOEXCEPT {return __table_.end();}
1914 _LIBCPP_INLINE_VISIBILITY
1915 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1916 _LIBCPP_INLINE_VISIBILITY
1917 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1919 _LIBCPP_INLINE_VISIBILITY
1920 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1922 _LIBCPP_INLINE_VISIBILITY
1923 iterator insert(const_iterator __p, const value_type& __x)
1924 {return __table_.__insert_multi(__p.__i_, __x);}
1926 template <class _InputIterator>
1927 _LIBCPP_INLINE_VISIBILITY
1928 void insert(_InputIterator __first, _InputIterator __last);
1930 #ifndef _LIBCPP_CXX03_LANG
1931 _LIBCPP_INLINE_VISIBILITY
1932 void insert(initializer_list<value_type> __il)
1933 {insert(__il.begin(), __il.end());}
1934 _LIBCPP_INLINE_VISIBILITY
1935 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1937 _LIBCPP_INLINE_VISIBILITY
1938 iterator insert(const_iterator __p, value_type&& __x)
1939 {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));}
1941 template <class _Pp,
1942 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1943 _LIBCPP_INLINE_VISIBILITY
1944 iterator insert(_Pp&& __x)
1945 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1947 template <class _Pp,
1948 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1949 _LIBCPP_INLINE_VISIBILITY
1950 iterator insert(const_iterator __p, _Pp&& __x)
1951 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1953 template <class... _Args>
1954 iterator emplace(_Args&&... __args) {
1955 return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1958 template <class... _Args>
1959 iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1960 return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1962 #endif // _LIBCPP_CXX03_LANG
1965 _LIBCPP_INLINE_VISIBILITY
1966 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1967 _LIBCPP_INLINE_VISIBILITY
1968 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
1969 _LIBCPP_INLINE_VISIBILITY
1970 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1971 _LIBCPP_INLINE_VISIBILITY
1972 iterator erase(const_iterator __first, const_iterator __last)
1973 {return __table_.erase(__first.__i_, __last.__i_);}
1974 _LIBCPP_INLINE_VISIBILITY
1975 void clear() _NOEXCEPT {__table_.clear();}
1977 #if _LIBCPP_STD_VER > 14
1978 _LIBCPP_INLINE_VISIBILITY
1979 iterator insert(node_type&& __nh)
1981 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1982 "node_type with incompatible allocator passed to unordered_multimap::insert()");
1983 return __table_.template __node_handle_insert_multi<node_type>(
1986 _LIBCPP_INLINE_VISIBILITY
1987 iterator insert(const_iterator __hint, node_type&& __nh)
1989 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1990 "node_type with incompatible allocator passed to unordered_multimap::insert()");
1991 return __table_.template __node_handle_insert_multi<node_type>(
1992 __hint.__i_, _VSTD::move(__nh));
1994 _LIBCPP_INLINE_VISIBILITY
1995 node_type extract(key_type const& __key)
1997 return __table_.template __node_handle_extract<node_type>(__key);
1999 _LIBCPP_INLINE_VISIBILITY
2000 node_type extract(const_iterator __it)
2002 return __table_.template __node_handle_extract<node_type>(
2006 template <class _H2, class _P2>
2007 _LIBCPP_INLINE_VISIBILITY
2008 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
2010 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2011 "merging container with incompatible allocator");
2012 return __table_.__node_handle_merge_multi(__source.__table_);
2014 template <class _H2, class _P2>
2015 _LIBCPP_INLINE_VISIBILITY
2016 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
2018 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2019 "merging container with incompatible allocator");
2020 return __table_.__node_handle_merge_multi(__source.__table_);
2022 template <class _H2, class _P2>
2023 _LIBCPP_INLINE_VISIBILITY
2024 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
2026 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2027 "merging container with incompatible allocator");
2028 return __table_.__node_handle_merge_multi(__source.__table_);
2030 template <class _H2, class _P2>
2031 _LIBCPP_INLINE_VISIBILITY
2032 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
2034 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2035 "merging container with incompatible allocator");
2036 return __table_.__node_handle_merge_multi(__source.__table_);
2040 _LIBCPP_INLINE_VISIBILITY
2041 void swap(unordered_multimap& __u)
2042 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
2043 {__table_.swap(__u.__table_);}
2045 _LIBCPP_INLINE_VISIBILITY
2046 hasher hash_function() const
2047 {return __table_.hash_function().hash_function();}
2048 _LIBCPP_INLINE_VISIBILITY
2049 key_equal key_eq() const
2050 {return __table_.key_eq().key_eq();}
2052 _LIBCPP_INLINE_VISIBILITY
2053 iterator find(const key_type& __k) {return __table_.find(__k);}
2054 _LIBCPP_INLINE_VISIBILITY
2055 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
2056 _LIBCPP_INLINE_VISIBILITY
2057 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
2058 #if _LIBCPP_STD_VER > 17
2059 _LIBCPP_INLINE_VISIBILITY
2060 bool contains(const key_type& __k) const {return find(__k) != end();}
2061 #endif // _LIBCPP_STD_VER > 17
2062 _LIBCPP_INLINE_VISIBILITY
2063 pair<iterator, iterator> equal_range(const key_type& __k)
2064 {return __table_.__equal_range_multi(__k);}
2065 _LIBCPP_INLINE_VISIBILITY
2066 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
2067 {return __table_.__equal_range_multi(__k);}
2069 _LIBCPP_INLINE_VISIBILITY
2070 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
2071 _LIBCPP_INLINE_VISIBILITY
2072 size_type max_bucket_count() const _NOEXCEPT
2073 {return __table_.max_bucket_count();}
2075 _LIBCPP_INLINE_VISIBILITY
2076 size_type bucket_size(size_type __n) const
2077 {return __table_.bucket_size(__n);}
2078 _LIBCPP_INLINE_VISIBILITY
2079 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
2081 _LIBCPP_INLINE_VISIBILITY
2082 local_iterator begin(size_type __n) {return __table_.begin(__n);}
2083 _LIBCPP_INLINE_VISIBILITY
2084 local_iterator end(size_type __n) {return __table_.end(__n);}
2085 _LIBCPP_INLINE_VISIBILITY
2086 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
2087 _LIBCPP_INLINE_VISIBILITY
2088 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
2089 _LIBCPP_INLINE_VISIBILITY
2090 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
2091 _LIBCPP_INLINE_VISIBILITY
2092 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
2094 _LIBCPP_INLINE_VISIBILITY
2095 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
2096 _LIBCPP_INLINE_VISIBILITY
2097 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
2098 _LIBCPP_INLINE_VISIBILITY
2099 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
2100 _LIBCPP_INLINE_VISIBILITY
2101 void rehash(size_type __n) {__table_.rehash(__n);}
2102 _LIBCPP_INLINE_VISIBILITY
2103 void reserve(size_type __n) {__table_.reserve(__n);}
2105 #if _LIBCPP_DEBUG_LEVEL >= 2
2107 bool __dereferenceable(const const_iterator* __i) const
2108 {return __table_.__dereferenceable(&__i->__i_);}
2109 bool __decrementable(const const_iterator* __i) const
2110 {return __table_.__decrementable(&__i->__i_);}
2111 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
2112 {return __table_.__addable(&__i->__i_, __n);}
2113 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2114 {return __table_.__addable(&__i->__i_, __n);}
2116 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2121 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
2122 template<class _InputIterator,
2123 class _Hash = hash<__iter_key_type<_InputIterator>>,
2124 class _Pred = equal_to<__iter_key_type<_InputIterator>>,
2125 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2126 class = _EnableIf<!__is_allocator<_Hash>::value>,
2127 class = _EnableIf<!is_integral<_Hash>::value>,
2128 class = _EnableIf<!__is_allocator<_Pred>::value>,
2129 class = _EnableIf<__is_allocator<_Allocator>::value>>
2130 unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
2131 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
2132 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>;
2134 template<class _Key, class _Tp, class _Hash = hash<remove_const_t<_Key>>,
2135 class _Pred = equal_to<remove_const_t<_Key>>,
2136 class _Allocator = allocator<pair<const _Key, _Tp>>,
2137 class = _EnableIf<!__is_allocator<_Hash>::value>,
2138 class = _EnableIf<!is_integral<_Hash>::value>,
2139 class = _EnableIf<!__is_allocator<_Pred>::value>,
2140 class = _EnableIf<__is_allocator<_Allocator>::value>>
2141 unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type = 0,
2142 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
2143 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
2145 template<class _InputIterator, class _Allocator,
2146 class = _EnableIf<__is_allocator<_Allocator>::value>>
2147 unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
2148 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2149 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
2151 template<class _InputIterator, class _Allocator,
2152 class = _EnableIf<__is_allocator<_Allocator>::value>>
2153 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2154 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2155 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
2157 template<class _InputIterator, class _Hash, class _Allocator,
2158 class = _EnableIf<!__is_allocator<_Hash>::value>,
2159 class = _EnableIf<!is_integral<_Hash>::value>,
2160 class = _EnableIf<__is_allocator<_Allocator>::value>>
2161 unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2162 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2163 _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
2165 template<class _Key, class _Tp, class _Allocator,
2166 class = _EnableIf<__is_allocator<_Allocator>::value>>
2167 unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
2168 -> unordered_multimap<remove_const_t<_Key>, _Tp,
2169 hash<remove_const_t<_Key>>,
2170 equal_to<remove_const_t<_Key>>, _Allocator>;
2172 template<class _Key, class _Tp, class _Allocator,
2173 class = _EnableIf<__is_allocator<_Allocator>::value>>
2174 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2175 -> unordered_multimap<remove_const_t<_Key>, _Tp,
2176 hash<remove_const_t<_Key>>,
2177 equal_to<remove_const_t<_Key>>, _Allocator>;
2179 template<class _Key, class _Tp, class _Hash, class _Allocator,
2180 class = _EnableIf<!__is_allocator<_Hash>::value>,
2181 class = _EnableIf<!is_integral<_Hash>::value>,
2182 class = _EnableIf<__is_allocator<_Allocator>::value>>
2183 unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2184 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash,
2185 equal_to<remove_const_t<_Key>>, _Allocator>;
2188 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2189 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2190 size_type __n, const hasher& __hf, const key_equal& __eql)
2191 : __table_(__hf, __eql)
2193 #if _LIBCPP_DEBUG_LEVEL >= 2
2194 __get_db()->__insert_c(this);
2196 __table_.rehash(__n);
2199 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2200 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2201 size_type __n, const hasher& __hf, const key_equal& __eql,
2202 const allocator_type& __a)
2203 : __table_(__hf, __eql, typename __table::allocator_type(__a))
2205 #if _LIBCPP_DEBUG_LEVEL >= 2
2206 __get_db()->__insert_c(this);
2208 __table_.rehash(__n);
2211 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2212 template <class _InputIterator>
2213 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2214 _InputIterator __first, _InputIterator __last)
2216 #if _LIBCPP_DEBUG_LEVEL >= 2
2217 __get_db()->__insert_c(this);
2219 insert(__first, __last);
2222 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2223 template <class _InputIterator>
2224 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2225 _InputIterator __first, _InputIterator __last, size_type __n,
2226 const hasher& __hf, const key_equal& __eql)
2227 : __table_(__hf, __eql)
2229 #if _LIBCPP_DEBUG_LEVEL >= 2
2230 __get_db()->__insert_c(this);
2232 __table_.rehash(__n);
2233 insert(__first, __last);
2236 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2237 template <class _InputIterator>
2238 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2239 _InputIterator __first, _InputIterator __last, size_type __n,
2240 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
2241 : __table_(__hf, __eql, typename __table::allocator_type(__a))
2243 #if _LIBCPP_DEBUG_LEVEL >= 2
2244 __get_db()->__insert_c(this);
2246 __table_.rehash(__n);
2247 insert(__first, __last);
2250 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2252 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2253 const allocator_type& __a)
2254 : __table_(typename __table::allocator_type(__a))
2256 #if _LIBCPP_DEBUG_LEVEL >= 2
2257 __get_db()->__insert_c(this);
2261 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2262 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2263 const unordered_multimap& __u)
2264 : __table_(__u.__table_)
2266 #if _LIBCPP_DEBUG_LEVEL >= 2
2267 __get_db()->__insert_c(this);
2269 __table_.rehash(__u.bucket_count());
2270 insert(__u.begin(), __u.end());
2273 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2274 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2275 const unordered_multimap& __u, const allocator_type& __a)
2276 : __table_(__u.__table_, typename __table::allocator_type(__a))
2278 #if _LIBCPP_DEBUG_LEVEL >= 2
2279 __get_db()->__insert_c(this);
2281 __table_.rehash(__u.bucket_count());
2282 insert(__u.begin(), __u.end());
2285 #ifndef _LIBCPP_CXX03_LANG
2287 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2289 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2290 unordered_multimap&& __u)
2291 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
2292 : __table_(_VSTD::move(__u.__table_))
2294 #if _LIBCPP_DEBUG_LEVEL >= 2
2295 __get_db()->__insert_c(this);
2296 __get_db()->swap(this, &__u);
2300 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2301 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2302 unordered_multimap&& __u, const allocator_type& __a)
2303 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
2305 #if _LIBCPP_DEBUG_LEVEL >= 2
2306 __get_db()->__insert_c(this);
2308 if (__a != __u.get_allocator())
2310 iterator __i = __u.begin();
2311 while (__u.size() != 0)
2313 __table_.__insert_multi(
2314 __u.__table_.remove((__i++).__i_)->__value_.__move());
2317 #if _LIBCPP_DEBUG_LEVEL >= 2
2319 __get_db()->swap(this, &__u);
2323 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2324 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2325 initializer_list<value_type> __il)
2327 #if _LIBCPP_DEBUG_LEVEL >= 2
2328 __get_db()->__insert_c(this);
2330 insert(__il.begin(), __il.end());
2333 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2334 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2335 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2336 const key_equal& __eql)
2337 : __table_(__hf, __eql)
2339 #if _LIBCPP_DEBUG_LEVEL >= 2
2340 __get_db()->__insert_c(this);
2342 __table_.rehash(__n);
2343 insert(__il.begin(), __il.end());
2346 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2347 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2348 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2349 const key_equal& __eql, const allocator_type& __a)
2350 : __table_(__hf, __eql, typename __table::allocator_type(__a))
2352 #if _LIBCPP_DEBUG_LEVEL >= 2
2353 __get_db()->__insert_c(this);
2355 __table_.rehash(__n);
2356 insert(__il.begin(), __il.end());
2359 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2361 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2362 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
2363 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
2365 __table_ = _VSTD::move(__u.__table_);
2369 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2371 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2372 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
2373 initializer_list<value_type> __il)
2375 __table_.__assign_multi(__il.begin(), __il.end());
2379 #endif // _LIBCPP_CXX03_LANG
2383 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2384 template <class _InputIterator>
2387 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
2388 _InputIterator __last)
2390 for (; __first != __last; ++__first)
2391 __table_.__insert_multi(*__first);
2394 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2395 inline _LIBCPP_INLINE_VISIBILITY
2397 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2398 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2399 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2404 #if _LIBCPP_STD_VER > 17
2405 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
2406 inline _LIBCPP_INLINE_VISIBILITY
2407 void erase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
2408 { __libcpp_erase_if_container(__c, __pred); }
2411 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2413 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2414 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2416 if (__x.size() != __y.size())
2418 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2420 typedef pair<const_iterator, const_iterator> _EqRng;
2421 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2423 _EqRng __xeq = __x.equal_range(__i->first);
2424 _EqRng __yeq = __y.equal_range(__i->first);
2425 if (_VSTD::distance(__xeq.first, __xeq.second) !=
2426 _VSTD::distance(__yeq.first, __yeq.second) ||
2427 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2434 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2435 inline _LIBCPP_INLINE_VISIBILITY
2437 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2438 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2440 return !(__x == __y);
2443 _LIBCPP_END_NAMESPACE_STD
2445 #endif // _LIBCPP_UNORDERED_MAP