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_UNORDERED_MAP
11#define _LIBCPP_UNORDERED_MAP
12
13/*
14
15 unordered_map synopsis
16
17#include <initializer_list>
18
19namespace std
20{
21
22template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
23 class Alloc = allocator<pair<const Key, T>>>
24class unordered_map
25{
26public:
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 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&&)
66 noexcept(
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
90 ~unordered_map();
91 unordered_map& operator=(const unordered_map&);
92 unordered_map& operator=(unordered_map&&)
93 noexcept(
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>);
99
100 allocator_type get_allocator() const noexcept;
101
102 bool empty() const noexcept;
103 size_type size() const noexcept;
104 size_type max_size() const noexcept;
105
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;
112
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);
118 template <class P>
119 pair<iterator, bool> insert(P&& obj);
120 iterator insert(const_iterator hint, const value_type& obj);
121 template <class P>
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>);
126
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
131
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
140 template <class M>
141 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
142 template <class M>
143 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
144 template <class M>
145 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
146 template <class M>
147 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
148
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;
154
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
163
164 void swap(unordered_map&)
165 noexcept(
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);
170
171 hasher hash_function() const;
172 key_equal key_eq() const;
173
174 iterator find(const key_type& k);
175 const_iterator find(const key_type& k) const;
176 template<typename K>
177 iterator find(const K& x); // C++20
178 template<typename K>
179 const_iterator find(const K& x) const; // C++20
180 size_type count(const key_type& k) const;
181 template<typename K>
182 size_type count(const K& k) const; // C++20
183 bool contains(const key_type& k) const; // C++20
184 template<typename K>
185 bool contains(const K& k) const; // C++20
186 pair<iterator, iterator> equal_range(const key_type& k);
187 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
188 template<typename K>
189 pair<iterator, iterator> equal_range(const K& k); // C++20
190 template<typename K>
191 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
192
193 mapped_type& operator[](const key_type& k);
194 mapped_type& operator[](key_type&& k);
195
196 mapped_type& at(const key_type& k);
197 const mapped_type& at(const key_type& k) const;
198
199 size_type bucket_count() const noexcept;
200 size_type max_bucket_count() const noexcept;
201
202 size_type bucket_size(size_type n) const;
203 size_type bucket(const key_type& k) const;
204
205 local_iterator begin(size_type n);
206 local_iterator end(size_type n);
207 const_local_iterator begin(size_type n) const;
208 const_local_iterator end(size_type n) const;
209 const_local_iterator cbegin(size_type n) const;
210 const_local_iterator cend(size_type n) const;
211
212 float load_factor() const noexcept;
213 float max_load_factor() const noexcept;
214 void max_load_factor(float z);
215 void rehash(size_type n);
216 void reserve(size_type n);
217};
218
219template<class InputIterator,
220 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,
221 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
222unordered_map(InputIterator, InputIterator, typename see below::size_type = see below,
223 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
224 -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
225 Allocator>; // C++17
226
227template<class Key, class T, class Hash = hash<Key>,
228 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
229unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,
230 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
231 -> unordered_map<Key, T, Hash, Pred, Allocator>; // C++17
232
233template<class InputIterator, class Allocator>
234unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)
235 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
236 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
237
238template<class InputIterator, class Allocator>
239unordered_map(InputIterator, InputIterator, Allocator)
240 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
241 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
242
243template<class InputIterator, class Hash, class Allocator>
244unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
245 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
246 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
247
248template<class Key, class T, typename Allocator>
249unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)
250 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
251
252template<class Key, class T, typename Allocator>
253unordered_map(initializer_list<pair<const Key, T>>, Allocator)
254 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
255
256template<class Key, class T, class Hash, class Allocator>
257unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, Allocator)
258 -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>; // C++17
259
260template <class Key, class T, class Hash, class Pred, class Alloc>
261 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
262 unordered_map<Key, T, Hash, Pred, Alloc>& y)
263 noexcept(noexcept(x.swap(y)));
264
265template <class Key, class T, class Hash, class Pred, class Alloc>
266 bool
267 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
268 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
269
270template <class Key, class T, class Hash, class Pred, class Alloc>
271 bool
272 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
273 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
274
275template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
276 class Alloc = allocator<pair<const Key, T>>>
277class unordered_multimap
278{
279public:
280 // types
281 typedef Key key_type;
282 typedef T mapped_type;
283 typedef Hash hasher;
284 typedef Pred key_equal;
285 typedef Alloc allocator_type;
286 typedef pair<const key_type, mapped_type> value_type;
287 typedef value_type& reference;
288 typedef const value_type& const_reference;
289 typedef typename allocator_traits<allocator_type>::pointer pointer;
290 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
291 typedef typename allocator_traits<allocator_type>::size_type size_type;
292 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
293
294 typedef /unspecified/ iterator;
295 typedef /unspecified/ const_iterator;
296 typedef /unspecified/ local_iterator;
297 typedef /unspecified/ const_local_iterator;
298
299 typedef unspecified node_type; // C++17
300
301 unordered_multimap()
302 noexcept(
303 is_nothrow_default_constructible<hasher>::value &&
304 is_nothrow_default_constructible<key_equal>::value &&
305 is_nothrow_default_constructible<allocator_type>::value);
306 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
307 const key_equal& eql = key_equal(),
308 const allocator_type& a = allocator_type());
309 template <class InputIterator>
310 unordered_multimap(InputIterator f, InputIterator l,
311 size_type n = 0, const hasher& hf = hasher(),
312 const key_equal& eql = key_equal(),
313 const allocator_type& a = allocator_type());
314 explicit unordered_multimap(const allocator_type&);
315 unordered_multimap(const unordered_multimap&);
316 unordered_multimap(const unordered_multimap&, const Allocator&);
317 unordered_multimap(unordered_multimap&&)
318 noexcept(
319 is_nothrow_move_constructible<hasher>::value &&
320 is_nothrow_move_constructible<key_equal>::value &&
321 is_nothrow_move_constructible<allocator_type>::value);
322 unordered_multimap(unordered_multimap&&, const Allocator&);
323 unordered_multimap(initializer_list<value_type>, size_type n = 0,
324 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
325 const allocator_type& a = allocator_type());
326 unordered_multimap(size_type n, const allocator_type& a)
327 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14
328 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
329 : unordered_multimap(n, hf, key_equal(), a) {} // C++14
330 template <class InputIterator>
331 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
332 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14
333 template <class InputIterator>
334 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
335 const allocator_type& a)
336 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14
337 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)
338 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14
339 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
340 const allocator_type& a)
341 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14
342 ~unordered_multimap();
343 unordered_multimap& operator=(const unordered_multimap&);
344 unordered_multimap& operator=(unordered_multimap&&)
345 noexcept(
346 allocator_type::propagate_on_container_move_assignment::value &&
347 is_nothrow_move_assignable<allocator_type>::value &&
348 is_nothrow_move_assignable<hasher>::value &&
349 is_nothrow_move_assignable<key_equal>::value);
350 unordered_multimap& operator=(initializer_list<value_type>);
351
352 allocator_type get_allocator() const noexcept;
353
354 bool empty() const noexcept;
355 size_type size() const noexcept;
356 size_type max_size() const noexcept;
357
358 iterator begin() noexcept;
359 iterator end() noexcept;
360 const_iterator begin() const noexcept;
361 const_iterator end() const noexcept;
362 const_iterator cbegin() const noexcept;
363 const_iterator cend() const noexcept;
364
365 template <class... Args>
366 iterator emplace(Args&&... args);
367 template <class... Args>
368 iterator emplace_hint(const_iterator position, Args&&... args);
369 iterator insert(const value_type& obj);
370 template <class P>
371 iterator insert(P&& obj);
372 iterator insert(const_iterator hint, const value_type& obj);
373 template <class P>
374 iterator insert(const_iterator hint, P&& obj);
375 template <class InputIterator>
376 void insert(InputIterator first, InputIterator last);
377 void insert(initializer_list<value_type>);
378
379 node_type extract(const_iterator position); // C++17
380 node_type extract(const key_type& x); // C++17
381 iterator insert(node_type&& nh); // C++17
382 iterator insert(const_iterator hint, node_type&& nh); // C++17
383
384 iterator erase(const_iterator position);
385 iterator erase(iterator position); // C++14
386 size_type erase(const key_type& k);
387 iterator erase(const_iterator first, const_iterator last);
388 void clear() noexcept;
389
390 template<class H2, class P2>
391 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17
392 template<class H2, class P2>
393 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17
394 template<class H2, class P2>
395 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17
396 template<class H2, class P2>
397 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17
398
399 void swap(unordered_multimap&)
400 noexcept(
401 (!allocator_type::propagate_on_container_swap::value ||
402 __is_nothrow_swappable<allocator_type>::value) &&
403 __is_nothrow_swappable<hasher>::value &&
404 __is_nothrow_swappable<key_equal>::value);
405
406 hasher hash_function() const;
407 key_equal key_eq() const;
408
409 iterator find(const key_type& k);
410 const_iterator find(const key_type& k) const;
411 template<typename K>
412 iterator find(const K& x); // C++20
413 template<typename K>
414 const_iterator find(const K& x) const; // C++20
415 size_type count(const key_type& k) const;
416 template<typename K>
417 size_type count(const K& k) const; // C++20
418 bool contains(const key_type& k) const; // C++20
419 template<typename K>
420 bool contains(const K& k) const; // C++20
421 pair<iterator, iterator> equal_range(const key_type& k);
422 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
423 template<typename K>
424 pair<iterator, iterator> equal_range(const K& k); // C++20
425 template<typename K>
426 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
427
428 size_type bucket_count() const noexcept;
429 size_type max_bucket_count() const noexcept;
430
431 size_type bucket_size(size_type n) const;
432 size_type bucket(const key_type& k) const;
433
434 local_iterator begin(size_type n);
435 local_iterator end(size_type n);
436 const_local_iterator begin(size_type n) const;
437 const_local_iterator end(size_type n) const;
438 const_local_iterator cbegin(size_type n) const;
439 const_local_iterator cend(size_type n) const;
440
441 float load_factor() const noexcept;
442 float max_load_factor() const noexcept;
443 void max_load_factor(float z);
444 void rehash(size_type n);
445 void reserve(size_type n);
446};
447
448template<class InputIterator,
449 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,
450 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
451unordered_multimap(InputIterator, InputIterator, typename see below::size_type = see below,
452 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
453 -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
454 Allocator>; // C++17
455
456template<class Key, class T, class Hash = hash<Key>,
457 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
458unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,
459 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
460 -> unordered_multimap<Key, T, Hash, Pred, Allocator>; // C++17
461
462template<class InputIterator, class Allocator>
463unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)
464 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
465 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
466
467template<class InputIterator, class Allocator>
468unordered_multimap(InputIterator, InputIterator, Allocator)
469 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
470 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
471
472template<class InputIterator, class Hash, class Allocator>
473unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
474 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
475 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
476
477template<class Key, class T, typename Allocator>
478unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)
479 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
480
481template<class Key, class T, typename Allocator>
482unordered_multimap(initializer_list<pair<const Key, T>>, Allocator)
483 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
484
485template<class Key, class T, class Hash, class Allocator>
486unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash,
487 Allocator)
488 -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>; // C++17
489
490template <class Key, class T, class Hash, class Pred, class Alloc>
491 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
492 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
493 noexcept(noexcept(x.swap(y)));
494
495template <class K, class T, class H, class P, class A, class Predicate>
496 typename unordered_map<K, T, H, P, A>::size_type
497 erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred); // C++20
498
499template <class K, class T, class H, class P, class A, class Predicate>
500 typename unordered_multimap<K, T, H, P, A>::size_type
501 erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred); // C++20
502
503template <class Key, class T, class Hash, class Pred, class Alloc>
504 bool
505 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
506 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
507
508template <class Key, class T, class Hash, class Pred, class Alloc>
509 bool
510 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
511 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
512
513} // std
514
515*/
516
517#include <__algorithm/is_permutation.h>
518#include <__assert> // all public C++ headers provide the assertion handler
519#include <__config>
520#include <__debug>
521#include <__functional/is_transparent.h>
522#include <__functional/operations.h>
523#include <__hash_table>
524#include <__iterator/distance.h>
525#include <__iterator/erase_if_container.h>
526#include <__iterator/iterator_traits.h>
527#include <__memory/addressof.h>
528#include <__node_handle>
529#include <__utility/forward.h>
530#include <stdexcept>
531#include <tuple>
532#include <version>
533
534#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES
535# include <algorithm>
536# include <bit>
537# include <iterator>
538#endif
539
540// standard-mandated includes
541
542// [iterator.range]
543#include <__iterator/access.h>
544#include <__iterator/data.h>
545#include <__iterator/empty.h>
546#include <__iterator/reverse_access.h>
547#include <__iterator/size.h>
548
549// [unord.map.syn]
550#include <compare>
551#include <initializer_list>
552
553#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
554# pragma GCC system_header
555#endif
556
557_LIBCPP_BEGIN_NAMESPACE_STD
558
559template <class _Key, class _Cp, class _Hash, class _Pred,
560 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
561class __unordered_map_hasher
562 : private _Hash
563{
564public:
565 _LIBCPP_INLINE_VISIBILITY
566 __unordered_map_hasher()
567 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
568 : _Hash() {}
569 _LIBCPP_INLINE_VISIBILITY
570 __unordered_map_hasher(const _Hash& __h)
571 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
572 : _Hash(__h) {}
573 _LIBCPP_INLINE_VISIBILITY
574 const _Hash& hash_function() const _NOEXCEPT {return *this;}
575 _LIBCPP_INLINE_VISIBILITY
576 size_t operator()(const _Cp& __x) const
577 {return static_cast<const _Hash&>(*this)(__x.__get_value().first);}
578 _LIBCPP_INLINE_VISIBILITY
579 size_t operator()(const _Key& __x) const
580 {return static_cast<const _Hash&>(*this)(__x);}
581#if _LIBCPP_STD_VER > 17
582 template <typename _K2>
583 _LIBCPP_INLINE_VISIBILITY
584 size_t operator()(const _K2& __x) const
585 {return static_cast<const _Hash&>(*this)(__x);}
586#endif
587 _LIBCPP_INLINE_VISIBILITY
588 void swap(__unordered_map_hasher& __y)
589 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
590 {
591 using _VSTD::swap;
592 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
593 }
594};
595
596template <class _Key, class _Cp, class _Hash, class _Pred>
597class __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false>
598{
599 _Hash __hash_;
600public:
601 _LIBCPP_INLINE_VISIBILITY
602 __unordered_map_hasher()
603 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
604 : __hash_() {}
605 _LIBCPP_INLINE_VISIBILITY
606 __unordered_map_hasher(const _Hash& __h)
607 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
608 : __hash_(__h) {}
609 _LIBCPP_INLINE_VISIBILITY
610 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
611 _LIBCPP_INLINE_VISIBILITY
612 size_t operator()(const _Cp& __x) const
613 {return __hash_(__x.__get_value().first);}
614 _LIBCPP_INLINE_VISIBILITY
615 size_t operator()(const _Key& __x) const
616 {return __hash_(__x);}
617#if _LIBCPP_STD_VER > 17
618 template <typename _K2>
619 _LIBCPP_INLINE_VISIBILITY
620 size_t operator()(const _K2& __x) const
621 {return __hash_(__x);}
622#endif
623 _LIBCPP_INLINE_VISIBILITY
624 void swap(__unordered_map_hasher& __y)
625 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
626 {
627 using _VSTD::swap;
628 swap(__hash_, __y.__hash_);
629 }
630};
631
632template <class _Key, class _Cp, class _Hash, class _Pred, bool __b>
633inline _LIBCPP_INLINE_VISIBILITY
634void
635swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x,
636 __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y)
637 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
638{
639 __x.swap(__y);
640}
641
642template <class _Key, class _Cp, class _Pred, class _Hash,
643 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>
644class __unordered_map_equal
645 : private _Pred
646{
647public:
648 _LIBCPP_INLINE_VISIBILITY
649 __unordered_map_equal()
650 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
651 : _Pred() {}
652 _LIBCPP_INLINE_VISIBILITY
653 __unordered_map_equal(const _Pred& __p)
654 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
655 : _Pred(__p) {}
656 _LIBCPP_INLINE_VISIBILITY
657 const _Pred& key_eq() const _NOEXCEPT {return *this;}
658 _LIBCPP_INLINE_VISIBILITY
659 bool operator()(const _Cp& __x, const _Cp& __y) const
660 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);}
661 _LIBCPP_INLINE_VISIBILITY
662 bool operator()(const _Cp& __x, const _Key& __y) const
663 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);}
664 _LIBCPP_INLINE_VISIBILITY
665 bool operator()(const _Key& __x, const _Cp& __y) const
666 {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);}
667#if _LIBCPP_STD_VER > 17
668 template <typename _K2>
669 _LIBCPP_INLINE_VISIBILITY
670 bool operator()(const _Cp& __x, const _K2& __y) const
671 {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);}
672 template <typename _K2>
673 _LIBCPP_INLINE_VISIBILITY
674 bool operator()(const _K2& __x, const _Cp& __y) const
675 {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);}
676 template <typename _K2>
677 _LIBCPP_INLINE_VISIBILITY
678 bool operator()(const _Key& __x, const _K2& __y) const
679 {return static_cast<const _Pred&>(*this)(__x, __y);}
680 template <typename _K2>
681 _LIBCPP_INLINE_VISIBILITY
682 bool operator()(const _K2& __x, const _Key& __y) const
683 {return static_cast<const _Pred&>(*this)(__x, __y);}
684#endif
685 _LIBCPP_INLINE_VISIBILITY
686 void swap(__unordered_map_equal& __y)
687 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
688 {
689 using _VSTD::swap;
690 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
691 }
692};
693
694template <class _Key, class _Cp, class _Pred, class _Hash>
695class __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false>
696{
697 _Pred __pred_;
698public:
699 _LIBCPP_INLINE_VISIBILITY
700 __unordered_map_equal()
701 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
702 : __pred_() {}
703 _LIBCPP_INLINE_VISIBILITY
704 __unordered_map_equal(const _Pred& __p)
705 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
706 : __pred_(__p) {}
707 _LIBCPP_INLINE_VISIBILITY
708 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
709 _LIBCPP_INLINE_VISIBILITY
710 bool operator()(const _Cp& __x, const _Cp& __y) const
711 {return __pred_(__x.__get_value().first, __y.__get_value().first);}
712 _LIBCPP_INLINE_VISIBILITY
713 bool operator()(const _Cp& __x, const _Key& __y) const
714 {return __pred_(__x.__get_value().first, __y);}
715 _LIBCPP_INLINE_VISIBILITY
716 bool operator()(const _Key& __x, const _Cp& __y) const
717 {return __pred_(__x, __y.__get_value().first);}
718#if _LIBCPP_STD_VER > 17
719 template <typename _K2>
720 _LIBCPP_INLINE_VISIBILITY
721 bool operator()(const _Cp& __x, const _K2& __y) const
722 {return __pred_(__x.__get_value().first, __y);}
723 template <typename _K2>
724 _LIBCPP_INLINE_VISIBILITY
725 bool operator()(const _K2& __x, const _Cp& __y) const
726 {return __pred_(__x, __y.__get_value().first);}
727 template <typename _K2>
728 _LIBCPP_INLINE_VISIBILITY
729 bool operator()(const _Key& __x, const _K2& __y) const
730 {return __pred_(__x, __y);}
731 template <typename _K2>
732 _LIBCPP_INLINE_VISIBILITY
733 bool operator()(const _K2& __x, const _Key& __y) const
734 {return __pred_(__x, __y);}
735#endif
736 _LIBCPP_INLINE_VISIBILITY
737 void swap(__unordered_map_equal& __y)
738 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
739 {
740 using _VSTD::swap;
741 swap(__pred_, __y.__pred_);
742 }
743};
744
745template <class _Key, class _Cp, class _Pred, class _Hash, bool __b>
746inline _LIBCPP_INLINE_VISIBILITY
747void
748swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x,
749 __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y)
750 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
751{
752 __x.swap(__y);
753}
754
755template <class _Alloc>
756class __hash_map_node_destructor
757{
758 typedef _Alloc allocator_type;
759 typedef allocator_traits<allocator_type> __alloc_traits;
760
761public:
762
763 typedef typename __alloc_traits::pointer pointer;
764private:
765
766 allocator_type& __na_;
767
768 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
769
770public:
771 bool __first_constructed;
772 bool __second_constructed;
773
774 _LIBCPP_INLINE_VISIBILITY
775 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
776 : __na_(__na),
777 __first_constructed(false),
778 __second_constructed(false)
779 {}
780
781#ifndef _LIBCPP_CXX03_LANG
782 _LIBCPP_INLINE_VISIBILITY
783 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
784 _NOEXCEPT
785 : __na_(__x.__na_),
786 __first_constructed(__x.__value_constructed),
787 __second_constructed(__x.__value_constructed)
788 {
789 __x.__value_constructed = false;
790 }
791#else // _LIBCPP_CXX03_LANG
792 _LIBCPP_INLINE_VISIBILITY
793 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
794 : __na_(__x.__na_),
795 __first_constructed(__x.__value_constructed),
796 __second_constructed(__x.__value_constructed)
797 {
798 const_cast<bool&>(__x.__value_constructed) = false;
799 }
800#endif // _LIBCPP_CXX03_LANG
801
802 _LIBCPP_INLINE_VISIBILITY
803 void operator()(pointer __p) _NOEXCEPT
804 {
805 if (__second_constructed)
806 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
807 if (__first_constructed)
808 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
809 if (__p)
810 __alloc_traits::deallocate(__na_, __p, 1);
811 }
812};
813
814#ifndef _LIBCPP_CXX03_LANG
815template <class _Key, class _Tp>
816struct _LIBCPP_STANDALONE_DEBUG __hash_value_type
817{
818 typedef _Key key_type;
819 typedef _Tp mapped_type;
820 typedef pair<const key_type, mapped_type> value_type;
821 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
822 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
823
824private:
825 value_type __cc;
826
827public:
828 _LIBCPP_INLINE_VISIBILITY
829 value_type& __get_value()
830 {
831#if _LIBCPP_STD_VER > 14
832 return *_VSTD::launder(_VSTD::addressof(__cc));
833#else
834 return __cc;
835#endif
836 }
837
838 _LIBCPP_INLINE_VISIBILITY
839 const value_type& __get_value() const
840 {
841#if _LIBCPP_STD_VER > 14
842 return *_VSTD::launder(_VSTD::addressof(__cc));
843#else
844 return __cc;
845#endif
846 }
847
848 _LIBCPP_INLINE_VISIBILITY
849 __nc_ref_pair_type __ref()
850 {
851 value_type& __v = __get_value();
852 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
853 }
854
855 _LIBCPP_INLINE_VISIBILITY
856 __nc_rref_pair_type __move()
857 {
858 value_type& __v = __get_value();
859 return __nc_rref_pair_type(
860 _VSTD::move(const_cast<key_type&>(__v.first)),
861 _VSTD::move(__v.second));
862 }
863
864 _LIBCPP_INLINE_VISIBILITY
865 __hash_value_type& operator=(const __hash_value_type& __v)
866 {
867 __ref() = __v.__get_value();
868 return *this;
869 }
870
871 _LIBCPP_INLINE_VISIBILITY
872 __hash_value_type& operator=(__hash_value_type&& __v)
873 {
874 __ref() = __v.__move();
875 return *this;
876 }
877
878 template <class _ValueTp,
879 class = __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value>
880 >
881 _LIBCPP_INLINE_VISIBILITY
882 __hash_value_type& operator=(_ValueTp&& __v)
883 {
884 __ref() = _VSTD::forward<_ValueTp>(__v);
885 return *this;
886 }
887
888private:
889 __hash_value_type(const __hash_value_type& __v) = delete;
890 __hash_value_type(__hash_value_type&& __v) = delete;
891 template <class ..._Args>
892 explicit __hash_value_type(_Args&& ...__args) = delete;
893
894 ~__hash_value_type() = delete;
895};
896
897#else
898
899template <class _Key, class _Tp>
900struct __hash_value_type
901{
902 typedef _Key key_type;
903 typedef _Tp mapped_type;
904 typedef pair<const key_type, mapped_type> value_type;
905
906private:
907 value_type __cc;
908
909public:
910 _LIBCPP_INLINE_VISIBILITY
911 value_type& __get_value() { return __cc; }
912 _LIBCPP_INLINE_VISIBILITY
913 const value_type& __get_value() const { return __cc; }
914
915private:
916 ~__hash_value_type();
917};
918
919#endif
920
921template <class _HashIterator>
922class _LIBCPP_TEMPLATE_VIS __hash_map_iterator
923{
924 _HashIterator __i_;
925
926 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
927
928public:
929 typedef forward_iterator_tag iterator_category;
930 typedef typename _NodeTypes::__map_value_type value_type;
931 typedef typename _NodeTypes::difference_type difference_type;
932 typedef value_type& reference;
933 typedef typename _NodeTypes::__map_value_type_pointer pointer;
934
935 _LIBCPP_INLINE_VISIBILITY
936 __hash_map_iterator() _NOEXCEPT {}
937
938 _LIBCPP_INLINE_VISIBILITY
939 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
940
941 _LIBCPP_INLINE_VISIBILITY
942 reference operator*() const {return __i_->__get_value();}
943 _LIBCPP_INLINE_VISIBILITY
944 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
945
946 _LIBCPP_INLINE_VISIBILITY
947 __hash_map_iterator& operator++() {++__i_; return *this;}
948 _LIBCPP_INLINE_VISIBILITY
949 __hash_map_iterator operator++(int)
950 {
951 __hash_map_iterator __t(*this);
952 ++(*this);
953 return __t;
954 }
955
956 friend _LIBCPP_INLINE_VISIBILITY
957 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
958 {return __x.__i_ == __y.__i_;}
959 friend _LIBCPP_INLINE_VISIBILITY
960 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
961 {return __x.__i_ != __y.__i_;}
962
963 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
964 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
965 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
966 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
967 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
968};
969
970template <class _HashIterator>
971class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator
972{
973 _HashIterator __i_;
974
975 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
976
977public:
978 typedef forward_iterator_tag iterator_category;
979 typedef typename _NodeTypes::__map_value_type value_type;
980 typedef typename _NodeTypes::difference_type difference_type;
981 typedef const value_type& reference;
982 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
983
984 _LIBCPP_INLINE_VISIBILITY
985 __hash_map_const_iterator() _NOEXCEPT {}
986
987 _LIBCPP_INLINE_VISIBILITY
988 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
989 _LIBCPP_INLINE_VISIBILITY
990 __hash_map_const_iterator(
991 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
992 _NOEXCEPT
993 : __i_(__i.__i_) {}
994
995 _LIBCPP_INLINE_VISIBILITY
996 reference operator*() const {return __i_->__get_value();}
997 _LIBCPP_INLINE_VISIBILITY
998 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
999
1000 _LIBCPP_INLINE_VISIBILITY
1001 __hash_map_const_iterator& operator++() {++__i_; return *this;}
1002 _LIBCPP_INLINE_VISIBILITY
1003 __hash_map_const_iterator operator++(int)
1004 {
1005 __hash_map_const_iterator __t(*this);
1006 ++(*this);
1007 return __t;
1008 }
1009
1010 friend _LIBCPP_INLINE_VISIBILITY
1011 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
1012 {return __x.__i_ == __y.__i_;}
1013 friend _LIBCPP_INLINE_VISIBILITY
1014 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
1015 {return __x.__i_ != __y.__i_;}
1016
1017 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1018 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1019 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
1020 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
1021};
1022
1023template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1024class unordered_multimap;
1025
1026template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1027 class _Alloc = allocator<pair<const _Key, _Tp> > >
1028class _LIBCPP_TEMPLATE_VIS unordered_map
1029{
1030public:
1031 // types
1032 typedef _Key key_type;
1033 typedef _Tp mapped_type;
1034 typedef __type_identity_t<_Hash> hasher;
1035 typedef __type_identity_t<_Pred> key_equal;
1036 typedef __type_identity_t<_Alloc> allocator_type;
1037 typedef pair<const key_type, mapped_type> value_type;
1038 typedef value_type& reference;
1039 typedef const value_type& const_reference;
1040 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1041 "Invalid allocator::value_type");
1042
1043private:
1044 typedef __hash_value_type<key_type, mapped_type> __value_type;
1045 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
1046 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
1047 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1048 __value_type>::type __allocator_type;
1049
1050 typedef __hash_table<__value_type, __hasher,
1051 __key_equal, __allocator_type> __table;
1052
1053 __table __table_;
1054
1055 typedef typename __table::_NodeTypes _NodeTypes;
1056 typedef typename __table::__node_pointer __node_pointer;
1057 typedef typename __table::__node_const_pointer __node_const_pointer;
1058 typedef typename __table::__node_traits __node_traits;
1059 typedef typename __table::__node_allocator __node_allocator;
1060 typedef typename __table::__node __node;
1061 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1062 typedef unique_ptr<__node, _Dp> __node_holder;
1063 typedef allocator_traits<allocator_type> __alloc_traits;
1064
1065 static_assert((is_same<typename __table::__container_value_type, value_type>::value), "");
1066 static_assert((is_same<typename __table::__node_value_type, __value_type>::value), "");
1067public:
1068 typedef typename __alloc_traits::pointer pointer;
1069 typedef typename __alloc_traits::const_pointer const_pointer;
1070 typedef typename __table::size_type size_type;
1071 typedef typename __table::difference_type difference_type;
1072
1073 typedef __hash_map_iterator<typename __table::iterator> iterator;
1074 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1075 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1076 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1077
1078#if _LIBCPP_STD_VER > 14
1079 typedef __map_node_handle<__node, allocator_type> node_type;
1080 typedef __insert_return_type<iterator, node_type> insert_return_type;
1081#endif
1082
1083 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1084 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1085 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1086 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1087
1088 _LIBCPP_INLINE_VISIBILITY
1089 unordered_map()
1090 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1091 {
1092 _VSTD::__debug_db_insert_c(this);
1093 }
1094 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
1095 const key_equal& __eql = key_equal());
1096 unordered_map(size_type __n, const hasher& __hf,
1097 const key_equal& __eql,
1098 const allocator_type& __a);
1099 template <class _InputIterator>
1100 unordered_map(_InputIterator __first, _InputIterator __last);
1101 template <class _InputIterator>
1102 unordered_map(_InputIterator __first, _InputIterator __last,
1103 size_type __n, const hasher& __hf = hasher(),
1104 const key_equal& __eql = key_equal());
1105 template <class _InputIterator>
1106 unordered_map(_InputIterator __first, _InputIterator __last,
1107 size_type __n, const hasher& __hf,
1108 const key_equal& __eql,
1109 const allocator_type& __a);
1110 _LIBCPP_INLINE_VISIBILITY
1111 explicit unordered_map(const allocator_type& __a);
1112 unordered_map(const unordered_map& __u);
1113 unordered_map(const unordered_map& __u, const allocator_type& __a);
1114#ifndef _LIBCPP_CXX03_LANG
1115 _LIBCPP_INLINE_VISIBILITY
1116 unordered_map(unordered_map&& __u)
1117 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1118 unordered_map(unordered_map&& __u, const allocator_type& __a);
1119 unordered_map(initializer_list<value_type> __il);
1120 unordered_map(initializer_list<value_type> __il, size_type __n,
1121 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1122 unordered_map(initializer_list<value_type> __il, size_type __n,
1123 const hasher& __hf, const key_equal& __eql,
1124 const allocator_type& __a);
1125#endif // _LIBCPP_CXX03_LANG
1126#if _LIBCPP_STD_VER > 11
1127 _LIBCPP_INLINE_VISIBILITY
1128 unordered_map(size_type __n, const allocator_type& __a)
1129 : unordered_map(__n, hasher(), key_equal(), __a) {}
1130 _LIBCPP_INLINE_VISIBILITY
1131 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
1132 : unordered_map(__n, __hf, key_equal(), __a) {}
1133 template <class _InputIterator>
1134 _LIBCPP_INLINE_VISIBILITY
1135 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1136 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
1137 template <class _InputIterator>
1138 _LIBCPP_INLINE_VISIBILITY
1139 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1140 const allocator_type& __a)
1141 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
1142 _LIBCPP_INLINE_VISIBILITY
1143 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1144 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
1145 _LIBCPP_INLINE_VISIBILITY
1146 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1147 const allocator_type& __a)
1148 : unordered_map(__il, __n, __hf, key_equal(), __a) {}
1149#endif
1150 _LIBCPP_INLINE_VISIBILITY
1151 ~unordered_map() {
1152 static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
1153 }
1154
1155 _LIBCPP_INLINE_VISIBILITY
1156 unordered_map& operator=(const unordered_map& __u)
1157 {
1158#ifndef _LIBCPP_CXX03_LANG
1159 __table_ = __u.__table_;
1160#else
1161 if (this != _VSTD::addressof(__u)) {
1162 __table_.clear();
1163 __table_.hash_function() = __u.__table_.hash_function();
1164 __table_.key_eq() = __u.__table_.key_eq();
1165 __table_.max_load_factor() = __u.__table_.max_load_factor();
1166 __table_.__copy_assign_alloc(__u.__table_);
1167 insert(__u.begin(), __u.end());
1168 }
1169#endif
1170 return *this;
1171 }
1172#ifndef _LIBCPP_CXX03_LANG
1173 _LIBCPP_INLINE_VISIBILITY
1174 unordered_map& operator=(unordered_map&& __u)
1175 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1176 _LIBCPP_INLINE_VISIBILITY
1177 unordered_map& operator=(initializer_list<value_type> __il);
1178#endif // _LIBCPP_CXX03_LANG
1179
1180 _LIBCPP_INLINE_VISIBILITY
1181 allocator_type get_allocator() const _NOEXCEPT
1182 {return allocator_type(__table_.__node_alloc());}
1183
1184 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1185 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1186 _LIBCPP_INLINE_VISIBILITY
1187 size_type size() const _NOEXCEPT {return __table_.size();}
1188 _LIBCPP_INLINE_VISIBILITY
1189 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1190
1191 _LIBCPP_INLINE_VISIBILITY
1192 iterator begin() _NOEXCEPT {return __table_.begin();}
1193 _LIBCPP_INLINE_VISIBILITY
1194 iterator end() _NOEXCEPT {return __table_.end();}
1195 _LIBCPP_INLINE_VISIBILITY
1196 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1197 _LIBCPP_INLINE_VISIBILITY
1198 const_iterator end() const _NOEXCEPT {return __table_.end();}
1199 _LIBCPP_INLINE_VISIBILITY
1200 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1201 _LIBCPP_INLINE_VISIBILITY
1202 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1203
1204 _LIBCPP_INLINE_VISIBILITY
1205 pair<iterator, bool> insert(const value_type& __x)
1206 {return __table_.__insert_unique(__x);}
1207
1208 iterator insert(const_iterator __p, const value_type& __x) {
1209 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1210 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not "
1211 "referring to this unordered_map");
1212 ((void)__p);
1213 return insert(__x).first;
1214 }
1215
1216 template <class _InputIterator>
1217 _LIBCPP_INLINE_VISIBILITY
1218 void insert(_InputIterator __first, _InputIterator __last);
1219
1220#ifndef _LIBCPP_CXX03_LANG
1221 _LIBCPP_INLINE_VISIBILITY
1222 void insert(initializer_list<value_type> __il)
1223 {insert(__il.begin(), __il.end());}
1224
1225 _LIBCPP_INLINE_VISIBILITY
1226 pair<iterator, bool> insert(value_type&& __x)
1227 {return __table_.__insert_unique(_VSTD::move(__x));}
1228
1229 iterator insert(const_iterator __p, value_type&& __x) {
1230 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1231 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
1232 " referring to this unordered_map");
1233 ((void)__p);
1234 return __table_.__insert_unique(_VSTD::move(__x)).first;
1235 }
1236
1237 template <class _Pp,
1238 class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
1239 _LIBCPP_INLINE_VISIBILITY
1240 pair<iterator, bool> insert(_Pp&& __x)
1241 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
1242
1243 template <class _Pp,
1244 class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
1245 _LIBCPP_INLINE_VISIBILITY
1246 iterator insert(const_iterator __p, _Pp&& __x)
1247 {
1248 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1249 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
1250 " referring to this unordered_map");
1251 ((void)__p);
1252 return insert(_VSTD::forward<_Pp>(__x)).first;
1253 }
1254
1255 template <class... _Args>
1256 _LIBCPP_INLINE_VISIBILITY
1257 pair<iterator, bool> emplace(_Args&&... __args) {
1258 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1259 }
1260
1261 template <class... _Args>
1262 _LIBCPP_INLINE_VISIBILITY
1263 iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1264 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1265 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
1266 " referring to this unordered_map");
1267 ((void)__p);
1268 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
1269 }
1270
1271#endif // _LIBCPP_CXX03_LANG
1272
1273#if _LIBCPP_STD_VER > 14
1274 template <class... _Args>
1275 _LIBCPP_INLINE_VISIBILITY
1276 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1277 {
1278 return __table_.__emplace_unique_key_args(__k, piecewise_construct,
1279 _VSTD::forward_as_tuple(__k),
1280 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1281 }
1282
1283 template <class... _Args>
1284 _LIBCPP_INLINE_VISIBILITY
1285 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1286 {
1287 return __table_.__emplace_unique_key_args(__k, piecewise_construct,
1288 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1289 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1290 }
1291
1292 template <class... _Args>
1293 _LIBCPP_INLINE_VISIBILITY
1294 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1295 {
1296 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__h)) == this,
1297 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1298 " referring to this unordered_map");
1299 ((void)__h);
1300 return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first;
1301 }
1302
1303 template <class... _Args>
1304 _LIBCPP_INLINE_VISIBILITY
1305 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1306 {
1307 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__h)) == this,
1308 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1309 " referring to this unordered_map");
1310 ((void)__h);
1311 return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first;
1312 }
1313
1314 template <class _Vp>
1315 _LIBCPP_INLINE_VISIBILITY
1316 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1317 {
1318 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1319 __k, _VSTD::forward<_Vp>(__v));
1320 if (!__res.second) {
1321 __res.first->second = _VSTD::forward<_Vp>(__v);
1322 }
1323 return __res;
1324 }
1325
1326 template <class _Vp>
1327 _LIBCPP_INLINE_VISIBILITY
1328 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1329 {
1330 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1331 _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1332 if (!__res.second) {
1333 __res.first->second = _VSTD::forward<_Vp>(__v);
1334 }
1335 return __res;
1336 }
1337
1338 template <class _Vp>
1339 _LIBCPP_INLINE_VISIBILITY
1340 iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v)
1341 {
1342 // FIXME: Add debug mode checking for the iterator input
1343 return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first;
1344 }
1345
1346 template <class _Vp>
1347 _LIBCPP_INLINE_VISIBILITY
1348 iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v)
1349 {
1350 // FIXME: Add debug mode checking for the iterator input
1351 return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first;
1352 }
1353#endif // _LIBCPP_STD_VER > 14
1354
1355 _LIBCPP_INLINE_VISIBILITY
1356 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1357 _LIBCPP_INLINE_VISIBILITY
1358 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
1359 _LIBCPP_INLINE_VISIBILITY
1360 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
1361 _LIBCPP_INLINE_VISIBILITY
1362 iterator erase(const_iterator __first, const_iterator __last)
1363 {return __table_.erase(__first.__i_, __last.__i_);}
1364 _LIBCPP_INLINE_VISIBILITY
1365 void clear() _NOEXCEPT {__table_.clear();}
1366
1367#if _LIBCPP_STD_VER > 14
1368 _LIBCPP_INLINE_VISIBILITY
1369 insert_return_type insert(node_type&& __nh)
1370 {
1371 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1372 "node_type with incompatible allocator passed to unordered_map::insert()");
1373 return __table_.template __node_handle_insert_unique<
1374 node_type, insert_return_type>(_VSTD::move(__nh));
1375 }
1376 _LIBCPP_INLINE_VISIBILITY
1377 iterator insert(const_iterator __hint, node_type&& __nh)
1378 {
1379 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1380 "node_type with incompatible allocator passed to unordered_map::insert()");
1381 return __table_.template __node_handle_insert_unique<node_type>(
1382 __hint.__i_, _VSTD::move(__nh));
1383 }
1384 _LIBCPP_INLINE_VISIBILITY
1385 node_type extract(key_type const& __key)
1386 {
1387 return __table_.template __node_handle_extract<node_type>(__key);
1388 }
1389 _LIBCPP_INLINE_VISIBILITY
1390 node_type extract(const_iterator __it)
1391 {
1392 return __table_.template __node_handle_extract<node_type>(
1393 __it.__i_);
1394 }
1395
1396 template <class _H2, class _P2>
1397 _LIBCPP_INLINE_VISIBILITY
1398 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
1399 {
1400 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1401 "merging container with incompatible allocator");
1402 return __table_.__node_handle_merge_unique(__source.__table_);
1403 }
1404 template <class _H2, class _P2>
1405 _LIBCPP_INLINE_VISIBILITY
1406 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
1407 {
1408 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1409 "merging container with incompatible allocator");
1410 return __table_.__node_handle_merge_unique(__source.__table_);
1411 }
1412 template <class _H2, class _P2>
1413 _LIBCPP_INLINE_VISIBILITY
1414 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
1415 {
1416 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1417 "merging container with incompatible allocator");
1418 return __table_.__node_handle_merge_unique(__source.__table_);
1419 }
1420 template <class _H2, class _P2>
1421 _LIBCPP_INLINE_VISIBILITY
1422 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
1423 {
1424 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1425 "merging container with incompatible allocator");
1426 return __table_.__node_handle_merge_unique(__source.__table_);
1427 }
1428#endif
1429
1430 _LIBCPP_INLINE_VISIBILITY
1431 void swap(unordered_map& __u)
1432 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1433 { __table_.swap(__u.__table_);}
1434
1435 _LIBCPP_INLINE_VISIBILITY
1436 hasher hash_function() const
1437 {return __table_.hash_function().hash_function();}
1438 _LIBCPP_INLINE_VISIBILITY
1439 key_equal key_eq() const
1440 {return __table_.key_eq().key_eq();}
1441
1442 _LIBCPP_INLINE_VISIBILITY
1443 iterator find(const key_type& __k) {return __table_.find(__k);}
1444 _LIBCPP_INLINE_VISIBILITY
1445 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1446#if _LIBCPP_STD_VER > 17
1447 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1448 _LIBCPP_INLINE_VISIBILITY
1449 iterator find(const _K2& __k) {return __table_.find(__k);}
1450 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1451 _LIBCPP_INLINE_VISIBILITY
1452 const_iterator find(const _K2& __k) const {return __table_.find(__k);}
1453#endif // _LIBCPP_STD_VER > 17
1454
1455 _LIBCPP_INLINE_VISIBILITY
1456 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
1457#if _LIBCPP_STD_VER > 17
1458 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1459 _LIBCPP_INLINE_VISIBILITY
1460 size_type count(const _K2& __k) const {return __table_.__count_unique(__k);}
1461#endif // _LIBCPP_STD_VER > 17
1462
1463#if _LIBCPP_STD_VER > 17
1464 _LIBCPP_INLINE_VISIBILITY
1465 bool contains(const key_type& __k) const {return find(__k) != end();}
1466
1467 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1468 _LIBCPP_INLINE_VISIBILITY
1469 bool contains(const _K2& __k) const {return find(__k) != end();}
1470#endif // _LIBCPP_STD_VER > 17
1471
1472 _LIBCPP_INLINE_VISIBILITY
1473 pair<iterator, iterator> equal_range(const key_type& __k)
1474 {return __table_.__equal_range_unique(__k);}
1475 _LIBCPP_INLINE_VISIBILITY
1476 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1477 {return __table_.__equal_range_unique(__k);}
1478#if _LIBCPP_STD_VER > 17
1479 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1480 _LIBCPP_INLINE_VISIBILITY
1481 pair<iterator, iterator> equal_range(const _K2& __k)
1482 {return __table_.__equal_range_unique(__k);}
1483 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1484 _LIBCPP_INLINE_VISIBILITY
1485 pair<const_iterator, const_iterator> equal_range(const _K2& __k) const
1486 {return __table_.__equal_range_unique(__k);}
1487#endif // _LIBCPP_STD_VER > 17
1488
1489 mapped_type& operator[](const key_type& __k);
1490#ifndef _LIBCPP_CXX03_LANG
1491 mapped_type& operator[](key_type&& __k);
1492#endif
1493
1494 mapped_type& at(const key_type& __k);
1495 const mapped_type& at(const key_type& __k) const;
1496
1497 _LIBCPP_INLINE_VISIBILITY
1498 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1499 _LIBCPP_INLINE_VISIBILITY
1500 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1501
1502 _LIBCPP_INLINE_VISIBILITY
1503 size_type bucket_size(size_type __n) const
1504 {return __table_.bucket_size(__n);}
1505 _LIBCPP_INLINE_VISIBILITY
1506 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1507
1508 _LIBCPP_INLINE_VISIBILITY
1509 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1510 _LIBCPP_INLINE_VISIBILITY
1511 local_iterator end(size_type __n) {return __table_.end(__n);}
1512 _LIBCPP_INLINE_VISIBILITY
1513 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1514 _LIBCPP_INLINE_VISIBILITY
1515 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1516 _LIBCPP_INLINE_VISIBILITY
1517 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1518 _LIBCPP_INLINE_VISIBILITY
1519 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1520
1521 _LIBCPP_INLINE_VISIBILITY
1522 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1523 _LIBCPP_INLINE_VISIBILITY
1524 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1525 _LIBCPP_INLINE_VISIBILITY
1526 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1527 _LIBCPP_INLINE_VISIBILITY
1528 void rehash(size_type __n) {__table_.rehash(__n);}
1529 _LIBCPP_INLINE_VISIBILITY
1530 void reserve(size_type __n) {__table_.reserve(__n);}
1531
1532#ifdef _LIBCPP_ENABLE_DEBUG_MODE
1533
1534 bool __dereferenceable(const const_iterator* __i) const
1535 {return __table_.__dereferenceable(_VSTD::addressof(__i->__i_));}
1536 bool __decrementable(const const_iterator* __i) const
1537 {return __table_.__decrementable(_VSTD::addressof(__i->__i_));}
1538 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1539 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);}
1540 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1541 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);}
1542
1543#endif // _LIBCPP_ENABLE_DEBUG_MODE
1544
1545private:
1546
1547#ifdef _LIBCPP_CXX03_LANG
1548 __node_holder __construct_node_with_key(const key_type& __k);
1549#endif
1550};
1551
1552#if _LIBCPP_STD_VER >= 17
1553template<class _InputIterator,
1554 class _Hash = hash<__iter_key_type<_InputIterator>>,
1555 class _Pred = equal_to<__iter_key_type<_InputIterator>>,
1556 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1557 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
1558 class = enable_if_t<!__is_allocator<_Hash>::value>,
1559 class = enable_if_t<!is_integral<_Hash>::value>,
1560 class = enable_if_t<!__is_allocator<_Pred>::value>,
1561 class = enable_if_t<__is_allocator<_Allocator>::value>>
1562unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
1563 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1564 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1565
1566template<class _Key, class _Tp, class _Hash = hash<remove_const_t<_Key>>,
1567 class _Pred = equal_to<remove_const_t<_Key>>,
1568 class _Allocator = allocator<pair<const _Key, _Tp>>,
1569 class = enable_if_t<!__is_allocator<_Hash>::value>,
1570 class = enable_if_t<!is_integral<_Hash>::value>,
1571 class = enable_if_t<!__is_allocator<_Pred>::value>,
1572 class = enable_if_t<__is_allocator<_Allocator>::value>>
1573unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type = 0,
1574 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1575 -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
1576
1577template<class _InputIterator, class _Allocator,
1578 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
1579 class = enable_if_t<__is_allocator<_Allocator>::value>>
1580unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1581 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1582 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
1583
1584template<class _InputIterator, class _Allocator,
1585 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
1586 class = enable_if_t<__is_allocator<_Allocator>::value>>
1587unordered_map(_InputIterator, _InputIterator, _Allocator)
1588 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1589 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
1590
1591template<class _InputIterator, class _Hash, class _Allocator,
1592 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
1593 class = enable_if_t<!__is_allocator<_Hash>::value>,
1594 class = enable_if_t<!is_integral<_Hash>::value>,
1595 class = enable_if_t<__is_allocator<_Allocator>::value>>
1596unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1597 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1598 _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
1599
1600template<class _Key, class _Tp, class _Allocator,
1601 class = enable_if_t<__is_allocator<_Allocator>::value>>
1602unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1603 -> unordered_map<remove_const_t<_Key>, _Tp,
1604 hash<remove_const_t<_Key>>,
1605 equal_to<remove_const_t<_Key>>, _Allocator>;
1606
1607template<class _Key, class _Tp, class _Allocator,
1608 class = enable_if_t<__is_allocator<_Allocator>::value>>
1609unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1610 -> unordered_map<remove_const_t<_Key>, _Tp,
1611 hash<remove_const_t<_Key>>,
1612 equal_to<remove_const_t<_Key>>, _Allocator>;
1613
1614template<class _Key, class _Tp, class _Hash, class _Allocator,
1615 class = enable_if_t<!__is_allocator<_Hash>::value>,
1616 class = enable_if_t<!is_integral<_Hash>::value>,
1617 class = enable_if_t<__is_allocator<_Allocator>::value>>
1618unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1619 -> unordered_map<remove_const_t<_Key>, _Tp, _Hash,
1620 equal_to<remove_const_t<_Key>>, _Allocator>;
1621#endif
1622
1623template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1624unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1625 size_type __n, const hasher& __hf, const key_equal& __eql)
1626 : __table_(__hf, __eql)
1627{
1628 _VSTD::__debug_db_insert_c(this);
1629 __table_.rehash(__n);
1630}
1631
1632template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1633unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1634 size_type __n, const hasher& __hf, const key_equal& __eql,
1635 const allocator_type& __a)
1636 : __table_(__hf, __eql, typename __table::allocator_type(__a))
1637{
1638 _VSTD::__debug_db_insert_c(this);
1639 __table_.rehash(__n);
1640}
1641
1642template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1643inline
1644unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1645 const allocator_type& __a)
1646 : __table_(typename __table::allocator_type(__a))
1647{
1648 _VSTD::__debug_db_insert_c(this);
1649}
1650
1651template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1652template <class _InputIterator>
1653unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1654 _InputIterator __first, _InputIterator __last)
1655{
1656 _VSTD::__debug_db_insert_c(this);
1657 insert(__first, __last);
1658}
1659
1660template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1661template <class _InputIterator>
1662unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1663 _InputIterator __first, _InputIterator __last, size_type __n,
1664 const hasher& __hf, const key_equal& __eql)
1665 : __table_(__hf, __eql)
1666{
1667 _VSTD::__debug_db_insert_c(this);
1668 __table_.rehash(__n);
1669 insert(__first, __last);
1670}
1671
1672template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1673template <class _InputIterator>
1674unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1675 _InputIterator __first, _InputIterator __last, size_type __n,
1676 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1677 : __table_(__hf, __eql, typename __table::allocator_type(__a))
1678{
1679 _VSTD::__debug_db_insert_c(this);
1680 __table_.rehash(__n);
1681 insert(__first, __last);
1682}
1683
1684template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1685unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1686 const unordered_map& __u)
1687 : __table_(__u.__table_)
1688{
1689 _VSTD::__debug_db_insert_c(this);
1690 __table_.rehash(__u.bucket_count());
1691 insert(__u.begin(), __u.end());
1692}
1693
1694template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1695unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1696 const unordered_map& __u, const allocator_type& __a)
1697 : __table_(__u.__table_, typename __table::allocator_type(__a))
1698{
1699 _VSTD::__debug_db_insert_c(this);
1700 __table_.rehash(__u.bucket_count());
1701 insert(__u.begin(), __u.end());
1702}
1703
1704#ifndef _LIBCPP_CXX03_LANG
1705
1706template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1707inline
1708unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1709 unordered_map&& __u)
1710 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1711 : __table_(_VSTD::move(__u.__table_))
1712{
1713 _VSTD::__debug_db_insert_c(this);
1714 std::__debug_db_swap(this, std::addressof(__u));
1715}
1716
1717template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1718unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1719 unordered_map&& __u, const allocator_type& __a)
1720 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
1721{
1722 _VSTD::__debug_db_insert_c(this);
1723 if (__a != __u.get_allocator())
1724 {
1725 iterator __i = __u.begin();
1726 while (__u.size() != 0) {
1727 __table_.__emplace_unique(
1728 __u.__table_.remove((__i++).__i_)->__value_.__move());
1729 }
1730 }
1731 else
1732 std::__debug_db_swap(this, std::addressof(__u));
1733}
1734
1735template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1736unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1737 initializer_list<value_type> __il)
1738{
1739 _VSTD::__debug_db_insert_c(this);
1740 insert(__il.begin(), __il.end());
1741}
1742
1743template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1744unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1745 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1746 const key_equal& __eql)
1747 : __table_(__hf, __eql)
1748{
1749 _VSTD::__debug_db_insert_c(this);
1750 __table_.rehash(__n);
1751 insert(__il.begin(), __il.end());
1752}
1753
1754template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1755unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1756 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1757 const key_equal& __eql, const allocator_type& __a)
1758 : __table_(__hf, __eql, typename __table::allocator_type(__a))
1759{
1760 _VSTD::__debug_db_insert_c(this);
1761 __table_.rehash(__n);
1762 insert(__il.begin(), __il.end());
1763}
1764
1765template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1766inline
1767unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1768unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1769 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1770{
1771 __table_ = _VSTD::move(__u.__table_);
1772 return *this;
1773}
1774
1775template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1776inline
1777unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1778unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1779 initializer_list<value_type> __il)
1780{
1781 __table_.__assign_unique(__il.begin(), __il.end());
1782 return *this;
1783}
1784
1785#endif // _LIBCPP_CXX03_LANG
1786
1787template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1788template <class _InputIterator>
1789inline
1790void
1791unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1792 _InputIterator __last)
1793{
1794 for (; __first != __last; ++__first)
1795 __table_.__insert_unique(*__first);
1796}
1797
1798#ifndef _LIBCPP_CXX03_LANG
1799
1800template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1801_Tp&
1802unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1803{
1804 return __table_.__emplace_unique_key_args(__k,
1805 piecewise_construct, _VSTD::forward_as_tuple(__k),
1806 _VSTD::forward_as_tuple()).first->__get_value().second;
1807}
1808
1809template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1810_Tp&
1811unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1812{
1813 return __table_.__emplace_unique_key_args(__k,
1814 piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),
1815 _VSTD::forward_as_tuple()).first->__get_value().second;
1816}
1817#else // _LIBCPP_CXX03_LANG
1818
1819template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1820typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1821unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1822{
1823 __node_allocator& __na = __table_.__node_alloc();
1824 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1825 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
1826 __h.get_deleter().__first_constructed = true;
1827 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
1828 __h.get_deleter().__second_constructed = true;
1829 return __h;
1830}
1831
1832template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1833_Tp&
1834unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1835{
1836 iterator __i = find(__k);
1837 if (__i != end())
1838 return __i->second;
1839 __node_holder __h = __construct_node_with_key(__k);
1840 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1841 __h.release();
1842 return __r.first->second;
1843}
1844
1845#endif // _LIBCPP_CXX03_LANG
1846
1847template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1848_Tp&
1849unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1850{
1851 iterator __i = find(__k);
1852 if (__i == end())
1853 __throw_out_of_range(msg: "unordered_map::at: key not found");
1854 return __i->second;
1855}
1856
1857template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1858const _Tp&
1859unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1860{
1861 const_iterator __i = find(__k);
1862 if (__i == end())
1863 __throw_out_of_range(msg: "unordered_map::at: key not found");
1864 return __i->second;
1865}
1866
1867template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1868inline _LIBCPP_INLINE_VISIBILITY
1869void
1870swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1871 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1872 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1873{
1874 __x.swap(__y);
1875}
1876
1877#if _LIBCPP_STD_VER > 17
1878template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
1879 class _Predicate>
1880inline _LIBCPP_INLINE_VISIBILITY
1881 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
1882 erase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c,
1883 _Predicate __pred) {
1884 return _VSTD::__libcpp_erase_if_container(__c, __pred);
1885}
1886#endif
1887
1888template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1889bool
1890operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1891 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1892{
1893 if (__x.size() != __y.size())
1894 return false;
1895 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1896 const_iterator;
1897 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1898 __i != __ex; ++__i)
1899 {
1900 const_iterator __j = __y.find(__i->first);
1901 if (__j == __ey || !(*__i == *__j))
1902 return false;
1903 }
1904 return true;
1905}
1906
1907template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1908inline _LIBCPP_INLINE_VISIBILITY
1909bool
1910operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1911 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1912{
1913 return !(__x == __y);
1914}
1915
1916template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1917 class _Alloc = allocator<pair<const _Key, _Tp> > >
1918class _LIBCPP_TEMPLATE_VIS unordered_multimap
1919{
1920public:
1921 // types
1922 typedef _Key key_type;
1923 typedef _Tp mapped_type;
1924 typedef __type_identity_t<_Hash> hasher;
1925 typedef __type_identity_t<_Pred> key_equal;
1926 typedef __type_identity_t<_Alloc> allocator_type;
1927 typedef pair<const key_type, mapped_type> value_type;
1928 typedef value_type& reference;
1929 typedef const value_type& const_reference;
1930 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1931 "Invalid allocator::value_type");
1932
1933private:
1934 typedef __hash_value_type<key_type, mapped_type> __value_type;
1935 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
1936 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
1937 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1938 __value_type>::type __allocator_type;
1939
1940 typedef __hash_table<__value_type, __hasher,
1941 __key_equal, __allocator_type> __table;
1942
1943 __table __table_;
1944
1945 typedef typename __table::_NodeTypes _NodeTypes;
1946 typedef typename __table::__node_traits __node_traits;
1947 typedef typename __table::__node_allocator __node_allocator;
1948 typedef typename __table::__node __node;
1949 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1950 typedef unique_ptr<__node, _Dp> __node_holder;
1951 typedef allocator_traits<allocator_type> __alloc_traits;
1952 static_assert((is_same<typename __node_traits::size_type,
1953 typename __alloc_traits::size_type>::value),
1954 "Allocator uses different size_type for different types");
1955public:
1956 typedef typename __alloc_traits::pointer pointer;
1957 typedef typename __alloc_traits::const_pointer const_pointer;
1958 typedef typename __table::size_type size_type;
1959 typedef typename __table::difference_type difference_type;
1960
1961 typedef __hash_map_iterator<typename __table::iterator> iterator;
1962 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1963 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1964 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1965
1966#if _LIBCPP_STD_VER > 14
1967 typedef __map_node_handle<__node, allocator_type> node_type;
1968#endif
1969
1970 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1971 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1972 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1973 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1974
1975 _LIBCPP_INLINE_VISIBILITY
1976 unordered_multimap()
1977 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1978 {
1979 _VSTD::__debug_db_insert_c(this);
1980 }
1981 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1982 const key_equal& __eql = key_equal());
1983 unordered_multimap(size_type __n, const hasher& __hf,
1984 const key_equal& __eql,
1985 const allocator_type& __a);
1986 template <class _InputIterator>
1987 unordered_multimap(_InputIterator __first, _InputIterator __last);
1988 template <class _InputIterator>
1989 unordered_multimap(_InputIterator __first, _InputIterator __last,
1990 size_type __n, const hasher& __hf = hasher(),
1991 const key_equal& __eql = key_equal());
1992 template <class _InputIterator>
1993 unordered_multimap(_InputIterator __first, _InputIterator __last,
1994 size_type __n, const hasher& __hf,
1995 const key_equal& __eql,
1996 const allocator_type& __a);
1997 _LIBCPP_INLINE_VISIBILITY
1998 explicit unordered_multimap(const allocator_type& __a);
1999 unordered_multimap(const unordered_multimap& __u);
2000 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
2001#ifndef _LIBCPP_CXX03_LANG
2002 _LIBCPP_INLINE_VISIBILITY
2003 unordered_multimap(unordered_multimap&& __u)
2004 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
2005 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
2006 unordered_multimap(initializer_list<value_type> __il);
2007 unordered_multimap(initializer_list<value_type> __il, size_type __n,
2008 const hasher& __hf = hasher(),
2009 const key_equal& __eql = key_equal());
2010 unordered_multimap(initializer_list<value_type> __il, size_type __n,
2011 const hasher& __hf, const key_equal& __eql,
2012 const allocator_type& __a);
2013#endif // _LIBCPP_CXX03_LANG
2014#if _LIBCPP_STD_VER > 11
2015 _LIBCPP_INLINE_VISIBILITY
2016 unordered_multimap(size_type __n, const allocator_type& __a)
2017 : unordered_multimap(__n, hasher(), key_equal(), __a) {}
2018 _LIBCPP_INLINE_VISIBILITY
2019 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
2020 : unordered_multimap(__n, __hf, key_equal(), __a) {}
2021 template <class _InputIterator>
2022 _LIBCPP_INLINE_VISIBILITY
2023 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
2024 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
2025 template <class _InputIterator>
2026 _LIBCPP_INLINE_VISIBILITY
2027 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
2028 const allocator_type& __a)
2029 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
2030 _LIBCPP_INLINE_VISIBILITY
2031 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
2032 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
2033 _LIBCPP_INLINE_VISIBILITY
2034 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2035 const allocator_type& __a)
2036 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
2037#endif
2038 _LIBCPP_INLINE_VISIBILITY
2039 ~unordered_multimap() {
2040 static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
2041 }
2042
2043 _LIBCPP_INLINE_VISIBILITY
2044 unordered_multimap& operator=(const unordered_multimap& __u)
2045 {
2046#ifndef _LIBCPP_CXX03_LANG
2047 __table_ = __u.__table_;
2048#else
2049 if (this != _VSTD::addressof(__u)) {
2050 __table_.clear();
2051 __table_.hash_function() = __u.__table_.hash_function();
2052 __table_.key_eq() = __u.__table_.key_eq();
2053 __table_.max_load_factor() = __u.__table_.max_load_factor();
2054 __table_.__copy_assign_alloc(__u.__table_);
2055 insert(__u.begin(), __u.end());
2056 }
2057#endif
2058 return *this;
2059 }
2060#ifndef _LIBCPP_CXX03_LANG
2061 _LIBCPP_INLINE_VISIBILITY
2062 unordered_multimap& operator=(unordered_multimap&& __u)
2063 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
2064 _LIBCPP_INLINE_VISIBILITY
2065 unordered_multimap& operator=(initializer_list<value_type> __il);
2066#endif // _LIBCPP_CXX03_LANG
2067
2068 _LIBCPP_INLINE_VISIBILITY
2069 allocator_type get_allocator() const _NOEXCEPT
2070 {return allocator_type(__table_.__node_alloc());}
2071
2072 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
2073 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
2074 _LIBCPP_INLINE_VISIBILITY
2075 size_type size() const _NOEXCEPT {return __table_.size();}
2076 _LIBCPP_INLINE_VISIBILITY
2077 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
2078
2079 _LIBCPP_INLINE_VISIBILITY
2080 iterator begin() _NOEXCEPT {return __table_.begin();}
2081 _LIBCPP_INLINE_VISIBILITY
2082 iterator end() _NOEXCEPT {return __table_.end();}
2083 _LIBCPP_INLINE_VISIBILITY
2084 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
2085 _LIBCPP_INLINE_VISIBILITY
2086 const_iterator end() const _NOEXCEPT {return __table_.end();}
2087 _LIBCPP_INLINE_VISIBILITY
2088 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
2089 _LIBCPP_INLINE_VISIBILITY
2090 const_iterator cend() const _NOEXCEPT {return __table_.end();}
2091
2092 _LIBCPP_INLINE_VISIBILITY
2093 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
2094
2095 _LIBCPP_INLINE_VISIBILITY
2096 iterator insert(const_iterator __p, const value_type& __x)
2097 {return __table_.__insert_multi(__p.__i_, __x);}
2098
2099 template <class _InputIterator>
2100 _LIBCPP_INLINE_VISIBILITY
2101 void insert(_InputIterator __first, _InputIterator __last);
2102
2103#ifndef _LIBCPP_CXX03_LANG
2104 _LIBCPP_INLINE_VISIBILITY
2105 void insert(initializer_list<value_type> __il)
2106 {insert(__il.begin(), __il.end());}
2107 _LIBCPP_INLINE_VISIBILITY
2108 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
2109
2110 _LIBCPP_INLINE_VISIBILITY
2111 iterator insert(const_iterator __p, value_type&& __x)
2112 {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));}
2113
2114 template <class _Pp,
2115 class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
2116 _LIBCPP_INLINE_VISIBILITY
2117 iterator insert(_Pp&& __x)
2118 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
2119
2120 template <class _Pp,
2121 class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
2122 _LIBCPP_INLINE_VISIBILITY
2123 iterator insert(const_iterator __p, _Pp&& __x)
2124 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
2125
2126 template <class... _Args>
2127 iterator emplace(_Args&&... __args) {
2128 return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
2129 }
2130
2131 template <class... _Args>
2132 iterator emplace_hint(const_iterator __p, _Args&&... __args) {
2133 return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
2134 }
2135#endif // _LIBCPP_CXX03_LANG
2136
2137
2138 _LIBCPP_INLINE_VISIBILITY
2139 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
2140 _LIBCPP_INLINE_VISIBILITY
2141 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
2142 _LIBCPP_INLINE_VISIBILITY
2143 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
2144 _LIBCPP_INLINE_VISIBILITY
2145 iterator erase(const_iterator __first, const_iterator __last)
2146 {return __table_.erase(__first.__i_, __last.__i_);}
2147 _LIBCPP_INLINE_VISIBILITY
2148 void clear() _NOEXCEPT {__table_.clear();}
2149
2150#if _LIBCPP_STD_VER > 14
2151 _LIBCPP_INLINE_VISIBILITY
2152 iterator insert(node_type&& __nh)
2153 {
2154 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
2155 "node_type with incompatible allocator passed to unordered_multimap::insert()");
2156 return __table_.template __node_handle_insert_multi<node_type>(
2157 _VSTD::move(__nh));
2158 }
2159 _LIBCPP_INLINE_VISIBILITY
2160 iterator insert(const_iterator __hint, node_type&& __nh)
2161 {
2162 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
2163 "node_type with incompatible allocator passed to unordered_multimap::insert()");
2164 return __table_.template __node_handle_insert_multi<node_type>(
2165 __hint.__i_, _VSTD::move(__nh));
2166 }
2167 _LIBCPP_INLINE_VISIBILITY
2168 node_type extract(key_type const& __key)
2169 {
2170 return __table_.template __node_handle_extract<node_type>(__key);
2171 }
2172 _LIBCPP_INLINE_VISIBILITY
2173 node_type extract(const_iterator __it)
2174 {
2175 return __table_.template __node_handle_extract<node_type>(
2176 __it.__i_);
2177 }
2178
2179 template <class _H2, class _P2>
2180 _LIBCPP_INLINE_VISIBILITY
2181 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
2182 {
2183 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2184 "merging container with incompatible allocator");
2185 return __table_.__node_handle_merge_multi(__source.__table_);
2186 }
2187 template <class _H2, class _P2>
2188 _LIBCPP_INLINE_VISIBILITY
2189 void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
2190 {
2191 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2192 "merging container with incompatible allocator");
2193 return __table_.__node_handle_merge_multi(__source.__table_);
2194 }
2195 template <class _H2, class _P2>
2196 _LIBCPP_INLINE_VISIBILITY
2197 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
2198 {
2199 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2200 "merging container with incompatible allocator");
2201 return __table_.__node_handle_merge_multi(__source.__table_);
2202 }
2203 template <class _H2, class _P2>
2204 _LIBCPP_INLINE_VISIBILITY
2205 void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
2206 {
2207 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2208 "merging container with incompatible allocator");
2209 return __table_.__node_handle_merge_multi(__source.__table_);
2210 }
2211#endif
2212
2213 _LIBCPP_INLINE_VISIBILITY
2214 void swap(unordered_multimap& __u)
2215 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
2216 {__table_.swap(__u.__table_);}
2217
2218 _LIBCPP_INLINE_VISIBILITY
2219 hasher hash_function() const
2220 {return __table_.hash_function().hash_function();}
2221 _LIBCPP_INLINE_VISIBILITY
2222 key_equal key_eq() const
2223 {return __table_.key_eq().key_eq();}
2224
2225 _LIBCPP_INLINE_VISIBILITY
2226 iterator find(const key_type& __k) {return __table_.find(__k);}
2227 _LIBCPP_INLINE_VISIBILITY
2228 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
2229#if _LIBCPP_STD_VER > 17
2230 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2231 _LIBCPP_INLINE_VISIBILITY
2232 iterator find(const _K2& __k) {return __table_.find(__k);}
2233 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2234 _LIBCPP_INLINE_VISIBILITY
2235 const_iterator find(const _K2& __k) const {return __table_.find(__k);}
2236#endif // _LIBCPP_STD_VER > 17
2237
2238 _LIBCPP_INLINE_VISIBILITY
2239 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
2240#if _LIBCPP_STD_VER > 17
2241 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2242 _LIBCPP_INLINE_VISIBILITY
2243 size_type count(const _K2& __k) const {return __table_.__count_multi(__k);}
2244#endif // _LIBCPP_STD_VER > 17
2245
2246#if _LIBCPP_STD_VER > 17
2247 _LIBCPP_INLINE_VISIBILITY
2248 bool contains(const key_type& __k) const {return find(__k) != end();}
2249
2250 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2251 _LIBCPP_INLINE_VISIBILITY
2252 bool contains(const _K2& __k) const {return find(__k) != end();}
2253#endif // _LIBCPP_STD_VER > 17
2254
2255 _LIBCPP_INLINE_VISIBILITY
2256 pair<iterator, iterator> equal_range(const key_type& __k)
2257 {return __table_.__equal_range_multi(__k);}
2258 _LIBCPP_INLINE_VISIBILITY
2259 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
2260 {return __table_.__equal_range_multi(__k);}
2261#if _LIBCPP_STD_VER > 17
2262 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2263 _LIBCPP_INLINE_VISIBILITY
2264 pair<iterator, iterator> equal_range(const _K2& __k)
2265 {return __table_.__equal_range_multi(__k);}
2266 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2267 _LIBCPP_INLINE_VISIBILITY
2268 pair<const_iterator, const_iterator> equal_range(const _K2& __k) const
2269 {return __table_.__equal_range_multi(__k);}
2270#endif // _LIBCPP_STD_VER > 17
2271
2272 _LIBCPP_INLINE_VISIBILITY
2273 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
2274 _LIBCPP_INLINE_VISIBILITY
2275 size_type max_bucket_count() const _NOEXCEPT
2276 {return __table_.max_bucket_count();}
2277
2278 _LIBCPP_INLINE_VISIBILITY
2279 size_type bucket_size(size_type __n) const
2280 {return __table_.bucket_size(__n);}
2281 _LIBCPP_INLINE_VISIBILITY
2282 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
2283
2284 _LIBCPP_INLINE_VISIBILITY
2285 local_iterator begin(size_type __n) {return __table_.begin(__n);}
2286 _LIBCPP_INLINE_VISIBILITY
2287 local_iterator end(size_type __n) {return __table_.end(__n);}
2288 _LIBCPP_INLINE_VISIBILITY
2289 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
2290 _LIBCPP_INLINE_VISIBILITY
2291 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
2292 _LIBCPP_INLINE_VISIBILITY
2293 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
2294 _LIBCPP_INLINE_VISIBILITY
2295 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
2296
2297 _LIBCPP_INLINE_VISIBILITY
2298 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
2299 _LIBCPP_INLINE_VISIBILITY
2300 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
2301 _LIBCPP_INLINE_VISIBILITY
2302 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
2303 _LIBCPP_INLINE_VISIBILITY
2304 void rehash(size_type __n) {__table_.rehash(__n);}
2305 _LIBCPP_INLINE_VISIBILITY
2306 void reserve(size_type __n) {__table_.reserve(__n);}
2307
2308#ifdef _LIBCPP_ENABLE_DEBUG_MODE
2309
2310 bool __dereferenceable(const const_iterator* __i) const
2311 {return __table_.__dereferenceable(_VSTD::addressof(__i->__i_));}
2312 bool __decrementable(const const_iterator* __i) const
2313 {return __table_.__decrementable(_VSTD::addressof(__i->__i_));}
2314 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
2315 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);}
2316 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2317 {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);}
2318
2319#endif // _LIBCPP_ENABLE_DEBUG_MODE
2320
2321
2322};
2323
2324#if _LIBCPP_STD_VER >= 17
2325template<class _InputIterator,
2326 class _Hash = hash<__iter_key_type<_InputIterator>>,
2327 class _Pred = equal_to<__iter_key_type<_InputIterator>>,
2328 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2329 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
2330 class = enable_if_t<!__is_allocator<_Hash>::value>,
2331 class = enable_if_t<!is_integral<_Hash>::value>,
2332 class = enable_if_t<!__is_allocator<_Pred>::value>,
2333 class = enable_if_t<__is_allocator<_Allocator>::value>>
2334unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
2335 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
2336 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>;
2337
2338template<class _Key, class _Tp, class _Hash = hash<remove_const_t<_Key>>,
2339 class _Pred = equal_to<remove_const_t<_Key>>,
2340 class _Allocator = allocator<pair<const _Key, _Tp>>,
2341 class = enable_if_t<!__is_allocator<_Hash>::value>,
2342 class = enable_if_t<!is_integral<_Hash>::value>,
2343 class = enable_if_t<!__is_allocator<_Pred>::value>,
2344 class = enable_if_t<__is_allocator<_Allocator>::value>>
2345unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type = 0,
2346 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
2347 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
2348
2349template<class _InputIterator, class _Allocator,
2350 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
2351 class = enable_if_t<__is_allocator<_Allocator>::value>>
2352unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
2353 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2354 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
2355
2356template<class _InputIterator, class _Allocator,
2357 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
2358 class = enable_if_t<__is_allocator<_Allocator>::value>>
2359unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2360 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2361 hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
2362
2363template<class _InputIterator, class _Hash, class _Allocator,
2364 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
2365 class = enable_if_t<!__is_allocator<_Hash>::value>,
2366 class = enable_if_t<!is_integral<_Hash>::value>,
2367 class = enable_if_t<__is_allocator<_Allocator>::value>>
2368unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2369 -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2370 _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>;
2371
2372template<class _Key, class _Tp, class _Allocator,
2373 class = enable_if_t<__is_allocator<_Allocator>::value>>
2374unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
2375 -> unordered_multimap<remove_const_t<_Key>, _Tp,
2376 hash<remove_const_t<_Key>>,
2377 equal_to<remove_const_t<_Key>>, _Allocator>;
2378
2379template<class _Key, class _Tp, class _Allocator,
2380 class = enable_if_t<__is_allocator<_Allocator>::value>>
2381unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2382 -> unordered_multimap<remove_const_t<_Key>, _Tp,
2383 hash<remove_const_t<_Key>>,
2384 equal_to<remove_const_t<_Key>>, _Allocator>;
2385
2386template<class _Key, class _Tp, class _Hash, class _Allocator,
2387 class = enable_if_t<!__is_allocator<_Hash>::value>,
2388 class = enable_if_t<!is_integral<_Hash>::value>,
2389 class = enable_if_t<__is_allocator<_Allocator>::value>>
2390unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2391 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash,
2392 equal_to<remove_const_t<_Key>>, _Allocator>;
2393#endif
2394
2395template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2396unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2397 size_type __n, const hasher& __hf, const key_equal& __eql)
2398 : __table_(__hf, __eql)
2399{
2400 _VSTD::__debug_db_insert_c(this);
2401 __table_.rehash(__n);
2402}
2403
2404template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2405unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2406 size_type __n, const hasher& __hf, const key_equal& __eql,
2407 const allocator_type& __a)
2408 : __table_(__hf, __eql, typename __table::allocator_type(__a))
2409{
2410 _VSTD::__debug_db_insert_c(this);
2411 __table_.rehash(__n);
2412}
2413
2414template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2415template <class _InputIterator>
2416unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2417 _InputIterator __first, _InputIterator __last)
2418{
2419 _VSTD::__debug_db_insert_c(this);
2420 insert(__first, __last);
2421}
2422
2423template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2424template <class _InputIterator>
2425unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2426 _InputIterator __first, _InputIterator __last, size_type __n,
2427 const hasher& __hf, const key_equal& __eql)
2428 : __table_(__hf, __eql)
2429{
2430 _VSTD::__debug_db_insert_c(this);
2431 __table_.rehash(__n);
2432 insert(__first, __last);
2433}
2434
2435template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2436template <class _InputIterator>
2437unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2438 _InputIterator __first, _InputIterator __last, size_type __n,
2439 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
2440 : __table_(__hf, __eql, typename __table::allocator_type(__a))
2441{
2442 _VSTD::__debug_db_insert_c(this);
2443 __table_.rehash(__n);
2444 insert(__first, __last);
2445}
2446
2447template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2448inline
2449unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2450 const allocator_type& __a)
2451 : __table_(typename __table::allocator_type(__a))
2452{
2453 _VSTD::__debug_db_insert_c(this);
2454}
2455
2456template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2457unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2458 const unordered_multimap& __u)
2459 : __table_(__u.__table_)
2460{
2461 _VSTD::__debug_db_insert_c(this);
2462 __table_.rehash(__u.bucket_count());
2463 insert(__u.begin(), __u.end());
2464}
2465
2466template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2467unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2468 const unordered_multimap& __u, const allocator_type& __a)
2469 : __table_(__u.__table_, typename __table::allocator_type(__a))
2470{
2471 _VSTD::__debug_db_insert_c(this);
2472 __table_.rehash(__u.bucket_count());
2473 insert(__u.begin(), __u.end());
2474}
2475
2476#ifndef _LIBCPP_CXX03_LANG
2477
2478template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2479inline
2480unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2481 unordered_multimap&& __u)
2482 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
2483 : __table_(_VSTD::move(__u.__table_))
2484{
2485 _VSTD::__debug_db_insert_c(this);
2486 std::__debug_db_swap(this, std::addressof(__u));
2487}
2488
2489template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2490unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2491 unordered_multimap&& __u, const allocator_type& __a)
2492 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
2493{
2494 _VSTD::__debug_db_insert_c(this);
2495 if (__a != __u.get_allocator())
2496 {
2497 iterator __i = __u.begin();
2498 while (__u.size() != 0)
2499 {
2500 __table_.__insert_multi(
2501 __u.__table_.remove((__i++).__i_)->__value_.__move());
2502 }
2503 }
2504 else
2505 std::__debug_db_swap(this, std::addressof(__u));
2506}
2507
2508template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2509unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2510 initializer_list<value_type> __il)
2511{
2512 _VSTD::__debug_db_insert_c(this);
2513 insert(__il.begin(), __il.end());
2514}
2515
2516template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2517unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2518 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2519 const key_equal& __eql)
2520 : __table_(__hf, __eql)
2521{
2522 _VSTD::__debug_db_insert_c(this);
2523 __table_.rehash(__n);
2524 insert(__il.begin(), __il.end());
2525}
2526
2527template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2528unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2529 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2530 const key_equal& __eql, const allocator_type& __a)
2531 : __table_(__hf, __eql, typename __table::allocator_type(__a))
2532{
2533 _VSTD::__debug_db_insert_c(this);
2534 __table_.rehash(__n);
2535 insert(__il.begin(), __il.end());
2536}
2537
2538template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2539inline
2540unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2541unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
2542 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
2543{
2544 __table_ = _VSTD::move(__u.__table_);
2545 return *this;
2546}
2547
2548template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2549inline
2550unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2551unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
2552 initializer_list<value_type> __il)
2553{
2554 __table_.__assign_multi(__il.begin(), __il.end());
2555 return *this;
2556}
2557
2558#endif // _LIBCPP_CXX03_LANG
2559
2560
2561
2562template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2563template <class _InputIterator>
2564inline
2565void
2566unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
2567 _InputIterator __last)
2568{
2569 for (; __first != __last; ++__first)
2570 __table_.__insert_multi(*__first);
2571}
2572
2573template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2574inline _LIBCPP_INLINE_VISIBILITY
2575void
2576swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2577 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2578 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2579{
2580 __x.swap(__y);
2581}
2582
2583#if _LIBCPP_STD_VER > 17
2584template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
2585 class _Predicate>
2586inline _LIBCPP_INLINE_VISIBILITY
2587 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
2588 erase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c,
2589 _Predicate __pred) {
2590 return _VSTD::__libcpp_erase_if_container(__c, __pred);
2591}
2592#endif
2593
2594template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2595bool
2596operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2597 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2598{
2599 if (__x.size() != __y.size())
2600 return false;
2601 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2602 const_iterator;
2603 typedef pair<const_iterator, const_iterator> _EqRng;
2604 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2605 {
2606 _EqRng __xeq = __x.equal_range(__i->first);
2607 _EqRng __yeq = __y.equal_range(__i->first);
2608 if (_VSTD::distance(__xeq.first, __xeq.second) !=
2609 _VSTD::distance(__yeq.first, __yeq.second) ||
2610 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2611 return false;
2612 __i = __xeq.second;
2613 }
2614 return true;
2615}
2616
2617template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2618inline _LIBCPP_INLINE_VISIBILITY
2619bool
2620operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2621 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2622{
2623 return !(__x == __y);
2624}
2625
2626_LIBCPP_END_NAMESPACE_STD
2627
2628#endif // _LIBCPP_UNORDERED_MAP
2629

source code of flutter_engine/third_party/libcxx/include/unordered_map