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