libstdc++
unordered_map.h
Go to the documentation of this file.
1// unordered_map implementation -*- C++ -*-
2
3// Copyright (C) 2010-2023 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file bits/unordered_map.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{unordered_map}
28 */
29
30#ifndef _UNORDERED_MAP_H
31#define _UNORDERED_MAP_H
32
33#include <bits/hashtable.h>
34#include <bits/allocator.h>
35#include <bits/functional_hash.h> // hash
36#include <bits/stl_function.h> // equal_to
37
38namespace std _GLIBCXX_VISIBILITY(default)
39{
40_GLIBCXX_BEGIN_NAMESPACE_VERSION
41_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
42
43 /// Base types for unordered_map.
44 template<bool _Cache>
45 using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
46
47 template<typename _Key,
48 typename _Tp,
49 typename _Hash = hash<_Key>,
50 typename _Pred = std::equal_to<_Key>,
51 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
52 typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
53 using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
54 _Alloc, __detail::_Select1st,
55 _Pred, _Hash,
56 __detail::_Mod_range_hashing,
57 __detail::_Default_ranged_hash,
58 __detail::_Prime_rehash_policy, _Tr>;
59
60 /// Base types for unordered_multimap.
61 template<bool _Cache>
62 using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
63
64 template<typename _Key,
65 typename _Tp,
66 typename _Hash = hash<_Key>,
67 typename _Pred = std::equal_to<_Key>,
68 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
69 typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
70 using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
71 _Alloc, __detail::_Select1st,
72 _Pred, _Hash,
73 __detail::_Mod_range_hashing,
74 __detail::_Default_ranged_hash,
75 __detail::_Prime_rehash_policy, _Tr>;
76
77 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
78 class unordered_multimap;
79
80 /**
81 * @brief A standard container composed of unique keys (containing
82 * at most one of each key value) that associates values of another type
83 * with the keys.
84 *
85 * @ingroup unordered_associative_containers
86 *
87 * @tparam _Key Type of key objects.
88 * @tparam _Tp Type of mapped objects.
89 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
90 * @tparam _Pred Predicate function object type, defaults
91 * to equal_to<_Value>.
92 * @tparam _Alloc Allocator type, defaults to
93 * std::allocator<std::pair<const _Key, _Tp>>.
94 *
95 * Meets the requirements of a <a href="tables.html#65">container</a>, and
96 * <a href="tables.html#xx">unordered associative container</a>
97 *
98 * The resulting value type of the container is std::pair<const _Key, _Tp>.
99 *
100 * Base is _Hashtable, dispatched at compile time via template
101 * alias __umap_hashtable.
102 */
103 template<typename _Key, typename _Tp,
104 typename _Hash = hash<_Key>,
105 typename _Pred = equal_to<_Key>,
106 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
107 class unordered_map
108 {
109 typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
110 _Hashtable _M_h;
111
112 public:
113 // typedefs:
114 ///@{
115 /// Public typedefs.
116 typedef typename _Hashtable::key_type key_type;
117 typedef typename _Hashtable::value_type value_type;
118 typedef typename _Hashtable::mapped_type mapped_type;
119 typedef typename _Hashtable::hasher hasher;
120 typedef typename _Hashtable::key_equal key_equal;
121 typedef typename _Hashtable::allocator_type allocator_type;
122 ///@}
123
124 ///@{
125 /// Iterator-related typedefs.
126 typedef typename _Hashtable::pointer pointer;
127 typedef typename _Hashtable::const_pointer const_pointer;
128 typedef typename _Hashtable::reference reference;
129 typedef typename _Hashtable::const_reference const_reference;
130 typedef typename _Hashtable::iterator iterator;
131 typedef typename _Hashtable::const_iterator const_iterator;
132 typedef typename _Hashtable::local_iterator local_iterator;
133 typedef typename _Hashtable::const_local_iterator const_local_iterator;
134 typedef typename _Hashtable::size_type size_type;
135 typedef typename _Hashtable::difference_type difference_type;
136 ///@}
137
138#if __cplusplus > 201402L
139 using node_type = typename _Hashtable::node_type;
140 using insert_return_type = typename _Hashtable::insert_return_type;
141#endif
142
143 //construct/destroy/copy
144
145 /// Default constructor.
146 unordered_map() = default;
147
148 /**
149 * @brief Default constructor creates no elements.
150 * @param __n Minimal initial number of buckets.
151 * @param __hf A hash functor.
152 * @param __eql A key equality functor.
153 * @param __a An allocator object.
154 */
155 explicit
156 unordered_map(size_type __n,
157 const hasher& __hf = hasher(),
158 const key_equal& __eql = key_equal(),
159 const allocator_type& __a = allocator_type())
160 : _M_h(__n, __hf, __eql, __a)
161 { }
162
163 /**
164 * @brief Builds an %unordered_map from a range.
165 * @param __first An input iterator.
166 * @param __last An input iterator.
167 * @param __n Minimal initial number of buckets.
168 * @param __hf A hash functor.
169 * @param __eql A key equality functor.
170 * @param __a An allocator object.
171 *
172 * Create an %unordered_map consisting of copies of the elements from
173 * [__first,__last). This is linear in N (where N is
174 * distance(__first,__last)).
175 */
176 template<typename _InputIterator>
177 unordered_map(_InputIterator __first, _InputIterator __last,
178 size_type __n = 0,
179 const hasher& __hf = hasher(),
180 const key_equal& __eql = key_equal(),
181 const allocator_type& __a = allocator_type())
182 : _M_h(__first, __last, __n, __hf, __eql, __a)
183 { }
184
185 /// Copy constructor.
186 unordered_map(const unordered_map&) = default;
187
188 /// Move constructor.
189 unordered_map(unordered_map&&) = default;
190
191 /**
192 * @brief Creates an %unordered_map with no elements.
193 * @param __a An allocator object.
194 */
195 explicit
196 unordered_map(const allocator_type& __a)
197 : _M_h(__a)
198 { }
199
200 /*
201 * @brief Copy constructor with allocator argument.
202 * @param __uset Input %unordered_map to copy.
203 * @param __a An allocator object.
204 */
205 unordered_map(const unordered_map& __umap,
206 const allocator_type& __a)
207 : _M_h(__umap._M_h, __a)
208 { }
209
210 /*
211 * @brief Move constructor with allocator argument.
212 * @param __uset Input %unordered_map to move.
213 * @param __a An allocator object.
214 */
215 unordered_map(unordered_map&& __umap,
216 const allocator_type& __a)
217 noexcept( noexcept(_Hashtable(std::move(__umap._M_h), __a)) )
218 : _M_h(std::move(__umap._M_h), __a)
219 { }
220
221 /**
222 * @brief Builds an %unordered_map from an initializer_list.
223 * @param __l An initializer_list.
224 * @param __n Minimal initial number of buckets.
225 * @param __hf A hash functor.
226 * @param __eql A key equality functor.
227 * @param __a An allocator object.
228 *
229 * Create an %unordered_map consisting of copies of the elements in the
230 * list. This is linear in N (where N is @a __l.size()).
231 */
232 unordered_map(initializer_list<value_type> __l,
233 size_type __n = 0,
234 const hasher& __hf = hasher(),
235 const key_equal& __eql = key_equal(),
236 const allocator_type& __a = allocator_type())
237 : _M_h(__l, __n, __hf, __eql, __a)
238 { }
239
240 unordered_map(size_type __n, const allocator_type& __a)
241 : unordered_map(__n, hasher(), key_equal(), __a)
242 { }
243
244 unordered_map(size_type __n, const hasher& __hf,
245 const allocator_type& __a)
246 : unordered_map(__n, __hf, key_equal(), __a)
247 { }
248
249 template<typename _InputIterator>
250 unordered_map(_InputIterator __first, _InputIterator __last,
251 size_type __n,
252 const allocator_type& __a)
253 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
254 { }
255
256 template<typename _InputIterator>
257 unordered_map(_InputIterator __first, _InputIterator __last,
258 size_type __n, const hasher& __hf,
259 const allocator_type& __a)
260 : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
261 { }
262
263 unordered_map(initializer_list<value_type> __l,
264 size_type __n,
265 const allocator_type& __a)
266 : unordered_map(__l, __n, hasher(), key_equal(), __a)
267 { }
268
269 unordered_map(initializer_list<value_type> __l,
270 size_type __n, const hasher& __hf,
271 const allocator_type& __a)
272 : unordered_map(__l, __n, __hf, key_equal(), __a)
273 { }
274
275 /// Copy assignment operator.
276 unordered_map&
277 operator=(const unordered_map&) = default;
278
279 /// Move assignment operator.
280 unordered_map&
281 operator=(unordered_map&&) = default;
282
283 /**
284 * @brief %Unordered_map list assignment operator.
285 * @param __l An initializer_list.
286 *
287 * This function fills an %unordered_map with copies of the elements in
288 * the initializer list @a __l.
289 *
290 * Note that the assignment completely changes the %unordered_map and
291 * that the resulting %unordered_map's size is the same as the number
292 * of elements assigned.
293 */
294 unordered_map&
295 operator=(initializer_list<value_type> __l)
296 {
297 _M_h = __l;
298 return *this;
299 }
300
301 /// Returns the allocator object used by the %unordered_map.
302 allocator_type
303 get_allocator() const noexcept
304 { return _M_h.get_allocator(); }
305
306 // size and capacity:
307
308 /// Returns true if the %unordered_map is empty.
309 _GLIBCXX_NODISCARD bool
310 empty() const noexcept
311 { return _M_h.empty(); }
312
313 /// Returns the size of the %unordered_map.
314 size_type
315 size() const noexcept
316 { return _M_h.size(); }
317
318 /// Returns the maximum size of the %unordered_map.
319 size_type
320 max_size() const noexcept
321 { return _M_h.max_size(); }
322
323 // iterators.
324
325 /**
326 * Returns a read/write iterator that points to the first element in the
327 * %unordered_map.
328 */
329 iterator
330 begin() noexcept
331 { return _M_h.begin(); }
332
333 ///@{
334 /**
335 * Returns a read-only (constant) iterator that points to the first
336 * element in the %unordered_map.
337 */
338 const_iterator
339 begin() const noexcept
340 { return _M_h.begin(); }
341
342 const_iterator
343 cbegin() const noexcept
344 { return _M_h.begin(); }
345 ///@}
346
347 /**
348 * Returns a read/write iterator that points one past the last element in
349 * the %unordered_map.
350 */
351 iterator
352 end() noexcept
353 { return _M_h.end(); }
354
355 ///@{
356 /**
357 * Returns a read-only (constant) iterator that points one past the last
358 * element in the %unordered_map.
359 */
360 const_iterator
361 end() const noexcept
362 { return _M_h.end(); }
363
364 const_iterator
365 cend() const noexcept
366 { return _M_h.end(); }
367 ///@}
368
369 // modifiers.
370
371 /**
372 * @brief Attempts to build and insert a std::pair into the
373 * %unordered_map.
374 *
375 * @param __args Arguments used to generate a new pair instance (see
376 * std::piecewise_contruct for passing arguments to each
377 * part of the pair constructor).
378 *
379 * @return A pair, of which the first element is an iterator that points
380 * to the possibly inserted pair, and the second is a bool that
381 * is true if the pair was actually inserted.
382 *
383 * This function attempts to build and insert a (key, value) %pair into
384 * the %unordered_map.
385 * An %unordered_map relies on unique keys and thus a %pair is only
386 * inserted if its first element (the key) is not already present in the
387 * %unordered_map.
388 *
389 * Insertion requires amortized constant time.
390 */
391 template<typename... _Args>
392 std::pair<iterator, bool>
393 emplace(_Args&&... __args)
394 { return _M_h.emplace(std::forward<_Args>(__args)...); }
395
396 /**
397 * @brief Attempts to build and insert a std::pair into the
398 * %unordered_map.
399 *
400 * @param __pos An iterator that serves as a hint as to where the pair
401 * should be inserted.
402 * @param __args Arguments used to generate a new pair instance (see
403 * std::piecewise_contruct for passing arguments to each
404 * part of the pair constructor).
405 * @return An iterator that points to the element with key of the
406 * std::pair built from @a __args (may or may not be that
407 * std::pair).
408 *
409 * This function is not concerned about whether the insertion took place,
410 * and thus does not return a boolean like the single-argument emplace()
411 * does.
412 * Note that the first parameter is only a hint and can potentially
413 * improve the performance of the insertion process. A bad hint would
414 * cause no gains in efficiency.
415 *
416 * See
417 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
418 * for more on @a hinting.
419 *
420 * Insertion requires amortized constant time.
421 */
422 template<typename... _Args>
423 iterator
424 emplace_hint(const_iterator __pos, _Args&&... __args)
425 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
426
427#if __cplusplus > 201402L
428 /// Extract a node.
429 node_type
430 extract(const_iterator __pos)
431 {
432 __glibcxx_assert(__pos != end());
433 return _M_h.extract(__pos);
434 }
435
436 /// Extract a node.
437 node_type
438 extract(const key_type& __key)
439 { return _M_h.extract(__key); }
440
441 /// Re-insert an extracted node.
442 insert_return_type
443 insert(node_type&& __nh)
444 { return _M_h._M_reinsert_node(std::move(__nh)); }
445
446 /// Re-insert an extracted node.
447 iterator
448 insert(const_iterator, node_type&& __nh)
449 { return _M_h._M_reinsert_node(std::move(__nh)).position; }
450
451#define __cpp_lib_unordered_map_try_emplace 201411L
452 /**
453 * @brief Attempts to build and insert a std::pair into the
454 * %unordered_map.
455 *
456 * @param __k Key to use for finding a possibly existing pair in
457 * the unordered_map.
458 * @param __args Arguments used to generate the .second for a
459 * new pair instance.
460 *
461 * @return A pair, of which the first element is an iterator that points
462 * to the possibly inserted pair, and the second is a bool that
463 * is true if the pair was actually inserted.
464 *
465 * This function attempts to build and insert a (key, value) %pair into
466 * the %unordered_map.
467 * An %unordered_map relies on unique keys and thus a %pair is only
468 * inserted if its first element (the key) is not already present in the
469 * %unordered_map.
470 * If a %pair is not inserted, this function has no effect.
471 *
472 * Insertion requires amortized constant time.
473 */
474 template <typename... _Args>
475 pair<iterator, bool>
476 try_emplace(const key_type& __k, _Args&&... __args)
477 {
478 return _M_h.try_emplace(cend(), __k, std::forward<_Args>(__args)...);
479 }
480
481 // move-capable overload
482 template <typename... _Args>
483 pair<iterator, bool>
484 try_emplace(key_type&& __k, _Args&&... __args)
485 {
486 return _M_h.try_emplace(cend(), std::move(__k),
487 std::forward<_Args>(__args)...);
488 }
489
490 /**
491 * @brief Attempts to build and insert a std::pair into the
492 * %unordered_map.
493 *
494 * @param __hint An iterator that serves as a hint as to where the pair
495 * should be inserted.
496 * @param __k Key to use for finding a possibly existing pair in
497 * the unordered_map.
498 * @param __args Arguments used to generate the .second for a
499 * new pair instance.
500 * @return An iterator that points to the element with key of the
501 * std::pair built from @a __args (may or may not be that
502 * std::pair).
503 *
504 * This function is not concerned about whether the insertion took place,
505 * and thus does not return a boolean like the single-argument emplace()
506 * does. However, if insertion did not take place,
507 * this function has no effect.
508 * Note that the first parameter is only a hint and can potentially
509 * improve the performance of the insertion process. A bad hint would
510 * cause no gains in efficiency.
511 *
512 * See
513 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
514 * for more on @a hinting.
515 *
516 * Insertion requires amortized constant time.
517 */
518 template <typename... _Args>
519 iterator
520 try_emplace(const_iterator __hint, const key_type& __k,
521 _Args&&... __args)
522 {
523 return _M_h.try_emplace(__hint, __k,
524 std::forward<_Args>(__args)...).first;
525 }
526
527 // move-capable overload
528 template <typename... _Args>
529 iterator
530 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
531 {
532 return _M_h.try_emplace(__hint, std::move(__k),
533 std::forward<_Args>(__args)...).first;
534 }
535#endif // C++17
536
537 ///@{
538 /**
539 * @brief Attempts to insert a std::pair into the %unordered_map.
540
541 * @param __x Pair to be inserted (see std::make_pair for easy
542 * creation of pairs).
543 *
544 * @return A pair, of which the first element is an iterator that
545 * points to the possibly inserted pair, and the second is
546 * a bool that is true if the pair was actually inserted.
547 *
548 * This function attempts to insert a (key, value) %pair into the
549 * %unordered_map. An %unordered_map relies on unique keys and thus a
550 * %pair is only inserted if its first element (the key) is not already
551 * present in the %unordered_map.
552 *
553 * Insertion requires amortized constant time.
554 */
555 std::pair<iterator, bool>
556 insert(const value_type& __x)
557 { return _M_h.insert(__x); }
558
559 // _GLIBCXX_RESOLVE_LIB_DEFECTS
560 // 2354. Unnecessary copying when inserting into maps with braced-init
561 std::pair<iterator, bool>
562 insert(value_type&& __x)
563 { return _M_h.insert(std::move(__x)); }
564
565 template<typename _Pair>
566 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
567 pair<iterator, bool>>
568 insert(_Pair&& __x)
569 { return _M_h.emplace(std::forward<_Pair>(__x)); }
570 ///@}
571
572 ///@{
573 /**
574 * @brief Attempts to insert a std::pair into the %unordered_map.
575 * @param __hint An iterator that serves as a hint as to where the
576 * pair should be inserted.
577 * @param __x Pair to be inserted (see std::make_pair for easy creation
578 * of pairs).
579 * @return An iterator that points to the element with key of
580 * @a __x (may or may not be the %pair passed in).
581 *
582 * This function is not concerned about whether the insertion took place,
583 * and thus does not return a boolean like the single-argument insert()
584 * does. Note that the first parameter is only a hint and can
585 * potentially improve the performance of the insertion process. A bad
586 * hint would cause no gains in efficiency.
587 *
588 * See
589 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
590 * for more on @a hinting.
591 *
592 * Insertion requires amortized constant time.
593 */
594 iterator
595 insert(const_iterator __hint, const value_type& __x)
596 { return _M_h.insert(__hint, __x); }
597
598 // _GLIBCXX_RESOLVE_LIB_DEFECTS
599 // 2354. Unnecessary copying when inserting into maps with braced-init
600 iterator
601 insert(const_iterator __hint, value_type&& __x)
602 { return _M_h.insert(__hint, std::move(__x)); }
603
604 template<typename _Pair>
605 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
606 insert(const_iterator __hint, _Pair&& __x)
607 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
608 ///@}
609
610 /**
611 * @brief A template function that attempts to insert a range of
612 * elements.
613 * @param __first Iterator pointing to the start of the range to be
614 * inserted.
615 * @param __last Iterator pointing to the end of the range.
616 *
617 * Complexity similar to that of the range constructor.
618 */
619 template<typename _InputIterator>
620 void
621 insert(_InputIterator __first, _InputIterator __last)
622 { _M_h.insert(__first, __last); }
623
624 /**
625 * @brief Attempts to insert a list of elements into the %unordered_map.
626 * @param __l A std::initializer_list<value_type> of elements
627 * to be inserted.
628 *
629 * Complexity similar to that of the range constructor.
630 */
631 void
632 insert(initializer_list<value_type> __l)
633 { _M_h.insert(__l); }
634
635
636#if __cplusplus > 201402L
637 /**
638 * @brief Attempts to insert a std::pair into the %unordered_map.
639 * @param __k Key to use for finding a possibly existing pair in
640 * the map.
641 * @param __obj Argument used to generate the .second for a pair
642 * instance.
643 *
644 * @return A pair, of which the first element is an iterator that
645 * points to the possibly inserted pair, and the second is
646 * a bool that is true if the pair was actually inserted.
647 *
648 * This function attempts to insert a (key, value) %pair into the
649 * %unordered_map. An %unordered_map relies on unique keys and thus a
650 * %pair is only inserted if its first element (the key) is not already
651 * present in the %unordered_map.
652 * If the %pair was already in the %unordered_map, the .second of
653 * the %pair is assigned from __obj.
654 *
655 * Insertion requires amortized constant time.
656 */
657 template <typename _Obj>
658 pair<iterator, bool>
659 insert_or_assign(const key_type& __k, _Obj&& __obj)
660 {
661 auto __ret = _M_h.try_emplace(cend(), __k,
662 std::forward<_Obj>(__obj));
663 if (!__ret.second)
664 __ret.first->second = std::forward<_Obj>(__obj);
665 return __ret;
666 }
667
668 // move-capable overload
669 template <typename _Obj>
670 pair<iterator, bool>
671 insert_or_assign(key_type&& __k, _Obj&& __obj)
672 {
673 auto __ret = _M_h.try_emplace(cend(), std::move(__k),
674 std::forward<_Obj>(__obj));
675 if (!__ret.second)
676 __ret.first->second = std::forward<_Obj>(__obj);
677 return __ret;
678 }
679
680 /**
681 * @brief Attempts to insert a std::pair into the %unordered_map.
682 * @param __hint An iterator that serves as a hint as to where the
683 * pair should be inserted.
684 * @param __k Key to use for finding a possibly existing pair in
685 * the unordered_map.
686 * @param __obj Argument used to generate the .second for a pair
687 * instance.
688 * @return An iterator that points to the element with key of
689 * @a __x (may or may not be the %pair passed in).
690 *
691 * This function is not concerned about whether the insertion took place,
692 * and thus does not return a boolean like the single-argument insert()
693 * does.
694 * If the %pair was already in the %unordered map, the .second of
695 * the %pair is assigned from __obj.
696 * Note that the first parameter is only a hint and can
697 * potentially improve the performance of the insertion process. A bad
698 * hint would cause no gains in efficiency.
699 *
700 * See
701 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
702 * for more on @a hinting.
703 *
704 * Insertion requires amortized constant time.
705 */
706 template <typename _Obj>
707 iterator
708 insert_or_assign(const_iterator __hint, const key_type& __k,
709 _Obj&& __obj)
710 {
711 auto __ret = _M_h.try_emplace(__hint, __k, std::forward<_Obj>(__obj));
712 if (!__ret.second)
713 __ret.first->second = std::forward<_Obj>(__obj);
714 return __ret.first;
715 }
716
717 // move-capable overload
718 template <typename _Obj>
719 iterator
720 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
721 {
722 auto __ret = _M_h.try_emplace(__hint, std::move(__k),
723 std::forward<_Obj>(__obj));
724 if (!__ret.second)
725 __ret.first->second = std::forward<_Obj>(__obj);
726 return __ret.first;
727 }
728#endif
729
730 ///@{
731 /**
732 * @brief Erases an element from an %unordered_map.
733 * @param __position An iterator pointing to the element to be erased.
734 * @return An iterator pointing to the element immediately following
735 * @a __position prior to the element being erased. If no such
736 * element exists, end() is returned.
737 *
738 * This function erases an element, pointed to by the given iterator,
739 * from an %unordered_map.
740 * Note that this function only erases the element, and that if the
741 * element is itself a pointer, the pointed-to memory is not touched in
742 * any way. Managing the pointer is the user's responsibility.
743 */
744 iterator
745 erase(const_iterator __position)
746 { return _M_h.erase(__position); }
747
748 // LWG 2059.
749 iterator
750 erase(iterator __position)
751 { return _M_h.erase(__position); }
752 ///@}
753
754 /**
755 * @brief Erases elements according to the provided key.
756 * @param __x Key of element to be erased.
757 * @return The number of elements erased.
758 *
759 * This function erases all the elements located by the given key from
760 * an %unordered_map. For an %unordered_map the result of this function
761 * can only be 0 (not present) or 1 (present).
762 * Note that this function only erases the element, and that if the
763 * element is itself a pointer, the pointed-to memory is not touched in
764 * any way. Managing the pointer is the user's responsibility.
765 */
766 size_type
767 erase(const key_type& __x)
768 { return _M_h.erase(__x); }
769
770 /**
771 * @brief Erases a [__first,__last) range of elements from an
772 * %unordered_map.
773 * @param __first Iterator pointing to the start of the range to be
774 * erased.
775 * @param __last Iterator pointing to the end of the range to
776 * be erased.
777 * @return The iterator @a __last.
778 *
779 * This function erases a sequence of elements from an %unordered_map.
780 * Note that this function only erases the elements, and that if
781 * the element is itself a pointer, the pointed-to memory is not touched
782 * in any way. Managing the pointer is the user's responsibility.
783 */
784 iterator
785 erase(const_iterator __first, const_iterator __last)
786 { return _M_h.erase(__first, __last); }
787
788 /**
789 * Erases all elements in an %unordered_map.
790 * Note that this function only erases the elements, and that if the
791 * elements themselves are pointers, the pointed-to memory is not touched
792 * in any way. Managing the pointer is the user's responsibility.
793 */
794 void
795 clear() noexcept
796 { _M_h.clear(); }
797
798 /**
799 * @brief Swaps data with another %unordered_map.
800 * @param __x An %unordered_map of the same element and allocator
801 * types.
802 *
803 * This exchanges the elements between two %unordered_map in constant
804 * time.
805 * Note that the global std::swap() function is specialized such that
806 * std::swap(m1,m2) will feed to this function.
807 */
808 void
809 swap(unordered_map& __x)
810 noexcept( noexcept(_M_h.swap(__x._M_h)) )
811 { _M_h.swap(__x._M_h); }
812
813#if __cplusplus > 201402L
814 template<typename, typename, typename>
815 friend class std::_Hash_merge_helper;
816
817 template<typename _H2, typename _P2>
818 void
819 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
820 {
821 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
822 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
823 }
824
825 template<typename _H2, typename _P2>
826 void
827 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
828 { merge(__source); }
829
830 template<typename _H2, typename _P2>
831 void
832 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
833 {
834 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
835 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
836 }
837
838 template<typename _H2, typename _P2>
839 void
840 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
841 { merge(__source); }
842#endif // C++17
843
844 // observers.
845
846 /// Returns the hash functor object with which the %unordered_map was
847 /// constructed.
848 hasher
849 hash_function() const
850 { return _M_h.hash_function(); }
851
852 /// Returns the key comparison object with which the %unordered_map was
853 /// constructed.
854 key_equal
855 key_eq() const
856 { return _M_h.key_eq(); }
857
858 // lookup.
859
860 ///@{
861 /**
862 * @brief Tries to locate an element in an %unordered_map.
863 * @param __x Key to be located.
864 * @return Iterator pointing to sought-after element, or end() if not
865 * found.
866 *
867 * This function takes a key and tries to locate the element with which
868 * the key matches. If successful the function returns an iterator
869 * pointing to the sought after element. If unsuccessful it returns the
870 * past-the-end ( @c end() ) iterator.
871 */
872 iterator
873 find(const key_type& __x)
874 { return _M_h.find(__x); }
875
876#if __cplusplus > 201703L
877 template<typename _Kt>
878 auto
879 find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
880 { return _M_h._M_find_tr(__x); }
881#endif
882
883 const_iterator
884 find(const key_type& __x) const
885 { return _M_h.find(__x); }
886
887#if __cplusplus > 201703L
888 template<typename _Kt>
889 auto
890 find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
891 { return _M_h._M_find_tr(__x); }
892#endif
893 ///@}
894
895 ///@{
896 /**
897 * @brief Finds the number of elements.
898 * @param __x Key to count.
899 * @return Number of elements with specified key.
900 *
901 * This function only makes sense for %unordered_multimap; for
902 * %unordered_map the result will either be 0 (not present) or 1
903 * (present).
904 */
905 size_type
906 count(const key_type& __x) const
907 { return _M_h.count(__x); }
908
909#if __cplusplus > 201703L
910 template<typename _Kt>
911 auto
912 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
913 { return _M_h._M_count_tr(__x); }
914#endif
915 ///@}
916
917#if __cplusplus > 201703L
918 ///@{
919 /**
920 * @brief Finds whether an element with the given key exists.
921 * @param __x Key of elements to be located.
922 * @return True if there is any element with the specified key.
923 */
924 bool
925 contains(const key_type& __x) const
926 { return _M_h.find(__x) != _M_h.end(); }
927
928 template<typename _Kt>
929 auto
930 contains(const _Kt& __x) const
931 -> decltype(_M_h._M_find_tr(__x), void(), true)
932 { return _M_h._M_find_tr(__x) != _M_h.end(); }
933 ///@}
934#endif
935
936 ///@{
937 /**
938 * @brief Finds a subsequence matching given key.
939 * @param __x Key to be located.
940 * @return Pair of iterators that possibly points to the subsequence
941 * matching given key.
942 *
943 * This function probably only makes sense for %unordered_multimap.
944 */
945 std::pair<iterator, iterator>
946 equal_range(const key_type& __x)
947 { return _M_h.equal_range(__x); }
948
949#if __cplusplus > 201703L
950 template<typename _Kt>
951 auto
952 equal_range(const _Kt& __x)
953 -> decltype(_M_h._M_equal_range_tr(__x))
954 { return _M_h._M_equal_range_tr(__x); }
955#endif
956
957 std::pair<const_iterator, const_iterator>
958 equal_range(const key_type& __x) const
959 { return _M_h.equal_range(__x); }
960
961#if __cplusplus > 201703L
962 template<typename _Kt>
963 auto
964 equal_range(const _Kt& __x) const
965 -> decltype(_M_h._M_equal_range_tr(__x))
966 { return _M_h._M_equal_range_tr(__x); }
967#endif
968 ///@}
969
970 ///@{
971 /**
972 * @brief Subscript ( @c [] ) access to %unordered_map data.
973 * @param __k The key for which data should be retrieved.
974 * @return A reference to the data of the (key,data) %pair.
975 *
976 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
977 * data associated with the key specified in subscript. If the key does
978 * not exist, a pair with that key is created using default values, which
979 * is then returned.
980 *
981 * Lookup requires constant time.
982 */
983 mapped_type&
984 operator[](const key_type& __k)
985 { return _M_h[__k]; }
986
987 mapped_type&
988 operator[](key_type&& __k)
989 { return _M_h[std::move(__k)]; }
990 ///@}
991
992 ///@{
993 /**
994 * @brief Access to %unordered_map data.
995 * @param __k The key for which data should be retrieved.
996 * @return A reference to the data whose key is equal to @a __k, if
997 * such a data is present in the %unordered_map.
998 * @throw std::out_of_range If no such data is present.
999 */
1000 mapped_type&
1001 at(const key_type& __k)
1002 { return _M_h.at(__k); }
1003
1004 const mapped_type&
1005 at(const key_type& __k) const
1006 { return _M_h.at(__k); }
1007 ///@}
1008
1009 // bucket interface.
1010
1011 /// Returns the number of buckets of the %unordered_map.
1012 size_type
1013 bucket_count() const noexcept
1014 { return _M_h.bucket_count(); }
1015
1016 /// Returns the maximum number of buckets of the %unordered_map.
1017 size_type
1018 max_bucket_count() const noexcept
1019 { return _M_h.max_bucket_count(); }
1020
1021 /*
1022 * @brief Returns the number of elements in a given bucket.
1023 * @param __n A bucket index.
1024 * @return The number of elements in the bucket.
1025 */
1026 size_type
1027 bucket_size(size_type __n) const
1028 { return _M_h.bucket_size(__n); }
1029
1030 /*
1031 * @brief Returns the bucket index of a given element.
1032 * @param __key A key instance.
1033 * @return The key bucket index.
1034 */
1035 size_type
1036 bucket(const key_type& __key) const
1037 { return _M_h.bucket(__key); }
1038
1039 /**
1040 * @brief Returns a read/write iterator pointing to the first bucket
1041 * element.
1042 * @param __n The bucket index.
1043 * @return A read/write local iterator.
1044 */
1045 local_iterator
1046 begin(size_type __n)
1047 { return _M_h.begin(__n); }
1048
1049 ///@{
1050 /**
1051 * @brief Returns a read-only (constant) iterator pointing to the first
1052 * bucket element.
1053 * @param __n The bucket index.
1054 * @return A read-only local iterator.
1055 */
1056 const_local_iterator
1057 begin(size_type __n) const
1058 { return _M_h.begin(__n); }
1059
1060 const_local_iterator
1061 cbegin(size_type __n) const
1062 { return _M_h.cbegin(__n); }
1063 ///@}
1064
1065 /**
1066 * @brief Returns a read/write iterator pointing to one past the last
1067 * bucket elements.
1068 * @param __n The bucket index.
1069 * @return A read/write local iterator.
1070 */
1071 local_iterator
1072 end(size_type __n)
1073 { return _M_h.end(__n); }
1074
1075 ///@{
1076 /**
1077 * @brief Returns a read-only (constant) iterator pointing to one past
1078 * the last bucket elements.
1079 * @param __n The bucket index.
1080 * @return A read-only local iterator.
1081 */
1082 const_local_iterator
1083 end(size_type __n) const
1084 { return _M_h.end(__n); }
1085
1086 const_local_iterator
1087 cend(size_type __n) const
1088 { return _M_h.cend(__n); }
1089 ///@}
1090
1091 // hash policy.
1092
1093 /// Returns the average number of elements per bucket.
1094 float
1095 load_factor() const noexcept
1096 { return _M_h.load_factor(); }
1097
1098 /// Returns a positive number that the %unordered_map tries to keep the
1099 /// load factor less than or equal to.
1100 float
1101 max_load_factor() const noexcept
1102 { return _M_h.max_load_factor(); }
1103
1104 /**
1105 * @brief Change the %unordered_map maximum load factor.
1106 * @param __z The new maximum load factor.
1107 */
1108 void
1109 max_load_factor(float __z)
1110 { _M_h.max_load_factor(__z); }
1111
1112 /**
1113 * @brief May rehash the %unordered_map.
1114 * @param __n The new number of buckets.
1115 *
1116 * Rehash will occur only if the new number of buckets respect the
1117 * %unordered_map maximum load factor.
1118 */
1119 void
1120 rehash(size_type __n)
1121 { _M_h.rehash(__n); }
1122
1123 /**
1124 * @brief Prepare the %unordered_map for a specified number of
1125 * elements.
1126 * @param __n Number of elements required.
1127 *
1128 * Same as rehash(ceil(n / max_load_factor())).
1129 */
1130 void
1131 reserve(size_type __n)
1132 { _M_h.reserve(__n); }
1133
1134 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1135 typename _Alloc1>
1136 friend bool
1137 operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
1138 const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
1139 };
1140
1141#if __cpp_deduction_guides >= 201606
1142
1143 template<typename _InputIterator,
1144 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1145 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1146 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1147 typename = _RequireInputIter<_InputIterator>,
1148 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1149 typename = _RequireNotAllocator<_Pred>,
1150 typename = _RequireAllocator<_Allocator>>
1151 unordered_map(_InputIterator, _InputIterator,
1152 typename unordered_map<int, int>::size_type = {},
1153 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1154 -> unordered_map<__iter_key_t<_InputIterator>,
1155 __iter_val_t<_InputIterator>,
1156 _Hash, _Pred, _Allocator>;
1157
1158 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1159 typename _Pred = equal_to<_Key>,
1160 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1161 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1162 typename = _RequireNotAllocator<_Pred>,
1163 typename = _RequireAllocator<_Allocator>>
1164 unordered_map(initializer_list<pair<_Key, _Tp>>,
1165 typename unordered_map<int, int>::size_type = {},
1166 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1167 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1168
1169 template<typename _InputIterator, typename _Allocator,
1170 typename = _RequireInputIter<_InputIterator>,
1171 typename = _RequireAllocator<_Allocator>>
1172 unordered_map(_InputIterator, _InputIterator,
1173 typename unordered_map<int, int>::size_type, _Allocator)
1174 -> unordered_map<__iter_key_t<_InputIterator>,
1175 __iter_val_t<_InputIterator>,
1176 hash<__iter_key_t<_InputIterator>>,
1177 equal_to<__iter_key_t<_InputIterator>>,
1178 _Allocator>;
1179
1180 template<typename _InputIterator, typename _Allocator,
1181 typename = _RequireInputIter<_InputIterator>,
1182 typename = _RequireAllocator<_Allocator>>
1183 unordered_map(_InputIterator, _InputIterator, _Allocator)
1184 -> unordered_map<__iter_key_t<_InputIterator>,
1185 __iter_val_t<_InputIterator>,
1186 hash<__iter_key_t<_InputIterator>>,
1187 equal_to<__iter_key_t<_InputIterator>>,
1188 _Allocator>;
1189
1190 template<typename _InputIterator, typename _Hash, typename _Allocator,
1191 typename = _RequireInputIter<_InputIterator>,
1192 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1193 typename = _RequireAllocator<_Allocator>>
1194 unordered_map(_InputIterator, _InputIterator,
1195 typename unordered_map<int, int>::size_type,
1196 _Hash, _Allocator)
1197 -> unordered_map<__iter_key_t<_InputIterator>,
1198 __iter_val_t<_InputIterator>, _Hash,
1199 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1200
1201 template<typename _Key, typename _Tp, typename _Allocator,
1202 typename = _RequireAllocator<_Allocator>>
1203 unordered_map(initializer_list<pair<_Key, _Tp>>,
1204 typename unordered_map<int, int>::size_type,
1205 _Allocator)
1206 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1207
1208 template<typename _Key, typename _Tp, typename _Allocator,
1209 typename = _RequireAllocator<_Allocator>>
1210 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1211 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1212
1213 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1214 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1215 typename = _RequireAllocator<_Allocator>>
1216 unordered_map(initializer_list<pair<_Key, _Tp>>,
1217 typename unordered_map<int, int>::size_type,
1218 _Hash, _Allocator)
1219 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1220
1221#endif
1222
1223 /**
1224 * @brief A standard container composed of equivalent keys
1225 * (possibly containing multiple of each key value) that associates
1226 * values of another type with the keys.
1227 *
1228 * @ingroup unordered_associative_containers
1229 *
1230 * @tparam _Key Type of key objects.
1231 * @tparam _Tp Type of mapped objects.
1232 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1233 * @tparam _Pred Predicate function object type, defaults
1234 * to equal_to<_Value>.
1235 * @tparam _Alloc Allocator type, defaults to
1236 * std::allocator<std::pair<const _Key, _Tp>>.
1237 *
1238 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1239 * <a href="tables.html#xx">unordered associative container</a>
1240 *
1241 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1242 *
1243 * Base is _Hashtable, dispatched at compile time via template
1244 * alias __ummap_hashtable.
1245 */
1246 template<typename _Key, typename _Tp,
1247 typename _Hash = hash<_Key>,
1248 typename _Pred = equal_to<_Key>,
1249 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1250 class unordered_multimap
1251 {
1252 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
1253 _Hashtable _M_h;
1254
1255 public:
1256 // typedefs:
1257 ///@{
1258 /// Public typedefs.
1259 typedef typename _Hashtable::key_type key_type;
1260 typedef typename _Hashtable::value_type value_type;
1261 typedef typename _Hashtable::mapped_type mapped_type;
1262 typedef typename _Hashtable::hasher hasher;
1263 typedef typename _Hashtable::key_equal key_equal;
1264 typedef typename _Hashtable::allocator_type allocator_type;
1265 ///@}
1266
1267 ///@{
1268 /// Iterator-related typedefs.
1269 typedef typename _Hashtable::pointer pointer;
1270 typedef typename _Hashtable::const_pointer const_pointer;
1271 typedef typename _Hashtable::reference reference;
1272 typedef typename _Hashtable::const_reference const_reference;
1273 typedef typename _Hashtable::iterator iterator;
1274 typedef typename _Hashtable::const_iterator const_iterator;
1275 typedef typename _Hashtable::local_iterator local_iterator;
1276 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1277 typedef typename _Hashtable::size_type size_type;
1278 typedef typename _Hashtable::difference_type difference_type;
1279 ///@}
1280
1281#if __cplusplus > 201402L
1282 using node_type = typename _Hashtable::node_type;
1283#endif
1284
1285 //construct/destroy/copy
1286
1287 /// Default constructor.
1288 unordered_multimap() = default;
1289
1290 /**
1291 * @brief Default constructor creates no elements.
1292 * @param __n Mnimal initial number of buckets.
1293 * @param __hf A hash functor.
1294 * @param __eql A key equality functor.
1295 * @param __a An allocator object.
1296 */
1297 explicit
1298 unordered_multimap(size_type __n,
1299 const hasher& __hf = hasher(),
1300 const key_equal& __eql = key_equal(),
1301 const allocator_type& __a = allocator_type())
1302 : _M_h(__n, __hf, __eql, __a)
1303 { }
1304
1305 /**
1306 * @brief Builds an %unordered_multimap from a range.
1307 * @param __first An input iterator.
1308 * @param __last An input iterator.
1309 * @param __n Minimal initial number of buckets.
1310 * @param __hf A hash functor.
1311 * @param __eql A key equality functor.
1312 * @param __a An allocator object.
1313 *
1314 * Create an %unordered_multimap consisting of copies of the elements
1315 * from [__first,__last). This is linear in N (where N is
1316 * distance(__first,__last)).
1317 */
1318 template<typename _InputIterator>
1319 unordered_multimap(_InputIterator __first, _InputIterator __last,
1320 size_type __n = 0,
1321 const hasher& __hf = hasher(),
1322 const key_equal& __eql = key_equal(),
1323 const allocator_type& __a = allocator_type())
1324 : _M_h(__first, __last, __n, __hf, __eql, __a)
1325 { }
1326
1327 /// Copy constructor.
1328 unordered_multimap(const unordered_multimap&) = default;
1329
1330 /// Move constructor.
1331 unordered_multimap(unordered_multimap&&) = default;
1332
1333 /**
1334 * @brief Creates an %unordered_multimap with no elements.
1335 * @param __a An allocator object.
1336 */
1337 explicit
1338 unordered_multimap(const allocator_type& __a)
1339 : _M_h(__a)
1340 { }
1341
1342 /*
1343 * @brief Copy constructor with allocator argument.
1344 * @param __uset Input %unordered_multimap to copy.
1345 * @param __a An allocator object.
1346 */
1347 unordered_multimap(const unordered_multimap& __ummap,
1348 const allocator_type& __a)
1349 : _M_h(__ummap._M_h, __a)
1350 { }
1351
1352 /*
1353 * @brief Move constructor with allocator argument.
1354 * @param __uset Input %unordered_multimap to move.
1355 * @param __a An allocator object.
1356 */
1357 unordered_multimap(unordered_multimap&& __ummap,
1358 const allocator_type& __a)
1359 noexcept( noexcept(_Hashtable(std::move(__ummap._M_h), __a)) )
1360 : _M_h(std::move(__ummap._M_h), __a)
1361 { }
1362
1363 /**
1364 * @brief Builds an %unordered_multimap from an initializer_list.
1365 * @param __l An initializer_list.
1366 * @param __n Minimal initial number of buckets.
1367 * @param __hf A hash functor.
1368 * @param __eql A key equality functor.
1369 * @param __a An allocator object.
1370 *
1371 * Create an %unordered_multimap consisting of copies of the elements in
1372 * the list. This is linear in N (where N is @a __l.size()).
1373 */
1374 unordered_multimap(initializer_list<value_type> __l,
1375 size_type __n = 0,
1376 const hasher& __hf = hasher(),
1377 const key_equal& __eql = key_equal(),
1378 const allocator_type& __a = allocator_type())
1379 : _M_h(__l, __n, __hf, __eql, __a)
1380 { }
1381
1382 unordered_multimap(size_type __n, const allocator_type& __a)
1383 : unordered_multimap(__n, hasher(), key_equal(), __a)
1384 { }
1385
1386 unordered_multimap(size_type __n, const hasher& __hf,
1387 const allocator_type& __a)
1388 : unordered_multimap(__n, __hf, key_equal(), __a)
1389 { }
1390
1391 template<typename _InputIterator>
1392 unordered_multimap(_InputIterator __first, _InputIterator __last,
1393 size_type __n,
1394 const allocator_type& __a)
1395 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1396 { }
1397
1398 template<typename _InputIterator>
1399 unordered_multimap(_InputIterator __first, _InputIterator __last,
1400 size_type __n, const hasher& __hf,
1401 const allocator_type& __a)
1402 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1403 { }
1404
1405 unordered_multimap(initializer_list<value_type> __l,
1406 size_type __n,
1407 const allocator_type& __a)
1408 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1409 { }
1410
1411 unordered_multimap(initializer_list<value_type> __l,
1412 size_type __n, const hasher& __hf,
1413 const allocator_type& __a)
1414 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1415 { }
1416
1417 /// Copy assignment operator.
1418 unordered_multimap&
1419 operator=(const unordered_multimap&) = default;
1420
1421 /// Move assignment operator.
1422 unordered_multimap&
1423 operator=(unordered_multimap&&) = default;
1424
1425 /**
1426 * @brief %Unordered_multimap list assignment operator.
1427 * @param __l An initializer_list.
1428 *
1429 * This function fills an %unordered_multimap with copies of the
1430 * elements in the initializer list @a __l.
1431 *
1432 * Note that the assignment completely changes the %unordered_multimap
1433 * and that the resulting %unordered_multimap's size is the same as the
1434 * number of elements assigned.
1435 */
1436 unordered_multimap&
1437 operator=(initializer_list<value_type> __l)
1438 {
1439 _M_h = __l;
1440 return *this;
1441 }
1442
1443 /// Returns the allocator object used by the %unordered_multimap.
1444 allocator_type
1445 get_allocator() const noexcept
1446 { return _M_h.get_allocator(); }
1447
1448 // size and capacity:
1449
1450 /// Returns true if the %unordered_multimap is empty.
1451 _GLIBCXX_NODISCARD bool
1452 empty() const noexcept
1453 { return _M_h.empty(); }
1454
1455 /// Returns the size of the %unordered_multimap.
1456 size_type
1457 size() const noexcept
1458 { return _M_h.size(); }
1459
1460 /// Returns the maximum size of the %unordered_multimap.
1461 size_type
1462 max_size() const noexcept
1463 { return _M_h.max_size(); }
1464
1465 // iterators.
1466
1467 /**
1468 * Returns a read/write iterator that points to the first element in the
1469 * %unordered_multimap.
1470 */
1471 iterator
1472 begin() noexcept
1473 { return _M_h.begin(); }
1474
1475 ///@{
1476 /**
1477 * Returns a read-only (constant) iterator that points to the first
1478 * element in the %unordered_multimap.
1479 */
1480 const_iterator
1481 begin() const noexcept
1482 { return _M_h.begin(); }
1483
1484 const_iterator
1485 cbegin() const noexcept
1486 { return _M_h.begin(); }
1487 ///@}
1488
1489 /**
1490 * Returns a read/write iterator that points one past the last element in
1491 * the %unordered_multimap.
1492 */
1493 iterator
1494 end() noexcept
1495 { return _M_h.end(); }
1496
1497 ///@{
1498 /**
1499 * Returns a read-only (constant) iterator that points one past the last
1500 * element in the %unordered_multimap.
1501 */
1502 const_iterator
1503 end() const noexcept
1504 { return _M_h.end(); }
1505
1506 const_iterator
1507 cend() const noexcept
1508 { return _M_h.end(); }
1509 ///@}
1510
1511 // modifiers.
1512
1513 /**
1514 * @brief Attempts to build and insert a std::pair into the
1515 * %unordered_multimap.
1516 *
1517 * @param __args Arguments used to generate a new pair instance (see
1518 * std::piecewise_contruct for passing arguments to each
1519 * part of the pair constructor).
1520 *
1521 * @return An iterator that points to the inserted pair.
1522 *
1523 * This function attempts to build and insert a (key, value) %pair into
1524 * the %unordered_multimap.
1525 *
1526 * Insertion requires amortized constant time.
1527 */
1528 template<typename... _Args>
1529 iterator
1530 emplace(_Args&&... __args)
1531 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1532
1533 /**
1534 * @brief Attempts to build and insert a std::pair into the
1535 * %unordered_multimap.
1536 *
1537 * @param __pos An iterator that serves as a hint as to where the pair
1538 * should be inserted.
1539 * @param __args Arguments used to generate a new pair instance (see
1540 * std::piecewise_contruct for passing arguments to each
1541 * part of the pair constructor).
1542 * @return An iterator that points to the element with key of the
1543 * std::pair built from @a __args.
1544 *
1545 * Note that the first parameter is only a hint and can potentially
1546 * improve the performance of the insertion process. A bad hint would
1547 * cause no gains in efficiency.
1548 *
1549 * See
1550 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1551 * for more on @a hinting.
1552 *
1553 * Insertion requires amortized constant time.
1554 */
1555 template<typename... _Args>
1556 iterator
1557 emplace_hint(const_iterator __pos, _Args&&... __args)
1558 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1559
1560 ///@{
1561 /**
1562 * @brief Inserts a std::pair into the %unordered_multimap.
1563 * @param __x Pair to be inserted (see std::make_pair for easy
1564 * creation of pairs).
1565 *
1566 * @return An iterator that points to the inserted pair.
1567 *
1568 * Insertion requires amortized constant time.
1569 */
1570 iterator
1571 insert(const value_type& __x)
1572 { return _M_h.insert(__x); }
1573
1574 iterator
1575 insert(value_type&& __x)
1576 { return _M_h.insert(std::move(__x)); }
1577
1578 template<typename _Pair>
1579 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1580 insert(_Pair&& __x)
1581 { return _M_h.emplace(std::forward<_Pair>(__x)); }
1582 ///@}
1583
1584 ///@{
1585 /**
1586 * @brief Inserts a std::pair into the %unordered_multimap.
1587 * @param __hint An iterator that serves as a hint as to where the
1588 * pair should be inserted.
1589 * @param __x Pair to be inserted (see std::make_pair for easy creation
1590 * of pairs).
1591 * @return An iterator that points to the element with key of
1592 * @a __x (may or may not be the %pair passed in).
1593 *
1594 * Note that the first parameter is only a hint and can potentially
1595 * improve the performance of the insertion process. A bad hint would
1596 * cause no gains in efficiency.
1597 *
1598 * See
1599 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1600 * for more on @a hinting.
1601 *
1602 * Insertion requires amortized constant time.
1603 */
1604 iterator
1605 insert(const_iterator __hint, const value_type& __x)
1606 { return _M_h.insert(__hint, __x); }
1607
1608 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1609 // 2354. Unnecessary copying when inserting into maps with braced-init
1610 iterator
1611 insert(const_iterator __hint, value_type&& __x)
1612 { return _M_h.insert(__hint, std::move(__x)); }
1613
1614 template<typename _Pair>
1615 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1616 insert(const_iterator __hint, _Pair&& __x)
1617 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1618 ///@}
1619
1620 /**
1621 * @brief A template function that attempts to insert a range of
1622 * elements.
1623 * @param __first Iterator pointing to the start of the range to be
1624 * inserted.
1625 * @param __last Iterator pointing to the end of the range.
1626 *
1627 * Complexity similar to that of the range constructor.
1628 */
1629 template<typename _InputIterator>
1630 void
1631 insert(_InputIterator __first, _InputIterator __last)
1632 { _M_h.insert(__first, __last); }
1633
1634 /**
1635 * @brief Attempts to insert a list of elements into the
1636 * %unordered_multimap.
1637 * @param __l A std::initializer_list<value_type> of elements
1638 * to be inserted.
1639 *
1640 * Complexity similar to that of the range constructor.
1641 */
1642 void
1643 insert(initializer_list<value_type> __l)
1644 { _M_h.insert(__l); }
1645
1646#if __cplusplus > 201402L
1647 /// Extract a node.
1648 node_type
1649 extract(const_iterator __pos)
1650 {
1651 __glibcxx_assert(__pos != end());
1652 return _M_h.extract(__pos);
1653 }
1654
1655 /// Extract a node.
1656 node_type
1657 extract(const key_type& __key)
1658 { return _M_h.extract(__key); }
1659
1660 /// Re-insert an extracted node.
1661 iterator
1662 insert(node_type&& __nh)
1663 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1664
1665 /// Re-insert an extracted node.
1666 iterator
1667 insert(const_iterator __hint, node_type&& __nh)
1668 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1669#endif // C++17
1670
1671 ///@{
1672 /**
1673 * @brief Erases an element from an %unordered_multimap.
1674 * @param __position An iterator pointing to the element to be erased.
1675 * @return An iterator pointing to the element immediately following
1676 * @a __position prior to the element being erased. If no such
1677 * element exists, end() is returned.
1678 *
1679 * This function erases an element, pointed to by the given iterator,
1680 * from an %unordered_multimap.
1681 * Note that this function only erases the element, and that if the
1682 * element is itself a pointer, the pointed-to memory is not touched in
1683 * any way. Managing the pointer is the user's responsibility.
1684 */
1685 iterator
1686 erase(const_iterator __position)
1687 { return _M_h.erase(__position); }
1688
1689 // LWG 2059.
1690 iterator
1691 erase(iterator __position)
1692 { return _M_h.erase(__position); }
1693 ///@}
1694
1695 /**
1696 * @brief Erases elements according to the provided key.
1697 * @param __x Key of elements to be erased.
1698 * @return The number of elements erased.
1699 *
1700 * This function erases all the elements located by the given key from
1701 * an %unordered_multimap.
1702 * Note that this function only erases the element, and that if the
1703 * element is itself a pointer, the pointed-to memory is not touched in
1704 * any way. Managing the pointer is the user's responsibility.
1705 */
1706 size_type
1707 erase(const key_type& __x)
1708 { return _M_h.erase(__x); }
1709
1710 /**
1711 * @brief Erases a [__first,__last) range of elements from an
1712 * %unordered_multimap.
1713 * @param __first Iterator pointing to the start of the range to be
1714 * erased.
1715 * @param __last Iterator pointing to the end of the range to
1716 * be erased.
1717 * @return The iterator @a __last.
1718 *
1719 * This function erases a sequence of elements from an
1720 * %unordered_multimap.
1721 * Note that this function only erases the elements, and that if
1722 * the element is itself a pointer, the pointed-to memory is not touched
1723 * in any way. Managing the pointer is the user's responsibility.
1724 */
1725 iterator
1726 erase(const_iterator __first, const_iterator __last)
1727 { return _M_h.erase(__first, __last); }
1728
1729 /**
1730 * Erases all elements in an %unordered_multimap.
1731 * Note that this function only erases the elements, and that if the
1732 * elements themselves are pointers, the pointed-to memory is not touched
1733 * in any way. Managing the pointer is the user's responsibility.
1734 */
1735 void
1736 clear() noexcept
1737 { _M_h.clear(); }
1738
1739 /**
1740 * @brief Swaps data with another %unordered_multimap.
1741 * @param __x An %unordered_multimap of the same element and allocator
1742 * types.
1743 *
1744 * This exchanges the elements between two %unordered_multimap in
1745 * constant time.
1746 * Note that the global std::swap() function is specialized such that
1747 * std::swap(m1,m2) will feed to this function.
1748 */
1749 void
1750 swap(unordered_multimap& __x)
1751 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1752 { _M_h.swap(__x._M_h); }
1753
1754#if __cplusplus > 201402L
1755 template<typename, typename, typename>
1756 friend class std::_Hash_merge_helper;
1757
1758 template<typename _H2, typename _P2>
1759 void
1760 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1761 {
1762 using _Merge_helper
1763 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1764 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1765 }
1766
1767 template<typename _H2, typename _P2>
1768 void
1769 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1770 { merge(__source); }
1771
1772 template<typename _H2, typename _P2>
1773 void
1774 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1775 {
1776 using _Merge_helper
1777 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1778 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1779 }
1780
1781 template<typename _H2, typename _P2>
1782 void
1783 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1784 { merge(__source); }
1785#endif // C++17
1786
1787 // observers.
1788
1789 /// Returns the hash functor object with which the %unordered_multimap
1790 /// was constructed.
1791 hasher
1792 hash_function() const
1793 { return _M_h.hash_function(); }
1794
1795 /// Returns the key comparison object with which the %unordered_multimap
1796 /// was constructed.
1797 key_equal
1798 key_eq() const
1799 { return _M_h.key_eq(); }
1800
1801 // lookup.
1802
1803 ///@{
1804 /**
1805 * @brief Tries to locate an element in an %unordered_multimap.
1806 * @param __x Key to be located.
1807 * @return Iterator pointing to sought-after element, or end() if not
1808 * found.
1809 *
1810 * This function takes a key and tries to locate the element with which
1811 * the key matches. If successful the function returns an iterator
1812 * pointing to the sought after element. If unsuccessful it returns the
1813 * past-the-end ( @c end() ) iterator.
1814 */
1815 iterator
1816 find(const key_type& __x)
1817 { return _M_h.find(__x); }
1818
1819#if __cplusplus > 201703L
1820 template<typename _Kt>
1821 auto
1822 find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
1823 { return _M_h._M_find_tr(__x); }
1824#endif
1825
1826 const_iterator
1827 find(const key_type& __x) const
1828 { return _M_h.find(__x); }
1829
1830#if __cplusplus > 201703L
1831 template<typename _Kt>
1832 auto
1833 find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
1834 { return _M_h._M_find_tr(__x); }
1835#endif
1836 ///@}
1837
1838 ///@{
1839 /**
1840 * @brief Finds the number of elements.
1841 * @param __x Key to count.
1842 * @return Number of elements with specified key.
1843 */
1844 size_type
1845 count(const key_type& __x) const
1846 { return _M_h.count(__x); }
1847
1848#if __cplusplus > 201703L
1849 template<typename _Kt>
1850 auto
1851 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
1852 { return _M_h._M_count_tr(__x); }
1853#endif
1854 ///@}
1855
1856#if __cplusplus > 201703L
1857 ///@{
1858 /**
1859 * @brief Finds whether an element with the given key exists.
1860 * @param __x Key of elements to be located.
1861 * @return True if there is any element with the specified key.
1862 */
1863 bool
1864 contains(const key_type& __x) const
1865 { return _M_h.find(__x) != _M_h.end(); }
1866
1867 template<typename _Kt>
1868 auto
1869 contains(const _Kt& __x) const
1870 -> decltype(_M_h._M_find_tr(__x), void(), true)
1871 { return _M_h._M_find_tr(__x) != _M_h.end(); }
1872 ///@}
1873#endif
1874
1875 ///@{
1876 /**
1877 * @brief Finds a subsequence matching given key.
1878 * @param __x Key to be located.
1879 * @return Pair of iterators that possibly points to the subsequence
1880 * matching given key.
1881 */
1882 std::pair<iterator, iterator>
1883 equal_range(const key_type& __x)
1884 { return _M_h.equal_range(__x); }
1885
1886#if __cplusplus > 201703L
1887 template<typename _Kt>
1888 auto
1889 equal_range(const _Kt& __x)
1890 -> decltype(_M_h._M_equal_range_tr(__x))
1891 { return _M_h._M_equal_range_tr(__x); }
1892#endif
1893
1894 std::pair<const_iterator, const_iterator>
1895 equal_range(const key_type& __x) const
1896 { return _M_h.equal_range(__x); }
1897
1898#if __cplusplus > 201703L
1899 template<typename _Kt>
1900 auto
1901 equal_range(const _Kt& __x) const
1902 -> decltype(_M_h._M_equal_range_tr(__x))
1903 { return _M_h._M_equal_range_tr(__x); }
1904#endif
1905 ///@}
1906
1907 // bucket interface.
1908
1909 /// Returns the number of buckets of the %unordered_multimap.
1910 size_type
1911 bucket_count() const noexcept
1912 { return _M_h.bucket_count(); }
1913
1914 /// Returns the maximum number of buckets of the %unordered_multimap.
1915 size_type
1916 max_bucket_count() const noexcept
1917 { return _M_h.max_bucket_count(); }
1918
1919 /*
1920 * @brief Returns the number of elements in a given bucket.
1921 * @param __n A bucket index.
1922 * @return The number of elements in the bucket.
1923 */
1924 size_type
1925 bucket_size(size_type __n) const
1926 { return _M_h.bucket_size(__n); }
1927
1928 /*
1929 * @brief Returns the bucket index of a given element.
1930 * @param __key A key instance.
1931 * @return The key bucket index.
1932 */
1933 size_type
1934 bucket(const key_type& __key) const
1935 { return _M_h.bucket(__key); }
1936
1937 /**
1938 * @brief Returns a read/write iterator pointing to the first bucket
1939 * element.
1940 * @param __n The bucket index.
1941 * @return A read/write local iterator.
1942 */
1943 local_iterator
1944 begin(size_type __n)
1945 { return _M_h.begin(__n); }
1946
1947 ///@{
1948 /**
1949 * @brief Returns a read-only (constant) iterator pointing to the first
1950 * bucket element.
1951 * @param __n The bucket index.
1952 * @return A read-only local iterator.
1953 */
1954 const_local_iterator
1955 begin(size_type __n) const
1956 { return _M_h.begin(__n); }
1957
1958 const_local_iterator
1959 cbegin(size_type __n) const
1960 { return _M_h.cbegin(__n); }
1961 ///@}
1962
1963 /**
1964 * @brief Returns a read/write iterator pointing to one past the last
1965 * bucket elements.
1966 * @param __n The bucket index.
1967 * @return A read/write local iterator.
1968 */
1969 local_iterator
1970 end(size_type __n)
1971 { return _M_h.end(__n); }
1972
1973 ///@{
1974 /**
1975 * @brief Returns a read-only (constant) iterator pointing to one past
1976 * the last bucket elements.
1977 * @param __n The bucket index.
1978 * @return A read-only local iterator.
1979 */
1980 const_local_iterator
1981 end(size_type __n) const
1982 { return _M_h.end(__n); }
1983
1984 const_local_iterator
1985 cend(size_type __n) const
1986 { return _M_h.cend(__n); }
1987 ///@}
1988
1989 // hash policy.
1990
1991 /// Returns the average number of elements per bucket.
1992 float
1993 load_factor() const noexcept
1994 { return _M_h.load_factor(); }
1995
1996 /// Returns a positive number that the %unordered_multimap tries to keep
1997 /// the load factor less than or equal to.
1998 float
1999 max_load_factor() const noexcept
2000 { return _M_h.max_load_factor(); }
2001
2002 /**
2003 * @brief Change the %unordered_multimap maximum load factor.
2004 * @param __z The new maximum load factor.
2005 */
2006 void
2007 max_load_factor(float __z)
2008 { _M_h.max_load_factor(__z); }
2009
2010 /**
2011 * @brief May rehash the %unordered_multimap.
2012 * @param __n The new number of buckets.
2013 *
2014 * Rehash will occur only if the new number of buckets respect the
2015 * %unordered_multimap maximum load factor.
2016 */
2017 void
2018 rehash(size_type __n)
2019 { _M_h.rehash(__n); }
2020
2021 /**
2022 * @brief Prepare the %unordered_multimap for a specified number of
2023 * elements.
2024 * @param __n Number of elements required.
2025 *
2026 * Same as rehash(ceil(n / max_load_factor())).
2027 */
2028 void
2029 reserve(size_type __n)
2030 { _M_h.reserve(__n); }
2031
2032 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
2033 typename _Alloc1>
2034 friend bool
2035 operator==(const unordered_multimap<_Key1, _Tp1,
2036 _Hash1, _Pred1, _Alloc1>&,
2037 const unordered_multimap<_Key1, _Tp1,
2038 _Hash1, _Pred1, _Alloc1>&);
2039 };
2040
2041#if __cpp_deduction_guides >= 201606
2042
2043 template<typename _InputIterator,
2044 typename _Hash = hash<__iter_key_t<_InputIterator>>,
2045 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
2046 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
2047 typename = _RequireInputIter<_InputIterator>,
2048 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2049 typename = _RequireNotAllocator<_Pred>,
2050 typename = _RequireAllocator<_Allocator>>
2051 unordered_multimap(_InputIterator, _InputIterator,
2052 unordered_multimap<int, int>::size_type = {},
2053 _Hash = _Hash(), _Pred = _Pred(),
2054 _Allocator = _Allocator())
2055 -> unordered_multimap<__iter_key_t<_InputIterator>,
2056 __iter_val_t<_InputIterator>, _Hash, _Pred,
2057 _Allocator>;
2058
2059 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
2060 typename _Pred = equal_to<_Key>,
2061 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2062 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2063 typename = _RequireNotAllocator<_Pred>,
2064 typename = _RequireAllocator<_Allocator>>
2065 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2066 unordered_multimap<int, int>::size_type = {},
2067 _Hash = _Hash(), _Pred = _Pred(),
2068 _Allocator = _Allocator())
2069 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2070
2071 template<typename _InputIterator, typename _Allocator,
2072 typename = _RequireInputIter<_InputIterator>,
2073 typename = _RequireAllocator<_Allocator>>
2074 unordered_multimap(_InputIterator, _InputIterator,
2075 unordered_multimap<int, int>::size_type, _Allocator)
2076 -> unordered_multimap<__iter_key_t<_InputIterator>,
2077 __iter_val_t<_InputIterator>,
2078 hash<__iter_key_t<_InputIterator>>,
2079 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2080
2081 template<typename _InputIterator, typename _Allocator,
2082 typename = _RequireInputIter<_InputIterator>,
2083 typename = _RequireAllocator<_Allocator>>
2084 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2085 -> unordered_multimap<__iter_key_t<_InputIterator>,
2086 __iter_val_t<_InputIterator>,
2087 hash<__iter_key_t<_InputIterator>>,
2088 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2089
2090 template<typename _InputIterator, typename _Hash, typename _Allocator,
2091 typename = _RequireInputIter<_InputIterator>,
2092 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2093 typename = _RequireAllocator<_Allocator>>
2094 unordered_multimap(_InputIterator, _InputIterator,
2095 unordered_multimap<int, int>::size_type, _Hash,
2096 _Allocator)
2097 -> unordered_multimap<__iter_key_t<_InputIterator>,
2098 __iter_val_t<_InputIterator>, _Hash,
2099 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2100
2101 template<typename _Key, typename _Tp, typename _Allocator,
2102 typename = _RequireAllocator<_Allocator>>
2103 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2104 unordered_multimap<int, int>::size_type,
2105 _Allocator)
2106 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2107
2108 template<typename _Key, typename _Tp, typename _Allocator,
2109 typename = _RequireAllocator<_Allocator>>
2110 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2111 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2112
2113 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
2114 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2115 typename = _RequireAllocator<_Allocator>>
2116 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2117 unordered_multimap<int, int>::size_type,
2118 _Hash, _Allocator)
2119 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2120
2121#endif
2122
2123 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2124 inline void
2125 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2126 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2127 noexcept(noexcept(__x.swap(__y)))
2128 { __x.swap(__y); }
2129
2130 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2131 inline void
2132 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2133 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2134 noexcept(noexcept(__x.swap(__y)))
2135 { __x.swap(__y); }
2136
2137 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2138 inline bool
2139 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2140 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2141 { return __x._M_h._M_equal(__y._M_h); }
2142
2143#if __cpp_impl_three_way_comparison < 201907L
2144 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2145 inline bool
2146 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2147 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2148 { return !(__x == __y); }
2149#endif
2150
2151 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2152 inline bool
2153 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2154 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2155 { return __x._M_h._M_equal(__y._M_h); }
2156
2157#if __cpp_impl_three_way_comparison < 201907L
2158 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2159 inline bool
2160 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2161 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2162 { return !(__x == __y); }
2163#endif
2164
2165_GLIBCXX_END_NAMESPACE_CONTAINER
2166
2167#if __cplusplus > 201402L
2168 // Allow std::unordered_map access to internals of compatible maps.
2169 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2170 typename _Alloc, typename _Hash2, typename _Eq2>
2171 struct _Hash_merge_helper<
2172 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2173 _Hash2, _Eq2>
2174 {
2175 private:
2176 template<typename... _Tp>
2177 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2178 template<typename... _Tp>
2179 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2180
2181 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2182
2183 static auto&
2184 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2185 { return __map._M_h; }
2186
2187 static auto&
2188 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2189 { return __map._M_h; }
2190 };
2191
2192 // Allow std::unordered_multimap access to internals of compatible maps.
2193 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2194 typename _Alloc, typename _Hash2, typename _Eq2>
2195 struct _Hash_merge_helper<
2196 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2197 _Hash2, _Eq2>
2198 {
2199 private:
2200 template<typename... _Tp>
2201 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2202 template<typename... _Tp>
2203 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2204
2205 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2206
2207 static auto&
2208 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2209 { return __map._M_h; }
2210
2211 static auto&
2212 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2213 { return __map._M_h; }
2214 };
2215#endif // C++17
2216
2217_GLIBCXX_END_NAMESPACE_VERSION
2218} // namespace std
2219
2220#endif /* _UNORDERED_MAP_H */
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
std
ISO C++ entities toplevel namespace is std.
std::__ummap_traits
__detail::_Hashtable_traits< _Cache, false, false > __ummap_traits
Base types for unordered_multimap.
Definition: unordered_map.h:62
std::__umap_traits
__detail::_Hashtable_traits< _Cache, false, true > __umap_traits
Base types for unordered_map.
Definition: unordered_map.h:45
std::initializer_list
initializer_list
Definition: initializer_list:46
std::hash
Primary class template hash.
Definition: functional_hash.h:103
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:131
std::equal_to
One of the comparison functors.
Definition: stl_function.h:374
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:189
std::iterator
Common iterator class.
Definition: stl_iterator_base_types.h:128
std::unordered_multimap
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
Definition: unordered_map.h:1251
std::unordered_multimap::load_factor
float load_factor() const noexcept
Returns the average number of elements per bucket.
Definition: unordered_map.h:1993
std::unordered_multimap::reference
_Hashtable::reference reference
Iterator-related typedefs.
Definition: unordered_map.h:1271
std::unordered_multimap::erase
iterator erase(iterator __position)
Erases an element from an unordered_multimap.
Definition: unordered_map.h:1691
std::unordered_multimap::end
const_iterator end() const noexcept
Definition: unordered_map.h:1503
std::unordered_multimap::erase
size_type erase(const key_type &__x)
Erases elements according to the provided key.
Definition: unordered_map.h:1707
std::unordered_multimap::equal_range
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
Definition: unordered_map.h:1883
std::unordered_multimap::bucket_count
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multimap.
Definition: unordered_map.h:1911
std::unordered_multimap::iterator
_Hashtable::iterator iterator
Iterator-related typedefs.
Definition: unordered_map.h:1273
std::unordered_multimap::max_bucket_count
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multimap.
Definition: unordered_map.h:1916
std::unordered_multimap::begin
iterator begin() noexcept
Definition: unordered_map.h:1472
std::unordered_multimap::begin
const_iterator begin() const noexcept
Definition: unordered_map.h:1481
std::unordered_multimap::hash_function
hasher hash_function() const
Returns the hash functor object with which the unordered_multimap was constructed.
Definition: unordered_map.h:1792
std::unordered_multimap::insert
iterator insert(const_iterator __hint, node_type &&__nh)
Re-insert an extracted node.
Definition: unordered_map.h:1667
std::unordered_multimap::insert
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(const_iterator __hint, _Pair &&__x)
Inserts a std::pair into the unordered_multimap.
Definition: unordered_map.h:1616
std::unordered_multimap::operator=
unordered_multimap & operator=(const unordered_multimap &)=default
Copy assignment operator.
std::unordered_multimap::key_eq
key_equal key_eq() const
Returns the key comparison object with which the unordered_multimap was constructed.
Definition: unordered_map.h:1798
std::unordered_multimap::count
size_type count(const key_type &__x) const
Finds the number of elements.
Definition: unordered_map.h:1845
std::unordered_multimap::find
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multimap.
Definition: unordered_map.h:1827
std::unordered_multimap::mapped_type
_Hashtable::mapped_type mapped_type
Public typedefs.
Definition: unordered_map.h:1261
std::unordered_multimap::find
auto find(const _Kt &__x) -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multimap.
Definition: unordered_map.h:1822
std::unordered_multimap::end
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
Definition: unordered_map.h:1970
std::unordered_multimap::insert
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
Definition: unordered_map.h:1631
std::unordered_multimap::operator=
unordered_multimap & operator=(initializer_list< value_type > __l)
Unordered_multimap list assignment operator.
Definition: unordered_map.h:1437
std::unordered_multimap::unordered_multimap
unordered_multimap(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
Definition: unordered_map.h:1298
std::unordered_multimap::value_type
_Hashtable::value_type value_type
Public typedefs.
Definition: unordered_map.h:1260
std::unordered_multimap::emplace
iterator emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
Definition: unordered_map.h:1530
std::unordered_multimap::extract
node_type extract(const key_type &__key)
Extract a node.
Definition: unordered_map.h:1657
std::unordered_multimap::contains
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
Definition: unordered_map.h:1864
std::unordered_multimap::const_reference
_Hashtable::const_reference const_reference
Iterator-related typedefs.
Definition: unordered_map.h:1272
std::unordered_multimap::insert
iterator insert(node_type &&__nh)
Re-insert an extracted node.
Definition: unordered_map.h:1662
std::unordered_multimap::erase
iterator erase(const_iterator __position)
Erases an element from an unordered_multimap.
Definition: unordered_map.h:1686
std::unordered_multimap::end
iterator end() noexcept
Definition: unordered_map.h:1494
std::unordered_multimap::begin
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
Definition: unordered_map.h:1944
std::unordered_multimap::max_load_factor
float max_load_factor() const noexcept
Returns a positive number that the unordered_multimap tries to keep the load factor less than or equa...
Definition: unordered_map.h:1999
std::unordered_multimap::unordered_multimap
unordered_multimap()=default
Default constructor.
std::unordered_multimap::insert
iterator insert(value_type &&__x)
Inserts a std::pair into the unordered_multimap.
Definition: unordered_map.h:1575
std::unordered_multimap::insert
iterator insert(const value_type &__x)
Inserts a std::pair into the unordered_multimap.
Definition: unordered_map.h:1571
std::unordered_multimap::operator=
unordered_multimap & operator=(unordered_multimap &&)=default
Move assignment operator.
std::unordered_multimap::hasher
_Hashtable::hasher hasher
Public typedefs.
Definition: unordered_map.h:1262
std::unordered_multimap::local_iterator
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
Definition: unordered_map.h:1275
std::unordered_multimap::reserve
void reserve(size_type __n)
Prepare the unordered_multimap for a specified number of elements.
Definition: unordered_map.h:2029
std::unordered_multimap::equal_range
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
Definition: unordered_map.h:1895
std::unordered_multimap::unordered_multimap
unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multimap from a range.
Definition: unordered_map.h:1319
std::unordered_multimap::find
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multimap.
Definition: unordered_map.h:1816
std::unordered_multimap::unordered_multimap
unordered_multimap(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multimap from an initializer_list.
Definition: unordered_map.h:1374
std::unordered_multimap::count
auto count(const _Kt &__x) const -> decltype(_M_h._M_count_tr(__x))
Finds the number of elements.
Definition: unordered_map.h:1851
std::unordered_multimap::erase
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multimap.
Definition: unordered_map.h:1726
std::unordered_multimap::end
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
Definition: unordered_map.h:1981
std::unordered_multimap::pointer
_Hashtable::pointer pointer
Iterator-related typedefs.
Definition: unordered_map.h:1269
std::unordered_multimap::allocator_type
_Hashtable::allocator_type allocator_type
Public typedefs.
Definition: unordered_map.h:1264
std::unordered_multimap::begin
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
Definition: unordered_map.h:1955
std::unordered_multimap::find
auto find(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multimap.
Definition: unordered_map.h:1833
std::unordered_multimap::const_local_iterator
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
Definition: unordered_map.h:1276
std::unordered_multimap::unordered_multimap
unordered_multimap(unordered_multimap &&)=default
Move constructor.
std::unordered_multimap::unordered_multimap
unordered_multimap(const allocator_type &__a)
Creates an unordered_multimap with no elements.
Definition: unordered_map.h:1338
std::unordered_multimap::difference_type
_Hashtable::difference_type difference_type
Iterator-related typedefs.
Definition: unordered_map.h:1278
std::unordered_multimap::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition: unordered_map.h:1277
std::unordered_multimap::const_pointer
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
Definition: unordered_map.h:1270
std::unordered_multimap::insert
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(_Pair &&__x)
Inserts a std::pair into the unordered_multimap.
Definition: unordered_map.h:1580
std::unordered_multimap::contains
auto contains(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x), void(), true)
Finds whether an element with the given key exists.
Definition: unordered_map.h:1869
std::unordered_multimap::swap
void swap(unordered_multimap &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_multimap.
Definition: unordered_map.h:1750
std::unordered_multimap::rehash
void rehash(size_type __n)
May rehash the unordered_multimap.
Definition: unordered_map.h:2018
std::unordered_multimap::const_iterator
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
Definition: unordered_map.h:1274
std::unordered_multimap::insert
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_multimap.
Definition: unordered_map.h:1643
std::unordered_multimap::cend
const_iterator cend() const noexcept
Definition: unordered_map.h:1507
std::unordered_multimap::max_size
size_type max_size() const noexcept
Returns the maximum size of the unordered_multimap.
Definition: unordered_map.h:1462
std::unordered_multimap::cbegin
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
Definition: unordered_map.h:1959
std::unordered_multimap::empty
bool empty() const noexcept
Returns true if the unordered_multimap is empty.
Definition: unordered_map.h:1452
std::unordered_multimap::cbegin
const_iterator cbegin() const noexcept
Definition: unordered_map.h:1485
std::unordered_multimap::key_type
_Hashtable::key_type key_type
Public typedefs.
Definition: unordered_map.h:1259
std::unordered_multimap::extract
node_type extract(const_iterator __pos)
Extract a node.
Definition: unordered_map.h:1649
std::unordered_multimap::cend
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
Definition: unordered_map.h:1985
std::unordered_multimap::insert
iterator insert(const_iterator __hint, const value_type &__x)
Inserts a std::pair into the unordered_multimap.
Definition: unordered_map.h:1605
std::unordered_multimap::size
size_type size() const noexcept
Returns the size of the unordered_multimap.
Definition: unordered_map.h:1457
std::unordered_multimap::unordered_multimap
unordered_multimap(const unordered_multimap &)=default
Copy constructor.
std::unordered_multimap::emplace_hint
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
Definition: unordered_map.h:1557
std::unordered_multimap::insert
iterator insert(const_iterator __hint, value_type &&__x)
Inserts a std::pair into the unordered_multimap.
Definition: unordered_map.h:1611
std::unordered_multimap::equal_range
auto equal_range(const _Kt &__x) -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
Definition: unordered_map.h:1889
std::unordered_multimap::key_equal
_Hashtable::key_equal key_equal
Public typedefs.
Definition: unordered_map.h:1263
std::unordered_multimap::get_allocator
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_multimap.
Definition: unordered_map.h:1445
std::unordered_multimap::max_load_factor
void max_load_factor(float __z)
Change the unordered_multimap maximum load factor.
Definition: unordered_map.h:2007
std::unordered_multimap::equal_range
auto equal_range(const _Kt &__x) const -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
Definition: unordered_map.h:1901
std::unordered_map
A standard container composed of unique keys (containing at most one of each key value) that associat...
Definition: unordered_map.h:108
std::unordered_map::insert
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert a std::pair into the unordered_map.
Definition: unordered_map.h:601
std::unordered_map::iterator
_Hashtable::iterator iterator
Iterator-related typedefs.
Definition: unordered_map.h:130
std::unordered_map::max_load_factor
void max_load_factor(float __z)
Change the unordered_map maximum load factor.
Definition: unordered_map.h:1109
std::unordered_map::at
const mapped_type & at(const key_type &__k) const
Access to unordered_map data.
Definition: unordered_map.h:1005
std::unordered_map::contains
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
Definition: unordered_map.h:925
std::unordered_map::extract
node_type extract(const key_type &__key)
Extract a node.
Definition: unordered_map.h:438
std::unordered_map::insert
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
Definition: unordered_map.h:621
std::unordered_map::get_allocator
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_map.
Definition: unordered_map.h:303
std::unordered_map::find
auto find(const _Kt &__x) -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_map.
Definition: unordered_map.h:879
std::unordered_map::operator=
unordered_map & operator=(initializer_list< value_type > __l)
Unordered_map list assignment operator.
Definition: unordered_map.h:295
std::unordered_map::const_pointer
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
Definition: unordered_map.h:127
std::unordered_map::find
auto find(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_map.
Definition: unordered_map.h:890
std::unordered_map::insert
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_map.
Definition: unordered_map.h:632
std::unordered_map::insert
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(const_iterator __hint, _Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
Definition: unordered_map.h:606
std::unordered_map::equal_range
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
Definition: unordered_map.h:946
std::unordered_map::at
mapped_type & at(const key_type &__k)
Access to unordered_map data.
Definition: unordered_map.h:1001
std::unordered_map::erase
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_map.
Definition: unordered_map.h:785
std::unordered_map::try_emplace
iterator try_emplace(const_iterator __hint, const key_type &__k, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
Definition: unordered_map.h:520
std::unordered_map::extract
node_type extract(const_iterator __pos)
Extract a node.
Definition: unordered_map.h:430
std::unordered_map::insert
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
Definition: unordered_map.h:556
std::unordered_map::reserve
void reserve(size_type __n)
Prepare the unordered_map for a specified number of elements.
Definition: unordered_map.h:1131
std::unordered_map::cbegin
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
Definition: unordered_map.h:1061
std::unordered_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
Definition: unordered_map.h:958
std::unordered_map::insert
iterator insert(const_iterator, node_type &&__nh)
Re-insert an extracted node.
Definition: unordered_map.h:448
std::unordered_map::reference
_Hashtable::reference reference
Iterator-related typedefs.
Definition: unordered_map.h:128
std::unordered_map::insert
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
Definition: unordered_map.h:595
std::unordered_map::end
iterator end() noexcept
Definition: unordered_map.h:352
std::unordered_map::allocator_type
_Hashtable::allocator_type allocator_type
Public typedefs.
Definition: unordered_map.h:121
std::unordered_map::unordered_map
unordered_map(const unordered_map &)=default
Copy constructor.
std::unordered_map::count
size_type count(const key_type &__x) const
Finds the number of elements.
Definition: unordered_map.h:906
std::unordered_map::empty
bool empty() const noexcept
Returns true if the unordered_map is empty.
Definition: unordered_map.h:310
std::unordered_map::erase
size_type erase(const key_type &__x)
Erases elements according to the provided key.
Definition: unordered_map.h:767
std::unordered_map::find
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_map.
Definition: unordered_map.h:884
std::unordered_map::unordered_map
unordered_map(unordered_map &&)=default
Move constructor.
std::unordered_map::end
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
Definition: unordered_map.h:1083
std::unordered_map::equal_range
auto equal_range(const _Kt &__x) -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
Definition: unordered_map.h:952
std::unordered_map::contains
auto contains(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x), void(), true)
Finds whether an element with the given key exists.
Definition: unordered_map.h:930
std::unordered_map::max_size
size_type max_size() const noexcept
Returns the maximum size of the unordered_map.
Definition: unordered_map.h:320
std::unordered_map::end
const_iterator end() const noexcept
Definition: unordered_map.h:361
std::unordered_map::unordered_map
unordered_map()=default
Default constructor.
std::unordered_map::mapped_type
_Hashtable::mapped_type mapped_type
Public typedefs.
Definition: unordered_map.h:118
std::unordered_map::operator=
unordered_map & operator=(unordered_map &&)=default
Move assignment operator.
std::unordered_map::begin
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
Definition: unordered_map.h:1057
std::unordered_map::unordered_map
unordered_map(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
Definition: unordered_map.h:156
std::unordered_map::emplace
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
Definition: unordered_map.h:393
std::unordered_map::cend
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
Definition: unordered_map.h:1087
std::unordered_map::size
size_type size() const noexcept
Returns the size of the unordered_map.
Definition: unordered_map.h:315
std::unordered_map::insert
__enable_if_t< is_constructible< value_type, _Pair && >::value, pair< iterator, bool > > insert(_Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
Definition: unordered_map.h:568
std::unordered_map::operator[]
mapped_type & operator[](key_type &&__k)
Subscript ( [] ) access to unordered_map data.
Definition: unordered_map.h:988
std::unordered_map::insert
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert a std::pair into the unordered_map.
Definition: unordered_map.h:562
std::unordered_map::hasher
_Hashtable::hasher hasher
Public typedefs.
Definition: unordered_map.h:119
std::unordered_map::insert_or_assign
pair< iterator, bool > insert_or_assign(const key_type &__k, _Obj &&__obj)
Attempts to insert a std::pair into the unordered_map.
Definition: unordered_map.h:659
std::unordered_map::unordered_map
unordered_map(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_map from a range.
Definition: unordered_map.h:177
std::unordered_map::clear
void clear() noexcept
Definition: unordered_map.h:795
std::unordered_map::operator[]
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to unordered_map data.
Definition: unordered_map.h:984
std::unordered_map::try_emplace
pair< iterator, bool > try_emplace(const key_type &__k, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
Definition: unordered_map.h:476
std::unordered_map::begin
const_iterator begin() const noexcept
Definition: unordered_map.h:339
std::unordered_map::key_eq
key_equal key_eq() const
Returns the key comparison object with which the unordered_map was constructed.
Definition: unordered_map.h:855
std::unordered_map::const_reference
_Hashtable::const_reference const_reference
Iterator-related typedefs.
Definition: unordered_map.h:129
std::unordered_map::key_equal
_Hashtable::key_equal key_equal
Public typedefs.
Definition: unordered_map.h:120
std::unordered_map::local_iterator
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
Definition: unordered_map.h:132
std::unordered_map::erase
iterator erase(iterator __position)
Erases an element from an unordered_map.
Definition: unordered_map.h:750
std::unordered_map::cend
const_iterator cend() const noexcept
Definition: unordered_map.h:365
std::unordered_map::end
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
Definition: unordered_map.h:1072
std::unordered_map::pointer
_Hashtable::pointer pointer
Iterator-related typedefs.
Definition: unordered_map.h:126
std::unordered_map::insert_or_assign
iterator insert_or_assign(const_iterator __hint, const key_type &__k, _Obj &&__obj)
Attempts to insert a std::pair into the unordered_map.
Definition: unordered_map.h:708
std::unordered_map::unordered_map
unordered_map(const allocator_type &__a)
Creates an unordered_map with no elements.
Definition: unordered_map.h:196
std::unordered_map::key_type
_Hashtable::key_type key_type
Public typedefs.
Definition: unordered_map.h:116
std::unordered_map::bucket_count
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_map.
Definition: unordered_map.h:1013
std::unordered_map::begin
iterator begin() noexcept
Definition: unordered_map.h:330
std::unordered_map::hash_function
hasher hash_function() const
Returns the hash functor object with which the unordered_map was constructed.
Definition: unordered_map.h:849
std::unordered_map::equal_range
auto equal_range(const _Kt &__x) const -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
Definition: unordered_map.h:964
std::unordered_map::unordered_map
unordered_map(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_map from an initializer_list.
Definition: unordered_map.h:232
std::unordered_map::const_iterator
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
Definition: unordered_map.h:131
std::unordered_map::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition: unordered_map.h:134
std::unordered_map::find
iterator find(const key_type &__x)
Tries to locate an element in an unordered_map.
Definition: unordered_map.h:873
std::unordered_map::load_factor
float load_factor() const noexcept
Returns the average number of elements per bucket.
Definition: unordered_map.h:1095
std::unordered_map::erase
iterator erase(const_iterator __position)
Erases an element from an unordered_map.
Definition: unordered_map.h:745
std::unordered_map::swap
void swap(unordered_map &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_map.
Definition: unordered_map.h:809
std::unordered_map::begin
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
Definition: unordered_map.h:1046
std::unordered_map::max_load_factor
float max_load_factor() const noexcept
Returns a positive number that the unordered_map tries to keep the load factor less than or equal to.
Definition: unordered_map.h:1101
std::unordered_map::operator=
unordered_map & operator=(const unordered_map &)=default
Copy assignment operator.
std::unordered_map::difference_type
_Hashtable::difference_type difference_type
Iterator-related typedefs.
Definition: unordered_map.h:135
std::unordered_map::count
auto count(const _Kt &__x) const -> decltype(_M_h._M_count_tr(__x))
Finds the number of elements.
Definition: unordered_map.h:912
std::unordered_map::const_local_iterator
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
Definition: unordered_map.h:133
std::unordered_map::max_bucket_count
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_map.
Definition: unordered_map.h:1018
std::unordered_map::emplace_hint
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
Definition: unordered_map.h:424
std::unordered_map::insert
insert_return_type insert(node_type &&__nh)
Re-insert an extracted node.
Definition: unordered_map.h:443
std::unordered_map::value_type
_Hashtable::value_type value_type
Public typedefs.
Definition: unordered_map.h:117
std::unordered_map::rehash
void rehash(size_type __n)
May rehash the unordered_map.
Definition: unordered_map.h:1120
std::unordered_map::cbegin
const_iterator cbegin() const noexcept
Definition: unordered_map.h:343