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 | |
26 | namespace boost { |
27 | namespace 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) |
65 | template<class T, class ...Options> |
66 | #else |
67 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class SizeType, class BucketTraits, std::size_t BoolFlags> |
68 | #endif |
69 | class 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) |
416 | template<class T, class ...Options> |
417 | #else |
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 |
423 | > |
424 | #endif |
425 | struct 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) |
465 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10> |
466 | #else |
467 | template<class T, class ...Options> |
468 | #endif |
469 | class 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) |
573 | template<class T, class ...Options> |
574 | #else |
575 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class SizeType, class BucketTraits, std::size_t BoolFlags> |
576 | #endif |
577 | class 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) |
866 | template<class T, class ...Options> |
867 | #else |
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 |
873 | > |
874 | #endif |
875 | struct 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) |
915 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10> |
916 | #else |
917 | template<class T, class ...Options> |
918 | #endif |
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 |
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 | |