libstdc++
unordered_set.h
Go to the documentation of this file.
1 // unordered_set implementation -*- C++ -*-
2 
3 // Copyright (C) 2010, 2011, 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 
25 /** @file bits/unordered_set.h
26  * This is an internal header file, included by other library headers.
27  * Do not attempt to use it directly. @headername{unordered_set}
28  */
29 
30 #ifndef _UNORDERED_SET_H
31 #define _UNORDERED_SET_H
32 
33 namespace std _GLIBCXX_VISIBILITY(default)
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
36 
37  // NB: When we get typedef templates these class definitions
38  // will be unnecessary.
39  template<class _Value,
40  class _Hash = hash<_Value>,
41  class _Pred = std::equal_to<_Value>,
42  class _Alloc = std::allocator<_Value>,
43  bool __cache_hash_code =
44  __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
45  integral_constant<bool, !__is_final(_Hash)>,
46  __detail::__is_noexcept_hash<_Value, _Hash>>>::value>
47  class __unordered_set
48  : public _Hashtable<_Value, _Value, _Alloc,
49  std::_Identity<_Value>, _Pred,
50  _Hash, __detail::_Mod_range_hashing,
51  __detail::_Default_ranged_hash,
52  __detail::_Prime_rehash_policy,
53  __cache_hash_code, true, true>,
54  __check_copy_constructible<_Alloc>
55  {
56  typedef _Hashtable<_Value, _Value, _Alloc,
57  std::_Identity<_Value>, _Pred,
58  _Hash, __detail::_Mod_range_hashing,
59  __detail::_Default_ranged_hash,
60  __detail::_Prime_rehash_policy,
61  __cache_hash_code, true, true>
62  _Base;
63 
64  public:
65  typedef typename _Base::value_type value_type;
66  typedef typename _Base::size_type size_type;
67  typedef typename _Base::hasher hasher;
68  typedef typename _Base::key_equal key_equal;
69  typedef typename _Base::allocator_type allocator_type;
70  typedef typename _Base::iterator iterator;
71  typedef typename _Base::const_iterator const_iterator;
72 
73  explicit
74  __unordered_set(size_type __n = 10,
75  const hasher& __hf = hasher(),
76  const key_equal& __eql = key_equal(),
77  const allocator_type& __a = allocator_type())
78  : _Base(__n, __hf, __detail::_Mod_range_hashing(),
79  __detail::_Default_ranged_hash(), __eql,
80  std::_Identity<value_type>(), __a)
81  { }
82 
83  template<typename _InputIterator>
84  __unordered_set(_InputIterator __f, _InputIterator __l,
85  size_type __n = 0,
86  const hasher& __hf = hasher(),
87  const key_equal& __eql = key_equal(),
88  const allocator_type& __a = allocator_type())
89  : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
90  __detail::_Default_ranged_hash(), __eql,
91  std::_Identity<value_type>(), __a)
92  { }
93 
94  __unordered_set(initializer_list<value_type> __l,
95  size_type __n = 0,
96  const hasher& __hf = hasher(),
97  const key_equal& __eql = key_equal(),
98  const allocator_type& __a = allocator_type())
99  : _Base(__l.begin(), __l.end(), __n, __hf,
100  __detail::_Mod_range_hashing(),
101  __detail::_Default_ranged_hash(), __eql,
102  std::_Identity<value_type>(), __a)
103  { }
104 
105  __unordered_set&
106  operator=(initializer_list<value_type> __l)
107  {
108  this->clear();
109  this->insert(__l.begin(), __l.end());
110  return *this;
111  }
112 
113  using _Base::insert;
114 
115  std::pair<iterator, bool>
116  insert(value_type&& __v)
117  { return this->_M_insert(std::move(__v), std::true_type()); }
118 
119  iterator
120  insert(const_iterator, value_type&& __v)
121  { return insert(std::move(__v)).first; }
122  };
123 
124  template<class _Value,
125  class _Hash = hash<_Value>,
126  class _Pred = std::equal_to<_Value>,
127  class _Alloc = std::allocator<_Value>,
128  bool __cache_hash_code =
129  __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
130  integral_constant<bool, !__is_final(_Hash)>,
131  __detail::__is_noexcept_hash<_Value, _Hash>>>::value>
132  class __unordered_multiset
133  : public _Hashtable<_Value, _Value, _Alloc,
134  std::_Identity<_Value>, _Pred,
135  _Hash, __detail::_Mod_range_hashing,
136  __detail::_Default_ranged_hash,
137  __detail::_Prime_rehash_policy,
138  __cache_hash_code, true, false>,
139  __check_copy_constructible<_Alloc>
140  {
141  typedef _Hashtable<_Value, _Value, _Alloc,
142  std::_Identity<_Value>, _Pred,
143  _Hash, __detail::_Mod_range_hashing,
144  __detail::_Default_ranged_hash,
145  __detail::_Prime_rehash_policy,
146  __cache_hash_code, true, false>
147  _Base;
148 
149  public:
150  typedef typename _Base::value_type value_type;
151  typedef typename _Base::size_type size_type;
152  typedef typename _Base::hasher hasher;
153  typedef typename _Base::key_equal key_equal;
154  typedef typename _Base::allocator_type allocator_type;
155  typedef typename _Base::iterator iterator;
156  typedef typename _Base::const_iterator const_iterator;
157 
158  explicit
159  __unordered_multiset(size_type __n = 10,
160  const hasher& __hf = hasher(),
161  const key_equal& __eql = key_equal(),
162  const allocator_type& __a = allocator_type())
163  : _Base(__n, __hf, __detail::_Mod_range_hashing(),
164  __detail::_Default_ranged_hash(), __eql,
165  std::_Identity<value_type>(), __a)
166  { }
167 
168 
169  template<typename _InputIterator>
170  __unordered_multiset(_InputIterator __f, _InputIterator __l,
171  size_type __n = 0,
172  const hasher& __hf = hasher(),
173  const key_equal& __eql = key_equal(),
174  const allocator_type& __a = allocator_type())
175  : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
176  __detail::_Default_ranged_hash(), __eql,
177  std::_Identity<value_type>(), __a)
178  { }
179 
180  __unordered_multiset(initializer_list<value_type> __l,
181  size_type __n = 0,
182  const hasher& __hf = hasher(),
183  const key_equal& __eql = key_equal(),
184  const allocator_type& __a = allocator_type())
185  : _Base(__l.begin(), __l.end(), __n, __hf,
186  __detail::_Mod_range_hashing(),
187  __detail::_Default_ranged_hash(), __eql,
188  std::_Identity<value_type>(), __a)
189  { }
190 
191  __unordered_multiset&
192  operator=(initializer_list<value_type> __l)
193  {
194  this->clear();
195  this->insert(__l.begin(), __l.end());
196  return *this;
197  }
198 
199  using _Base::insert;
200 
201  iterator
202  insert(value_type&& __v)
203  { return this->_M_insert(std::move(__v), std::false_type()); }
204 
205  iterator
206  insert(const_iterator, value_type&& __v)
207  { return insert(std::move(__v)); }
208  };
209 
210  template<class _Value, class _Hash, class _Pred, class _Alloc,
211  bool __cache_hash_code>
212  inline void
213  swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x,
214  __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y)
215  { __x.swap(__y); }
216 
217  template<class _Value, class _Hash, class _Pred, class _Alloc,
218  bool __cache_hash_code>
219  inline void
220  swap(__unordered_multiset<_Value, _Hash, _Pred,
221  _Alloc, __cache_hash_code>& __x,
222  __unordered_multiset<_Value, _Hash, _Pred,
223  _Alloc, __cache_hash_code>& __y)
224  { __x.swap(__y); }
225 
226  template<class _Value, class _Hash, class _Pred, class _Alloc,
227  bool __cache_hash_code>
228  inline bool
229  operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
230  __cache_hash_code>& __x,
231  const __unordered_set<_Value, _Hash, _Pred, _Alloc,
232  __cache_hash_code>& __y)
233  { return __x._M_equal(__y); }
234 
235  template<class _Value, class _Hash, class _Pred, class _Alloc,
236  bool __cache_hash_code>
237  inline bool
238  operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
239  __cache_hash_code>& __x,
240  const __unordered_set<_Value, _Hash, _Pred, _Alloc,
241  __cache_hash_code>& __y)
242  { return !(__x == __y); }
243 
244  template<class _Value, class _Hash, class _Pred, class _Alloc,
245  bool __cache_hash_code>
246  inline bool
247  operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
248  __cache_hash_code>& __x,
249  const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
250  __cache_hash_code>& __y)
251  { return __x._M_equal(__y); }
252 
253  template<class _Value, class _Hash, class _Pred, class _Alloc,
254  bool __cache_hash_code>
255  inline bool
256  operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
257  __cache_hash_code>& __x,
258  const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
259  __cache_hash_code>& __y)
260  { return !(__x == __y); }
261 
262  /**
263  * @brief A standard container composed of unique keys (containing
264  * at most one of each key value) in which the elements' keys are
265  * the elements themselves.
266  *
267  * @ingroup unordered_associative_containers
268  *
269  * Meets the requirements of a <a href="tables.html#65">container</a>, and
270  * <a href="tables.html#xx">unordered associative container</a>
271  *
272  * @param Value Type of key objects.
273  * @param Hash Hashing function object type, defaults to hash<Value>.
274  * @param Pred Predicate function object type, defaults to equal_to<Value>.
275  * @param Alloc Allocator type, defaults to allocator<Key>.
276  */
277  template<class _Value,
278  class _Hash = hash<_Value>,
279  class _Pred = std::equal_to<_Value>,
280  class _Alloc = std::allocator<_Value> >
281  class unordered_set
282  : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
283  {
284  typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base;
285 
286  public:
287  typedef typename _Base::value_type value_type;
288  typedef typename _Base::size_type size_type;
289  typedef typename _Base::hasher hasher;
290  typedef typename _Base::key_equal key_equal;
291  typedef typename _Base::allocator_type allocator_type;
292 
293  explicit
294  unordered_set(size_type __n = 10,
295  const hasher& __hf = hasher(),
296  const key_equal& __eql = key_equal(),
297  const allocator_type& __a = allocator_type())
298  : _Base(__n, __hf, __eql, __a)
299  { }
300 
301  template<typename _InputIterator>
302  unordered_set(_InputIterator __f, _InputIterator __l,
303  size_type __n = 0,
304  const hasher& __hf = hasher(),
305  const key_equal& __eql = key_equal(),
306  const allocator_type& __a = allocator_type())
307  : _Base(__f, __l, __n, __hf, __eql, __a)
308  { }
309 
310  unordered_set(initializer_list<value_type> __l,
311  size_type __n = 0,
312  const hasher& __hf = hasher(),
313  const key_equal& __eql = key_equal(),
314  const allocator_type& __a = allocator_type())
315  : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
316  { }
317 
318  unordered_set&
319  operator=(initializer_list<value_type> __l)
320  {
321  this->clear();
322  this->insert(__l.begin(), __l.end());
323  return *this;
324  }
325  };
326 
327  /**
328  * @brief A standard container composed of equivalent keys
329  * (possibly containing multiple of each key value) in which the
330  * elements' keys are the elements themselves.
331  *
332  * @ingroup unordered_associative_containers
333  *
334  * Meets the requirements of a <a href="tables.html#65">container</a>, and
335  * <a href="tables.html#xx">unordered associative container</a>
336  *
337  * @param Value Type of key objects.
338  * @param Hash Hashing function object type, defaults to hash<Value>.
339  * @param Pred Predicate function object type, defaults to equal_to<Value>.
340  * @param Alloc Allocator type, defaults to allocator<Key>.
341  */
342  template<class _Value,
343  class _Hash = hash<_Value>,
344  class _Pred = std::equal_to<_Value>,
345  class _Alloc = std::allocator<_Value> >
346  class unordered_multiset
347  : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc>
348  {
349  typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base;
350 
351  public:
352  typedef typename _Base::value_type value_type;
353  typedef typename _Base::size_type size_type;
354  typedef typename _Base::hasher hasher;
355  typedef typename _Base::key_equal key_equal;
356  typedef typename _Base::allocator_type allocator_type;
357 
358  explicit
359  unordered_multiset(size_type __n = 10,
360  const hasher& __hf = hasher(),
361  const key_equal& __eql = key_equal(),
362  const allocator_type& __a = allocator_type())
363  : _Base(__n, __hf, __eql, __a)
364  { }
365 
366 
367  template<typename _InputIterator>
368  unordered_multiset(_InputIterator __f, _InputIterator __l,
369  size_type __n = 0,
370  const hasher& __hf = hasher(),
371  const key_equal& __eql = key_equal(),
372  const allocator_type& __a = allocator_type())
373  : _Base(__f, __l, __n, __hf, __eql, __a)
374  { }
375 
376  unordered_multiset(initializer_list<value_type> __l,
377  size_type __n = 0,
378  const hasher& __hf = hasher(),
379  const key_equal& __eql = key_equal(),
380  const allocator_type& __a = allocator_type())
381  : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
382  { }
383 
384  unordered_multiset&
385  operator=(initializer_list<value_type> __l)
386  {
387  this->clear();
388  this->insert(__l.begin(), __l.end());
389  return *this;
390  }
391  };
392 
393  template<class _Value, class _Hash, class _Pred, class _Alloc>
394  inline void
395  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
396  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
397  { __x.swap(__y); }
398 
399  template<class _Value, class _Hash, class _Pred, class _Alloc>
400  inline void
401  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
402  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
403  { __x.swap(__y); }
404 
405  template<class _Value, class _Hash, class _Pred, class _Alloc>
406  inline bool
407  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
408  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
409  { return __x._M_equal(__y); }
410 
411  template<class _Value, class _Hash, class _Pred, class _Alloc>
412  inline bool
413  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
414  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
415  { return !(__x == __y); }
416 
417  template<class _Value, class _Hash, class _Pred, class _Alloc>
418  inline bool
419  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
420  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
421  { return __x._M_equal(__y); }
422 
423  template<class _Value, class _Hash, class _Pred, class _Alloc>
424  inline bool
425  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
426  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
427  { return !(__x == __y); }
428 
429 _GLIBCXX_END_NAMESPACE_CONTAINER
430 } // namespace std
431 
432 #endif /* _UNORDERED_SET_H */
433 
std::initializer_list
initializer_list
Definition: initializer_list:47
std::allocator
The standard allocator, as per [20.4].
Definition: bits/alloc_traits.h:43
std::equal_to
One of the comparison functors.
Definition: stl_function.h:206
std::unordered_set
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition: unordered_set.h:281
std::end
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initilizer_list.
Definition: initializer_list:99
std::unordered_multiset
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Definition: unordered_set.h:346
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:88
std::integral_constant
integral_constant
Definition: type_traits:57
std::hash
Primary class template hash.
Definition: system_error:112
std::begin
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initilizer_list.
Definition: initializer_list:89