1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Ion Gaztanaga 2006-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_RBTREE_HPP |
13 | #define BOOST_INTRUSIVE_RBTREE_HPP |
14 | |
15 | #include <boost/intrusive/detail/config_begin.hpp> |
16 | #include <boost/intrusive/intrusive_fwd.hpp> |
17 | #include <cstddef> |
18 | #include <boost/intrusive/detail/minimal_less_equal_header.hpp> |
19 | #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair |
20 | |
21 | #include <boost/intrusive/set_hook.hpp> |
22 | #include <boost/intrusive/detail/rbtree_node.hpp> |
23 | #include <boost/intrusive/bstree.hpp> |
24 | #include <boost/intrusive/detail/tree_node.hpp> |
25 | #include <boost/intrusive/detail/mpl.hpp> |
26 | #include <boost/intrusive/pointer_traits.hpp> |
27 | #include <boost/intrusive/detail/get_value_traits.hpp> |
28 | #include <boost/intrusive/rbtree_algorithms.hpp> |
29 | #include <boost/intrusive/link_mode.hpp> |
30 | |
31 | #include <boost/move/utility_core.hpp> |
32 | #include <boost/static_assert.hpp> |
33 | |
34 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
35 | # pragma once |
36 | #endif |
37 | |
38 | namespace boost { |
39 | namespace intrusive { |
40 | |
41 | /// @cond |
42 | |
43 | struct default_rbtree_hook_applier |
44 | { template <class T> struct apply{ typedef typename T::default_rbtree_hook type; }; }; |
45 | |
46 | template<> |
47 | struct is_default_hook_tag<default_rbtree_hook_applier> |
48 | { static const bool value = true; }; |
49 | |
50 | struct rbtree_defaults |
51 | : bstree_defaults |
52 | { |
53 | typedef default_rbtree_hook_applier proto_value_traits; |
54 | }; |
55 | |
56 | /// @endcond |
57 | |
58 | //! The class template rbtree is an intrusive red-black tree container, that |
59 | //! is used to construct intrusive set and multiset containers. The no-throw |
60 | //! guarantee holds only, if the key_compare object |
61 | //! doesn't throw. |
62 | //! |
63 | //! The template parameter \c T is the type to be managed by the container. |
64 | //! The user can specify additional options and if no options are provided |
65 | //! default options are used. |
66 | //! |
67 | //! The container supports the following options: |
68 | //! \c base_hook<>/member_hook<>/value_traits<>, |
69 | //! \c constant_time_size<>, \c size_type<> and |
70 | //! \c compare<>. |
71 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
72 | template<class T, class ...Options> |
73 | #else |
74 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder> |
75 | #endif |
76 | class rbtree_impl |
77 | /// @cond |
78 | : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder> |
79 | /// @endcond |
80 | { |
81 | public: |
82 | typedef ValueTraits value_traits; |
83 | /// @cond |
84 | typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType |
85 | , ConstantTimeSize, RbTreeAlgorithms |
86 | , HeaderHolder> tree_type; |
87 | typedef tree_type implementation_defined; |
88 | /// @endcond |
89 | |
90 | typedef typename implementation_defined::pointer pointer; |
91 | typedef typename implementation_defined::const_pointer const_pointer; |
92 | typedef typename implementation_defined::value_type value_type; |
93 | typedef typename implementation_defined::key_type key_type; |
94 | typedef typename implementation_defined::key_of_value key_of_value; |
95 | typedef typename implementation_defined::reference reference; |
96 | typedef typename implementation_defined::const_reference const_reference; |
97 | typedef typename implementation_defined::difference_type difference_type; |
98 | typedef typename implementation_defined::size_type size_type; |
99 | typedef typename implementation_defined::value_compare value_compare; |
100 | typedef typename implementation_defined::key_compare key_compare; |
101 | typedef typename implementation_defined::iterator iterator; |
102 | typedef typename implementation_defined::const_iterator const_iterator; |
103 | typedef typename implementation_defined::reverse_iterator reverse_iterator; |
104 | typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; |
105 | typedef typename implementation_defined::node_traits node_traits; |
106 | typedef typename implementation_defined::node node; |
107 | typedef typename implementation_defined::node_ptr node_ptr; |
108 | typedef typename implementation_defined::const_node_ptr const_node_ptr; |
109 | typedef typename implementation_defined::node_algorithms node_algorithms; |
110 | |
111 | static const bool constant_time_size = implementation_defined::constant_time_size; |
112 | /// @cond |
113 | private: |
114 | |
115 | //noncopyable |
116 | BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree_impl) |
117 | |
118 | /// @endcond |
119 | |
120 | public: |
121 | |
122 | typedef typename implementation_defined::insert_commit_data insert_commit_data; |
123 | |
124 | //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &) |
125 | explicit rbtree_impl( const key_compare &cmp = key_compare() |
126 | , const value_traits &v_traits = value_traits()) |
127 | : tree_type(cmp, v_traits) |
128 | {} |
129 | |
130 | //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &) |
131 | template<class Iterator> |
132 | rbtree_impl( bool unique, Iterator b, Iterator e |
133 | , const key_compare &cmp = key_compare() |
134 | , const value_traits &v_traits = value_traits()) |
135 | : tree_type(unique, b, e, cmp, v_traits) |
136 | {} |
137 | |
138 | //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) |
139 | rbtree_impl(BOOST_RV_REF(rbtree_impl) x) |
140 | : tree_type(BOOST_MOVE_BASE(tree_type, x)) |
141 | {} |
142 | |
143 | //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) |
144 | rbtree_impl& operator=(BOOST_RV_REF(rbtree_impl) x) |
145 | { return static_cast<rbtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } |
146 | |
147 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
148 | //! @copydoc ::boost::intrusive::bstree::~bstree() |
149 | ~rbtree_impl(); |
150 | |
151 | //! @copydoc ::boost::intrusive::bstree::begin() |
152 | iterator begin(); |
153 | |
154 | //! @copydoc ::boost::intrusive::bstree::begin()const |
155 | const_iterator begin() const; |
156 | |
157 | //! @copydoc ::boost::intrusive::bstree::cbegin()const |
158 | const_iterator cbegin() const; |
159 | |
160 | //! @copydoc ::boost::intrusive::bstree::end() |
161 | iterator end(); |
162 | |
163 | //! @copydoc ::boost::intrusive::bstree::end()const |
164 | const_iterator end() const; |
165 | |
166 | //! @copydoc ::boost::intrusive::bstree::cend()const |
167 | const_iterator cend() const; |
168 | |
169 | //! @copydoc ::boost::intrusive::bstree::rbegin() |
170 | reverse_iterator rbegin(); |
171 | |
172 | //! @copydoc ::boost::intrusive::bstree::rbegin()const |
173 | const_reverse_iterator rbegin() const; |
174 | |
175 | //! @copydoc ::boost::intrusive::bstree::crbegin()const |
176 | const_reverse_iterator crbegin() const; |
177 | |
178 | //! @copydoc ::boost::intrusive::bstree::rend() |
179 | reverse_iterator rend(); |
180 | |
181 | //! @copydoc ::boost::intrusive::bstree::rend()const |
182 | const_reverse_iterator rend() const; |
183 | |
184 | //! @copydoc ::boost::intrusive::bstree::crend()const |
185 | const_reverse_iterator crend() const; |
186 | |
187 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) |
188 | static rbtree_impl &container_from_end_iterator(iterator end_iterator); |
189 | |
190 | //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) |
191 | static const rbtree_impl &container_from_end_iterator(const_iterator end_iterator); |
192 | |
193 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) |
194 | static rbtree_impl &container_from_iterator(iterator it); |
195 | |
196 | //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) |
197 | static const rbtree_impl &container_from_iterator(const_iterator it); |
198 | |
199 | //! @copydoc ::boost::intrusive::bstree::key_comp()const |
200 | key_compare key_comp() const; |
201 | |
202 | //! @copydoc ::boost::intrusive::bstree::value_comp()const |
203 | value_compare value_comp() const; |
204 | |
205 | //! @copydoc ::boost::intrusive::bstree::empty()const |
206 | bool empty() const; |
207 | |
208 | //! @copydoc ::boost::intrusive::bstree::size()const |
209 | size_type size() const; |
210 | |
211 | //! @copydoc ::boost::intrusive::bstree::swap |
212 | void swap(rbtree_impl& other); |
213 | |
214 | //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer) |
215 | template <class Cloner, class Disposer> |
216 | void clone_from(const rbtree_impl &src, Cloner cloner, Disposer disposer); |
217 | |
218 | #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED |
219 | |
220 | using tree_type::clone_from; |
221 | |
222 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
223 | |
224 | //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) |
225 | template <class Cloner, class Disposer> |
226 | void clone_from(BOOST_RV_REF(rbtree_impl) src, Cloner cloner, Disposer disposer) |
227 | { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } |
228 | |
229 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
230 | |
231 | //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) |
232 | template <class Cloner, class Disposer> |
233 | void clone_from(rbtree_impl &&src, Cloner cloner, Disposer disposer); |
234 | |
235 | //! @copydoc ::boost::intrusive::bstree::insert_equal(reference) |
236 | iterator insert_equal(reference value); |
237 | |
238 | //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference) |
239 | iterator insert_equal(const_iterator hint, reference value); |
240 | |
241 | //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator) |
242 | template<class Iterator> |
243 | void insert_equal(Iterator b, Iterator e); |
244 | |
245 | //! @copydoc ::boost::intrusive::bstree::insert_unique(reference) |
246 | std::pair<iterator, bool> insert_unique(reference value); |
247 | |
248 | //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference) |
249 | iterator insert_unique(const_iterator hint, reference value); |
250 | |
251 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&) |
252 | template<class KeyType, class KeyTypeKeyCompare> |
253 | std::pair<iterator, bool> insert_unique_check |
254 | (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); |
255 | |
256 | //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&) |
257 | template<class KeyType, class KeyTypeKeyCompare> |
258 | std::pair<iterator, bool> insert_unique_check |
259 | (const_iterator hint, const KeyType &key |
260 | ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); |
261 | |
262 | //! @copydoc ::boost::intrusive::bstree::insert_unique_commit |
263 | iterator insert_unique_commit(reference value, const insert_commit_data &commit_data); |
264 | |
265 | //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator) |
266 | template<class Iterator> |
267 | void insert_unique(Iterator b, Iterator e); |
268 | |
269 | //! @copydoc ::boost::intrusive::bstree::insert_before |
270 | iterator insert_before(const_iterator pos, reference value); |
271 | |
272 | //! @copydoc ::boost::intrusive::bstree::push_back |
273 | void push_back(reference value); |
274 | |
275 | //! @copydoc ::boost::intrusive::bstree::push_front |
276 | void push_front(reference value); |
277 | |
278 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator) |
279 | iterator erase(const_iterator i); |
280 | |
281 | //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator) |
282 | iterator erase(const_iterator b, const_iterator e); |
283 | |
284 | //! @copydoc ::boost::intrusive::bstree::erase(const key_type &key) |
285 | size_type erase(const key_type &key); |
286 | |
287 | //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare) |
288 | template<class KeyType, class KeyTypeKeyCompare> |
289 | size_type erase(const KeyType& key, KeyTypeKeyCompare comp); |
290 | |
291 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer) |
292 | template<class Disposer> |
293 | iterator erase_and_dispose(const_iterator i, Disposer disposer); |
294 | |
295 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer) |
296 | template<class Disposer> |
297 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); |
298 | |
299 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer) |
300 | template<class Disposer> |
301 | size_type erase_and_dispose(const key_type &key, Disposer disposer); |
302 | |
303 | //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) |
304 | template<class KeyType, class KeyTypeKeyCompare, class Disposer> |
305 | size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); |
306 | |
307 | //! @copydoc ::boost::intrusive::bstree::clear |
308 | void clear(); |
309 | |
310 | //! @copydoc ::boost::intrusive::bstree::clear_and_dispose |
311 | template<class Disposer> |
312 | void clear_and_dispose(Disposer disposer); |
313 | |
314 | //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const |
315 | size_type count(const key_type &key) const; |
316 | |
317 | //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const |
318 | template<class KeyType, class KeyTypeKeyCompare> |
319 | size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; |
320 | |
321 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) |
322 | iterator lower_bound(const key_type &key); |
323 | |
324 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) |
325 | template<class KeyType, class KeyTypeKeyCompare> |
326 | iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); |
327 | |
328 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const |
329 | const_iterator lower_bound(const key_type &key) const; |
330 | |
331 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const |
332 | template<class KeyType, class KeyTypeKeyCompare> |
333 | const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; |
334 | |
335 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) |
336 | iterator upper_bound(const key_type &key); |
337 | |
338 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) |
339 | template<class KeyType, class KeyTypeKeyCompare> |
340 | iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); |
341 | |
342 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const |
343 | const_iterator upper_bound(const key_type &key) const; |
344 | |
345 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const |
346 | template<class KeyType, class KeyTypeKeyCompare> |
347 | const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; |
348 | |
349 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &) |
350 | iterator find(const key_type &key); |
351 | |
352 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) |
353 | template<class KeyType, class KeyTypeKeyCompare> |
354 | iterator find(const KeyType& key, KeyTypeKeyCompare comp); |
355 | |
356 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const |
357 | const_iterator find(const key_type &key) const; |
358 | |
359 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const |
360 | template<class KeyType, class KeyTypeKeyCompare> |
361 | const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; |
362 | |
363 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) |
364 | std::pair<iterator,iterator> equal_range(const key_type &key); |
365 | |
366 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) |
367 | template<class KeyType, class KeyTypeKeyCompare> |
368 | std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); |
369 | |
370 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const |
371 | std::pair<const_iterator, const_iterator> |
372 | equal_range(const key_type &key) const; |
373 | |
374 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const |
375 | template<class KeyType, class KeyTypeKeyCompare> |
376 | std::pair<const_iterator, const_iterator> |
377 | equal_range(const KeyType& key, KeyTypeKeyCompare comp) const; |
378 | |
379 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) |
380 | std::pair<iterator,iterator> bounded_range |
381 | (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed); |
382 | |
383 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) |
384 | template<class KeyType, class KeyTypeKeyCompare> |
385 | std::pair<iterator,iterator> bounded_range |
386 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); |
387 | |
388 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const |
389 | std::pair<const_iterator, const_iterator> |
390 | bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; |
391 | |
392 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const |
393 | template<class KeyType, class KeyTypeKeyCompare> |
394 | std::pair<const_iterator, const_iterator> bounded_range |
395 | (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; |
396 | |
397 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) |
398 | static iterator s_iterator_to(reference value); |
399 | |
400 | //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) |
401 | static const_iterator s_iterator_to(const_reference value); |
402 | |
403 | //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) |
404 | iterator iterator_to(reference value); |
405 | |
406 | //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const |
407 | const_iterator iterator_to(const_reference value) const; |
408 | |
409 | //! @copydoc ::boost::intrusive::bstree::init_node(reference) |
410 | static void init_node(reference value); |
411 | |
412 | //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance |
413 | pointer unlink_leftmost_without_rebalance(); |
414 | |
415 | //! @copydoc ::boost::intrusive::bstree::replace_node |
416 | void replace_node(iterator replace_this, reference with_this); |
417 | |
418 | //! @copydoc ::boost::intrusive::bstree::remove_node |
419 | void remove_node(reference value); |
420 | |
421 | friend bool operator< (const rbtree_impl &x, const rbtree_impl &y); |
422 | |
423 | friend bool operator==(const rbtree_impl &x, const rbtree_impl &y); |
424 | |
425 | friend bool operator!= (const rbtree_impl &x, const rbtree_impl &y); |
426 | |
427 | friend bool operator>(const rbtree_impl &x, const rbtree_impl &y); |
428 | |
429 | friend bool operator<=(const rbtree_impl &x, const rbtree_impl &y); |
430 | |
431 | friend bool operator>=(const rbtree_impl &x, const rbtree_impl &y); |
432 | |
433 | friend void swap(rbtree_impl &x, rbtree_impl &y); |
434 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
435 | }; |
436 | |
437 | |
438 | //! Helper metafunction to define a \c rbtree that yields to the same type when the |
439 | //! same options (either explicitly or implicitly) are used. |
440 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
441 | template<class T, class ...Options> |
442 | #else |
443 | template<class T, class O1 = void, class O2 = void |
444 | , class O3 = void, class O4 = void |
445 | , class O5 = void, class O6 = void> |
446 | #endif |
447 | struct make_rbtree |
448 | { |
449 | /// @cond |
450 | typedef typename pack_options |
451 | < rbtree_defaults, |
452 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
453 | O1, O2, O3, O4, O5, O6 |
454 | #else |
455 | Options... |
456 | #endif |
457 | >::type packed_options; |
458 | |
459 | typedef typename detail::get_value_traits |
460 | <T, typename packed_options::proto_value_traits>::type value_traits; |
461 | |
462 | typedef rbtree_impl |
463 | < value_traits |
464 | , typename packed_options::key_of_value |
465 | , typename packed_options::compare |
466 | , typename packed_options::size_type |
467 | , packed_options::constant_time_size |
468 | , typename packed_options::header_holder_type |
469 | > implementation_defined; |
470 | /// @endcond |
471 | typedef implementation_defined type; |
472 | }; |
473 | |
474 | |
475 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
476 | |
477 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
478 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6> |
479 | #else |
480 | template<class T, class ...Options> |
481 | #endif |
482 | class rbtree |
483 | : public make_rbtree<T, |
484 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
485 | O1, O2, O3, O4, O5, O6 |
486 | #else |
487 | Options... |
488 | #endif |
489 | >::type |
490 | { |
491 | typedef typename make_rbtree |
492 | <T, |
493 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
494 | O1, O2, O3, O4, O5, O6 |
495 | #else |
496 | Options... |
497 | #endif |
498 | >::type Base; |
499 | BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree) |
500 | |
501 | public: |
502 | typedef typename Base::key_compare key_compare; |
503 | typedef typename Base::value_traits value_traits; |
504 | typedef typename Base::iterator iterator; |
505 | typedef typename Base::const_iterator const_iterator; |
506 | typedef typename Base::reverse_iterator reverse_iterator; |
507 | typedef typename Base::const_reverse_iterator const_reverse_iterator; |
508 | |
509 | //Assert if passed value traits are compatible with the type |
510 | BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); |
511 | |
512 | explicit rbtree( const key_compare &cmp = key_compare() |
513 | , const value_traits &v_traits = value_traits()) |
514 | : Base(cmp, v_traits) |
515 | {} |
516 | |
517 | template<class Iterator> |
518 | rbtree( bool unique, Iterator b, Iterator e |
519 | , const key_compare &cmp = key_compare() |
520 | , const value_traits &v_traits = value_traits()) |
521 | : Base(unique, b, e, cmp, v_traits) |
522 | {} |
523 | |
524 | rbtree(BOOST_RV_REF(rbtree) x) |
525 | : Base(BOOST_MOVE_BASE(Base, x)) |
526 | {} |
527 | |
528 | rbtree& operator=(BOOST_RV_REF(rbtree) x) |
529 | { return static_cast<rbtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } |
530 | |
531 | template <class Cloner, class Disposer> |
532 | void clone_from(const rbtree &src, Cloner cloner, Disposer disposer) |
533 | { Base::clone_from(src, cloner, disposer); } |
534 | |
535 | template <class Cloner, class Disposer> |
536 | void clone_from(BOOST_RV_REF(rbtree) src, Cloner cloner, Disposer disposer) |
537 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } |
538 | |
539 | static rbtree &container_from_end_iterator(iterator end_iterator) |
540 | { return static_cast<rbtree &>(Base::container_from_end_iterator(end_iterator)); } |
541 | |
542 | static const rbtree &container_from_end_iterator(const_iterator end_iterator) |
543 | { return static_cast<const rbtree &>(Base::container_from_end_iterator(end_iterator)); } |
544 | |
545 | static rbtree &container_from_iterator(iterator it) |
546 | { return static_cast<rbtree &>(Base::container_from_iterator(it)); } |
547 | |
548 | static const rbtree &container_from_iterator(const_iterator it) |
549 | { return static_cast<const rbtree &>(Base::container_from_iterator(it)); } |
550 | }; |
551 | |
552 | #endif |
553 | |
554 | } //namespace intrusive |
555 | } //namespace boost |
556 | |
557 | #include <boost/intrusive/detail/config_end.hpp> |
558 | |
559 | #endif //BOOST_INTRUSIVE_RBTREE_HPP |
560 | |