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