STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
unordered_map.h
Go to the documentation of this file.
1 // unordered_map implementation -*- C++ -*-
2 
3 // Copyright (C) 2010-2013 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 
30 #ifndef _UNORDERED_MAP_H
31 #define _UNORDERED_MAP_H
32 
33 namespace std _GLIBCXX_VISIBILITY(default)
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
36 
38  template<bool _Cache>
39  using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
40 
41  template<typename _Key,
42  typename _Tp,
43  typename _Hash = hash<_Key>,
44  typename _Pred = std::equal_to<_Key>,
45  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
46  typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
47  using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
48  _Alloc, __detail::_Select1st,
49  _Pred, _Hash,
50  __detail::_Mod_range_hashing,
51  __detail::_Default_ranged_hash,
52  __detail::_Prime_rehash_policy, _Tr>;
53 
55  template<bool _Cache>
56  using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
57 
58  template<typename _Key,
59  typename _Tp,
60  typename _Hash = hash<_Key>,
61  typename _Pred = std::equal_to<_Key>,
62  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
63  typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
64  using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
65  _Alloc, __detail::_Select1st,
66  _Pred, _Hash,
67  __detail::_Mod_range_hashing,
68  __detail::_Default_ranged_hash,
69  __detail::_Prime_rehash_policy, _Tr>;
70 
93  template<class _Key, class _Tp,
94  class _Hash = hash<_Key>,
95  class _Pred = std::equal_to<_Key>,
96  class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
97  class unordered_map : __check_copy_constructible<_Alloc>
98  {
99  typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
100  _Hashtable _M_h;
101 
102  public:
103  // typedefs:
105  typedef typename _Hashtable::key_type key_type;
107  typedef typename _Hashtable::value_type value_type;
108  typedef typename _Hashtable::mapped_type mapped_type;
109  typedef typename _Hashtable::hasher hasher;
110  typedef typename _Hashtable::key_equal key_equal;
111  typedef typename _Hashtable::allocator_type allocator_type;
113 
115  typedef typename allocator_type::pointer pointer;
117  typedef typename allocator_type::const_pointer const_pointer;
118  typedef typename allocator_type::reference reference;
119  typedef typename allocator_type::const_reference const_reference;
120  typedef typename _Hashtable::iterator iterator;
121  typedef typename _Hashtable::const_iterator const_iterator;
122  typedef typename _Hashtable::local_iterator local_iterator;
123  typedef typename _Hashtable::const_local_iterator const_local_iterator;
124  typedef typename _Hashtable::size_type size_type;
125  typedef typename _Hashtable::difference_type difference_type;
127 
128  //construct/destroy/copy
129 
137  explicit
138  unordered_map(size_type __n = 10,
139  const hasher& __hf = hasher(),
140  const key_equal& __eql = key_equal(),
141  const allocator_type& __a = allocator_type())
142  : _M_h(__n, __hf, __eql, __a)
143  { }
144 
158  template<typename _InputIterator>
159  unordered_map(_InputIterator __f, _InputIterator __l,
160  size_type __n = 0,
161  const hasher& __hf = hasher(),
162  const key_equal& __eql = key_equal(),
163  const allocator_type& __a = allocator_type())
164  : _M_h(__f, __l, __n, __hf, __eql, __a)
165  { }
166 
168  unordered_map(const unordered_map&) = default;
169 
171  unordered_map(unordered_map&&) = default;
172 
184  unordered_map(initializer_list<value_type> __l,
185  size_type __n = 0,
186  const hasher& __hf = hasher(),
187  const key_equal& __eql = key_equal(),
188  const allocator_type& __a = allocator_type())
189  : _M_h(__l, __n, __hf, __eql, __a)
190  { }
191 
193  unordered_map&
194  operator=(const unordered_map&) = default;
195 
197  unordered_map&
198  operator=(unordered_map&&) = default;
199 
211  unordered_map&
212  operator=(initializer_list<value_type> __l)
213  {
214  _M_h = __l;
215  return *this;
216  }
217 
220  allocator_type
221  get_allocator() const noexcept
222  { return _M_h.get_allocator(); }
223 
224  // size and capacity:
225 
227  bool
228  empty() const noexcept
229  { return _M_h.empty(); }
230 
232  size_type
233  size() const noexcept
234  { return _M_h.size(); }
235 
237  size_type
238  max_size() const noexcept
239  { return _M_h.max_size(); }
240 
241  // iterators.
242 
247  iterator
248  begin() noexcept
249  { return _M_h.begin(); }
250 
252 
256  const_iterator
257  begin() const noexcept
258  { return _M_h.begin(); }
259 
260  const_iterator
261  cbegin() const noexcept
262  { return _M_h.begin(); }
264 
269  iterator
270  end() noexcept
271  { return _M_h.end(); }
272 
274 
278  const_iterator
279  end() const noexcept
280  { return _M_h.end(); }
281 
282  const_iterator
283  cend() const noexcept
284  { return _M_h.end(); }
286 
287  // modifiers.
288 
308  template<typename... _Args>
309  std::pair<iterator, bool>
310  emplace(_Args&&... __args)
311  { return _M_h.emplace(std::forward<_Args>(__args)...); }
312 
338  template<typename... _Args>
339  iterator
340  emplace_hint(const_iterator __pos, _Args&&... __args)
341  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
342 
344 
361  std::pair<iterator, bool>
362  insert(const value_type& __x)
363  { return _M_h.insert(__x); }
364 
365  template<typename _Pair, typename = typename
366  std::enable_if<std::is_constructible<value_type,
367  _Pair&&>::value>::type>
368  std::pair<iterator, bool>
369  insert(_Pair&& __x)
370  { return _M_h.insert(std::forward<_Pair>(__x)); }
372 
374 
395  iterator
396  insert(const_iterator __hint, const value_type& __x)
397  { return _M_h.insert(__hint, __x); }
398 
399  template<typename _Pair, typename = typename
400  std::enable_if<std::is_constructible<value_type,
401  _Pair&&>::value>::type>
402  iterator
403  insert(const_iterator __hint, _Pair&& __x)
404  { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
406 
416  template<typename _InputIterator>
417  void
418  insert(_InputIterator __first, _InputIterator __last)
419  { _M_h.insert(__first, __last); }
420 
428  void
429  insert(initializer_list<value_type> __l)
430  { _M_h.insert(__l); }
431 
433 
446  iterator
447  erase(const_iterator __position)
448  { return _M_h.erase(__position); }
449 
450  // LWG 2059.
451  iterator
452  erase(iterator __it)
453  { return _M_h.erase(__it); }
455 
468  size_type
469  erase(const key_type& __x)
470  { return _M_h.erase(__x); }
471 
486  iterator
487  erase(const_iterator __first, const_iterator __last)
488  { return _M_h.erase(__first, __last); }
489 
496  void
497  clear() noexcept
498  { _M_h.clear(); }
499 
509  void
510  swap(unordered_map& __x)
511  { _M_h.swap(__x._M_h); }
512 
513  // observers.
514 
517  hasher
518  hash_function() const
519  { return _M_h.hash_function(); }
520 
523  key_equal
524  key_eq() const
525  { return _M_h.key_eq(); }
526 
527  // lookup.
528 
530 
541  iterator
542  find(const key_type& __x)
543  { return _M_h.find(__x); }
544 
545  const_iterator
546  find(const key_type& __x) const
547  { return _M_h.find(__x); }
549 
559  size_type
560  count(const key_type& __x) const
561  { return _M_h.count(__x); }
562 
564 
572  std::pair<iterator, iterator>
573  equal_range(const key_type& __x)
574  { return _M_h.equal_range(__x); }
575 
576  std::pair<const_iterator, const_iterator>
577  equal_range(const key_type& __x) const
578  { return _M_h.equal_range(__x); }
580 
582 
594  mapped_type&
595  operator[](const key_type& __k)
596  { return _M_h[__k]; }
597 
598  mapped_type&
599  operator[](key_type&& __k)
600  { return _M_h[std::move(__k)]; }
602 
604 
611  mapped_type&
612  at(const key_type& __k)
613  { return _M_h.at(__k); }
614 
615  const mapped_type&
616  at(const key_type& __k) const
617  { return _M_h.at(__k); }
619 
620  // bucket interface.
621 
623  size_type
624  bucket_count() const noexcept
625  { return _M_h.bucket_count(); }
626 
628  size_type
629  max_bucket_count() const noexcept
630  { return _M_h.max_bucket_count(); }
631 
632  /*
633  * @brief Returns the number of elements in a given bucket.
634  * @param __n A bucket index.
635  * @return The number of elements in the bucket.
636  */
637  size_type
638  bucket_size(size_type __n) const
639  { return _M_h.bucket_size(__n); }
640 
641  /*
642  * @brief Returns the bucket index of a given element.
643  * @param __key A key instance.
644  * @return The key bucket index.
645  */
646  size_type
647  bucket(const key_type& __key) const
648  { return _M_h.bucket(__key); }
649 
656  local_iterator
657  begin(size_type __n)
658  { return _M_h.begin(__n); }
659 
661 
667  const_local_iterator
668  begin(size_type __n) const
669  { return _M_h.begin(__n); }
670 
671  const_local_iterator
672  cbegin(size_type __n) const
673  { return _M_h.cbegin(__n); }
675 
682  local_iterator
683  end(size_type __n)
684  { return _M_h.end(__n); }
685 
687 
693  const_local_iterator
694  end(size_type __n) const
695  { return _M_h.end(__n); }
696 
697  const_local_iterator
698  cend(size_type __n) const
699  { return _M_h.cend(__n); }
701 
702  // hash policy.
703 
705  float
706  load_factor() const noexcept
707  { return _M_h.load_factor(); }
708 
711  float
712  max_load_factor() const noexcept
713  { return _M_h.max_load_factor(); }
714 
719  void
720  max_load_factor(float __z)
721  { _M_h.max_load_factor(__z); }
722 
730  void
731  rehash(size_type __n)
732  { _M_h.rehash(__n); }
733 
741  void
742  reserve(size_type __n)
743  { _M_h.reserve(__n); }
744 
745  template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
746  typename _Alloc1>
747  friend bool
748  operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
749  const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
750  };
751 
774  template<class _Key, class _Tp,
775  class _Hash = hash<_Key>,
776  class _Pred = std::equal_to<_Key>,
777  class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
778  class unordered_multimap : __check_copy_constructible<_Alloc>
779  {
780  typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
781  _Hashtable _M_h;
782 
783  public:
784  // typedefs:
786  typedef typename _Hashtable::key_type key_type;
788  typedef typename _Hashtable::value_type value_type;
789  typedef typename _Hashtable::mapped_type mapped_type;
790  typedef typename _Hashtable::hasher hasher;
791  typedef typename _Hashtable::key_equal key_equal;
792  typedef typename _Hashtable::allocator_type allocator_type;
794 
796  typedef typename allocator_type::pointer pointer;
798  typedef typename allocator_type::const_pointer const_pointer;
799  typedef typename allocator_type::reference reference;
800  typedef typename allocator_type::const_reference const_reference;
801  typedef typename _Hashtable::iterator iterator;
802  typedef typename _Hashtable::const_iterator const_iterator;
803  typedef typename _Hashtable::local_iterator local_iterator;
804  typedef typename _Hashtable::const_local_iterator const_local_iterator;
805  typedef typename _Hashtable::size_type size_type;
806  typedef typename _Hashtable::difference_type difference_type;
808 
809  //construct/destroy/copy
810 
818  explicit
819  unordered_multimap(size_type __n = 10,
820  const hasher& __hf = hasher(),
821  const key_equal& __eql = key_equal(),
822  const allocator_type& __a = allocator_type())
823  : _M_h(__n, __hf, __eql, __a)
824  { }
825 
839  template<typename _InputIterator>
840  unordered_multimap(_InputIterator __f, _InputIterator __l,
841  size_type __n = 0,
842  const hasher& __hf = hasher(),
843  const key_equal& __eql = key_equal(),
844  const allocator_type& __a = allocator_type())
845  : _M_h(__f, __l, __n, __hf, __eql, __a)
846  { }
847 
849  unordered_multimap(const unordered_multimap&) = default;
850 
852  unordered_multimap(unordered_multimap&&) = default;
853 
865  unordered_multimap(initializer_list<value_type> __l,
866  size_type __n = 0,
867  const hasher& __hf = hasher(),
868  const key_equal& __eql = key_equal(),
869  const allocator_type& __a = allocator_type())
870  : _M_h(__l, __n, __hf, __eql, __a)
871  { }
872 
874  unordered_multimap&
875  operator=(const unordered_multimap&) = default;
876 
878  unordered_multimap&
879  operator=(unordered_multimap&&) = default;
880 
892  unordered_multimap&
893  operator=(initializer_list<value_type> __l)
894  {
895  _M_h = __l;
896  return *this;
897  }
898 
901  allocator_type
902  get_allocator() const noexcept
903  { return _M_h.get_allocator(); }
904 
905  // size and capacity:
906 
908  bool
909  empty() const noexcept
910  { return _M_h.empty(); }
911 
913  size_type
914  size() const noexcept
915  { return _M_h.size(); }
916 
918  size_type
919  max_size() const noexcept
920  { return _M_h.max_size(); }
921 
922  // iterators.
923 
928  iterator
929  begin() noexcept
930  { return _M_h.begin(); }
931 
933 
937  const_iterator
938  begin() const noexcept
939  { return _M_h.begin(); }
940 
941  const_iterator
942  cbegin() const noexcept
943  { return _M_h.begin(); }
945 
950  iterator
951  end() noexcept
952  { return _M_h.end(); }
953 
955 
959  const_iterator
960  end() const noexcept
961  { return _M_h.end(); }
962 
963  const_iterator
964  cend() const noexcept
965  { return _M_h.end(); }
967 
968  // modifiers.
969 
985  template<typename... _Args>
986  iterator
987  emplace(_Args&&... __args)
988  { return _M_h.emplace(std::forward<_Args>(__args)...); }
989 
1011  template<typename... _Args>
1012  iterator
1013  emplace_hint(const_iterator __pos, _Args&&... __args)
1014  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1015 
1017 
1026  iterator
1027  insert(const value_type& __x)
1028  { return _M_h.insert(__x); }
1029 
1030  template<typename _Pair, typename = typename
1031  std::enable_if<std::is_constructible<value_type,
1032  _Pair&&>::value>::type>
1033  iterator
1034  insert(_Pair&& __x)
1035  { return _M_h.insert(std::forward<_Pair>(__x)); }
1037 
1039 
1058  iterator
1059  insert(const_iterator __hint, const value_type& __x)
1060  { return _M_h.insert(__hint, __x); }
1061 
1062  template<typename _Pair, typename = typename
1063  std::enable_if<std::is_constructible<value_type,
1064  _Pair&&>::value>::type>
1065  iterator
1066  insert(const_iterator __hint, _Pair&& __x)
1067  { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
1069 
1079  template<typename _InputIterator>
1080  void
1081  insert(_InputIterator __first, _InputIterator __last)
1082  { _M_h.insert(__first, __last); }
1083 
1092  void
1093  insert(initializer_list<value_type> __l)
1094  { _M_h.insert(__l); }
1095 
1097 
1110  iterator
1111  erase(const_iterator __position)
1112  { return _M_h.erase(__position); }
1113 
1114  // LWG 2059.
1115  iterator
1116  erase(iterator __it)
1117  { return _M_h.erase(__it); }
1119 
1131  size_type
1132  erase(const key_type& __x)
1133  { return _M_h.erase(__x); }
1134 
1150  iterator
1151  erase(const_iterator __first, const_iterator __last)
1152  { return _M_h.erase(__first, __last); }
1153 
1160  void
1161  clear() noexcept
1162  { _M_h.clear(); }
1163 
1174  void
1175  swap(unordered_multimap& __x)
1176  { _M_h.swap(__x._M_h); }
1177 
1178  // observers.
1179 
1182  hasher
1183  hash_function() const
1184  { return _M_h.hash_function(); }
1185 
1188  key_equal
1189  key_eq() const
1190  { return _M_h.key_eq(); }
1191 
1192  // lookup.
1193 
1195 
1206  iterator
1207  find(const key_type& __x)
1208  { return _M_h.find(__x); }
1209 
1210  const_iterator
1211  find(const key_type& __x) const
1212  { return _M_h.find(__x); }
1214 
1220  size_type
1221  count(const key_type& __x) const
1222  { return _M_h.count(__x); }
1223 
1225 
1231  std::pair<iterator, iterator>
1232  equal_range(const key_type& __x)
1233  { return _M_h.equal_range(__x); }
1234 
1235  std::pair<const_iterator, const_iterator>
1236  equal_range(const key_type& __x) const
1237  { return _M_h.equal_range(__x); }
1239 
1240  // bucket interface.
1241 
1243  size_type
1244  bucket_count() const noexcept
1245  { return _M_h.bucket_count(); }
1246 
1248  size_type
1249  max_bucket_count() const noexcept
1250  { return _M_h.max_bucket_count(); }
1251 
1252  /*
1253  * @brief Returns the number of elements in a given bucket.
1254  * @param __n A bucket index.
1255  * @return The number of elements in the bucket.
1256  */
1257  size_type
1258  bucket_size(size_type __n) const
1259  { return _M_h.bucket_size(__n); }
1260 
1261  /*
1262  * @brief Returns the bucket index of a given element.
1263  * @param __key A key instance.
1264  * @return The key bucket index.
1265  */
1266  size_type
1267  bucket(const key_type& __key) const
1268  { return _M_h.bucket(__key); }
1269 
1276  local_iterator
1277  begin(size_type __n)
1278  { return _M_h.begin(__n); }
1279 
1281 
1287  const_local_iterator
1288  begin(size_type __n) const
1289  { return _M_h.begin(__n); }
1290 
1291  const_local_iterator
1292  cbegin(size_type __n) const
1293  { return _M_h.cbegin(__n); }
1295 
1302  local_iterator
1303  end(size_type __n)
1304  { return _M_h.end(__n); }
1305 
1307 
1313  const_local_iterator
1314  end(size_type __n) const
1315  { return _M_h.end(__n); }
1316 
1317  const_local_iterator
1318  cend(size_type __n) const
1319  { return _M_h.cend(__n); }
1321 
1322  // hash policy.
1323 
1325  float
1326  load_factor() const noexcept
1327  { return _M_h.load_factor(); }
1328 
1331  float
1332  max_load_factor() const noexcept
1333  { return _M_h.max_load_factor(); }
1334 
1339  void
1340  max_load_factor(float __z)
1341  { _M_h.max_load_factor(__z); }
1342 
1350  void
1351  rehash(size_type __n)
1352  { _M_h.rehash(__n); }
1353 
1361  void
1362  reserve(size_type __n)
1363  { _M_h.reserve(__n); }
1364 
1365  template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1366  typename _Alloc1>
1367  friend bool
1368  operator==(const unordered_multimap<_Key1, _Tp1,
1369  _Hash1, _Pred1, _Alloc1>&,
1370  const unordered_multimap<_Key1, _Tp1,
1371  _Hash1, _Pred1, _Alloc1>&);
1372  };
1373 
1374  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1375  inline void
1376  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1377  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1378  { __x.swap(__y); }
1379 
1380  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1381  inline void
1382  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1383  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1384  { __x.swap(__y); }
1385 
1386  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1387  inline bool
1388  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1389  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1390  { return __x._M_h._M_equal(__y._M_h); }
1391 
1392  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1393  inline bool
1394  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1395  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1396  { return !(__x == __y); }
1397 
1398  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1399  inline bool
1400  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1401  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1402  { return __x._M_h._M_equal(__y._M_h); }
1403 
1404  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1405  inline bool
1406  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1407  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1408  { return !(__x == __y); }
1409 
1410 _GLIBCXX_END_NAMESPACE_CONTAINER
1411 } // namespace std
1412 
1413 #endif /* _UNORDERED_MAP_H */
std::__exception_ptr::operator==
bool operator==(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
_GLIBCXX_VISIBILITY
namespace std _GLIBCXX_VISIBILITY(default)
Definition: unordered_map.h:33
std::__exception_ptr::operator!=
bool operator!=(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
std::__exception_ptr::swap
void swap(exception_ptr &__lhs, exception_ptr &__rhs)
Definition: exception_ptr.h:160
Generated on Sat Jul 22 2017 14:40:11 for STLdoc by   doxygen 1.8.6