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