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