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