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