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