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