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