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