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