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