STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
unordered_set.h
Go to the documentation of this file.
1 // unordered_set 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_SET_H
31 #define _UNORDERED_SET_H
32 
33 namespace std _GLIBCXX_VISIBILITY(default)
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
36 
38  template<bool _Cache>
39  using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
40 
41  template<typename _Value,
42  typename _Hash = hash<_Value>,
43  typename _Pred = std::equal_to<_Value>,
44  typename _Alloc = std::allocator<_Value>,
45  typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
46  using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
47  __detail::_Identity, _Pred, _Hash,
48  __detail::_Mod_range_hashing,
49  __detail::_Default_ranged_hash,
50  __detail::_Prime_rehash_policy, _Tr>;
51 
53  template<bool _Cache>
54  using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
55 
56  template<typename _Value,
57  typename _Hash = hash<_Value>,
58  typename _Pred = std::equal_to<_Value>,
59  typename _Alloc = std::allocator<_Value>,
60  typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>>
61  using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
62  __detail::_Identity,
63  _Pred, _Hash,
64  __detail::_Mod_range_hashing,
65  __detail::_Default_ranged_hash,
66  __detail::_Prime_rehash_policy, _Tr>;
67 
89  template<class _Value,
90  class _Hash = hash<_Value>,
91  class _Pred = std::equal_to<_Value>,
92  class _Alloc = std::allocator<_Value> >
93  class unordered_set : __check_copy_constructible<_Alloc>
94  {
95  typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
96  _Hashtable _M_h;
97 
98  public:
99  // typedefs:
101  typedef typename _Hashtable::key_type key_type;
103  typedef typename _Hashtable::value_type value_type;
104  typedef typename _Hashtable::hasher hasher;
105  typedef typename _Hashtable::key_equal key_equal;
106  typedef typename _Hashtable::allocator_type allocator_type;
108 
110  typedef typename allocator_type::pointer pointer;
112  typedef typename allocator_type::const_pointer const_pointer;
113  typedef typename allocator_type::reference reference;
114  typedef typename allocator_type::const_reference const_reference;
115  typedef typename _Hashtable::iterator iterator;
116  typedef typename _Hashtable::const_iterator const_iterator;
117  typedef typename _Hashtable::local_iterator local_iterator;
118  typedef typename _Hashtable::const_local_iterator const_local_iterator;
119  typedef typename _Hashtable::size_type size_type;
120  typedef typename _Hashtable::difference_type difference_type;
122 
123  // construct/destroy/copy
131  explicit
132  unordered_set(size_type __n = 10,
133  const hasher& __hf = hasher(),
134  const key_equal& __eql = key_equal(),
135  const allocator_type& __a = allocator_type())
136  : _M_h(__n, __hf, __eql, __a)
137  { }
138 
152  template<typename _InputIterator>
153  unordered_set(_InputIterator __f, _InputIterator __l,
154  size_type __n = 0,
155  const hasher& __hf = hasher(),
156  const key_equal& __eql = key_equal(),
157  const allocator_type& __a = allocator_type())
158  : _M_h(__f, __l, __n, __hf, __eql, __a)
159  { }
160 
162  unordered_set(const unordered_set&) = default;
163 
165  unordered_set(unordered_set&&) = default;
166 
178  unordered_set(initializer_list<value_type> __l,
179  size_type __n = 0,
180  const hasher& __hf = hasher(),
181  const key_equal& __eql = key_equal(),
182  const allocator_type& __a = allocator_type())
183  : _M_h(__l, __n, __hf, __eql, __a)
184  { }
185 
187  unordered_set&
188  operator=(const unordered_set&) = default;
189 
191  unordered_set&
192  operator=(unordered_set&&) = default;
193 
205  unordered_set&
206  operator=(initializer_list<value_type> __l)
207  {
208  _M_h = __l;
209  return *this;
210  }
211 
214  allocator_type
215  get_allocator() const noexcept
216  { return _M_h.get_allocator(); }
217 
218  // size and capacity:
219 
221  bool
222  empty() const noexcept
223  { return _M_h.empty(); }
224 
226  size_type
227  size() const noexcept
228  { return _M_h.size(); }
229 
231  size_type
232  max_size() const noexcept
233  { return _M_h.max_size(); }
234 
235  // iterators.
236 
238 
242  iterator
243  begin() noexcept
244  { return _M_h.begin(); }
245 
246  const_iterator
247  begin() const noexcept
248  { return _M_h.begin(); }
250 
252 
256  iterator
257  end() noexcept
258  { return _M_h.end(); }
259 
260  const_iterator
261  end() const noexcept
262  { return _M_h.end(); }
264 
269  const_iterator
270  cbegin() const noexcept
271  { return _M_h.begin(); }
272 
277  const_iterator
278  cend() const noexcept
279  { return _M_h.end(); }
280 
281  // modifiers.
282 
298  template<typename... _Args>
299  std::pair<iterator, bool>
300  emplace(_Args&&... __args)
301  { return _M_h.emplace(std::forward<_Args>(__args)...); }
302 
324  template<typename... _Args>
325  iterator
326  emplace_hint(const_iterator __pos, _Args&&... __args)
327  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
328 
330 
343  std::pair<iterator, bool>
344  insert(const value_type& __x)
345  { return _M_h.insert(__x); }
346 
347  std::pair<iterator, bool>
348  insert(value_type&& __x)
349  { return _M_h.insert(std::move(__x)); }
351 
353 
372  iterator
373  insert(const_iterator __hint, const value_type& __x)
374  { return _M_h.insert(__hint, __x); }
375 
376  iterator
377  insert(const_iterator __hint, value_type&& __x)
378  { return _M_h.insert(__hint, std::move(__x)); }
380 
390  template<typename _InputIterator>
391  void
392  insert(_InputIterator __first, _InputIterator __last)
393  { _M_h.insert(__first, __last); }
394 
402  void
403  insert(initializer_list<value_type> __l)
404  { _M_h.insert(__l); }
405 
407 
420  iterator
421  erase(const_iterator __position)
422  { return _M_h.erase(__position); }
423 
424  // LWG 2059.
425  iterator
426  erase(iterator __it)
427  { return _M_h.erase(__it); }
429 
442  size_type
443  erase(const key_type& __x)
444  { return _M_h.erase(__x); }
445 
460  iterator
461  erase(const_iterator __first, const_iterator __last)
462  { return _M_h.erase(__first, __last); }
463 
470  void
471  clear() noexcept
472  { _M_h.clear(); }
473 
483  void
484  swap(unordered_set& __x)
485  { _M_h.swap(__x._M_h); }
486 
487  // observers.
488 
491  hasher
492  hash_function() const
493  { return _M_h.hash_function(); }
494 
497  key_equal
498  key_eq() const
499  { return _M_h.key_eq(); }
500 
501  // lookup.
502 
504 
515  iterator
516  find(const key_type& __x)
517  { return _M_h.find(__x); }
518 
519  const_iterator
520  find(const key_type& __x) const
521  { return _M_h.find(__x); }
523 
533  size_type
534  count(const key_type& __x) const
535  { return _M_h.count(__x); }
536 
538 
546  std::pair<iterator, iterator>
547  equal_range(const key_type& __x)
548  { return _M_h.equal_range(__x); }
549 
550  std::pair<const_iterator, const_iterator>
551  equal_range(const key_type& __x) const
552  { return _M_h.equal_range(__x); }
554 
555  // bucket interface.
556 
558  size_type
559  bucket_count() const noexcept
560  { return _M_h.bucket_count(); }
561 
563  size_type
564  max_bucket_count() const noexcept
565  { return _M_h.max_bucket_count(); }
566 
567  /*
568  * @brief Returns the number of elements in a given bucket.
569  * @param __n A bucket index.
570  * @return The number of elements in the bucket.
571  */
572  size_type
573  bucket_size(size_type __n) const
574  { return _M_h.bucket_size(__n); }
575 
576  /*
577  * @brief Returns the bucket index of a given element.
578  * @param __key A key instance.
579  * @return The key bucket index.
580  */
581  size_type
582  bucket(const key_type& __key) const
583  { return _M_h.bucket(__key); }
584 
586 
592  local_iterator
593  begin(size_type __n)
594  { return _M_h.begin(__n); }
595 
596  const_local_iterator
597  begin(size_type __n) const
598  { return _M_h.begin(__n); }
599 
600  const_local_iterator
601  cbegin(size_type __n) const
602  { return _M_h.cbegin(__n); }
604 
606 
612  local_iterator
613  end(size_type __n)
614  { return _M_h.end(__n); }
615 
616  const_local_iterator
617  end(size_type __n) const
618  { return _M_h.end(__n); }
619 
620  const_local_iterator
621  cend(size_type __n) const
622  { return _M_h.cend(__n); }
624 
625  // hash policy.
626 
628  float
629  load_factor() const noexcept
630  { return _M_h.load_factor(); }
631 
634  float
635  max_load_factor() const noexcept
636  { return _M_h.max_load_factor(); }
637 
642  void
643  max_load_factor(float __z)
644  { _M_h.max_load_factor(__z); }
645 
653  void
654  rehash(size_type __n)
655  { _M_h.rehash(__n); }
656 
664  void
665  reserve(size_type __n)
666  { _M_h.reserve(__n); }
667 
668  template<typename _Value1, typename _Hash1, typename _Pred1,
669  typename _Alloc1>
670  friend bool
671  operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&,
672  const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&);
673  };
674 
694  template<class _Value,
695  class _Hash = hash<_Value>,
696  class _Pred = std::equal_to<_Value>,
697  class _Alloc = std::allocator<_Value> >
698  class unordered_multiset : __check_copy_constructible<_Alloc>
699  {
700  typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
701  _Hashtable _M_h;
702 
703  public:
704  // typedefs:
706  typedef typename _Hashtable::key_type key_type;
708  typedef typename _Hashtable::value_type value_type;
709  typedef typename _Hashtable::hasher hasher;
710  typedef typename _Hashtable::key_equal key_equal;
711  typedef typename _Hashtable::allocator_type allocator_type;
713 
715  typedef typename allocator_type::pointer pointer;
717  typedef typename allocator_type::const_pointer const_pointer;
718  typedef typename allocator_type::reference reference;
719  typedef typename allocator_type::const_reference const_reference;
720  typedef typename _Hashtable::iterator iterator;
721  typedef typename _Hashtable::const_iterator const_iterator;
722  typedef typename _Hashtable::local_iterator local_iterator;
723  typedef typename _Hashtable::const_local_iterator const_local_iterator;
724  typedef typename _Hashtable::size_type size_type;
725  typedef typename _Hashtable::difference_type difference_type;
727 
728  // construct/destroy/copy
736  explicit
737  unordered_multiset(size_type __n = 10,
738  const hasher& __hf = hasher(),
739  const key_equal& __eql = key_equal(),
740  const allocator_type& __a = allocator_type())
741  : _M_h(__n, __hf, __eql, __a)
742  { }
743 
757  template<typename _InputIterator>
758  unordered_multiset(_InputIterator __f, _InputIterator __l,
759  size_type __n = 0,
760  const hasher& __hf = hasher(),
761  const key_equal& __eql = key_equal(),
762  const allocator_type& __a = allocator_type())
763  : _M_h(__f, __l, __n, __hf, __eql, __a)
764  { }
765 
767  unordered_multiset(const unordered_multiset&) = default;
768 
770  unordered_multiset(unordered_multiset&&) = default;
771 
783  unordered_multiset(initializer_list<value_type> __l,
784  size_type __n = 0,
785  const hasher& __hf = hasher(),
786  const key_equal& __eql = key_equal(),
787  const allocator_type& __a = allocator_type())
788  : _M_h(__l, __n, __hf, __eql, __a)
789  { }
790 
792  unordered_multiset&
793  operator=(const unordered_multiset&) = default;
794 
796  unordered_multiset&
797  operator=(unordered_multiset&& __x) = default;
798 
810  unordered_multiset&
811  operator=(initializer_list<value_type> __l)
812  {
813  _M_h = __l;
814  return *this;
815  }
816 
819  allocator_type
820  get_allocator() const noexcept
821  { return _M_h.get_allocator(); }
822 
823  // size and capacity:
824 
826  bool
827  empty() const noexcept
828  { return _M_h.empty(); }
829 
831  size_type
832  size() const noexcept
833  { return _M_h.size(); }
834 
836  size_type
837  max_size() const noexcept
838  { return _M_h.max_size(); }
839 
840  // iterators.
841 
843 
847  iterator
848  begin() noexcept
849  { return _M_h.begin(); }
850 
851  const_iterator
852  begin() const noexcept
853  { return _M_h.begin(); }
855 
857 
861  iterator
862  end() noexcept
863  { return _M_h.end(); }
864 
865  const_iterator
866  end() const noexcept
867  { return _M_h.end(); }
869 
874  const_iterator
875  cbegin() const noexcept
876  { return _M_h.begin(); }
877 
882  const_iterator
883  cend() const noexcept
884  { return _M_h.end(); }
885 
886  // modifiers.
887 
895  template<typename... _Args>
896  iterator
897  emplace(_Args&&... __args)
898  { return _M_h.emplace(std::forward<_Args>(__args)...); }
899 
917  template<typename... _Args>
918  iterator
919  emplace_hint(const_iterator __pos, _Args&&... __args)
920  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
921 
923 
930  iterator
931  insert(const value_type& __x)
932  { return _M_h.insert(__x); }
933 
934  iterator
935  insert(value_type&& __x)
936  { return _M_h.insert(std::move(__x)); }
938 
940 
956  iterator
957  insert(const_iterator __hint, const value_type& __x)
958  { return _M_h.insert(__hint, __x); }
959 
960  iterator
961  insert(const_iterator __hint, value_type&& __x)
962  { return _M_h.insert(__hint, std::move(__x)); }
964 
973  template<typename _InputIterator>
974  void
975  insert(_InputIterator __first, _InputIterator __last)
976  { _M_h.insert(__first, __last); }
977 
985  void
986  insert(initializer_list<value_type> __l)
987  { _M_h.insert(__l); }
988 
990 
1004  iterator
1005  erase(const_iterator __position)
1006  { return _M_h.erase(__position); }
1007 
1008  // LWG 2059.
1009  iterator
1010  erase(iterator __it)
1011  { return _M_h.erase(__it); }
1013 
1014 
1027  size_type
1028  erase(const key_type& __x)
1029  { return _M_h.erase(__x); }
1030 
1047  iterator
1048  erase(const_iterator __first, const_iterator __last)
1049  { return _M_h.erase(__first, __last); }
1050 
1058  void
1059  clear() noexcept
1060  { _M_h.clear(); }
1061 
1071  void
1072  swap(unordered_multiset& __x)
1073  { _M_h.swap(__x._M_h); }
1074 
1075  // observers.
1076 
1079  hasher
1080  hash_function() const
1081  { return _M_h.hash_function(); }
1082 
1085  key_equal
1086  key_eq() const
1087  { return _M_h.key_eq(); }
1088 
1089  // lookup.
1090 
1092 
1103  iterator
1104  find(const key_type& __x)
1105  { return _M_h.find(__x); }
1106 
1107  const_iterator
1108  find(const key_type& __x) const
1109  { return _M_h.find(__x); }
1111 
1117  size_type
1118  count(const key_type& __x) const
1119  { return _M_h.count(__x); }
1120 
1122 
1128  std::pair<iterator, iterator>
1129  equal_range(const key_type& __x)
1130  { return _M_h.equal_range(__x); }
1131 
1132  std::pair<const_iterator, const_iterator>
1133  equal_range(const key_type& __x) const
1134  { return _M_h.equal_range(__x); }
1136 
1137  // bucket interface.
1138 
1140  size_type
1141  bucket_count() const noexcept
1142  { return _M_h.bucket_count(); }
1143 
1145  size_type
1146  max_bucket_count() const noexcept
1147  { return _M_h.max_bucket_count(); }
1148 
1149  /*
1150  * @brief Returns the number of elements in a given bucket.
1151  * @param __n A bucket index.
1152  * @return The number of elements in the bucket.
1153  */
1154  size_type
1155  bucket_size(size_type __n) const
1156  { return _M_h.bucket_size(__n); }
1157 
1158  /*
1159  * @brief Returns the bucket index of a given element.
1160  * @param __key A key instance.
1161  * @return The key bucket index.
1162  */
1163  size_type
1164  bucket(const key_type& __key) const
1165  { return _M_h.bucket(__key); }
1166 
1168 
1174  local_iterator
1175  begin(size_type __n)
1176  { return _M_h.begin(__n); }
1177 
1178  const_local_iterator
1179  begin(size_type __n) const
1180  { return _M_h.begin(__n); }
1181 
1182  const_local_iterator
1183  cbegin(size_type __n) const
1184  { return _M_h.cbegin(__n); }
1186 
1188 
1194  local_iterator
1195  end(size_type __n)
1196  { return _M_h.end(__n); }
1197 
1198  const_local_iterator
1199  end(size_type __n) const
1200  { return _M_h.end(__n); }
1201 
1202  const_local_iterator
1203  cend(size_type __n) const
1204  { return _M_h.cend(__n); }
1206 
1207  // hash policy.
1208 
1210  float
1211  load_factor() const noexcept
1212  { return _M_h.load_factor(); }
1213 
1216  float
1217  max_load_factor() const noexcept
1218  { return _M_h.max_load_factor(); }
1219 
1224  void
1225  max_load_factor(float __z)
1226  { _M_h.max_load_factor(__z); }
1227 
1235  void
1236  rehash(size_type __n)
1237  { _M_h.rehash(__n); }
1238 
1246  void
1247  reserve(size_type __n)
1248  { _M_h.reserve(__n); }
1249 
1250  template<typename _Value1, typename _Hash1, typename _Pred1,
1251  typename _Alloc1>
1252  friend bool
1253  operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&,
1254  const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&);
1255  };
1256 
1257  template<class _Value, class _Hash, class _Pred, class _Alloc>
1258  inline void
1259  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1260  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1261  { __x.swap(__y); }
1262 
1263  template<class _Value, class _Hash, class _Pred, class _Alloc>
1264  inline void
1265  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1266  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1267  { __x.swap(__y); }
1268 
1269  template<class _Value, class _Hash, class _Pred, class _Alloc>
1270  inline bool
1271  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1272  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1273  { return __x._M_h._M_equal(__y._M_h); }
1274 
1275  template<class _Value, class _Hash, class _Pred, class _Alloc>
1276  inline bool
1277  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1278  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1279  { return !(__x == __y); }
1280 
1281  template<class _Value, class _Hash, class _Pred, class _Alloc>
1282  inline bool
1283  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1284  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1285  { return __x._M_h._M_equal(__y._M_h); }
1286 
1287  template<class _Value, class _Hash, class _Pred, class _Alloc>
1288  inline bool
1289  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1290  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1291  { return !(__x == __y); }
1292 
1293 _GLIBCXX_END_NAMESPACE_CONTAINER
1294 } // namespace std
1295 
1296 #endif /* _UNORDERED_SET_H */
std::__exception_ptr::operator==
bool operator==(const exception_ptr &, const exception_ptr &) _GLIBCXX_USE_NOEXCEPT __attribute__((__pure__))
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_set.h:33
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:12 for STLdoc by   doxygen 1.8.6