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