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() rbtree_impl()125 rbtree_impl() 126 : tree_type() 127 {} 128 129 //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &) rbtree_impl(const key_compare & cmp,const value_traits & v_traits=value_traits ())130 explicit rbtree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits()) 131 : tree_type(cmp, v_traits) 132 {} 133 134 //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &) 135 template<class Iterator> rbtree_impl(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())136 rbtree_impl( bool unique, Iterator b, Iterator e 137 , const key_compare &cmp = key_compare() 138 , const value_traits &v_traits = value_traits()) 139 : tree_type(unique, b, e, cmp, v_traits) 140 {} 141 142 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) rbtree_impl(BOOST_RV_REF (rbtree_impl)x)143 rbtree_impl(BOOST_RV_REF(rbtree_impl) x) 144 : tree_type(BOOST_MOVE_BASE(tree_type, x)) 145 {} 146 147 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) operator =(BOOST_RV_REF (rbtree_impl)x)148 rbtree_impl& operator=(BOOST_RV_REF(rbtree_impl) x) 149 { return static_cast<rbtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } 150 151 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 152 //! @copydoc ::boost::intrusive::bstree::~bstree() 153 ~rbtree_impl(); 154 155 //! @copydoc ::boost::intrusive::bstree::begin() 156 iterator begin(); 157 158 //! @copydoc ::boost::intrusive::bstree::begin()const 159 const_iterator begin() const; 160 161 //! @copydoc ::boost::intrusive::bstree::cbegin()const 162 const_iterator cbegin() const; 163 164 //! @copydoc ::boost::intrusive::bstree::end() 165 iterator end(); 166 167 //! @copydoc ::boost::intrusive::bstree::end()const 168 const_iterator end() const; 169 170 //! @copydoc ::boost::intrusive::bstree::cend()const 171 const_iterator cend() const; 172 173 //! @copydoc ::boost::intrusive::bstree::rbegin() 174 reverse_iterator rbegin(); 175 176 //! @copydoc ::boost::intrusive::bstree::rbegin()const 177 const_reverse_iterator rbegin() const; 178 179 //! @copydoc ::boost::intrusive::bstree::crbegin()const 180 const_reverse_iterator crbegin() const; 181 182 //! @copydoc ::boost::intrusive::bstree::rend() 183 reverse_iterator rend(); 184 185 //! @copydoc ::boost::intrusive::bstree::rend()const 186 const_reverse_iterator rend() const; 187 188 //! @copydoc ::boost::intrusive::bstree::crend()const 189 const_reverse_iterator crend() const; 190 191 //! @copydoc ::boost::intrusive::bstree::root() 192 iterator root(); 193 194 //! @copydoc ::boost::intrusive::bstree::root()const 195 const_iterator root() const; 196 197 //! @copydoc ::boost::intrusive::bstree::croot()const 198 const_iterator croot() const; 199 200 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) 201 static rbtree_impl &container_from_end_iterator(iterator end_iterator); 202 203 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) 204 static const rbtree_impl &container_from_end_iterator(const_iterator end_iterator); 205 206 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) 207 static rbtree_impl &container_from_iterator(iterator it); 208 209 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) 210 static const rbtree_impl &container_from_iterator(const_iterator it); 211 212 //! @copydoc ::boost::intrusive::bstree::key_comp()const 213 key_compare key_comp() const; 214 215 //! @copydoc ::boost::intrusive::bstree::value_comp()const 216 value_compare value_comp() const; 217 218 //! @copydoc ::boost::intrusive::bstree::empty()const 219 bool empty() const; 220 221 //! @copydoc ::boost::intrusive::bstree::size()const 222 size_type size() const; 223 224 //! @copydoc ::boost::intrusive::bstree::swap 225 void swap(rbtree_impl& other); 226 227 //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer) 228 template <class Cloner, class Disposer> 229 void clone_from(const rbtree_impl &src, Cloner cloner, Disposer disposer); 230 231 #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED 232 233 using tree_type::clone_from; 234 235 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 236 237 //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) 238 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (rbtree_impl)src,Cloner cloner,Disposer disposer)239 void clone_from(BOOST_RV_REF(rbtree_impl) src, Cloner cloner, Disposer disposer) 240 { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } 241 242 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 243 244 //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer) 245 template <class Cloner, class Disposer> 246 void clone_from(rbtree_impl &&src, Cloner cloner, Disposer disposer); 247 248 //! @copydoc ::boost::intrusive::bstree::insert_equal(reference) 249 iterator insert_equal(reference value); 250 251 //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference) 252 iterator insert_equal(const_iterator hint, reference value); 253 254 //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator) 255 template<class Iterator> 256 void insert_equal(Iterator b, Iterator e); 257 258 //! @copydoc ::boost::intrusive::bstree::insert_unique(reference) 259 std::pair<iterator, bool> insert_unique(reference value); 260 261 //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference) 262 iterator insert_unique(const_iterator hint, reference value); 263 264 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&) 265 template<class KeyType, class KeyTypeKeyCompare> 266 std::pair<iterator, bool> insert_unique_check 267 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); 268 269 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&) 270 template<class KeyType, class KeyTypeKeyCompare> 271 std::pair<iterator, bool> insert_unique_check 272 (const_iterator hint, const KeyType &key 273 ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); 274 275 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const key_type&,insert_commit_data&) 276 std::pair<iterator, bool> insert_unique_check 277 (const key_type &key, insert_commit_data &commit_data); 278 279 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&) 280 std::pair<iterator, bool> insert_unique_check 281 (const_iterator hint, const key_type &key, insert_commit_data &commit_data); 282 283 //! @copydoc ::boost::intrusive::bstree::insert_unique_commit 284 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data); 285 286 //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator) 287 template<class Iterator> 288 void insert_unique(Iterator b, Iterator e); 289 290 //! @copydoc ::boost::intrusive::bstree::insert_before 291 iterator insert_before(const_iterator pos, reference value); 292 293 //! @copydoc ::boost::intrusive::bstree::push_back 294 void push_back(reference value); 295 296 //! @copydoc ::boost::intrusive::bstree::push_front 297 void push_front(reference value); 298 299 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator) 300 iterator erase(const_iterator i); 301 302 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator) 303 iterator erase(const_iterator b, const_iterator e); 304 305 //! @copydoc ::boost::intrusive::bstree::erase(const key_type &key) 306 size_type erase(const key_type &key); 307 308 //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare) 309 template<class KeyType, class KeyTypeKeyCompare> 310 size_type erase(const KeyType& key, KeyTypeKeyCompare comp); 311 312 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer) 313 template<class Disposer> 314 iterator erase_and_dispose(const_iterator i, Disposer disposer); 315 316 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer) 317 template<class Disposer> 318 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); 319 320 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer) 321 template<class Disposer> 322 size_type erase_and_dispose(const key_type &key, Disposer disposer); 323 324 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) 325 template<class KeyType, class KeyTypeKeyCompare, class Disposer> 326 size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); 327 328 //! @copydoc ::boost::intrusive::bstree::clear 329 void clear(); 330 331 //! @copydoc ::boost::intrusive::bstree::clear_and_dispose 332 template<class Disposer> 333 void clear_and_dispose(Disposer disposer); 334 335 //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const 336 size_type count(const key_type &key) const; 337 338 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const 339 template<class KeyType, class KeyTypeKeyCompare> 340 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; 341 342 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) 343 iterator lower_bound(const key_type &key); 344 345 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) 346 template<class KeyType, class KeyTypeKeyCompare> 347 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); 348 349 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const 350 const_iterator lower_bound(const key_type &key) const; 351 352 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const 353 template<class KeyType, class KeyTypeKeyCompare> 354 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 355 356 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) 357 iterator upper_bound(const key_type &key); 358 359 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) 360 template<class KeyType, class KeyTypeKeyCompare> 361 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); 362 363 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const 364 const_iterator upper_bound(const key_type &key) const; 365 366 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const 367 template<class KeyType, class KeyTypeKeyCompare> 368 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 369 370 //! @copydoc ::boost::intrusive::bstree::find(const key_type &) 371 iterator find(const key_type &key); 372 373 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) 374 template<class KeyType, class KeyTypeKeyCompare> 375 iterator find(const KeyType& key, KeyTypeKeyCompare comp); 376 377 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const 378 const_iterator find(const key_type &key) const; 379 380 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const 381 template<class KeyType, class KeyTypeKeyCompare> 382 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; 383 384 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) 385 std::pair<iterator,iterator> equal_range(const key_type &key); 386 387 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) 388 template<class KeyType, class KeyTypeKeyCompare> 389 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); 390 391 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const 392 std::pair<const_iterator, const_iterator> 393 equal_range(const key_type &key) const; 394 395 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const 396 template<class KeyType, class KeyTypeKeyCompare> 397 std::pair<const_iterator, const_iterator> 398 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const; 399 400 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) 401 std::pair<iterator,iterator> bounded_range 402 (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed); 403 404 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) 405 template<class KeyType, class KeyTypeKeyCompare> 406 std::pair<iterator,iterator> bounded_range 407 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); 408 409 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const 410 std::pair<const_iterator, const_iterator> 411 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; 412 413 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const 414 template<class KeyType, class KeyTypeKeyCompare> 415 std::pair<const_iterator, const_iterator> bounded_range 416 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; 417 418 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) 419 static iterator s_iterator_to(reference value); 420 421 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) 422 static const_iterator s_iterator_to(const_reference value); 423 424 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) 425 iterator iterator_to(reference value); 426 427 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const 428 const_iterator iterator_to(const_reference value) const; 429 430 //! @copydoc ::boost::intrusive::bstree::init_node(reference) 431 static void init_node(reference value); 432 433 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance 434 pointer unlink_leftmost_without_rebalance(); 435 436 //! @copydoc ::boost::intrusive::bstree::replace_node 437 void replace_node(iterator replace_this, reference with_this); 438 439 //! @copydoc ::boost::intrusive::bstree::remove_node 440 void remove_node(reference value); 441 442 //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&) 443 template<class T, class ...Options2> 444 void merge_unique(rbtree<T, Options2...> &); 445 446 //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&) 447 template<class T, class ...Options2> 448 void merge_equal(rbtree<T, Options2...> &); 449 450 friend bool operator< (const rbtree_impl &x, const rbtree_impl &y); 451 452 friend bool operator==(const rbtree_impl &x, const rbtree_impl &y); 453 454 friend bool operator!= (const rbtree_impl &x, const rbtree_impl &y); 455 456 friend bool operator>(const rbtree_impl &x, const rbtree_impl &y); 457 458 friend bool operator<=(const rbtree_impl &x, const rbtree_impl &y); 459 460 friend bool operator>=(const rbtree_impl &x, const rbtree_impl &y); 461 462 friend void swap(rbtree_impl &x, rbtree_impl &y); 463 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 464 }; 465 466 467 //! Helper metafunction to define a \c rbtree that yields to the same type when the 468 //! same options (either explicitly or implicitly) are used. 469 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 470 template<class T, class ...Options> 471 #else 472 template<class T, class O1 = void, class O2 = void 473 , class O3 = void, class O4 = void 474 , class O5 = void, class O6 = void> 475 #endif 476 struct make_rbtree 477 { 478 /// @cond 479 typedef typename pack_options 480 < rbtree_defaults, 481 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 482 O1, O2, O3, O4, O5, O6 483 #else 484 Options... 485 #endif 486 >::type packed_options; 487 488 typedef typename detail::get_value_traits 489 <T, typename packed_options::proto_value_traits>::type value_traits; 490 491 typedef rbtree_impl 492 < value_traits 493 , typename packed_options::key_of_value 494 , typename packed_options::compare 495 , typename packed_options::size_type 496 , packed_options::constant_time_size 497 , typename packed_options::header_holder_type 498 > implementation_defined; 499 /// @endcond 500 typedef implementation_defined type; 501 }; 502 503 504 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 505 506 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 507 template<class T, class O1, class O2, class O3, class O4, class O5, class O6> 508 #else 509 template<class T, class ...Options> 510 #endif 511 class rbtree 512 : public make_rbtree<T, 513 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 514 O1, O2, O3, O4, O5, O6 515 #else 516 Options... 517 #endif 518 >::type 519 { 520 typedef typename make_rbtree 521 <T, 522 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 523 O1, O2, O3, O4, O5, O6 524 #else 525 Options... 526 #endif 527 >::type Base; 528 BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree) 529 530 public: 531 typedef typename Base::key_compare key_compare; 532 typedef typename Base::value_traits value_traits; 533 typedef typename Base::iterator iterator; 534 typedef typename Base::const_iterator const_iterator; 535 typedef typename Base::reverse_iterator reverse_iterator; 536 typedef typename Base::const_reverse_iterator const_reverse_iterator; 537 538 //Assert if passed value traits are compatible with the type 539 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); 540 rbtree()541 rbtree() 542 : Base() 543 {} 544 rbtree(const key_compare & cmp,const value_traits & v_traits=value_traits ())545 explicit rbtree( const key_compare &cmp, const value_traits &v_traits = value_traits()) 546 : Base(cmp, v_traits) 547 {} 548 549 template<class Iterator> rbtree(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())550 rbtree( bool unique, Iterator b, Iterator e 551 , const key_compare &cmp = key_compare() 552 , const value_traits &v_traits = value_traits()) 553 : Base(unique, b, e, cmp, v_traits) 554 {} 555 rbtree(BOOST_RV_REF (rbtree)x)556 rbtree(BOOST_RV_REF(rbtree) x) 557 : Base(BOOST_MOVE_BASE(Base, x)) 558 {} 559 operator =(BOOST_RV_REF (rbtree)x)560 rbtree& operator=(BOOST_RV_REF(rbtree) x) 561 { return static_cast<rbtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 562 563 template <class Cloner, class Disposer> clone_from(const rbtree & src,Cloner cloner,Disposer disposer)564 void clone_from(const rbtree &src, Cloner cloner, Disposer disposer) 565 { Base::clone_from(src, cloner, disposer); } 566 567 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (rbtree)src,Cloner cloner,Disposer disposer)568 void clone_from(BOOST_RV_REF(rbtree) src, Cloner cloner, Disposer disposer) 569 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 570 container_from_end_iterator(iterator end_iterator)571 static rbtree &container_from_end_iterator(iterator end_iterator) 572 { return static_cast<rbtree &>(Base::container_from_end_iterator(end_iterator)); } 573 container_from_end_iterator(const_iterator end_iterator)574 static const rbtree &container_from_end_iterator(const_iterator end_iterator) 575 { return static_cast<const rbtree &>(Base::container_from_end_iterator(end_iterator)); } 576 container_from_iterator(iterator it)577 static rbtree &container_from_iterator(iterator it) 578 { return static_cast<rbtree &>(Base::container_from_iterator(it)); } 579 container_from_iterator(const_iterator it)580 static const rbtree &container_from_iterator(const_iterator it) 581 { return static_cast<const rbtree &>(Base::container_from_iterator(it)); } 582 }; 583 584 #endif 585 586 } //namespace intrusive 587 } //namespace boost 588 589 #include <boost/intrusive/detail/config_end.hpp> 590 591 #endif //BOOST_INTRUSIVE_RBTREE_HPP 592