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