1/////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Olaf Krzikalla 2004-2006.
4// (C) Copyright Ion Gaztanaga 2006-2014
5//
6// Distributed under the Boost Software License, Version 1.0.
7// (See accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//
10// See http://www.boost.org/libs/intrusive for documentation.
11//
12/////////////////////////////////////////////////////////////////////////////
13#ifndef BOOST_INTRUSIVE_UNORDERED_SET_HPP
14#define BOOST_INTRUSIVE_UNORDERED_SET_HPP
15
16#include <boost/intrusive/detail/config_begin.hpp>
17#include <boost/intrusive/intrusive_fwd.hpp>
18#include <boost/intrusive/hashtable.hpp>
19#include <boost/move/utility_core.hpp>
20#include <boost/static_assert.hpp>
21
22#if defined(BOOST_HAS_PRAGMA_ONCE)
23# pragma once
24#endif
25
26namespace boost {
27namespace intrusive {
28
29//! The class template unordered_set is an intrusive container, that mimics most of
30//! the interface of std::tr1::unordered_set as described in the C++ TR1.
31//!
32//! unordered_set is a semi-intrusive container: each object to be stored in the
33//! container must contain a proper hook, but the container also needs
34//! additional auxiliary memory to work: unordered_set needs a pointer to an array
35//! of type `bucket_type` to be passed in the constructor. This bucket array must
36//! have at least the same lifetime as the container. This makes the use of
37//! unordered_set more complicated than purely intrusive containers.
38//! `bucket_type` is default-constructible, copyable and assignable
39//!
40//! The template parameter \c T is the type to be managed by the container.
41//! The user can specify additional options and if no options are provided
42//! default options are used.
43//!
44//! The container supports the following options:
45//! \c base_hook<>/member_hook<>/value_traits<>,
46//! \c constant_time_size<>, \c size_type<>, \c hash<> and \c equal<>
47//! \c bucket_traits<>, \c power_2_buckets<> and \c cache_begin<>.
48//!
49//! unordered_set only provides forward iterators but it provides 4 iterator types:
50//! iterator and const_iterator to navigate through the whole container and
51//! local_iterator and const_local_iterator to navigate through the values
52//! stored in a single bucket. Local iterators are faster and smaller.
53//!
54//! It's not recommended to use non constant-time size unordered_sets because several
55//! key functions, like "empty()", become non-constant time functions. Non
56//! constant-time size unordered_sets are mainly provided to support auto-unlink hooks.
57//!
58//! unordered_set, unlike std::unordered_set, does not make automatic rehashings nor
59//! offers functions related to a load factor. Rehashing can be explicitly requested
60//! and the user must provide a new bucket array that will be used from that moment.
61//!
62//! Since no automatic rehashing is done, iterators are never invalidated when
63//! inserting or erasing elements. Iterators are only invalidated when rehasing.
64#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
65template<class T, class ...Options>
66#else
67template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class SizeType, class BucketTraits, std::size_t BoolFlags>
68#endif
69class unordered_set_impl
70 : public hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags|hash_bool_flags::unique_keys_pos>
71{
72 /// @cond
73 private:
74 typedef hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags|hash_bool_flags::unique_keys_pos> table_type;
75
76 template<class Iterator, class MaybeConstThis, class KeyType, class KeyHasher, class KeyEqual>
77 static std::pair<Iterator,Iterator> priv_equal_range(MaybeConstThis &c, const KeyType& key, KeyHasher hash_func, KeyEqual equal_func)
78 {
79 Iterator const it = c.find(key, hash_func, equal_func);
80 std::pair<Iterator,Iterator> ret(it, it);
81 if(it != c.end())
82 ++ret.second;
83 return ret;
84 }
85
86 //! This class is
87 //! movable
88 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_set_impl)
89
90 typedef table_type implementation_defined;
91 /// @endcond
92
93 public:
94 typedef typename implementation_defined::value_type value_type;
95 typedef typename implementation_defined::key_type key_type;
96 typedef typename implementation_defined::key_of_value key_of_value;
97 typedef typename implementation_defined::value_traits value_traits;
98 typedef typename implementation_defined::bucket_traits bucket_traits;
99 typedef typename implementation_defined::pointer pointer;
100 typedef typename implementation_defined::const_pointer const_pointer;
101 typedef typename implementation_defined::reference reference;
102 typedef typename implementation_defined::const_reference const_reference;
103 typedef typename implementation_defined::difference_type difference_type;
104 typedef typename implementation_defined::size_type size_type;
105 typedef typename implementation_defined::key_equal key_equal;
106 typedef typename implementation_defined::hasher hasher;
107 typedef typename implementation_defined::bucket_type bucket_type;
108 typedef typename implementation_defined::bucket_ptr bucket_ptr;
109 typedef typename implementation_defined::iterator iterator;
110 typedef typename implementation_defined::const_iterator const_iterator;
111 typedef typename implementation_defined::insert_commit_data insert_commit_data;
112 typedef typename implementation_defined::local_iterator local_iterator;
113 typedef typename implementation_defined::const_local_iterator const_local_iterator;
114 typedef typename implementation_defined::node_traits node_traits;
115 typedef typename implementation_defined::node node;
116 typedef typename implementation_defined::node_ptr node_ptr;
117 typedef typename implementation_defined::const_node_ptr const_node_ptr;
118 typedef typename implementation_defined::node_algorithms node_algorithms;
119
120 public:
121
122 //! @copydoc ::boost::intrusive::hashtable::hashtable(const bucket_traits &,const hasher &,const key_equal &,const value_traits &)
123 BOOST_INTRUSIVE_FORCEINLINE explicit unordered_set_impl( const bucket_traits &b_traits
124 , const hasher & hash_func = hasher()
125 , const key_equal &equal_func = key_equal()
126 , const value_traits &v_traits = value_traits())
127 : table_type(b_traits, hash_func, equal_func, v_traits)
128 {}
129
130 //! @copydoc ::boost::intrusive::hashtable::hashtable(bool,Iterator,Iterator,const bucket_traits &,const hasher &,const key_equal &,const value_traits &)
131 template<class Iterator>
132 BOOST_INTRUSIVE_FORCEINLINE unordered_set_impl( Iterator b
133 , Iterator e
134 , const bucket_traits &b_traits
135 , const hasher & hash_func = hasher()
136 , const key_equal &equal_func = key_equal()
137 , const value_traits &v_traits = value_traits())
138 : table_type(true, b, e, b_traits, hash_func, equal_func, v_traits)
139 {}
140
141 //! @copydoc ::boost::intrusive::hashtable::hashtable(hashtable&&)
142 BOOST_INTRUSIVE_FORCEINLINE unordered_set_impl(BOOST_RV_REF(unordered_set_impl) x)
143 : table_type(BOOST_MOVE_BASE(table_type, x))
144 {}
145
146 //! @copydoc ::boost::intrusive::hashtable::operator=(hashtable&&)
147 BOOST_INTRUSIVE_FORCEINLINE unordered_set_impl& operator=(BOOST_RV_REF(unordered_set_impl) x)
148 { return static_cast<unordered_set_impl&>(table_type::operator=(BOOST_MOVE_BASE(table_type, x))); }
149
150 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
151 //! @copydoc ::boost::intrusive::hashtable::~hashtable()
152 ~unordered_set_impl();
153
154 //! @copydoc ::boost::intrusive::hashtable::begin()
155 iterator begin();
156
157 //! @copydoc ::boost::intrusive::hashtable::begin()const
158 const_iterator begin() const;
159
160 //! @copydoc ::boost::intrusive::hashtable::cbegin()const
161 const_iterator cbegin() const;
162
163 //! @copydoc ::boost::intrusive::hashtable::end()
164 iterator end();
165
166 //! @copydoc ::boost::intrusive::hashtable::end()const
167 const_iterator end() const;
168
169 //! @copydoc ::boost::intrusive::hashtable::cend()const
170 const_iterator cend() const;
171
172 //! @copydoc ::boost::intrusive::hashtable::hash_function()const
173 hasher hash_function() const;
174
175 //! @copydoc ::boost::intrusive::hashtable::key_eq()const
176 key_equal key_eq() const;
177
178 //! @copydoc ::boost::intrusive::hashtable::empty()const
179 bool empty() const;
180
181 //! @copydoc ::boost::intrusive::hashtable::size()const
182 size_type size() const;
183
184 //! @copydoc ::boost::intrusive::hashtable::hashtable
185 void swap(unordered_set_impl& other);
186
187 //! @copydoc ::boost::intrusive::hashtable::clone_from(const hashtable&,Cloner,Disposer)
188 template <class Cloner, class Disposer>
189 void clone_from(const unordered_set_impl &src, Cloner cloner, Disposer disposer);
190
191 #else
192
193 using table_type::clone_from;
194
195 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
196
197 //! @copydoc ::boost::intrusive::hashtable::clone_from(hashtable&&,Cloner,Disposer)
198 template <class Cloner, class Disposer>
199 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(unordered_set_impl) src, Cloner cloner, Disposer disposer)
200 { table_type::clone_from(BOOST_MOVE_BASE(table_type, src), cloner, disposer); }
201
202 //! @copydoc ::boost::intrusive::hashtable::insert_unique(reference)
203 BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert(reference value)
204 { return table_type::insert_unique(value); }
205
206 //! @copydoc ::boost::intrusive::hashtable::insert_unique(Iterator,Iterator)
207 template<class Iterator>
208 BOOST_INTRUSIVE_FORCEINLINE void insert(Iterator b, Iterator e)
209 { table_type::insert_unique(b, e); }
210
211 //! @copydoc ::boost::intrusive::hashtable::insert_unique_check(const key_type&,insert_commit_data&)
212 BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_check(const key_type &key, insert_commit_data &commit_data)
213 { return table_type::insert_unique_check(key, commit_data); }
214
215 //! @copydoc ::boost::intrusive::hashtable::insert_unique_check(const KeyType&,KeyHasher,KeyEqual,insert_commit_data&)
216 template<class KeyType, class KeyHasher, class KeyEqual>
217 BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_check
218 (const KeyType &key, KeyHasher hasher, KeyEqual key_value_equal, insert_commit_data &commit_data)
219 { return table_type::insert_unique_check(key, hasher, key_value_equal, commit_data); }
220
221 //! @copydoc ::boost::intrusive::hashtable::insert_unique_commit
222 BOOST_INTRUSIVE_FORCEINLINE iterator insert_commit(reference value, const insert_commit_data &commit_data)
223 { return table_type::insert_unique_commit(value, commit_data); }
224
225 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
226
227 //! @copydoc ::boost::intrusive::hashtable::erase(const_iterator)
228 void erase(const_iterator i);
229
230 //! @copydoc ::boost::intrusive::hashtable::erase(const_iterator,const_iterator)
231 void erase(const_iterator b, const_iterator e);
232
233 //! @copydoc ::boost::intrusive::hashtable::erase(const key_type &)
234 size_type erase(const key_type &key);
235
236 //! @copydoc ::boost::intrusive::hashtable::erase(const KeyType&,KeyHasher,KeyEqual)
237 template<class KeyType, class KeyHasher, class KeyEqual>
238 size_type erase(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func);
239
240 //! @copydoc ::boost::intrusive::hashtable::erase_and_dispose(const_iterator,Disposer)
241 template<class Disposer>
242 BOOST_INTRUSIVE_DOC1ST(void
243 , typename detail::disable_if_convertible<Disposer BOOST_INTRUSIVE_I const_iterator>::type)
244 erase_and_dispose(const_iterator i, Disposer disposer);
245
246 //! @copydoc ::boost::intrusive::hashtable::erase_and_dispose(const_iterator,const_iterator,Disposer)
247 template<class Disposer>
248 void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
249
250 //! @copydoc ::boost::intrusive::hashtable::erase_and_dispose(const key_type &,Disposer)
251 template<class Disposer>
252 size_type erase_and_dispose(const key_type &key, Disposer disposer);
253
254 //! @copydoc ::boost::intrusive::hashtable::erase_and_dispose(const KeyType&,KeyHasher,KeyEqual,Disposer)
255 template<class KeyType, class KeyHasher, class KeyEqual, class Disposer>
256 size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func, Disposer disposer);
257
258 //! @copydoc ::boost::intrusive::hashtable::clear
259 void clear();
260
261 //! @copydoc ::boost::intrusive::hashtable::clear_and_dispose
262 template<class Disposer>
263 void clear_and_dispose(Disposer disposer);
264
265 //! @copydoc ::boost::intrusive::hashtable::count(const key_type &)const
266 size_type count(const key_type &key) const;
267
268 //! @copydoc ::boost::intrusive::hashtable::count(const KeyType&,KeyHasher,KeyEqual)const
269 template<class KeyType, class KeyHasher, class KeyEqual>
270 size_type count(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func) const;
271
272 //! @copydoc ::boost::intrusive::hashtable::find(const key_type &)
273 iterator find(const key_type &key);
274
275 //! @copydoc ::boost::intrusive::hashtable::find(const KeyType &,KeyHasher,KeyEqual)
276 template<class KeyType, class KeyHasher, class KeyEqual>
277 iterator find(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func);
278
279 //! @copydoc ::boost::intrusive::hashtable::count(const key_type &)const
280 const_iterator find(const key_type &key) const;
281
282 //! @copydoc ::boost::intrusive::hashtable::find(const KeyType &,KeyHasher,KeyEqual)const
283 template<class KeyType, class KeyHasher, class KeyEqual>
284 const_iterator find(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func) const;
285 #endif
286
287 //! @copydoc ::boost::intrusive::hashtable::equal_range(const key_type&)
288 std::pair<iterator,iterator> equal_range(const key_type &key)
289 { return this->equal_range(key, this->hash_function(), this->key_eq()); }
290
291 //! @copydoc ::boost::intrusive::hashtable::equal_range(const KeyType &,KeyHasher,KeyEqual)
292 template<class KeyType, class KeyHasher, class KeyEqual>
293 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func)
294 { return this->priv_equal_range<iterator>(*this, key, hash_func, equal_func); }
295
296 //! @copydoc ::boost::intrusive::hashtable::equal_range(const key_type&)const
297 std::pair<const_iterator, const_iterator>
298 equal_range(const key_type &key) const
299 { return this->equal_range(key, this->hash_function(), this->key_eq()); }
300
301 //! @copydoc ::boost::intrusive::hashtable::equal_range(const KeyType &,KeyHasher,KeyEqual)const
302 template<class KeyType, class KeyHasher, class KeyEqual>
303 std::pair<const_iterator, const_iterator>
304 equal_range(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func) const
305 { return this->priv_equal_range<const_iterator>(*this, key, hash_func, equal_func); }
306
307 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
308 //! @copydoc ::boost::intrusive::hashtable::iterator_to(reference)
309 iterator iterator_to(reference value);
310
311 //! @copydoc ::boost::intrusive::hashtable::iterator_to(const_reference)const
312 const_iterator iterator_to(const_reference value) const;
313
314 //! @copydoc ::boost::intrusive::hashtable::s_local_iterator_to(reference)
315 static local_iterator s_local_iterator_to(reference value);
316
317 //! @copydoc ::boost::intrusive::hashtable::s_local_iterator_to(const_reference)
318 static const_local_iterator s_local_iterator_to(const_reference value);
319
320 //! @copydoc ::boost::intrusive::hashtable::local_iterator_to(reference)
321 local_iterator local_iterator_to(reference value);
322
323 //! @copydoc ::boost::intrusive::hashtable::local_iterator_to(const_reference)
324 const_local_iterator local_iterator_to(const_reference value) const;
325
326 //! @copydoc ::boost::intrusive::hashtable::bucket_count
327 size_type bucket_count() const;
328
329 //! @copydoc ::boost::intrusive::hashtable::bucket_size
330 size_type bucket_size(size_type n) const;
331
332 //! @copydoc ::boost::intrusive::hashtable::bucket(const key_type&)const
333 size_type bucket(const key_type& k) const;
334
335 //! @copydoc ::boost::intrusive::hashtable::bucket(const KeyType&,KeyHasher)const
336 template<class KeyType, class KeyHasher>
337 size_type bucket(const KeyType& k, KeyHasher hash_func) const;
338
339 //! @copydoc ::boost::intrusive::hashtable::bucket_pointer
340 bucket_ptr bucket_pointer() const;
341
342 //! @copydoc ::boost::intrusive::hashtable::begin(size_type)
343 local_iterator begin(size_type n);
344
345 //! @copydoc ::boost::intrusive::hashtable::begin(size_type)const
346 const_local_iterator begin(size_type n) const;
347
348 //! @copydoc ::boost::intrusive::hashtable::cbegin(size_type)const
349 const_local_iterator cbegin(size_type n) const;
350
351 //! @copydoc ::boost::intrusive::hashtable::end(size_type)
352 local_iterator end(size_type n);
353
354 //! @copydoc ::boost::intrusive::hashtable::end(size_type)const
355 const_local_iterator end(size_type n) const;
356
357 //! @copydoc ::boost::intrusive::hashtable::cend(size_type)const
358 const_local_iterator cend(size_type n) const;
359
360 //! @copydoc ::boost::intrusive::hashtable::rehash(const bucket_traits &)
361 void rehash(const bucket_traits &new_bucket_traits);
362
363 //! @copydoc ::boost::intrusive::hashtable::full_rehash
364 void full_rehash();
365
366 //! @copydoc ::boost::intrusive::hashtable::incremental_rehash(bool)
367 bool incremental_rehash(bool grow = true);
368
369 //! @copydoc ::boost::intrusive::hashtable::incremental_rehash(const bucket_traits &)
370 bool incremental_rehash(const bucket_traits &new_bucket_traits);
371
372 //! @copydoc ::boost::intrusive::hashtable::split_count
373 size_type split_count() const;
374
375 //! @copydoc ::boost::intrusive::hashtable::suggested_upper_bucket_count
376 static size_type suggested_upper_bucket_count(size_type n);
377
378 //! @copydoc ::boost::intrusive::hashtable::suggested_lower_bucket_count
379 static size_type suggested_lower_bucket_count(size_type n);
380
381 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
382
383 friend bool operator==(const unordered_set_impl &x, const unordered_set_impl &y)
384 {
385 if(table_type::constant_time_size && x.size() != y.size()){
386 return false;
387 }
388 //Find each element of x in y
389 for (const_iterator ix = x.cbegin(), ex = x.cend(), ey = y.cend(); ix != ex; ++ix){
390 const_iterator iy = y.find(key_of_value()(*ix));
391 if (iy == ey || !(*ix == *iy))
392 return false;
393 }
394 return true;
395 }
396
397 friend bool operator!=(const unordered_set_impl &x, const unordered_set_impl &y)
398 { return !(x == y); }
399
400 friend bool operator<(const unordered_set_impl &x, const unordered_set_impl &y)
401 { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
402
403 friend bool operator>(const unordered_set_impl &x, const unordered_set_impl &y)
404 { return y < x; }
405
406 friend bool operator<=(const unordered_set_impl &x, const unordered_set_impl &y)
407 { return !(y < x); }
408
409 friend bool operator>=(const unordered_set_impl &x, const unordered_set_impl &y)
410 { return !(x < y); }
411};
412
413//! Helper metafunction to define an \c unordered_set that yields to the same type when the
414//! same options (either explicitly or implicitly) are used.
415#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
416template<class T, class ...Options>
417#else
418template<class T, class O1 = void, class O2 = void
419 , class O3 = void, class O4 = void
420 , class O5 = void, class O6 = void
421 , class O7 = void, class O8 = void
422 , class O9 = void, class O10= void
423 >
424#endif
425struct make_unordered_set
426{
427 /// @cond
428 typedef typename pack_options
429 < hashtable_defaults,
430 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
431 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
432 #else
433 Options...
434 #endif
435 >::type packed_options;
436
437 typedef typename detail::get_value_traits
438 <T, typename packed_options::proto_value_traits>::type value_traits;
439
440 typedef typename make_bucket_traits
441 <T, true, packed_options>::type bucket_traits;
442
443 typedef unordered_set_impl
444 < value_traits
445 , typename packed_options::key_of_value
446 , typename packed_options::hash
447 , typename packed_options::equal
448 , typename packed_options::size_type
449 , bucket_traits
450 , (std::size_t(true)*hash_bool_flags::unique_keys_pos)
451 | (std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos)
452 | (std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos)
453 | (std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos)
454 | (std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos)
455 | (std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos)
456 > implementation_defined;
457
458 /// @endcond
459 typedef implementation_defined type;
460};
461
462#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
463
464#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
465template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
466#else
467template<class T, class ...Options>
468#endif
469class unordered_set
470 : public make_unordered_set<T,
471 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
472 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
473 #else
474 Options...
475 #endif
476 >::type
477{
478 typedef typename make_unordered_set
479 <T,
480 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
481 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
482 #else
483 Options...
484 #endif
485 >::type Base;
486
487 //Assert if passed value traits are compatible with the type
488 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
489 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_set)
490
491 public:
492 typedef typename Base::value_traits value_traits;
493 typedef typename Base::bucket_traits bucket_traits;
494 typedef typename Base::iterator iterator;
495 typedef typename Base::const_iterator const_iterator;
496 typedef typename Base::bucket_ptr bucket_ptr;
497 typedef typename Base::size_type size_type;
498 typedef typename Base::hasher hasher;
499 typedef typename Base::key_equal key_equal;
500
501 explicit unordered_set ( const bucket_traits &b_traits
502 , const hasher & hash_func = hasher()
503 , const key_equal &equal_func = key_equal()
504 , const value_traits &v_traits = value_traits())
505 : Base(b_traits, hash_func, equal_func, v_traits)
506 {}
507
508 template<class Iterator>
509 BOOST_INTRUSIVE_FORCEINLINE unordered_set
510 ( Iterator b, Iterator e
511 , const bucket_traits &b_traits
512 , const hasher & hash_func = hasher()
513 , const key_equal &equal_func = key_equal()
514 , const value_traits &v_traits = value_traits())
515 : Base(b, e, b_traits, hash_func, equal_func, v_traits)
516 {}
517
518 BOOST_INTRUSIVE_FORCEINLINE unordered_set(BOOST_RV_REF(unordered_set) x)
519 : Base(BOOST_MOVE_BASE(Base, x))
520 {}
521
522 BOOST_INTRUSIVE_FORCEINLINE unordered_set& operator=(BOOST_RV_REF(unordered_set) x)
523 { return static_cast<unordered_set&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
524
525 template <class Cloner, class Disposer>
526 BOOST_INTRUSIVE_FORCEINLINE void clone_from(const unordered_set &src, Cloner cloner, Disposer disposer)
527 { Base::clone_from(src, cloner, disposer); }
528
529 template <class Cloner, class Disposer>
530 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(unordered_set) src, Cloner cloner, Disposer disposer)
531 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
532};
533
534#endif
535
536
537//! The class template unordered_multiset is an intrusive container, that mimics most of
538//! the interface of std::tr1::unordered_multiset as described in the C++ TR1.
539//!
540//! unordered_multiset is a semi-intrusive container: each object to be stored in the
541//! container must contain a proper hook, but the container also needs
542//! additional auxiliary memory to work: unordered_multiset needs a pointer to an array
543//! of type `bucket_type` to be passed in the constructor. This bucket array must
544//! have at least the same lifetime as the container. This makes the use of
545//! unordered_multiset more complicated than purely intrusive containers.
546//! `bucket_type` is default-constructible, copyable and assignable
547//!
548//! The template parameter \c T is the type to be managed by the container.
549//! The user can specify additional options and if no options are provided
550//! default options are used.
551//!
552//! The container supports the following options:
553//! \c base_hook<>/member_hook<>/value_traits<>,
554//! \c constant_time_size<>, \c size_type<>, \c hash<> and \c equal<>
555//! \c bucket_traits<>, \c power_2_buckets<> and \c cache_begin<>.
556//!
557//! unordered_multiset only provides forward iterators but it provides 4 iterator types:
558//! iterator and const_iterator to navigate through the whole container and
559//! local_iterator and const_local_iterator to navigate through the values
560//! stored in a single bucket. Local iterators are faster and smaller.
561//!
562//! It's not recommended to use non constant-time size unordered_multisets because several
563//! key functions, like "empty()", become non-constant time functions. Non
564//! constant-time size unordered_multisets are mainly provided to support auto-unlink hooks.
565//!
566//! unordered_multiset, unlike std::unordered_set, does not make automatic rehashings nor
567//! offers functions related to a load factor. Rehashing can be explicitly requested
568//! and the user must provide a new bucket array that will be used from that moment.
569//!
570//! Since no automatic rehashing is done, iterators are never invalidated when
571//! inserting or erasing elements. Iterators are only invalidated when rehasing.
572#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
573template<class T, class ...Options>
574#else
575template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class SizeType, class BucketTraits, std::size_t BoolFlags>
576#endif
577class unordered_multiset_impl
578 : public hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>
579{
580 /// @cond
581 private:
582 typedef hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags> table_type;
583 /// @endcond
584
585 //Movable
586 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_multiset_impl)
587
588 typedef table_type implementation_defined;
589
590 public:
591 typedef typename implementation_defined::value_type value_type;
592 typedef typename implementation_defined::key_type key_type;
593 typedef typename implementation_defined::value_traits value_traits;
594 typedef typename implementation_defined::bucket_traits bucket_traits;
595 typedef typename implementation_defined::pointer pointer;
596 typedef typename implementation_defined::const_pointer const_pointer;
597 typedef typename implementation_defined::reference reference;
598 typedef typename implementation_defined::const_reference const_reference;
599 typedef typename implementation_defined::difference_type difference_type;
600 typedef typename implementation_defined::size_type size_type;
601 typedef typename implementation_defined::key_equal key_equal;
602 typedef typename implementation_defined::hasher hasher;
603 typedef typename implementation_defined::bucket_type bucket_type;
604 typedef typename implementation_defined::bucket_ptr bucket_ptr;
605 typedef typename implementation_defined::iterator iterator;
606 typedef typename implementation_defined::const_iterator const_iterator;
607 typedef typename implementation_defined::insert_commit_data insert_commit_data;
608 typedef typename implementation_defined::local_iterator local_iterator;
609 typedef typename implementation_defined::const_local_iterator const_local_iterator;
610 typedef typename implementation_defined::node_traits node_traits;
611 typedef typename implementation_defined::node node;
612 typedef typename implementation_defined::node_ptr node_ptr;
613 typedef typename implementation_defined::const_node_ptr const_node_ptr;
614 typedef typename implementation_defined::node_algorithms node_algorithms;
615
616 public:
617
618 //! @copydoc ::boost::intrusive::hashtable::hashtable(const bucket_traits &,const hasher &,const key_equal &,const value_traits &)
619 BOOST_INTRUSIVE_FORCEINLINE explicit unordered_multiset_impl ( const bucket_traits &b_traits
620 , const hasher & hash_func = hasher()
621 , const key_equal &equal_func = key_equal()
622 , const value_traits &v_traits = value_traits())
623 : table_type(b_traits, hash_func, equal_func, v_traits)
624 {}
625
626 //! @copydoc ::boost::intrusive::hashtable::hashtable(bool,Iterator,Iterator,const bucket_traits &,const hasher &,const key_equal &,const value_traits &)
627 template<class Iterator>
628 BOOST_INTRUSIVE_FORCEINLINE unordered_multiset_impl ( Iterator b
629 , Iterator e
630 , const bucket_traits &b_traits
631 , const hasher & hash_func = hasher()
632 , const key_equal &equal_func = key_equal()
633 , const value_traits &v_traits = value_traits())
634 : table_type(false, b, e, b_traits, hash_func, equal_func, v_traits)
635 {}
636
637 //! <b>Effects</b>: to-do
638 //!
639 BOOST_INTRUSIVE_FORCEINLINE unordered_multiset_impl(BOOST_RV_REF(unordered_multiset_impl) x)
640 : table_type(BOOST_MOVE_BASE(table_type, x))
641 {}
642
643 //! <b>Effects</b>: to-do
644 //!
645 BOOST_INTRUSIVE_FORCEINLINE unordered_multiset_impl& operator=(BOOST_RV_REF(unordered_multiset_impl) x)
646 { return static_cast<unordered_multiset_impl&>(table_type::operator=(BOOST_MOVE_BASE(table_type, x))); }
647
648 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
649
650 //! @copydoc ::boost::intrusive::hashtable::~hashtable()
651 ~unordered_multiset_impl();
652
653 //! @copydoc ::boost::intrusive::hashtable::begin()
654 iterator begin();
655
656 //! @copydoc ::boost::intrusive::hashtable::begin()const
657 const_iterator begin() const;
658
659 //! @copydoc ::boost::intrusive::hashtable::cbegin()const
660 const_iterator cbegin() const;
661
662 //! @copydoc ::boost::intrusive::hashtable::end()
663 iterator end();
664
665 //! @copydoc ::boost::intrusive::hashtable::end()const
666 const_iterator end() const;
667
668 //! @copydoc ::boost::intrusive::hashtable::cend()const
669 const_iterator cend() const;
670
671 //! @copydoc ::boost::intrusive::hashtable::hash_function()const
672 hasher hash_function() const;
673
674 //! @copydoc ::boost::intrusive::hashtable::key_eq()const
675 key_equal key_eq() const;
676
677 //! @copydoc ::boost::intrusive::hashtable::empty()const
678 bool empty() const;
679
680 //! @copydoc ::boost::intrusive::hashtable::size()const
681 size_type size() const;
682
683 //! @copydoc ::boost::intrusive::hashtable::hashtable
684 void swap(unordered_multiset_impl& other);
685
686 //! @copydoc ::boost::intrusive::hashtable::clone_from(const hashtable&,Cloner,Disposer)
687 template <class Cloner, class Disposer>
688 void clone_from(const unordered_multiset_impl &src, Cloner cloner, Disposer disposer);
689
690 #else
691
692 using table_type::clone_from;
693
694 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
695
696 //! @copydoc ::boost::intrusive::hashtable::clone_from(hashtable&&,Cloner,Disposer)
697 template <class Cloner, class Disposer>
698 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(unordered_multiset_impl) src, Cloner cloner, Disposer disposer)
699 { table_type::clone_from(BOOST_MOVE_BASE(table_type, src), cloner, disposer); }
700
701 //! @copydoc ::boost::intrusive::hashtable::insert_equal(reference)
702 BOOST_INTRUSIVE_FORCEINLINE iterator insert(reference value)
703 { return table_type::insert_equal(value); }
704
705 //! @copydoc ::boost::intrusive::hashtable::insert_equal(Iterator,Iterator)
706 template<class Iterator>
707 BOOST_INTRUSIVE_FORCEINLINE void insert(Iterator b, Iterator e)
708 { table_type::insert_equal(b, e); }
709
710 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
711
712 //! @copydoc ::boost::intrusive::hashtable::erase(const_iterator)
713 void erase(const_iterator i);
714
715 //! @copydoc ::boost::intrusive::hashtable::erase(const_iterator,const_iterator)
716 void erase(const_iterator b, const_iterator e);
717
718 //! @copydoc ::boost::intrusive::hashtable::erase(const key_type &)
719 size_type erase(const key_type &key);
720
721 //! @copydoc ::boost::intrusive::hashtable::erase(const KeyType&,KeyHasher,KeyEqual)
722 template<class KeyType, class KeyHasher, class KeyEqual>
723 size_type erase(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func);
724
725 //! @copydoc ::boost::intrusive::hashtable::erase_and_dispose(const_iterator,Disposer)
726 template<class Disposer>
727 BOOST_INTRUSIVE_DOC1ST(void
728 , typename detail::disable_if_convertible<Disposer BOOST_INTRUSIVE_I const_iterator>::type)
729 erase_and_dispose(const_iterator i, Disposer disposer);
730
731 //! @copydoc ::boost::intrusive::hashtable::erase_and_dispose(const_iterator,const_iterator,Disposer)
732 template<class Disposer>
733 void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
734
735 //! @copydoc ::boost::intrusive::hashtable::erase_and_dispose(const key_type &,Disposer)
736 template<class Disposer>
737 size_type erase_and_dispose(const key_type &key, Disposer disposer);
738
739 //! @copydoc ::boost::intrusive::hashtable::erase_and_dispose(const KeyType&,KeyHasher,KeyEqual,Disposer)
740 template<class KeyType, class KeyHasher, class KeyEqual, class Disposer>
741 size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func, Disposer disposer);
742
743 //! @copydoc ::boost::intrusive::hashtable::clear
744 void clear();
745
746 //! @copydoc ::boost::intrusive::hashtable::clear_and_dispose
747 template<class Disposer>
748 void clear_and_dispose(Disposer disposer);
749
750 //! @copydoc ::boost::intrusive::hashtable::count(const key_type &)const
751 size_type count(const key_type &key) const;
752
753 //! @copydoc ::boost::intrusive::hashtable::count(const KeyType&,KeyHasher,KeyEqual)const
754 template<class KeyType, class KeyHasher, class KeyEqual>
755 size_type count(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func) const;
756
757 //! @copydoc ::boost::intrusive::hashtable::find(const key_type &)
758 iterator find(const key_type &key);
759
760 //! @copydoc ::boost::intrusive::hashtable::find(const KeyType &,KeyHasher,KeyEqual)
761 template<class KeyType, class KeyHasher, class KeyEqual>
762 iterator find(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func);
763
764 //! @copydoc ::boost::intrusive::hashtable::count(const key_type &)const
765 const_iterator find(const key_type &key) const;
766
767 //! @copydoc ::boost::intrusive::hashtable::find(const KeyType &,KeyHasher,KeyEqual)const
768 template<class KeyType, class KeyHasher, class KeyEqual>
769 const_iterator find(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func) const;
770
771 //! @copydoc ::boost::intrusive::hashtable::equal_range(const key_type&)
772 std::pair<iterator,iterator> equal_range(const key_type &key);
773
774 //! @copydoc ::boost::intrusive::hashtable::equal_range(const KeyType &,KeyHasher,KeyEqual)
775 template<class KeyType, class KeyHasher, class KeyEqual>
776 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func);
777
778 //! @copydoc ::boost::intrusive::hashtable::equal_range(const key_type&)const
779 std::pair<const_iterator, const_iterator>
780 equal_range(const key_type &key) const;
781
782 //! @copydoc ::boost::intrusive::hashtable::equal_range(const KeyType &,KeyHasher,KeyEqual)const
783 template<class KeyType, class KeyHasher, class KeyEqual>
784 std::pair<const_iterator, const_iterator>
785 equal_range(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func) const;
786
787 //! @copydoc ::boost::intrusive::hashtable::iterator_to(reference)
788 iterator iterator_to(reference value);
789
790 //! @copydoc ::boost::intrusive::hashtable::iterator_to(const_reference)const
791 const_iterator iterator_to(const_reference value) const;
792
793 //! @copydoc ::boost::intrusive::hashtable::s_local_iterator_to(reference)
794 static local_iterator s_local_iterator_to(reference value);
795
796 //! @copydoc ::boost::intrusive::hashtable::s_local_iterator_to(const_reference)
797 static const_local_iterator s_local_iterator_to(const_reference value);
798
799 //! @copydoc ::boost::intrusive::hashtable::local_iterator_to(reference)
800 local_iterator local_iterator_to(reference value);
801
802 //! @copydoc ::boost::intrusive::hashtable::local_iterator_to(const_reference)
803 const_local_iterator local_iterator_to(const_reference value) const;
804
805 //! @copydoc ::boost::intrusive::hashtable::bucket_count
806 size_type bucket_count() const;
807
808 //! @copydoc ::boost::intrusive::hashtable::bucket_size
809 size_type bucket_size(size_type n) const;
810
811 //! @copydoc ::boost::intrusive::hashtable::bucket(const key_type&)const
812 size_type bucket(const key_type& k) const;
813
814 //! @copydoc ::boost::intrusive::hashtable::bucket(const KeyType&,KeyHasher)const
815 template<class KeyType, class KeyHasher>
816 size_type bucket(const KeyType& k, KeyHasher hash_func) const;
817
818 //! @copydoc ::boost::intrusive::hashtable::bucket_pointer
819 bucket_ptr bucket_pointer() const;
820
821 //! @copydoc ::boost::intrusive::hashtable::begin(size_type)
822 local_iterator begin(size_type n);
823
824 //! @copydoc ::boost::intrusive::hashtable::begin(size_type)const
825 const_local_iterator begin(size_type n) const;
826
827 //! @copydoc ::boost::intrusive::hashtable::cbegin(size_type)const
828 const_local_iterator cbegin(size_type n) const;
829
830 //! @copydoc ::boost::intrusive::hashtable::end(size_type)
831 local_iterator end(size_type n);
832
833 //! @copydoc ::boost::intrusive::hashtable::end(size_type)const
834 const_local_iterator end(size_type n) const;
835
836 //! @copydoc ::boost::intrusive::hashtable::cend(size_type)const
837 const_local_iterator cend(size_type n) const;
838
839 //! @copydoc ::boost::intrusive::hashtable::rehash(const bucket_traits &)
840 void rehash(const bucket_traits &new_bucket_traits);
841
842 //! @copydoc ::boost::intrusive::hashtable::full_rehash
843 void full_rehash();
844
845 //! @copydoc ::boost::intrusive::hashtable::incremental_rehash(bool)
846 bool incremental_rehash(bool grow = true);
847
848 //! @copydoc ::boost::intrusive::hashtable::incremental_rehash(const bucket_traits &)
849 bool incremental_rehash(const bucket_traits &new_bucket_traits);
850
851 //! @copydoc ::boost::intrusive::hashtable::split_count
852 size_type split_count() const;
853
854 //! @copydoc ::boost::intrusive::hashtable::suggested_upper_bucket_count
855 static size_type suggested_upper_bucket_count(size_type n);
856
857 //! @copydoc ::boost::intrusive::hashtable::suggested_lower_bucket_count
858 static size_type suggested_lower_bucket_count(size_type n);
859
860 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
861};
862
863//! Helper metafunction to define an \c unordered_multiset that yields to the same type when the
864//! same options (either explicitly or implicitly) are used.
865#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
866template<class T, class ...Options>
867#else
868template<class T, class O1 = void, class O2 = void
869 , class O3 = void, class O4 = void
870 , class O5 = void, class O6 = void
871 , class O7 = void, class O8 = void
872 , class O9 = void, class O10= void
873 >
874#endif
875struct make_unordered_multiset
876{
877 /// @cond
878 typedef typename pack_options
879 < hashtable_defaults,
880 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
881 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
882 #else
883 Options...
884 #endif
885 >::type packed_options;
886
887 typedef typename detail::get_value_traits
888 <T, typename packed_options::proto_value_traits>::type value_traits;
889
890 typedef typename make_bucket_traits
891 <T, true, packed_options>::type bucket_traits;
892
893 typedef unordered_multiset_impl
894 < value_traits
895 , typename packed_options::key_of_value
896 , typename packed_options::hash
897 , typename packed_options::equal
898 , typename packed_options::size_type
899 , bucket_traits
900 , (std::size_t(false)*hash_bool_flags::unique_keys_pos)
901 | (std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos)
902 | (std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos)
903 | (std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos)
904 | (std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos)
905 | (std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos)
906 > implementation_defined;
907
908 /// @endcond
909 typedef implementation_defined type;
910};
911
912#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
913
914#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
915template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
916#else
917template<class T, class ...Options>
918#endif
919class unordered_multiset
920 : public make_unordered_multiset<T,
921 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
922 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
923 #else
924 Options...
925 #endif
926 >::type
927{
928 typedef typename make_unordered_multiset
929 <T,
930 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
931 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
932 #else
933 Options...
934 #endif
935 >::type Base;
936 //Assert if passed value traits are compatible with the type
937 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
938 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_multiset)
939
940 public:
941 typedef typename Base::value_traits value_traits;
942 typedef typename Base::bucket_traits bucket_traits;
943 typedef typename Base::iterator iterator;
944 typedef typename Base::const_iterator const_iterator;
945 typedef typename Base::bucket_ptr bucket_ptr;
946 typedef typename Base::size_type size_type;
947 typedef typename Base::hasher hasher;
948 typedef typename Base::key_equal key_equal;
949
950 explicit unordered_multiset( const bucket_traits &b_traits
951 , const hasher & hash_func = hasher()
952 , const key_equal &equal_func = key_equal()
953 , const value_traits &v_traits = value_traits())
954 : Base(b_traits, hash_func, equal_func, v_traits)
955 {}
956
957 template<class Iterator> BOOST_INTRUSIVE_FORCEINLINE
958 unordered_multiset( Iterator b
959 , Iterator e
960 , const bucket_traits &b_traits
961 , const hasher & hash_func = hasher()
962 , const key_equal &equal_func = key_equal()
963 , const value_traits &v_traits = value_traits())
964 : Base(b, e, b_traits, hash_func, equal_func, v_traits)
965 {}
966
967 BOOST_INTRUSIVE_FORCEINLINE unordered_multiset(BOOST_RV_REF(unordered_multiset) x)
968 : Base(BOOST_MOVE_BASE(Base, x))
969 {}
970
971 BOOST_INTRUSIVE_FORCEINLINE unordered_multiset& operator=(BOOST_RV_REF(unordered_multiset) x)
972 { return static_cast<unordered_multiset&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
973
974 template <class Cloner, class Disposer>
975 BOOST_INTRUSIVE_FORCEINLINE void clone_from(const unordered_multiset &src, Cloner cloner, Disposer disposer)
976 { Base::clone_from(src, cloner, disposer); }
977
978 template <class Cloner, class Disposer>
979 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(unordered_multiset) src, Cloner cloner, Disposer disposer)
980 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
981};
982
983#endif
984
985} //namespace intrusive
986} //namespace boost
987
988#include <boost/intrusive/detail/config_end.hpp>
989
990#endif //BOOST_INTRUSIVE_UNORDERED_SET_HPP
991