1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Olaf Krzikalla 2004-2006.
4 // (C) Copyright Ion Gaztanaga 2006-2014
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)
10 // See http://www.boost.org/libs/intrusive for documentation.
12 /////////////////////////////////////////////////////////////////////////////
13 #ifndef BOOST_INTRUSIVE_UNORDERED_SET_HPP
14 #define BOOST_INTRUSIVE_UNORDERED_SET_HPP
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>
22 #if defined(BOOST_HAS_PRAGMA_ONCE)
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.
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
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.
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<>.
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.
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.
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.
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)
65 template<class T, class ...Options>
67 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class SizeType, class BucketTraits, std::size_t BoolFlags>
69 class unordered_set_impl
70 : public hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags|hash_bool_flags::unique_keys_pos>
74 typedef hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags|hash_bool_flags::unique_keys_pos> table_type;
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)
79 Iterator const it = c.find(key, hash_func, equal_func);
80 std::pair<Iterator,Iterator> ret(it, it);
88 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_set_impl)
90 typedef table_type implementation_defined;
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;
122 //! @copydoc ::boost::intrusive::hashtable::hashtable(const bucket_traits &,const hasher &,const key_equal &,const value_traits &)
123 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)
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 unordered_set_impl( Iterator b
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)
141 //! @copydoc ::boost::intrusive::hashtable::hashtable(hashtable&&)
142 unordered_set_impl(BOOST_RV_REF(unordered_set_impl) x)
143 : table_type(BOOST_MOVE_BASE(table_type, x))
146 //! @copydoc ::boost::intrusive::hashtable::operator=(hashtable&&)
147 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))); }
150 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
151 //! @copydoc ::boost::intrusive::hashtable::~hashtable()
152 ~unordered_set_impl();
154 //! @copydoc ::boost::intrusive::hashtable::begin()
157 //! @copydoc ::boost::intrusive::hashtable::begin()const
158 const_iterator begin() const;
160 //! @copydoc ::boost::intrusive::hashtable::cbegin()const
161 const_iterator cbegin() const;
163 //! @copydoc ::boost::intrusive::hashtable::end()
166 //! @copydoc ::boost::intrusive::hashtable::end()const
167 const_iterator end() const;
169 //! @copydoc ::boost::intrusive::hashtable::cend()const
170 const_iterator cend() const;
172 //! @copydoc ::boost::intrusive::hashtable::hash_function()const
173 hasher hash_function() const;
175 //! @copydoc ::boost::intrusive::hashtable::key_eq()const
176 key_equal key_eq() const;
178 //! @copydoc ::boost::intrusive::hashtable::empty()const
181 //! @copydoc ::boost::intrusive::hashtable::size()const
182 size_type size() const;
184 //! @copydoc ::boost::intrusive::hashtable::hashtable
185 void swap(unordered_set_impl& other);
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);
193 using table_type::clone_from;
195 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
197 //! @copydoc ::boost::intrusive::hashtable::clone_from(hashtable&&,Cloner,Disposer)
198 template <class Cloner, class Disposer>
199 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); }
202 //! @copydoc ::boost::intrusive::hashtable::insert_unique(reference)
203 std::pair<iterator, bool> insert(reference value)
204 { return table_type::insert_unique(value); }
206 //! @copydoc ::boost::intrusive::hashtable::insert_unique(Iterator,Iterator)
207 template<class Iterator>
208 void insert(Iterator b, Iterator e)
209 { table_type::insert_unique(b, e); }
211 //! @copydoc ::boost::intrusive::hashtable::insert_unique_check(const key_type&,insert_commit_data&)
212 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); }
215 //! @copydoc ::boost::intrusive::hashtable::insert_unique_check(const KeyType&,KeyHasher,KeyEqual,insert_commit_data&)
216 template<class KeyType, class KeyHasher, class KeyEqual>
217 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); }
221 //! @copydoc ::boost::intrusive::hashtable::insert_unique_commit
222 iterator insert_commit(reference value, const insert_commit_data &commit_data)
223 { return table_type::insert_unique_commit(value, commit_data); }
225 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
227 //! @copydoc ::boost::intrusive::hashtable::erase(const_iterator)
228 void erase(const_iterator i);
230 //! @copydoc ::boost::intrusive::hashtable::erase(const_iterator,const_iterator)
231 void erase(const_iterator b, const_iterator e);
233 //! @copydoc ::boost::intrusive::hashtable::erase(const key_type &)
234 size_type erase(const key_type &key);
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);
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);
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);
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);
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);
258 //! @copydoc ::boost::intrusive::hashtable::clear
261 //! @copydoc ::boost::intrusive::hashtable::clear_and_dispose
262 template<class Disposer>
263 void clear_and_dispose(Disposer disposer);
265 //! @copydoc ::boost::intrusive::hashtable::count(const key_type &)const
266 size_type count(const key_type &key) const;
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;
272 //! @copydoc ::boost::intrusive::hashtable::find(const key_type &)
273 iterator find(const key_type &key);
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);
279 //! @copydoc ::boost::intrusive::hashtable::count(const key_type &)const
280 const_iterator find(const key_type &key) const;
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;
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()); }
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); }
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()); }
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); }
307 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
308 //! @copydoc ::boost::intrusive::hashtable::iterator_to(reference)
309 iterator iterator_to(reference value);
311 //! @copydoc ::boost::intrusive::hashtable::iterator_to(const_reference)const
312 const_iterator iterator_to(const_reference value) const;
314 //! @copydoc ::boost::intrusive::hashtable::s_local_iterator_to(reference)
315 static local_iterator s_local_iterator_to(reference value);
317 //! @copydoc ::boost::intrusive::hashtable::s_local_iterator_to(const_reference)
318 static const_local_iterator s_local_iterator_to(const_reference value);
320 //! @copydoc ::boost::intrusive::hashtable::local_iterator_to(reference)
321 local_iterator local_iterator_to(reference value);
323 //! @copydoc ::boost::intrusive::hashtable::local_iterator_to(const_reference)
324 const_local_iterator local_iterator_to(const_reference value) const;
326 //! @copydoc ::boost::intrusive::hashtable::bucket_count
327 size_type bucket_count() const;
329 //! @copydoc ::boost::intrusive::hashtable::bucket_size
330 size_type bucket_size(size_type n) const;
332 //! @copydoc ::boost::intrusive::hashtable::bucket(const key_type&)const
333 size_type bucket(const key_type& k) const;
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;
339 //! @copydoc ::boost::intrusive::hashtable::bucket_pointer
340 bucket_ptr bucket_pointer() const;
342 //! @copydoc ::boost::intrusive::hashtable::begin(size_type)
343 local_iterator begin(size_type n);
345 //! @copydoc ::boost::intrusive::hashtable::begin(size_type)const
346 const_local_iterator begin(size_type n) const;
348 //! @copydoc ::boost::intrusive::hashtable::cbegin(size_type)const
349 const_local_iterator cbegin(size_type n) const;
351 //! @copydoc ::boost::intrusive::hashtable::end(size_type)
352 local_iterator end(size_type n);
354 //! @copydoc ::boost::intrusive::hashtable::end(size_type)const
355 const_local_iterator end(size_type n) const;
357 //! @copydoc ::boost::intrusive::hashtable::cend(size_type)const
358 const_local_iterator cend(size_type n) const;
360 //! @copydoc ::boost::intrusive::hashtable::rehash(const bucket_traits &)
361 void rehash(const bucket_traits &new_bucket_traits);
363 //! @copydoc ::boost::intrusive::hashtable::full_rehash
366 //! @copydoc ::boost::intrusive::hashtable::incremental_rehash(bool)
367 bool incremental_rehash(bool grow = true);
369 //! @copydoc ::boost::intrusive::hashtable::incremental_rehash(const bucket_traits &)
370 bool incremental_rehash(const bucket_traits &new_bucket_traits);
372 //! @copydoc ::boost::intrusive::hashtable::split_count
373 size_type split_count() const;
375 //! @copydoc ::boost::intrusive::hashtable::suggested_upper_bucket_count
376 static size_type suggested_upper_bucket_count(size_type n);
378 //! @copydoc ::boost::intrusive::hashtable::suggested_lower_bucket_count
379 static size_type suggested_lower_bucket_count(size_type n);
381 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
383 friend bool operator==(const unordered_set_impl &x, const unordered_set_impl &y)
385 if(table_type::constant_time_size && x.size() != y.size()){
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))
397 friend bool operator!=(const unordered_set_impl &x, const unordered_set_impl &y)
398 { return !(x == y); }
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()); }
403 friend bool operator>(const unordered_set_impl &x, const unordered_set_impl &y)
406 friend bool operator<=(const unordered_set_impl &x, const unordered_set_impl &y)
409 friend bool operator>=(const unordered_set_impl &x, const unordered_set_impl &y)
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)
416 template<class T, class ...Options>
418 template<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
425 struct make_unordered_set
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
435 >::type packed_options;
437 typedef typename detail::get_value_traits
438 <T, typename packed_options::proto_value_traits>::type value_traits;
440 typedef typename make_bucket_traits
441 <T, true, packed_options>::type bucket_traits;
443 typedef unordered_set_impl
445 , typename packed_options::key_of_value
446 , typename packed_options::hash
447 , typename packed_options::equal
448 , typename packed_options::size_type
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;
459 typedef implementation_defined type;
462 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
464 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
465 template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
467 template<class T, class ...Options>
470 : public make_unordered_set<T,
471 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
472 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
478 typedef typename make_unordered_set
480 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
481 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
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)
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;
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)
508 template<class Iterator>
509 unordered_set ( Iterator b
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)
518 unordered_set(BOOST_RV_REF(unordered_set) x)
519 : Base(BOOST_MOVE_BASE(Base, x))
522 unordered_set& operator=(BOOST_RV_REF(unordered_set) x)
523 { return static_cast<unordered_set&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
525 template <class Cloner, class Disposer>
526 void clone_from(const unordered_set &src, Cloner cloner, Disposer disposer)
527 { Base::clone_from(src, cloner, disposer); }
529 template <class Cloner, class Disposer>
530 void clone_from(BOOST_RV_REF(unordered_set) src, Cloner cloner, Disposer disposer)
531 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
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.
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
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.
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<>.
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.
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.
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.
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)
573 template<class T, class ...Options>
575 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class SizeType, class BucketTraits, std::size_t BoolFlags>
577 class unordered_multiset_impl
578 : public hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>
582 typedef hashtable_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags> table_type;
586 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_multiset_impl)
588 typedef table_type implementation_defined;
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;
618 //! @copydoc ::boost::intrusive::hashtable::hashtable(const bucket_traits &,const hasher &,const key_equal &,const value_traits &)
619 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)
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 unordered_multiset_impl ( Iterator b
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)
637 //! <b>Effects</b>: to-do
639 unordered_multiset_impl(BOOST_RV_REF(unordered_multiset_impl) x)
640 : table_type(BOOST_MOVE_BASE(table_type, x))
643 //! <b>Effects</b>: to-do
645 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))); }
648 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
650 //! @copydoc ::boost::intrusive::hashtable::~hashtable()
651 ~unordered_multiset_impl();
653 //! @copydoc ::boost::intrusive::hashtable::begin()
656 //! @copydoc ::boost::intrusive::hashtable::begin()const
657 const_iterator begin() const;
659 //! @copydoc ::boost::intrusive::hashtable::cbegin()const
660 const_iterator cbegin() const;
662 //! @copydoc ::boost::intrusive::hashtable::end()
665 //! @copydoc ::boost::intrusive::hashtable::end()const
666 const_iterator end() const;
668 //! @copydoc ::boost::intrusive::hashtable::cend()const
669 const_iterator cend() const;
671 //! @copydoc ::boost::intrusive::hashtable::hash_function()const
672 hasher hash_function() const;
674 //! @copydoc ::boost::intrusive::hashtable::key_eq()const
675 key_equal key_eq() const;
677 //! @copydoc ::boost::intrusive::hashtable::empty()const
680 //! @copydoc ::boost::intrusive::hashtable::size()const
681 size_type size() const;
683 //! @copydoc ::boost::intrusive::hashtable::hashtable
684 void swap(unordered_multiset_impl& other);
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);
692 using table_type::clone_from;
694 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
696 //! @copydoc ::boost::intrusive::hashtable::clone_from(hashtable&&,Cloner,Disposer)
697 template <class Cloner, class Disposer>
698 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); }
701 //! @copydoc ::boost::intrusive::hashtable::insert_equal(reference)
702 iterator insert(reference value)
703 { return table_type::insert_equal(value); }
705 //! @copydoc ::boost::intrusive::hashtable::insert_equal(Iterator,Iterator)
706 template<class Iterator>
707 void insert(Iterator b, Iterator e)
708 { table_type::insert_equal(b, e); }
710 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
712 //! @copydoc ::boost::intrusive::hashtable::erase(const_iterator)
713 void erase(const_iterator i);
715 //! @copydoc ::boost::intrusive::hashtable::erase(const_iterator,const_iterator)
716 void erase(const_iterator b, const_iterator e);
718 //! @copydoc ::boost::intrusive::hashtable::erase(const key_type &)
719 size_type erase(const key_type &key);
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);
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);
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);
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);
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);
743 //! @copydoc ::boost::intrusive::hashtable::clear
746 //! @copydoc ::boost::intrusive::hashtable::clear_and_dispose
747 template<class Disposer>
748 void clear_and_dispose(Disposer disposer);
750 //! @copydoc ::boost::intrusive::hashtable::count(const key_type &)const
751 size_type count(const key_type &key) const;
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;
757 //! @copydoc ::boost::intrusive::hashtable::find(const key_type &)
758 iterator find(const key_type &key);
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);
764 //! @copydoc ::boost::intrusive::hashtable::count(const key_type &)const
765 const_iterator find(const key_type &key) const;
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;
771 //! @copydoc ::boost::intrusive::hashtable::equal_range(const key_type&)
772 std::pair<iterator,iterator> equal_range(const key_type &key);
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);
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;
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;
787 //! @copydoc ::boost::intrusive::hashtable::iterator_to(reference)
788 iterator iterator_to(reference value);
790 //! @copydoc ::boost::intrusive::hashtable::iterator_to(const_reference)const
791 const_iterator iterator_to(const_reference value) const;
793 //! @copydoc ::boost::intrusive::hashtable::s_local_iterator_to(reference)
794 static local_iterator s_local_iterator_to(reference value);
796 //! @copydoc ::boost::intrusive::hashtable::s_local_iterator_to(const_reference)
797 static const_local_iterator s_local_iterator_to(const_reference value);
799 //! @copydoc ::boost::intrusive::hashtable::local_iterator_to(reference)
800 local_iterator local_iterator_to(reference value);
802 //! @copydoc ::boost::intrusive::hashtable::local_iterator_to(const_reference)
803 const_local_iterator local_iterator_to(const_reference value) const;
805 //! @copydoc ::boost::intrusive::hashtable::bucket_count
806 size_type bucket_count() const;
808 //! @copydoc ::boost::intrusive::hashtable::bucket_size
809 size_type bucket_size(size_type n) const;
811 //! @copydoc ::boost::intrusive::hashtable::bucket(const key_type&)const
812 size_type bucket(const key_type& k) const;
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;
818 //! @copydoc ::boost::intrusive::hashtable::bucket_pointer
819 bucket_ptr bucket_pointer() const;
821 //! @copydoc ::boost::intrusive::hashtable::begin(size_type)
822 local_iterator begin(size_type n);
824 //! @copydoc ::boost::intrusive::hashtable::begin(size_type)const
825 const_local_iterator begin(size_type n) const;
827 //! @copydoc ::boost::intrusive::hashtable::cbegin(size_type)const
828 const_local_iterator cbegin(size_type n) const;
830 //! @copydoc ::boost::intrusive::hashtable::end(size_type)
831 local_iterator end(size_type n);
833 //! @copydoc ::boost::intrusive::hashtable::end(size_type)const
834 const_local_iterator end(size_type n) const;
836 //! @copydoc ::boost::intrusive::hashtable::cend(size_type)const
837 const_local_iterator cend(size_type n) const;
839 //! @copydoc ::boost::intrusive::hashtable::rehash(const bucket_traits &)
840 void rehash(const bucket_traits &new_bucket_traits);
842 //! @copydoc ::boost::intrusive::hashtable::full_rehash
845 //! @copydoc ::boost::intrusive::hashtable::incremental_rehash(bool)
846 bool incremental_rehash(bool grow = true);
848 //! @copydoc ::boost::intrusive::hashtable::incremental_rehash(const bucket_traits &)
849 bool incremental_rehash(const bucket_traits &new_bucket_traits);
851 //! @copydoc ::boost::intrusive::hashtable::split_count
852 size_type split_count() const;
854 //! @copydoc ::boost::intrusive::hashtable::suggested_upper_bucket_count
855 static size_type suggested_upper_bucket_count(size_type n);
857 //! @copydoc ::boost::intrusive::hashtable::suggested_lower_bucket_count
858 static size_type suggested_lower_bucket_count(size_type n);
860 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
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)
866 template<class T, class ...Options>
868 template<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
875 struct make_unordered_multiset
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
885 >::type packed_options;
887 typedef typename detail::get_value_traits
888 <T, typename packed_options::proto_value_traits>::type value_traits;
890 typedef typename make_bucket_traits
891 <T, true, packed_options>::type bucket_traits;
893 typedef unordered_multiset_impl
895 , typename packed_options::key_of_value
896 , typename packed_options::hash
897 , typename packed_options::equal
898 , typename packed_options::size_type
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;
909 typedef implementation_defined type;
912 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
914 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
915 template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
917 template<class T, class ...Options>
919 class 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
928 typedef typename make_unordered_multiset
930 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
931 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
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)
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;
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)
957 template<class Iterator>
958 unordered_multiset( Iterator b
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)
967 unordered_multiset(BOOST_RV_REF(unordered_multiset) x)
968 : Base(BOOST_MOVE_BASE(Base, x))
971 unordered_multiset& operator=(BOOST_RV_REF(unordered_multiset) x)
972 { return static_cast<unordered_multiset&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
974 template <class Cloner, class Disposer>
975 void clone_from(const unordered_multiset &src, Cloner cloner, Disposer disposer)
976 { Base::clone_from(src, cloner, disposer); }
978 template <class Cloner, class Disposer>
979 void clone_from(BOOST_RV_REF(unordered_multiset) src, Cloner cloner, Disposer disposer)
980 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
985 } //namespace intrusive
988 #include <boost/intrusive/detail/config_end.hpp>
990 #endif //BOOST_INTRUSIVE_UNORDERED_SET_HPP