libstdc++
unordered_map.h
Go to the documentation of this file.
1 // unordered_map implementation -*- C++ -*-
2 
3 // Copyright (C) 2010-2015 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>
40 
41  template<typename _Key,
42  typename _Tp,
43  typename _Hash = hash<_Key>,
44  typename _Pred = std::equal_to<_Key>,
48  _Alloc, __detail::_Select1st,
49  _Pred, _Hash,
53 
54  /// Base types for unordered_multimap.
55  template<bool _Cache>
57 
58  template<typename _Key,
59  typename _Tp,
60  typename _Hash = hash<_Key>,
61  typename _Pred = std::equal_to<_Key>,
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  /**
72  * @brief A standard container composed of unique keys (containing
73  * at most one of each key value) that associates values of another type
74  * with the keys.
75  *
76  * @ingroup unordered_associative_containers
77  *
78  * @tparam _Key Type of key objects.
79  * @tparam _Tp Type of mapped objects.
80  * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
81  * @tparam _Pred Predicate function object type, defaults
82  * to equal_to<_Value>.
83  * @tparam _Alloc Allocator type, defaults to
84  * std::allocator<std::pair<const _Key, _Tp>>.
85  *
86  * Meets the requirements of a <a href="tables.html#65">container</a>, and
87  * <a href="tables.html#xx">unordered associative container</a>
88  *
89  * The resulting value type of the container is std::pair<const _Key, _Tp>.
90  *
91  * Base is _Hashtable, dispatched at compile time via template
92  * alias __umap_hashtable.
93  */
94  template<class _Key, class _Tp,
95  class _Hash = hash<_Key>,
96  class _Pred = std::equal_to<_Key>,
99  {
101  _Hashtable _M_h;
102 
103  public:
104  // typedefs:
105  //@{
106  /// Public typedefs.
107  typedef typename _Hashtable::key_type key_type;
108  typedef typename _Hashtable::value_type value_type;
109  typedef typename _Hashtable::mapped_type mapped_type;
110  typedef typename _Hashtable::hasher hasher;
111  typedef typename _Hashtable::key_equal key_equal;
112  typedef typename _Hashtable::allocator_type allocator_type;
113  //@}
114 
115  //@{
116  /// Iterator-related typedefs.
117  typedef typename _Hashtable::pointer pointer;
118  typedef typename _Hashtable::const_pointer const_pointer;
119  typedef typename _Hashtable::reference reference;
120  typedef typename _Hashtable::const_reference const_reference;
121  typedef typename _Hashtable::iterator iterator;
122  typedef typename _Hashtable::const_iterator const_iterator;
123  typedef typename _Hashtable::local_iterator local_iterator;
124  typedef typename _Hashtable::const_local_iterator const_local_iterator;
125  typedef typename _Hashtable::size_type size_type;
126  typedef typename _Hashtable::difference_type difference_type;
127  //@}
128 
129  //construct/destroy/copy
130 
131  /// Default constructor.
132  unordered_map() = default;
133 
134  /**
135  * @brief Default constructor creates no elements.
136  * @param __n Minimal initial number of buckets.
137  * @param __hf A hash functor.
138  * @param __eql A key equality functor.
139  * @param __a An allocator object.
140  */
141  explicit
142  unordered_map(size_type __n,
143  const hasher& __hf = hasher(),
144  const key_equal& __eql = key_equal(),
145  const allocator_type& __a = allocator_type())
146  : _M_h(__n, __hf, __eql, __a)
147  { }
148 
149  /**
150  * @brief Builds an %unordered_map from a range.
151  * @param __first An input iterator.
152  * @param __last An input iterator.
153  * @param __n Minimal initial number of buckets.
154  * @param __hf A hash functor.
155  * @param __eql A key equality functor.
156  * @param __a An allocator object.
157  *
158  * Create an %unordered_map consisting of copies of the elements from
159  * [__first,__last). This is linear in N (where N is
160  * distance(__first,__last)).
161  */
162  template<typename _InputIterator>
163  unordered_map(_InputIterator __first, _InputIterator __last,
164  size_type __n = 0,
165  const hasher& __hf = hasher(),
166  const key_equal& __eql = key_equal(),
167  const allocator_type& __a = allocator_type())
168  : _M_h(__first, __last, __n, __hf, __eql, __a)
169  { }
170 
171  /// Copy constructor.
172  unordered_map(const unordered_map&) = default;
173 
174  /// Move constructor.
175  unordered_map(unordered_map&&) = default;
176 
177  /**
178  * @brief Creates an %unordered_map with no elements.
179  * @param __a An allocator object.
180  */
181  explicit
182  unordered_map(const allocator_type& __a)
183  : _M_h(__a)
184  { }
185 
186  /*
187  * @brief Copy constructor with allocator argument.
188  * @param __uset Input %unordered_map to copy.
189  * @param __a An allocator object.
190  */
191  unordered_map(const unordered_map& __umap,
192  const allocator_type& __a)
193  : _M_h(__umap._M_h, __a)
194  { }
195 
196  /*
197  * @brief Move constructor with allocator argument.
198  * @param __uset Input %unordered_map to move.
199  * @param __a An allocator object.
200  */
201  unordered_map(unordered_map&& __umap,
202  const allocator_type& __a)
203  : _M_h(std::move(__umap._M_h), __a)
204  { }
205 
206  /**
207  * @brief Builds an %unordered_map from an initializer_list.
208  * @param __l An initializer_list.
209  * @param __n Minimal initial number of buckets.
210  * @param __hf A hash functor.
211  * @param __eql A key equality functor.
212  * @param __a An allocator object.
213  *
214  * Create an %unordered_map consisting of copies of the elements in the
215  * list. This is linear in N (where N is @a __l.size()).
216  */
217  unordered_map(initializer_list<value_type> __l,
218  size_type __n = 0,
219  const hasher& __hf = hasher(),
220  const key_equal& __eql = key_equal(),
221  const allocator_type& __a = allocator_type())
222  : _M_h(__l, __n, __hf, __eql, __a)
223  { }
224 
225  /// Copy assignment operator.
227  operator=(const unordered_map&) = default;
228 
229  /// Move assignment operator.
231  operator=(unordered_map&&) = default;
232 
233  /**
234  * @brief %Unordered_map list assignment operator.
235  * @param __l An initializer_list.
236  *
237  * This function fills an %unordered_map with copies of the elements in
238  * the initializer list @a __l.
239  *
240  * Note that the assignment completely changes the %unordered_map and
241  * that the resulting %unordered_map's size is the same as the number
242  * of elements assigned. Old data may be lost.
243  */
245  operator=(initializer_list<value_type> __l)
246  {
247  _M_h = __l;
248  return *this;
249  }
250 
251  /// Returns the allocator object with which the %unordered_map was
252  /// constructed.
253  allocator_type
254  get_allocator() const noexcept
255  { return _M_h.get_allocator(); }
256 
257  // size and capacity:
258 
259  /// Returns true if the %unordered_map is empty.
260  bool
261  empty() const noexcept
262  { return _M_h.empty(); }
263 
264  /// Returns the size of the %unordered_map.
265  size_type
266  size() const noexcept
267  { return _M_h.size(); }
268 
269  /// Returns the maximum size of the %unordered_map.
270  size_type
271  max_size() const noexcept
272  { return _M_h.max_size(); }
273 
274  // iterators.
275 
276  /**
277  * Returns a read/write iterator that points to the first element in the
278  * %unordered_map.
279  */
280  iterator
281  begin() noexcept
282  { return _M_h.begin(); }
283 
284  //@{
285  /**
286  * Returns a read-only (constant) iterator that points to the first
287  * element in the %unordered_map.
288  */
289  const_iterator
290  begin() const noexcept
291  { return _M_h.begin(); }
292 
293  const_iterator
294  cbegin() const noexcept
295  { return _M_h.begin(); }
296  //@}
297 
298  /**
299  * Returns a read/write iterator that points one past the last element in
300  * the %unordered_map.
301  */
302  iterator
303  end() noexcept
304  { return _M_h.end(); }
305 
306  //@{
307  /**
308  * Returns a read-only (constant) iterator that points one past the last
309  * element in the %unordered_map.
310  */
311  const_iterator
312  end() const noexcept
313  { return _M_h.end(); }
314 
315  const_iterator
316  cend() const noexcept
317  { return _M_h.end(); }
318  //@}
319 
320  // modifiers.
321 
322  /**
323  * @brief Attempts to build and insert a std::pair into the %unordered_map.
324  *
325  * @param __args Arguments used to generate a new pair instance (see
326  * std::piecewise_contruct for passing arguments to each
327  * part of the pair constructor).
328  *
329  * @return A pair, of which the first element is an iterator that points
330  * to the possibly inserted pair, and the second is a bool that
331  * is true if the pair was actually inserted.
332  *
333  * This function attempts to build and insert a (key, value) %pair into
334  * the %unordered_map.
335  * An %unordered_map relies on unique keys and thus a %pair is only
336  * inserted if its first element (the key) is not already present in the
337  * %unordered_map.
338  *
339  * Insertion requires amortized constant time.
340  */
341  template<typename... _Args>
343  emplace(_Args&&... __args)
344  { return _M_h.emplace(std::forward<_Args>(__args)...); }
345 
346  /**
347  * @brief Attempts to build and insert a std::pair into the %unordered_map.
348  *
349  * @param __pos An iterator that serves as a hint as to where the pair
350  * should be inserted.
351  * @param __args Arguments used to generate a new pair instance (see
352  * std::piecewise_contruct for passing arguments to each
353  * part of the pair constructor).
354  * @return An iterator that points to the element with key of the
355  * std::pair built from @a __args (may or may not be that
356  * std::pair).
357  *
358  * This function is not concerned about whether the insertion took place,
359  * and thus does not return a boolean like the single-argument emplace()
360  * does.
361  * Note that the first parameter is only a hint and can potentially
362  * improve the performance of the insertion process. A bad hint would
363  * cause no gains in efficiency.
364  *
365  * See
366  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
367  * for more on @a hinting.
368  *
369  * Insertion requires amortized constant time.
370  */
371  template<typename... _Args>
372  iterator
373  emplace_hint(const_iterator __pos, _Args&&... __args)
374  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
375 
376  //@{
377  /**
378  * @brief Attempts to insert a std::pair into the %unordered_map.
379 
380  * @param __x Pair to be inserted (see std::make_pair for easy
381  * creation of pairs).
382  *
383  * @return A pair, of which the first element is an iterator that
384  * points to the possibly inserted pair, and the second is
385  * a bool that is true if the pair was actually inserted.
386  *
387  * This function attempts to insert a (key, value) %pair into the
388  * %unordered_map. An %unordered_map relies on unique keys and thus a
389  * %pair is only inserted if its first element (the key) is not already
390  * present in the %unordered_map.
391  *
392  * Insertion requires amortized constant time.
393  */
395  insert(const value_type& __x)
396  { return _M_h.insert(__x); }
397 
398  template<typename _Pair, typename = typename
399  std::enable_if<std::is_constructible<value_type,
400  _Pair&&>::value>::type>
402  insert(_Pair&& __x)
403  { return _M_h.insert(std::forward<_Pair>(__x)); }
404  //@}
405 
406  //@{
407  /**
408  * @brief Attempts to insert a std::pair into the %unordered_map.
409  * @param __hint An iterator that serves as a hint as to where the
410  * pair should be inserted.
411  * @param __x Pair to be inserted (see std::make_pair for easy creation
412  * of pairs).
413  * @return An iterator that points to the element with key of
414  * @a __x (may or may not be the %pair passed in).
415  *
416  * This function is not concerned about whether the insertion took place,
417  * and thus does not return a boolean like the single-argument insert()
418  * does. Note that the first parameter is only a hint and can
419  * potentially improve the performance of the insertion process. A bad
420  * hint would cause no gains in efficiency.
421  *
422  * See
423  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
424  * for more on @a hinting.
425  *
426  * Insertion requires amortized constant time.
427  */
428  iterator
429  insert(const_iterator __hint, const value_type& __x)
430  { return _M_h.insert(__hint, __x); }
431 
432  template<typename _Pair, typename = typename
433  std::enable_if<std::is_constructible<value_type,
434  _Pair&&>::value>::type>
435  iterator
436  insert(const_iterator __hint, _Pair&& __x)
437  { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
438  //@}
439 
440  /**
441  * @brief A template function that attempts to insert a range of
442  * elements.
443  * @param __first Iterator pointing to the start of the range to be
444  * inserted.
445  * @param __last Iterator pointing to the end of the range.
446  *
447  * Complexity similar to that of the range constructor.
448  */
449  template<typename _InputIterator>
450  void
451  insert(_InputIterator __first, _InputIterator __last)
452  { _M_h.insert(__first, __last); }
453 
454  /**
455  * @brief Attempts to insert a list of elements into the %unordered_map.
456  * @param __l A std::initializer_list<value_type> of elements
457  * to be inserted.
458  *
459  * Complexity similar to that of the range constructor.
460  */
461  void
462  insert(initializer_list<value_type> __l)
463  { _M_h.insert(__l); }
464 
465  //@{
466  /**
467  * @brief Erases an element from an %unordered_map.
468  * @param __position An iterator pointing to the element to be erased.
469  * @return An iterator pointing to the element immediately following
470  * @a __position prior to the element being erased. If no such
471  * element exists, end() is returned.
472  *
473  * This function erases an element, pointed to by the given iterator,
474  * from an %unordered_map.
475  * Note that this function only erases the element, and that if the
476  * element is itself a pointer, the pointed-to memory is not touched in
477  * any way. Managing the pointer is the user's responsibility.
478  */
479  iterator
480  erase(const_iterator __position)
481  { return _M_h.erase(__position); }
482 
483  // LWG 2059.
484  iterator
485  erase(iterator __position)
486  { return _M_h.erase(__position); }
487  //@}
488 
489  /**
490  * @brief Erases elements according to the provided key.
491  * @param __x Key of element to be erased.
492  * @return The number of elements erased.
493  *
494  * This function erases all the elements located by the given key from
495  * an %unordered_map. For an %unordered_map the result of this function
496  * can only be 0 (not present) or 1 (present).
497  * Note that this function only erases the element, and that if the
498  * element is itself a pointer, the pointed-to memory is not touched in
499  * any way. Managing the pointer is the user's responsibility.
500  */
501  size_type
502  erase(const key_type& __x)
503  { return _M_h.erase(__x); }
504 
505  /**
506  * @brief Erases a [__first,__last) range of elements from an
507  * %unordered_map.
508  * @param __first Iterator pointing to the start of the range to be
509  * erased.
510  * @param __last Iterator pointing to the end of the range to
511  * be erased.
512  * @return The iterator @a __last.
513  *
514  * This function erases a sequence of elements from an %unordered_map.
515  * Note that this function only erases the elements, and that if
516  * the element is itself a pointer, the pointed-to memory is not touched
517  * in any way. Managing the pointer is the user's responsibility.
518  */
519  iterator
520  erase(const_iterator __first, const_iterator __last)
521  { return _M_h.erase(__first, __last); }
522 
523  /**
524  * Erases all elements in an %unordered_map.
525  * Note that this function only erases the elements, and that if the
526  * elements themselves are pointers, the pointed-to memory is not touched
527  * in any way. Managing the pointer is the user's responsibility.
528  */
529  void
530  clear() noexcept
531  { _M_h.clear(); }
532 
533  /**
534  * @brief Swaps data with another %unordered_map.
535  * @param __x An %unordered_map of the same element and allocator
536  * types.
537  *
538  * This exchanges the elements between two %unordered_map in constant time.
539  * Note that the global std::swap() function is specialized such that
540  * std::swap(m1,m2) will feed to this function.
541  */
542  void
544  noexcept( noexcept(_M_h.swap(__x._M_h)) )
545  { _M_h.swap(__x._M_h); }
546 
547  // observers.
548 
549  /// Returns the hash functor object with which the %unordered_map was
550  /// constructed.
551  hasher
553  { return _M_h.hash_function(); }
554 
555  /// Returns the key comparison object with which the %unordered_map was
556  /// constructed.
557  key_equal
558  key_eq() const
559  { return _M_h.key_eq(); }
560 
561  // lookup.
562 
563  //@{
564  /**
565  * @brief Tries to locate an element in an %unordered_map.
566  * @param __x Key to be located.
567  * @return Iterator pointing to sought-after element, or end() if not
568  * found.
569  *
570  * This function takes a key and tries to locate the element with which
571  * the key matches. If successful the function returns an iterator
572  * pointing to the sought after element. If unsuccessful it returns the
573  * past-the-end ( @c end() ) iterator.
574  */
575  iterator
576  find(const key_type& __x)
577  { return _M_h.find(__x); }
578 
579  const_iterator
580  find(const key_type& __x) const
581  { return _M_h.find(__x); }
582  //@}
583 
584  /**
585  * @brief Finds the number of elements.
586  * @param __x Key to count.
587  * @return Number of elements with specified key.
588  *
589  * This function only makes sense for %unordered_multimap; for
590  * %unordered_map the result will either be 0 (not present) or 1
591  * (present).
592  */
593  size_type
594  count(const key_type& __x) const
595  { return _M_h.count(__x); }
596 
597  //@{
598  /**
599  * @brief Finds a subsequence matching given key.
600  * @param __x Key to be located.
601  * @return Pair of iterators that possibly points to the subsequence
602  * matching given key.
603  *
604  * This function probably only makes sense for %unordered_multimap.
605  */
607  equal_range(const key_type& __x)
608  { return _M_h.equal_range(__x); }
609 
611  equal_range(const key_type& __x) const
612  { return _M_h.equal_range(__x); }
613  //@}
614 
615  //@{
616  /**
617  * @brief Subscript ( @c [] ) access to %unordered_map data.
618  * @param __k The key for which data should be retrieved.
619  * @return A reference to the data of the (key,data) %pair.
620  *
621  * Allows for easy lookup with the subscript ( @c [] )operator. Returns
622  * data associated with the key specified in subscript. If the key does
623  * not exist, a pair with that key is created using default values, which
624  * is then returned.
625  *
626  * Lookup requires constant time.
627  */
628  mapped_type&
629  operator[](const key_type& __k)
630  { return _M_h[__k]; }
631 
632  mapped_type&
633  operator[](key_type&& __k)
634  { return _M_h[std::move(__k)]; }
635  //@}
636 
637  //@{
638  /**
639  * @brief Access to %unordered_map data.
640  * @param __k The key for which data should be retrieved.
641  * @return A reference to the data whose key is equal to @a __k, if
642  * such a data is present in the %unordered_map.
643  * @throw std::out_of_range If no such data is present.
644  */
645  mapped_type&
646  at(const key_type& __k)
647  { return _M_h.at(__k); }
648 
649  const mapped_type&
650  at(const key_type& __k) const
651  { return _M_h.at(__k); }
652  //@}
653 
654  // bucket interface.
655 
656  /// Returns the number of buckets of the %unordered_map.
657  size_type
658  bucket_count() const noexcept
659  { return _M_h.bucket_count(); }
660 
661  /// Returns the maximum number of buckets of the %unordered_map.
662  size_type
663  max_bucket_count() const noexcept
664  { return _M_h.max_bucket_count(); }
665 
666  /*
667  * @brief Returns the number of elements in a given bucket.
668  * @param __n A bucket index.
669  * @return The number of elements in the bucket.
670  */
671  size_type
672  bucket_size(size_type __n) const
673  { return _M_h.bucket_size(__n); }
674 
675  /*
676  * @brief Returns the bucket index of a given element.
677  * @param __key A key instance.
678  * @return The key bucket index.
679  */
680  size_type
681  bucket(const key_type& __key) const
682  { return _M_h.bucket(__key); }
683 
684  /**
685  * @brief Returns a read/write iterator pointing to the first bucket
686  * element.
687  * @param __n The bucket index.
688  * @return A read/write local iterator.
689  */
690  local_iterator
691  begin(size_type __n)
692  { return _M_h.begin(__n); }
693 
694  //@{
695  /**
696  * @brief Returns a read-only (constant) iterator pointing to the first
697  * bucket element.
698  * @param __n The bucket index.
699  * @return A read-only local iterator.
700  */
701  const_local_iterator
702  begin(size_type __n) const
703  { return _M_h.begin(__n); }
704 
705  const_local_iterator
706  cbegin(size_type __n) const
707  { return _M_h.cbegin(__n); }
708  //@}
709 
710  /**
711  * @brief Returns a read/write iterator pointing to one past the last
712  * bucket elements.
713  * @param __n The bucket index.
714  * @return A read/write local iterator.
715  */
716  local_iterator
717  end(size_type __n)
718  { return _M_h.end(__n); }
719 
720  //@{
721  /**
722  * @brief Returns a read-only (constant) iterator pointing to one past
723  * the last bucket elements.
724  * @param __n The bucket index.
725  * @return A read-only local iterator.
726  */
727  const_local_iterator
728  end(size_type __n) const
729  { return _M_h.end(__n); }
730 
731  const_local_iterator
732  cend(size_type __n) const
733  { return _M_h.cend(__n); }
734  //@}
735 
736  // hash policy.
737 
738  /// Returns the average number of elements per bucket.
739  float
740  load_factor() const noexcept
741  { return _M_h.load_factor(); }
742 
743  /// Returns a positive number that the %unordered_map tries to keep the
744  /// load factor less than or equal to.
745  float
746  max_load_factor() const noexcept
747  { return _M_h.max_load_factor(); }
748 
749  /**
750  * @brief Change the %unordered_map maximum load factor.
751  * @param __z The new maximum load factor.
752  */
753  void
754  max_load_factor(float __z)
755  { _M_h.max_load_factor(__z); }
756 
757  /**
758  * @brief May rehash the %unordered_map.
759  * @param __n The new number of buckets.
760  *
761  * Rehash will occur only if the new number of buckets respect the
762  * %unordered_map maximum load factor.
763  */
764  void
765  rehash(size_type __n)
766  { _M_h.rehash(__n); }
767 
768  /**
769  * @brief Prepare the %unordered_map for a specified number of
770  * elements.
771  * @param __n Number of elements required.
772  *
773  * Same as rehash(ceil(n / max_load_factor())).
774  */
775  void
776  reserve(size_type __n)
777  { _M_h.reserve(__n); }
778 
779  template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
780  typename _Alloc1>
781  friend bool
784  };
785 
786  /**
787  * @brief A standard container composed of equivalent keys
788  * (possibly containing multiple of each key value) that associates
789  * values of another type with the keys.
790  *
791  * @ingroup unordered_associative_containers
792  *
793  * @tparam _Key Type of key objects.
794  * @tparam _Tp Type of mapped objects.
795  * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
796  * @tparam _Pred Predicate function object type, defaults
797  * to equal_to<_Value>.
798  * @tparam _Alloc Allocator type, defaults to
799  * std::allocator<std::pair<const _Key, _Tp>>.
800  *
801  * Meets the requirements of a <a href="tables.html#65">container</a>, and
802  * <a href="tables.html#xx">unordered associative container</a>
803  *
804  * The resulting value type of the container is std::pair<const _Key, _Tp>.
805  *
806  * Base is _Hashtable, dispatched at compile time via template
807  * alias __ummap_hashtable.
808  */
809  template<class _Key, class _Tp,
810  class _Hash = hash<_Key>,
811  class _Pred = std::equal_to<_Key>,
814  {
816  _Hashtable _M_h;
817 
818  public:
819  // typedefs:
820  //@{
821  /// Public typedefs.
822  typedef typename _Hashtable::key_type key_type;
823  typedef typename _Hashtable::value_type value_type;
824  typedef typename _Hashtable::mapped_type mapped_type;
825  typedef typename _Hashtable::hasher hasher;
826  typedef typename _Hashtable::key_equal key_equal;
827  typedef typename _Hashtable::allocator_type allocator_type;
828  //@}
829 
830  //@{
831  /// Iterator-related typedefs.
832  typedef typename _Hashtable::pointer pointer;
833  typedef typename _Hashtable::const_pointer const_pointer;
834  typedef typename _Hashtable::reference reference;
835  typedef typename _Hashtable::const_reference const_reference;
836  typedef typename _Hashtable::iterator iterator;
837  typedef typename _Hashtable::const_iterator const_iterator;
838  typedef typename _Hashtable::local_iterator local_iterator;
839  typedef typename _Hashtable::const_local_iterator const_local_iterator;
840  typedef typename _Hashtable::size_type size_type;
841  typedef typename _Hashtable::difference_type difference_type;
842  //@}
843 
844  //construct/destroy/copy
845 
846  /// Default constructor.
847  unordered_multimap() = default;
848 
849  /**
850  * @brief Default constructor creates no elements.
851  * @param __n Mnimal initial number of buckets.
852  * @param __hf A hash functor.
853  * @param __eql A key equality functor.
854  * @param __a An allocator object.
855  */
856  explicit
857  unordered_multimap(size_type __n,
858  const hasher& __hf = hasher(),
859  const key_equal& __eql = key_equal(),
860  const allocator_type& __a = allocator_type())
861  : _M_h(__n, __hf, __eql, __a)
862  { }
863 
864  /**
865  * @brief Builds an %unordered_multimap from a range.
866  * @param __first An input iterator.
867  * @param __last An input iterator.
868  * @param __n Minimal initial number of buckets.
869  * @param __hf A hash functor.
870  * @param __eql A key equality functor.
871  * @param __a An allocator object.
872  *
873  * Create an %unordered_multimap consisting of copies of the elements
874  * from [__first,__last). This is linear in N (where N is
875  * distance(__first,__last)).
876  */
877  template<typename _InputIterator>
878  unordered_multimap(_InputIterator __first, _InputIterator __last,
879  size_type __n = 0,
880  const hasher& __hf = hasher(),
881  const key_equal& __eql = key_equal(),
882  const allocator_type& __a = allocator_type())
883  : _M_h(__first, __last, __n, __hf, __eql, __a)
884  { }
885 
886  /// Copy constructor.
887  unordered_multimap(const unordered_multimap&) = default;
888 
889  /// Move constructor.
891 
892  /**
893  * @brief Creates an %unordered_multimap with no elements.
894  * @param __a An allocator object.
895  */
896  explicit
897  unordered_multimap(const allocator_type& __a)
898  : _M_h(__a)
899  { }
900 
901  /*
902  * @brief Copy constructor with allocator argument.
903  * @param __uset Input %unordered_multimap to copy.
904  * @param __a An allocator object.
905  */
906  unordered_multimap(const unordered_multimap& __ummap,
907  const allocator_type& __a)
908  : _M_h(__ummap._M_h, __a)
909  { }
910 
911  /*
912  * @brief Move constructor with allocator argument.
913  * @param __uset Input %unordered_multimap to move.
914  * @param __a An allocator object.
915  */
917  const allocator_type& __a)
918  : _M_h(std::move(__ummap._M_h), __a)
919  { }
920 
921  /**
922  * @brief Builds an %unordered_multimap from an initializer_list.
923  * @param __l An initializer_list.
924  * @param __n Minimal initial number of buckets.
925  * @param __hf A hash functor.
926  * @param __eql A key equality functor.
927  * @param __a An allocator object.
928  *
929  * Create an %unordered_multimap consisting of copies of the elements in
930  * the list. This is linear in N (where N is @a __l.size()).
931  */
932  unordered_multimap(initializer_list<value_type> __l,
933  size_type __n = 0,
934  const hasher& __hf = hasher(),
935  const key_equal& __eql = key_equal(),
936  const allocator_type& __a = allocator_type())
937  : _M_h(__l, __n, __hf, __eql, __a)
938  { }
939 
940  /// Copy assignment operator.
942  operator=(const unordered_multimap&) = default;
943 
944  /// Move assignment operator.
946  operator=(unordered_multimap&&) = default;
947 
948  /**
949  * @brief %Unordered_multimap list assignment operator.
950  * @param __l An initializer_list.
951  *
952  * This function fills an %unordered_multimap with copies of the elements
953  * in the initializer list @a __l.
954  *
955  * Note that the assignment completely changes the %unordered_multimap
956  * and that the resulting %unordered_multimap's size is the same as the
957  * number of elements assigned. Old data may be lost.
958  */
960  operator=(initializer_list<value_type> __l)
961  {
962  _M_h = __l;
963  return *this;
964  }
965 
966  /// Returns the allocator object with which the %unordered_multimap was
967  /// constructed.
968  allocator_type
969  get_allocator() const noexcept
970  { return _M_h.get_allocator(); }
971 
972  // size and capacity:
973 
974  /// Returns true if the %unordered_multimap is empty.
975  bool
976  empty() const noexcept
977  { return _M_h.empty(); }
978 
979  /// Returns the size of the %unordered_multimap.
980  size_type
981  size() const noexcept
982  { return _M_h.size(); }
983 
984  /// Returns the maximum size of the %unordered_multimap.
985  size_type
986  max_size() const noexcept
987  { return _M_h.max_size(); }
988 
989  // iterators.
990 
991  /**
992  * Returns a read/write iterator that points to the first element in the
993  * %unordered_multimap.
994  */
995  iterator
996  begin() noexcept
997  { return _M_h.begin(); }
998 
999  //@{
1000  /**
1001  * Returns a read-only (constant) iterator that points to the first
1002  * element in the %unordered_multimap.
1003  */
1004  const_iterator
1005  begin() const noexcept
1006  { return _M_h.begin(); }
1007 
1008  const_iterator
1009  cbegin() const noexcept
1010  { return _M_h.begin(); }
1011  //@}
1012 
1013  /**
1014  * Returns a read/write iterator that points one past the last element in
1015  * the %unordered_multimap.
1016  */
1017  iterator
1018  end() noexcept
1019  { return _M_h.end(); }
1020 
1021  //@{
1022  /**
1023  * Returns a read-only (constant) iterator that points one past the last
1024  * element in the %unordered_multimap.
1025  */
1026  const_iterator
1027  end() const noexcept
1028  { return _M_h.end(); }
1029 
1030  const_iterator
1031  cend() const noexcept
1032  { return _M_h.end(); }
1033  //@}
1034 
1035  // modifiers.
1036 
1037  /**
1038  * @brief Attempts to build and insert a std::pair into the
1039  * %unordered_multimap.
1040  *
1041  * @param __args Arguments used to generate a new pair instance (see
1042  * std::piecewise_contruct for passing arguments to each
1043  * part of the pair constructor).
1044  *
1045  * @return An iterator that points to the inserted pair.
1046  *
1047  * This function attempts to build and insert a (key, value) %pair into
1048  * the %unordered_multimap.
1049  *
1050  * Insertion requires amortized constant time.
1051  */
1052  template<typename... _Args>
1053  iterator
1054  emplace(_Args&&... __args)
1055  { return _M_h.emplace(std::forward<_Args>(__args)...); }
1056 
1057  /**
1058  * @brief Attempts to build and insert a std::pair into the %unordered_multimap.
1059  *
1060  * @param __pos An iterator that serves as a hint as to where the pair
1061  * should be inserted.
1062  * @param __args Arguments used to generate a new pair instance (see
1063  * std::piecewise_contruct for passing arguments to each
1064  * part of the pair constructor).
1065  * @return An iterator that points to the element with key of the
1066  * std::pair built from @a __args.
1067  *
1068  * Note that the first parameter is only a hint and can potentially
1069  * improve the performance of the insertion process. A bad hint would
1070  * cause no gains in efficiency.
1071  *
1072  * See
1073  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1074  * for more on @a hinting.
1075  *
1076  * Insertion requires amortized constant time.
1077  */
1078  template<typename... _Args>
1079  iterator
1080  emplace_hint(const_iterator __pos, _Args&&... __args)
1081  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1082 
1083  //@{
1084  /**
1085  * @brief Inserts a std::pair into the %unordered_multimap.
1086  * @param __x Pair to be inserted (see std::make_pair for easy
1087  * creation of pairs).
1088  *
1089  * @return An iterator that points to the inserted pair.
1090  *
1091  * Insertion requires amortized constant time.
1092  */
1093  iterator
1094  insert(const value_type& __x)
1095  { return _M_h.insert(__x); }
1096 
1097  template<typename _Pair, typename = typename
1098  std::enable_if<std::is_constructible<value_type,
1099  _Pair&&>::value>::type>
1100  iterator
1101  insert(_Pair&& __x)
1102  { return _M_h.insert(std::forward<_Pair>(__x)); }
1103  //@}
1104 
1105  //@{
1106  /**
1107  * @brief Inserts a std::pair into the %unordered_multimap.
1108  * @param __hint An iterator that serves as a hint as to where the
1109  * pair should be inserted.
1110  * @param __x Pair to be inserted (see std::make_pair for easy creation
1111  * of pairs).
1112  * @return An iterator that points to the element with key of
1113  * @a __x (may or may not be the %pair passed in).
1114  *
1115  * Note that the first parameter is only a hint and can potentially
1116  * improve the performance of the insertion process. A bad hint would
1117  * cause no gains in efficiency.
1118  *
1119  * See
1120  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1121  * for more on @a hinting.
1122  *
1123  * Insertion requires amortized constant time.
1124  */
1125  iterator
1126  insert(const_iterator __hint, const value_type& __x)
1127  { return _M_h.insert(__hint, __x); }
1128 
1129  template<typename _Pair, typename = typename
1130  std::enable_if<std::is_constructible<value_type,
1131  _Pair&&>::value>::type>
1132  iterator
1133  insert(const_iterator __hint, _Pair&& __x)
1134  { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
1135  //@}
1136 
1137  /**
1138  * @brief A template function that attempts to insert a range of
1139  * elements.
1140  * @param __first Iterator pointing to the start of the range to be
1141  * inserted.
1142  * @param __last Iterator pointing to the end of the range.
1143  *
1144  * Complexity similar to that of the range constructor.
1145  */
1146  template<typename _InputIterator>
1147  void
1148  insert(_InputIterator __first, _InputIterator __last)
1149  { _M_h.insert(__first, __last); }
1150 
1151  /**
1152  * @brief Attempts to insert a list of elements into the
1153  * %unordered_multimap.
1154  * @param __l A std::initializer_list<value_type> of elements
1155  * to be inserted.
1156  *
1157  * Complexity similar to that of the range constructor.
1158  */
1159  void
1160  insert(initializer_list<value_type> __l)
1161  { _M_h.insert(__l); }
1162 
1163  //@{
1164  /**
1165  * @brief Erases an element from an %unordered_multimap.
1166  * @param __position An iterator pointing to the element to be erased.
1167  * @return An iterator pointing to the element immediately following
1168  * @a __position prior to the element being erased. If no such
1169  * element exists, end() is returned.
1170  *
1171  * This function erases an element, pointed to by the given iterator,
1172  * from an %unordered_multimap.
1173  * Note that this function only erases the element, and that if the
1174  * element is itself a pointer, the pointed-to memory is not touched in
1175  * any way. Managing the pointer is the user's responsibility.
1176  */
1177  iterator
1178  erase(const_iterator __position)
1179  { return _M_h.erase(__position); }
1180 
1181  // LWG 2059.
1182  iterator
1183  erase(iterator __position)
1184  { return _M_h.erase(__position); }
1185  //@}
1186 
1187  /**
1188  * @brief Erases elements according to the provided key.
1189  * @param __x Key of elements to be erased.
1190  * @return The number of elements erased.
1191  *
1192  * This function erases all the elements located by the given key from
1193  * an %unordered_multimap.
1194  * Note that this function only erases the element, and that if the
1195  * element is itself a pointer, the pointed-to memory is not touched in
1196  * any way. Managing the pointer is the user's responsibility.
1197  */
1198  size_type
1199  erase(const key_type& __x)
1200  { return _M_h.erase(__x); }
1201 
1202  /**
1203  * @brief Erases a [__first,__last) range of elements from an
1204  * %unordered_multimap.
1205  * @param __first Iterator pointing to the start of the range to be
1206  * erased.
1207  * @param __last Iterator pointing to the end of the range to
1208  * be erased.
1209  * @return The iterator @a __last.
1210  *
1211  * This function erases a sequence of elements from an
1212  * %unordered_multimap.
1213  * Note that this function only erases the elements, and that if
1214  * the element is itself a pointer, the pointed-to memory is not touched
1215  * in any way. Managing the pointer is the user's responsibility.
1216  */
1217  iterator
1218  erase(const_iterator __first, const_iterator __last)
1219  { return _M_h.erase(__first, __last); }
1220 
1221  /**
1222  * Erases all elements in an %unordered_multimap.
1223  * Note that this function only erases the elements, and that if the
1224  * elements themselves are pointers, the pointed-to memory is not touched
1225  * in any way. Managing the pointer is the user's responsibility.
1226  */
1227  void
1228  clear() noexcept
1229  { _M_h.clear(); }
1230 
1231  /**
1232  * @brief Swaps data with another %unordered_multimap.
1233  * @param __x An %unordered_multimap of the same element and allocator
1234  * types.
1235  *
1236  * This exchanges the elements between two %unordered_multimap in
1237  * constant time.
1238  * Note that the global std::swap() function is specialized such that
1239  * std::swap(m1,m2) will feed to this function.
1240  */
1241  void
1243  noexcept( noexcept(_M_h.swap(__x._M_h)) )
1244  { _M_h.swap(__x._M_h); }
1245 
1246  // observers.
1247 
1248  /// Returns the hash functor object with which the %unordered_multimap
1249  /// was constructed.
1250  hasher
1252  { return _M_h.hash_function(); }
1253 
1254  /// Returns the key comparison object with which the %unordered_multimap
1255  /// was constructed.
1256  key_equal
1257  key_eq() const
1258  { return _M_h.key_eq(); }
1259 
1260  // lookup.
1261 
1262  //@{
1263  /**
1264  * @brief Tries to locate an element in an %unordered_multimap.
1265  * @param __x Key to be located.
1266  * @return Iterator pointing to sought-after element, or end() if not
1267  * found.
1268  *
1269  * This function takes a key and tries to locate the element with which
1270  * the key matches. If successful the function returns an iterator
1271  * pointing to the sought after element. If unsuccessful it returns the
1272  * past-the-end ( @c end() ) iterator.
1273  */
1274  iterator
1275  find(const key_type& __x)
1276  { return _M_h.find(__x); }
1277 
1278  const_iterator
1279  find(const key_type& __x) const
1280  { return _M_h.find(__x); }
1281  //@}
1282 
1283  /**
1284  * @brief Finds the number of elements.
1285  * @param __x Key to count.
1286  * @return Number of elements with specified key.
1287  */
1288  size_type
1289  count(const key_type& __x) const
1290  { return _M_h.count(__x); }
1291 
1292  //@{
1293  /**
1294  * @brief Finds a subsequence matching given key.
1295  * @param __x Key to be located.
1296  * @return Pair of iterators that possibly points to the subsequence
1297  * matching given key.
1298  */
1300  equal_range(const key_type& __x)
1301  { return _M_h.equal_range(__x); }
1302 
1304  equal_range(const key_type& __x) const
1305  { return _M_h.equal_range(__x); }
1306  //@}
1307 
1308  // bucket interface.
1309 
1310  /// Returns the number of buckets of the %unordered_multimap.
1311  size_type
1312  bucket_count() const noexcept
1313  { return _M_h.bucket_count(); }
1314 
1315  /// Returns the maximum number of buckets of the %unordered_multimap.
1316  size_type
1317  max_bucket_count() const noexcept
1318  { return _M_h.max_bucket_count(); }
1319 
1320  /*
1321  * @brief Returns the number of elements in a given bucket.
1322  * @param __n A bucket index.
1323  * @return The number of elements in the bucket.
1324  */
1325  size_type
1326  bucket_size(size_type __n) const
1327  { return _M_h.bucket_size(__n); }
1328 
1329  /*
1330  * @brief Returns the bucket index of a given element.
1331  * @param __key A key instance.
1332  * @return The key bucket index.
1333  */
1334  size_type
1335  bucket(const key_type& __key) const
1336  { return _M_h.bucket(__key); }
1337 
1338  /**
1339  * @brief Returns a read/write iterator pointing to the first bucket
1340  * element.
1341  * @param __n The bucket index.
1342  * @return A read/write local iterator.
1343  */
1344  local_iterator
1345  begin(size_type __n)
1346  { return _M_h.begin(__n); }
1347 
1348  //@{
1349  /**
1350  * @brief Returns a read-only (constant) iterator pointing to the first
1351  * bucket element.
1352  * @param __n The bucket index.
1353  * @return A read-only local iterator.
1354  */
1355  const_local_iterator
1356  begin(size_type __n) const
1357  { return _M_h.begin(__n); }
1358 
1359  const_local_iterator
1360  cbegin(size_type __n) const
1361  { return _M_h.cbegin(__n); }
1362  //@}
1363 
1364  /**
1365  * @brief Returns a read/write iterator pointing to one past the last
1366  * bucket elements.
1367  * @param __n The bucket index.
1368  * @return A read/write local iterator.
1369  */
1370  local_iterator
1371  end(size_type __n)
1372  { return _M_h.end(__n); }
1373 
1374  //@{
1375  /**
1376  * @brief Returns a read-only (constant) iterator pointing to one past
1377  * the last bucket elements.
1378  * @param __n The bucket index.
1379  * @return A read-only local iterator.
1380  */
1381  const_local_iterator
1382  end(size_type __n) const
1383  { return _M_h.end(__n); }
1384 
1385  const_local_iterator
1386  cend(size_type __n) const
1387  { return _M_h.cend(__n); }
1388  //@}
1389 
1390  // hash policy.
1391 
1392  /// Returns the average number of elements per bucket.
1393  float
1394  load_factor() const noexcept
1395  { return _M_h.load_factor(); }
1396 
1397  /// Returns a positive number that the %unordered_multimap tries to keep
1398  /// the load factor less than or equal to.
1399  float
1400  max_load_factor() const noexcept
1401  { return _M_h.max_load_factor(); }
1402 
1403  /**
1404  * @brief Change the %unordered_multimap maximum load factor.
1405  * @param __z The new maximum load factor.
1406  */
1407  void
1408  max_load_factor(float __z)
1409  { _M_h.max_load_factor(__z); }
1410 
1411  /**
1412  * @brief May rehash the %unordered_multimap.
1413  * @param __n The new number of buckets.
1414  *
1415  * Rehash will occur only if the new number of buckets respect the
1416  * %unordered_multimap maximum load factor.
1417  */
1418  void
1419  rehash(size_type __n)
1420  { _M_h.rehash(__n); }
1421 
1422  /**
1423  * @brief Prepare the %unordered_multimap for a specified number of
1424  * elements.
1425  * @param __n Number of elements required.
1426  *
1427  * Same as rehash(ceil(n / max_load_factor())).
1428  */
1429  void
1430  reserve(size_type __n)
1431  { _M_h.reserve(__n); }
1432 
1433  template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1434  typename _Alloc1>
1435  friend bool
1436  operator==(const unordered_multimap<_Key1, _Tp1,
1437  _Hash1, _Pred1, _Alloc1>&,
1438  const unordered_multimap<_Key1, _Tp1,
1439  _Hash1, _Pred1, _Alloc1>&);
1440  };
1441 
1442  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1443  inline void
1444  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1445  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1446  { __x.swap(__y); }
1447 
1448  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1449  inline void
1450  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1451  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1452  { __x.swap(__y); }
1453 
1454  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1455  inline bool
1456  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1457  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1458  { return __x._M_h._M_equal(__y._M_h); }
1459 
1460  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1461  inline bool
1462  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1463  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1464  { return !(__x == __y); }
1465 
1466  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1467  inline bool
1468  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1469  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1470  { return __x._M_h._M_equal(__y._M_h); }
1471 
1472  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1473  inline bool
1474  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1475  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1476  { return !(__x == __y); }
1477 
1478 _GLIBCXX_END_NAMESPACE_CONTAINER
1479 } // namespace std
1480 
1481 #endif /* _UNORDERED_MAP_H */
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:176
_Hashtable::key_type key_type
Public typedefs.
size_type max_size() const noexcept
Returns the maximum size of the unordered_multimap.
float load_factor() const noexcept
Returns the average number of elements per bucket.
hasher hash_function() const
Returns the hash functor object with which the unordered_multimap was constructed.
unordered_multimap & operator=(const unordered_multimap &)=default
Copy assignment operator.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
void max_load_factor(float __z)
Change the unordered_map maximum load factor.
unordered_multimap(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multimap from an initializer_list.
size_type size() const noexcept
Returns the size of the unordered_map.
unordered_multimap(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_map.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
A standard container composed of unique keys (containing at most one of each key value) that associat...
Definition: unordered_map.h:98
_Hashtable::iterator iterator
Iterator-related typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multimap.
void swap(unordered_multimap &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_multimap.
_Hashtable::hasher hasher
Public typedefs.
_Hashtable::pointer pointer
Iterator-related typedefs.
void clear() noexcept
const_iterator begin() const noexcept
_Hashtable::reference reference
Iterator-related typedefs.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_map()=default
Default constructor.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_map(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_map from an initializer_list.
const_iterator begin() const noexcept
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::allocator_type allocator_type
Public typedefs.
iterator insert(const_iterator __hint, _Pair &&__x)
Inserts a std::pair into the unordered_multimap.
iterator begin() noexcept
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_map.
const_iterator end() const noexcept
float max_load_factor() const noexcept
Returns a positive number that the unordered_multimap tries to keep the load factor less than or equa...
size_type count(const key_type &__x) const
Finds the number of elements.
void rehash(size_type __n)
May rehash the unordered_map.
const_iterator cend() const noexcept
size_type erase(const key_type &__x)
Erases elements according to the provided key.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multimap.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
void max_load_factor(float __z)
Change the unordered_multimap maximum load factor.
_Hashtable::value_type value_type
Public typedefs.
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
_Hashtable::pointer pointer
Iterator-related typedefs.
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
unordered_map(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
float max_load_factor() const noexcept
Returns a positive number that the unordered_map tries to keep the load factor less than or equal to...
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multimap.
unordered_multimap()=default
Default constructor.
_Hashtable::size_type size_type
Iterator-related typedefs.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
iterator insert(const_iterator __hint, const value_type &__x)
Inserts a std::pair into the unordered_multimap.
key_equal key_eq() const
Returns the key comparison object with which the unordered_map was constructed.
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
void swap(unordered_map &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_map.
iterator emplace(_Args &&...__args)
Attempts to build and insert a std::pair into the unordered_multimap.
Primary class template hash.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
allocator_type get_allocator() const noexcept
Returns the allocator object with which the unordered_map was constructed.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
iterator end() noexcept
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_map.
const_iterator cbegin() const noexcept
std::pair< iterator, bool > emplace(_Args &&...__args)
Attempts to build and insert a std::pair into the unordered_map.
size_type size() const noexcept
Returns the size of the unordered_multimap.
_Hashtable::allocator_type allocator_type
Public typedefs.
_Hashtable::key_equal key_equal
Public typedefs.
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to unordered_map data.
iterator end() noexcept
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
void rehash(size_type __n)
May rehash the unordered_multimap.
iterator insert(_Pair &&__x)
Inserts a std::pair into the unordered_multimap.
unordered_map & operator=(initializer_list< value_type > __l)
Unordered_map list assignment operator.
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
size_type count(const key_type &__x) const
Finds the number of elements.
_Hashtable::value_type value_type
Public typedefs.
iterator insert(const value_type &__x)
Inserts a std::pair into the unordered_multimap.
mapped_type & operator[](key_type &&__k)
Subscript ( [] ) access to unordered_map data.
const_iterator end() const noexcept
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
unordered_multimap(const allocator_type &__a)
Creates an unordered_multimap with no elements.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_multimap.
_Hashtable::mapped_type mapped_type
Public typedefs.
const_iterator cbegin() const noexcept
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_map.
The standard allocator, as per [20.4].
Definition: allocator.h:92
Default range hashing function: use division to fold a large number into the range [0...
iterator insert(const_iterator __hint, _Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
void reserve(size_type __n)
Prepare the unordered_multimap for a specified number of elements.
iterator erase(const_iterator __position)
Erases an element from an unordered_map.
_Hashtable::size_type size_type
Iterator-related typedefs.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
unordered_map(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_map from a range.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_map.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
_Hashtable::hasher hasher
Public typedefs.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
_Hashtable::reference reference
Iterator-related typedefs.
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
iterator begin() noexcept
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
bool empty() const noexcept
Returns true if the unordered_map is empty.
const_iterator cend() const noexcept
One of the comparison functors.
Definition: stl_function.h:352
_Hashtable::mapped_type mapped_type
Public typedefs.
iterator erase(iterator __position)
Erases an element from an unordered_map.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Attempts to build and insert a std::pair into the unordered_map.
_Hashtable::key_equal key_equal
Public typedefs.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
bool empty() const noexcept
Returns true if the unordered_multimap is empty.
unordered_map(const allocator_type &__a)
Creates an unordered_map with no elements.
iterator erase(iterator __position)
Erases an element from an unordered_multimap.
_Hashtable::key_type key_type
Public typedefs.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
hasher hash_function() const
Returns the hash functor object with which the unordered_map was constructed.
unordered_map & operator=(const unordered_map &)=default
Copy assignment operator.
std::pair< iterator, bool > insert(_Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
const mapped_type & at(const key_type &__k) const
Access to unordered_map data.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multimap was constructed.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_map.
float load_factor() const noexcept
Returns the average number of elements per bucket.
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Attempts to build and insert a std::pair into the unordered_multimap.
unordered_multimap & operator=(initializer_list< value_type > __l)
Unordered_multimap list assignment operator.
iterator erase(const_iterator __position)
Erases an element from an unordered_multimap.
size_type max_size() const noexcept
Returns the maximum size of the unordered_map.
allocator_type get_allocator() const noexcept
Returns the allocator object with which the unordered_multimap was constructed.
unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multimap from a range.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multimap.
void reserve(size_type __n)
Prepare the unordered_map for a specified number of elements.
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
ISO C++ entities toplevel namespace is std.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
Default ranged hash function H. In principle it should be a function object composed from objects of ...
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multimap.
_Hashtable::iterator iterator
Iterator-related typedefs.
mapped_type & at(const key_type &__k)
Access to unordered_map data.