1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2008-2013 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_HPP 13 #define BOOST_INTRUSIVE_TREAP_HPP 14 15 #include <boost/intrusive/detail/config_begin.hpp> 16 #include <boost/intrusive/intrusive_fwd.hpp> 17 18 #include <boost/intrusive/detail/assert.hpp> 19 #include <boost/intrusive/bs_set_hook.hpp> 20 #include <boost/intrusive/bstree.hpp> 21 #include <boost/intrusive/detail/tree_node.hpp> 22 #include <boost/intrusive/detail/ebo_functor_holder.hpp> 23 #include <boost/intrusive/pointer_traits.hpp> 24 #include <boost/intrusive/detail/get_value_traits.hpp> 25 #include <boost/intrusive/detail/mpl.hpp> 26 #include <boost/intrusive/treap_algorithms.hpp> 27 #include <boost/intrusive/link_mode.hpp> 28 #include <boost/intrusive/priority_compare.hpp> 29 #include <boost/intrusive/detail/node_cloner_disposer.hpp> 30 #include <boost/intrusive/detail/key_nodeptr_comp.hpp> 31 32 #include <boost/static_assert.hpp> 33 #include <boost/move/utility_core.hpp> 34 #include <boost/move/adl_move_swap.hpp> 35 36 #include <cstddef> 37 #include <boost/intrusive/detail/minimal_less_equal_header.hpp> 38 #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair 39 40 #if defined(BOOST_HAS_PRAGMA_ONCE) 41 # pragma once 42 #endif 43 44 namespace boost { 45 namespace intrusive { 46 47 /// @cond 48 49 struct treap_defaults 50 : bstree_defaults 51 { 52 typedef void priority; 53 }; 54 55 /// @endcond 56 57 //! The class template treap is an intrusive treap container that 58 //! is used to construct intrusive set and multiset containers. The no-throw 59 //! guarantee holds only, if the key_compare object and priority_compare object 60 //! don't throw. 61 //! 62 //! The template parameter \c T is the type to be managed by the container. 63 //! The user can specify additional options and if no options are provided 64 //! default options are used. 65 //! 66 //! The container supports the following options: 67 //! \c base_hook<>/member_hook<>/value_traits<>, 68 //! \c constant_time_size<>, \c size_type<>, 69 //! \c compare<> and \c priority_compare<> 70 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 71 template<class T, class ...Options> 72 #else 73 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder> 74 #endif 75 class treap_impl 76 /// @cond 77 : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder> 78 //Use public inheritance to avoid MSVC bugs with closures 79 , public detail::ebo_functor_holder 80 < typename get_prio 81 < VoidOrPrioComp 82 , typename bstree_impl 83 <ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder>::key_type>::type 84 > 85 /// @endcond 86 { 87 public: 88 typedef ValueTraits value_traits; 89 /// @cond 90 typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType 91 , ConstantTimeSize, BsTreeAlgorithms 92 , HeaderHolder> tree_type; 93 typedef tree_type implementation_defined; 94 typedef get_prio 95 < VoidOrPrioComp 96 , typename tree_type::key_type> get_prio_type; 97 98 typedef detail::ebo_functor_holder 99 <typename get_prio_type::type> prio_base; 100 101 /// @endcond 102 103 typedef typename implementation_defined::pointer pointer; 104 typedef typename implementation_defined::const_pointer const_pointer; 105 typedef typename implementation_defined::value_type value_type; 106 typedef typename implementation_defined::key_type key_type; 107 typedef typename implementation_defined::key_of_value key_of_value; 108 typedef typename implementation_defined::reference reference; 109 typedef typename implementation_defined::const_reference const_reference; 110 typedef typename implementation_defined::difference_type difference_type; 111 typedef typename implementation_defined::size_type size_type; 112 typedef typename implementation_defined::value_compare value_compare; 113 typedef typename implementation_defined::key_compare key_compare; 114 typedef typename implementation_defined::iterator iterator; 115 typedef typename implementation_defined::const_iterator const_iterator; 116 typedef typename implementation_defined::reverse_iterator reverse_iterator; 117 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; 118 typedef typename implementation_defined::node_traits node_traits; 119 typedef typename implementation_defined::node node; 120 typedef typename implementation_defined::node_ptr node_ptr; 121 typedef typename implementation_defined::const_node_ptr const_node_ptr; 122 typedef BOOST_INTRUSIVE_IMPDEF(treap_algorithms<node_traits>) node_algorithms; 123 typedef BOOST_INTRUSIVE_IMPDEF(typename get_prio_type::type) priority_compare; 124 125 static const bool constant_time_size = implementation_defined::constant_time_size; 126 static const bool stateful_value_traits = implementation_defined::stateful_value_traits; 127 static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; 128 129 typedef detail::key_nodeptr_comp<priority_compare, value_traits, key_of_value> key_node_prio_comp_t; 130 131 template<class KeyPrioComp> key_node_prio_comp(KeyPrioComp keypriocomp) const132 detail::key_nodeptr_comp<KeyPrioComp, value_traits, key_of_value> key_node_prio_comp(KeyPrioComp keypriocomp) const 133 { return detail::key_nodeptr_comp<KeyPrioComp, value_traits, key_of_value>(keypriocomp, &this->get_value_traits()); } 134 135 /// @cond 136 private: 137 138 //noncopyable BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_impl) const139 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_impl) 140 141 const priority_compare &priv_pcomp() const 142 { return static_cast<const prio_base&>(*this).get(); } 143 priv_pcomp()144 priority_compare &priv_pcomp() 145 { return static_cast<prio_base&>(*this).get(); } 146 147 /// @endcond 148 149 public: 150 typedef typename node_algorithms::insert_commit_data insert_commit_data; 151 152 //! <b>Effects</b>: Constructs an empty container. 153 //! 154 //! <b>Complexity</b>: Constant. 155 //! 156 //! <b>Throws</b>: If value_traits::node_traits::node 157 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 158 //! or the copy constructor of the value_compare/priority_compare objects throw. Basic guarantee. treap_impl()159 treap_impl() 160 : tree_type(), prio_base(priority_compare()) 161 {} 162 163 //! <b>Effects</b>: Constructs an empty container. 164 //! 165 //! <b>Complexity</b>: Constant. 166 //! 167 //! <b>Throws</b>: If value_traits::node_traits::node 168 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 169 //! or the copy constructor of the value_compare/priority_compare objects throw. Basic guarantee. treap_impl(const key_compare & cmp,const priority_compare & pcmp=priority_compare (),const value_traits & v_traits=value_traits ())170 explicit treap_impl( const key_compare &cmp 171 , const priority_compare &pcmp = priority_compare() 172 , const value_traits &v_traits = value_traits()) 173 : tree_type(cmp, v_traits), prio_base(pcmp) 174 {} 175 176 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. 177 //! cmp must be a comparison function that induces a strict weak ordering. 178 //! 179 //! <b>Effects</b>: Constructs an empty container and inserts elements from 180 //! [b, e). 181 //! 182 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using 183 //! comp and otherwise N * log N, where N is the distance between first and last. 184 //! 185 //! <b>Throws</b>: If value_traits::node_traits::node 186 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 187 //! or the copy constructor/operator() of the key_compare/priority_compare objects 188 //! throw. Basic guarantee. 189 template<class Iterator> treap_impl(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const priority_compare & pcmp=priority_compare (),const value_traits & v_traits=value_traits ())190 treap_impl( bool unique, Iterator b, Iterator e 191 , const key_compare &cmp = key_compare() 192 , const priority_compare &pcmp = priority_compare() 193 , const value_traits &v_traits = value_traits()) 194 : tree_type(cmp, v_traits), prio_base(pcmp) 195 { 196 if(unique) 197 this->insert_unique(b, e); 198 else 199 this->insert_equal(b, e); 200 } 201 202 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) treap_impl(BOOST_RV_REF (treap_impl)x)203 treap_impl(BOOST_RV_REF(treap_impl) x) 204 : tree_type(BOOST_MOVE_BASE(tree_type, x)) 205 , prio_base(::boost::move(x.priv_pcomp())) 206 {} 207 208 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) operator =(BOOST_RV_REF (treap_impl)x)209 treap_impl& operator=(BOOST_RV_REF(treap_impl) x) 210 { this->swap(x); return *this; } 211 212 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 213 //! @copydoc ::boost::intrusive::bstree::~bstree() 214 ~treap_impl(); 215 216 //! @copydoc ::boost::intrusive::bstree::begin() 217 iterator begin(); 218 219 //! @copydoc ::boost::intrusive::bstree::begin()const 220 const_iterator begin() const; 221 222 //! @copydoc ::boost::intrusive::bstree::cbegin()const 223 const_iterator cbegin() const; 224 225 //! @copydoc ::boost::intrusive::bstree::end() 226 iterator end(); 227 228 //! @copydoc ::boost::intrusive::bstree::end()const 229 const_iterator end() const; 230 231 //! @copydoc ::boost::intrusive::bstree::cend()const 232 const_iterator cend() const; 233 #endif 234 235 //! <b>Effects</b>: Returns an iterator pointing to the highest priority object of the treap. 236 //! 237 //! <b>Complexity</b>: Constant. 238 //! 239 //! <b>Throws</b>: Nothing. top()240 iterator top() 241 { return this->tree_type::root(); } 242 243 //! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the treap.. 244 //! 245 //! <b>Complexity</b>: Constant. 246 //! 247 //! <b>Throws</b>: Nothing. top() const248 const_iterator top() const 249 { return this->ctop(); } 250 251 //! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the treap.. 252 //! 253 //! <b>Complexity</b>: Constant. 254 //! 255 //! <b>Throws</b>: Nothing. ctop() const256 const_iterator ctop() const 257 { return this->tree_type::root(); } 258 259 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 260 //! @copydoc ::boost::intrusive::bstree::rbegin() 261 reverse_iterator rbegin(); 262 263 //! @copydoc ::boost::intrusive::bstree::rbegin()const 264 const_reverse_iterator rbegin() const; 265 266 //! @copydoc ::boost::intrusive::bstree::crbegin()const 267 const_reverse_iterator crbegin() const; 268 269 //! @copydoc ::boost::intrusive::bstree::rend() 270 reverse_iterator rend(); 271 272 //! @copydoc ::boost::intrusive::bstree::rend()const 273 const_reverse_iterator rend() const; 274 275 //! @copydoc ::boost::intrusive::bstree::crend()const 276 const_reverse_iterator crend() const; 277 278 //! @copydoc ::boost::intrusive::bstree::root() 279 iterator root(); 280 281 //! @copydoc ::boost::intrusive::bstree::root()const 282 const_iterator root() const; 283 284 //! @copydoc ::boost::intrusive::bstree::croot()const 285 const_iterator croot() const; 286 287 #endif 288 289 //! <b>Effects</b>: Returns a reverse_iterator pointing to the highest priority object of the 290 //! reversed treap. 291 //! 292 //! <b>Complexity</b>: Constant. 293 //! 294 //! <b>Throws</b>: Nothing. rtop()295 reverse_iterator rtop() 296 { return reverse_iterator(this->top()); } 297 298 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority objec 299 //! of the reversed treap. 300 //! 301 //! <b>Complexity</b>: Constant. 302 //! 303 //! <b>Throws</b>: Nothing. rtop() const304 const_reverse_iterator rtop() const 305 { return const_reverse_iterator(this->top()); } 306 307 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority object 308 //! of the reversed treap. 309 //! 310 //! <b>Complexity</b>: Constant. 311 //! 312 //! <b>Throws</b>: Nothing. crtop() const313 const_reverse_iterator crtop() const 314 { return const_reverse_iterator(this->top()); } 315 316 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 317 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator) 318 static treap_impl &container_from_end_iterator(iterator end_iterator); 319 320 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator) 321 static const treap_impl &container_from_end_iterator(const_iterator end_iterator); 322 323 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator) 324 static treap_impl &container_from_iterator(iterator it); 325 326 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator) 327 static const treap_impl &container_from_iterator(const_iterator it); 328 329 //! @copydoc ::boost::intrusive::bstree::key_comp()const 330 key_compare key_comp() const; 331 332 //! @copydoc ::boost::intrusive::bstree::value_comp()const 333 value_compare value_comp() const; 334 335 //! @copydoc ::boost::intrusive::bstree::empty()const 336 bool empty() const; 337 338 //! @copydoc ::boost::intrusive::bstree::size()const 339 size_type size() const; 340 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 341 342 //! <b>Effects</b>: Returns the priority_compare object used by the container. 343 //! 344 //! <b>Complexity</b>: Constant. 345 //! 346 //! <b>Throws</b>: If priority_compare copy-constructor throws. priority_comp() const347 priority_compare priority_comp() const 348 { return this->priv_pcomp(); } 349 350 //! <b>Effects</b>: Swaps the contents of two treaps. 351 //! 352 //! <b>Complexity</b>: Constant. 353 //! 354 //! <b>Throws</b>: If the comparison functor's swap call throws. swap(treap_impl & other)355 void swap(treap_impl& other) 356 { 357 //This can throw 358 ::boost::adl_move_swap(this->priv_pcomp(), other.priv_pcomp()); 359 tree_type::swap(other); 360 } 361 362 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 363 //! Cloner should yield to nodes equivalent to the original nodes. 364 //! 365 //! <b>Effects</b>: Erases all the elements from *this 366 //! calling Disposer::operator()(pointer), clones all the 367 //! elements from src calling Cloner::operator()(const_reference ) 368 //! and inserts them on *this. Copies the predicate from the source container. 369 //! 370 //! If cloner throws, all cloned elements are unlinked and disposed 371 //! calling Disposer::operator()(pointer). 372 //! 373 //! <b>Complexity</b>: Linear to erased plus inserted elements. 374 //! 375 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee. 376 template <class Cloner, class Disposer> clone_from(const treap_impl & src,Cloner cloner,Disposer disposer)377 void clone_from(const treap_impl &src, Cloner cloner, Disposer disposer) 378 { 379 tree_type::clone_from(src, cloner, disposer); 380 this->priv_pcomp() = src.priv_pcomp(); 381 } 382 383 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 384 //! Cloner should yield to nodes equivalent to the original nodes. 385 //! 386 //! <b>Effects</b>: Erases all the elements from *this 387 //! calling Disposer::operator()(pointer), clones all the 388 //! elements from src calling Cloner::operator()(reference) 389 //! and inserts them on *this. Copies the predicate from the source container. 390 //! 391 //! If cloner throws, all cloned elements are unlinked and disposed 392 //! calling Disposer::operator()(pointer). 393 //! 394 //! <b>Complexity</b>: Linear to erased plus inserted elements. 395 //! 396 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee. 397 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (treap_impl)src,Cloner cloner,Disposer disposer)398 void clone_from(BOOST_RV_REF(treap_impl) src, Cloner cloner, Disposer disposer) 399 { 400 tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); 401 this->priv_pcomp() = ::boost::move(src.priv_pcomp()); 402 } 403 404 //! <b>Requires</b>: value must be an lvalue 405 //! 406 //! <b>Effects</b>: Inserts value into the container before the upper bound. 407 //! 408 //! <b>Complexity</b>: Average complexity for insert element is at 409 //! most logarithmic. 410 //! 411 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. Strong guarantee. 412 //! 413 //! <b>Note</b>: Does not affect the validity of iterators and references. 414 //! No copy-constructors are called. insert_equal(reference value)415 iterator insert_equal(reference value) 416 { 417 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 418 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 419 iterator ret 420 ( node_algorithms::insert_equal_upper_bound 421 ( this->tree_type::header_ptr() 422 , to_insert 423 , this->key_node_comp(this->key_comp()) 424 , this->key_node_prio_comp(this->priv_pcomp())) 425 , this->priv_value_traits_ptr()); 426 this->tree_type::sz_traits().increment(); 427 return ret; 428 } 429 430 //! <b>Requires</b>: value must be an lvalue, and "hint" must be 431 //! a valid iterator. 432 //! 433 //! <b>Effects</b>: Inserts x into the container, using "hint" as a hint to 434 //! where it will be inserted. If "hint" is the upper_bound 435 //! the insertion takes constant time (two comparisons in the worst case) 436 //! 437 //! <b>Complexity</b>: Logarithmic in general, but it is amortized 438 //! constant time if t is inserted immediately before hint. 439 //! 440 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. Strong guarantee. 441 //! 442 //! <b>Note</b>: Does not affect the validity of iterators and references. 443 //! No copy-constructors are called. insert_equal(const_iterator hint,reference value)444 iterator insert_equal(const_iterator hint, reference value) 445 { 446 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 447 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 448 iterator ret 449 (node_algorithms::insert_equal 450 ( this->tree_type::header_ptr() 451 , hint.pointed_node() 452 , to_insert 453 , this->key_node_comp(this->key_comp()) 454 , this->key_node_prio_comp(this->priv_pcomp())) 455 , this->priv_value_traits_ptr()); 456 this->tree_type::sz_traits().increment(); 457 return ret; 458 } 459 460 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 461 //! of type value_type. 462 //! 463 //! <b>Effects</b>: Inserts a each element of a range into the container 464 //! before the upper bound of the key of each element. 465 //! 466 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the 467 //! size of the range. However, it is linear in N if the range is already sorted 468 //! by key_comp(). 469 //! 470 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. 471 //! Strong guarantee. 472 //! 473 //! <b>Note</b>: Does not affect the validity of iterators and references. 474 //! No copy-constructors are called. 475 template<class Iterator> insert_equal(Iterator b,Iterator e)476 void insert_equal(Iterator b, Iterator e) 477 { 478 iterator iend(this->end()); 479 for (; b != e; ++b) 480 this->insert_equal(iend, *b); 481 } 482 483 //! <b>Requires</b>: value must be an lvalue 484 //! 485 //! <b>Effects</b>: Inserts value into the container if the value 486 //! is not already present. 487 //! 488 //! <b>Complexity</b>: Average complexity for insert element is at 489 //! most logarithmic. 490 //! 491 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. 492 //! Strong guarantee. 493 //! 494 //! <b>Note</b>: Does not affect the validity of iterators and references. 495 //! No copy-constructors are called. insert_unique(reference value)496 std::pair<iterator, bool> insert_unique(reference value) 497 { 498 insert_commit_data commit_data; 499 std::pair<iterator, bool> ret = this->insert_unique_check(key_of_value()(value), commit_data); 500 if(!ret.second) 501 return ret; 502 return std::pair<iterator, bool> (this->insert_unique_commit(value, commit_data), true); 503 } 504 505 //! <b>Requires</b>: value must be an lvalue, and "hint" must be 506 //! a valid iterator 507 //! 508 //! <b>Effects</b>: Tries to insert x into the container, using "hint" as a hint 509 //! to where it will be inserted. 510 //! 511 //! <b>Complexity</b>: Logarithmic in general, but it is amortized 512 //! constant time (two comparisons in the worst case) 513 //! if t is inserted immediately before hint. 514 //! 515 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. 516 //! Strong guarantee. 517 //! 518 //! <b>Note</b>: Does not affect the validity of iterators and references. 519 //! No copy-constructors are called. insert_unique(const_iterator hint,reference value)520 iterator insert_unique(const_iterator hint, reference value) 521 { 522 insert_commit_data commit_data; 523 std::pair<iterator, bool> ret = this->insert_unique_check(hint, key_of_value()(value), commit_data); 524 if(!ret.second) 525 return ret.first; 526 return this->insert_unique_commit(value, commit_data); 527 } 528 529 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 530 //! of type value_type. 531 //! 532 //! <b>Effects</b>: Tries to insert each element of a range into the container. 533 //! 534 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the 535 //! size of the range. However, it is linear in N if the range is already sorted 536 //! by key_comp(). 537 //! 538 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. 539 //! Strong guarantee. 540 //! 541 //! <b>Note</b>: Does not affect the validity of iterators and references. 542 //! No copy-constructors are called. 543 template<class Iterator> insert_unique(Iterator b,Iterator e)544 void insert_unique(Iterator b, Iterator e) 545 { 546 if(this->empty()){ 547 iterator iend(this->end()); 548 for (; b != e; ++b) 549 this->insert_unique(iend, *b); 550 } 551 else{ 552 for (; b != e; ++b) 553 this->insert_unique(*b); 554 } 555 } 556 557 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 558 //! a user provided key instead of the value itself. 559 //! 560 //! <b>Returns</b>: If there is an equivalent value 561 //! returns a pair containing an iterator to the already present value 562 //! and false. If the value can be inserted returns true in the returned 563 //! pair boolean and fills "commit_data" that is meant to be used with 564 //! the "insert_commit" function. 565 //! 566 //! <b>Complexity</b>: Average complexity is at most logarithmic. 567 //! 568 //! <b>Throws</b>: If the comparison or predicate functions throw. Strong guarantee. 569 //! 570 //! <b>Notes</b>: This function is used to improve performance when constructing 571 //! a value_type is expensive: if there is an equivalent value 572 //! the constructed object must be discarded. Many times, the part of the 573 //! node that is used to impose the order is much cheaper to construct 574 //! than the value_type and this function offers the possibility to use that 575 //! part to check if the insertion will be successful. 576 //! 577 //! If the check is successful, the user can construct the value_type and use 578 //! "insert_commit" to insert the object in constant-time. This gives a total 579 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). 580 //! 581 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more 582 //! objects are inserted or erased from the container. insert_unique_check(const key_type & key,insert_commit_data & commit_data)583 std::pair<iterator, bool> insert_unique_check 584 ( const key_type &key, insert_commit_data &commit_data) 585 { return this->insert_unique_check(key, this->key_comp(), this->priv_pcomp(), commit_data); } 586 587 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 588 //! a user provided key instead of the value itself, using "hint" 589 //! as a hint to where it will be inserted. 590 //! 591 //! <b>Returns</b>: If there is an equivalent value 592 //! returns a pair containing an iterator to the already present value 593 //! and false. If the value can be inserted returns true in the returned 594 //! pair boolean and fills "commit_data" that is meant to be used with 595 //! the "insert_commit" function. 596 //! 597 //! <b>Complexity</b>: Logarithmic in general, but it's amortized 598 //! constant time if t is inserted immediately before hint. 599 //! 600 //! <b>Throws</b>: If the comparison or predicate functions throw. Strong guarantee. 601 //! 602 //! <b>Notes</b>: This function is used to improve performance when constructing 603 //! a value_type is expensive: if there is an equivalent value 604 //! the constructed object must be discarded. Many times, the part of the 605 //! constructing that is used to impose the order is much cheaper to construct 606 //! than the value_type and this function offers the possibility to use that key 607 //! to check if the insertion will be successful. 608 //! 609 //! If the check is successful, the user can construct the value_type and use 610 //! "insert_commit" to insert the object in constant-time. This can give a total 611 //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)). 612 //! 613 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more 614 //! objects are inserted or erased from the container. insert_unique_check(const_iterator hint,const key_type & key,insert_commit_data & commit_data)615 std::pair<iterator, bool> insert_unique_check 616 ( const_iterator hint, const key_type &key, insert_commit_data &commit_data) 617 { return this->insert_unique_check(hint, key, this->key_comp(), this->priv_pcomp(), commit_data); } 618 619 //! <b>Requires</b>: comp must be a comparison function that induces 620 //! the same strict weak ordering as key_compare. 621 //! key_value_pcomp must be a comparison function that induces 622 //! the same strict weak ordering as priority_compare. The difference is that 623 //! key_value_pcomp and comp compare an arbitrary key with the contained values. 624 //! 625 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 626 //! a user provided key instead of the value itself. 627 //! 628 //! <b>Returns</b>: If there is an equivalent value 629 //! returns a pair containing an iterator to the already present value 630 //! and false. If the value can be inserted returns true in the returned 631 //! pair boolean and fills "commit_data" that is meant to be used with 632 //! the "insert_commit" function. 633 //! 634 //! <b>Complexity</b>: Average complexity is at most logarithmic. 635 //! 636 //! <b>Throws</b>: If the comp or key_value_pcomp 637 //! ordering functions throw. Strong guarantee. 638 //! 639 //! <b>Notes</b>: This function is used to improve performance when constructing 640 //! a value_type is expensive: if there is an equivalent value 641 //! the constructed object must be discarded. Many times, the part of the 642 //! node that is used to impose the order is much cheaper to construct 643 //! than the value_type and this function offers the possibility to use that 644 //! part to check if the insertion will be successful. 645 //! 646 //! If the check is successful, the user can construct the value_type and use 647 //! "insert_commit" to insert the object in constant-time. This gives a total 648 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). 649 //! 650 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more 651 //! objects are inserted or erased from the container. 652 template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare> BOOST_INTRUSIVE_DOC1ST(std::pair<iterator BOOST_INTRUSIVE_I bool>,typename detail::disable_if_convertible<KeyType BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I std::pair<iterator BOOST_INTRUSIVE_I bool>>::type)653 BOOST_INTRUSIVE_DOC1ST(std::pair<iterator BOOST_INTRUSIVE_I bool> 654 , typename detail::disable_if_convertible 655 <KeyType BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I 656 std::pair<iterator BOOST_INTRUSIVE_I bool> >::type) 657 insert_unique_check 658 ( const KeyType &key, KeyTypeKeyCompare comp 659 , KeyValuePrioCompare key_value_pcomp, insert_commit_data &commit_data) 660 { 661 std::pair<node_ptr, bool> const ret = 662 (node_algorithms::insert_unique_check 663 ( this->tree_type::header_ptr(), key 664 , this->key_node_comp(comp), this->key_node_prio_comp(key_value_pcomp), commit_data)); 665 return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second); 666 } 667 668 //! <b>Requires</b>: comp must be a comparison function that induces 669 //! the same strict weak ordering as key_compare. 670 //! key_value_pcomp must be a comparison function that induces 671 //! the same strict weak ordering as priority_compare. The difference is that 672 //! key_value_pcomp and comp compare an arbitrary key with the contained values. 673 //! 674 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 675 //! a user provided key instead of the value itself, using "hint" 676 //! as a hint to where it will be inserted. 677 //! 678 //! <b>Returns</b>: If there is an equivalent value 679 //! returns a pair containing an iterator to the already present value 680 //! and false. If the value can be inserted returns true in the returned 681 //! pair boolean and fills "commit_data" that is meant to be used with 682 //! the "insert_commit" function. 683 //! 684 //! <b>Complexity</b>: Logarithmic in general, but it's amortized 685 //! constant time if t is inserted immediately before hint. 686 //! 687 //! <b>Throws</b>: If the comp or key_value_pcomp 688 //! ordering functions throw. Strong guarantee. 689 //! 690 //! <b>Notes</b>: This function is used to improve performance when constructing 691 //! a value_type is expensive: if there is an equivalent value 692 //! the constructed object must be discarded. Many times, the part of the 693 //! constructing that is used to impose the order is much cheaper to construct 694 //! than the value_type and this function offers the possibility to use that key 695 //! to check if the insertion will be successful. 696 //! 697 //! If the check is successful, the user can construct the value_type and use 698 //! "insert_commit" to insert the object in constant-time. This can give a total 699 //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)). 700 //! 701 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more 702 //! objects are inserted or erased from the container. 703 template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare> insert_unique_check(const_iterator hint,const KeyType & key,KeyTypeKeyCompare comp,KeyValuePrioCompare key_value_pcomp,insert_commit_data & commit_data)704 std::pair<iterator, bool> insert_unique_check 705 ( const_iterator hint, const KeyType &key 706 , KeyTypeKeyCompare comp 707 , KeyValuePrioCompare key_value_pcomp 708 , insert_commit_data &commit_data) 709 { 710 std::pair<node_ptr, bool> const ret = 711 (node_algorithms::insert_unique_check 712 ( this->tree_type::header_ptr(), hint.pointed_node(), key 713 , this->key_node_comp(comp), this->key_node_prio_comp(key_value_pcomp), commit_data)); 714 return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second); 715 } 716 717 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data 718 //! must have been obtained from a previous call to "insert_check". 719 //! No objects should have been inserted or erased from the container between 720 //! the "insert_check" that filled "commit_data" and the call to "insert_commit". 721 //! 722 //! <b>Effects</b>: Inserts the value in the avl_set using the information obtained 723 //! from the "commit_data" that a previous "insert_check" filled. 724 //! 725 //! <b>Returns</b>: An iterator to the newly inserted object. 726 //! 727 //! <b>Complexity</b>: Constant time. 728 //! 729 //! <b>Throws</b>: Nothing 730 //! 731 //! <b>Notes</b>: This function has only sense if a "insert_check" has been 732 //! previously executed to fill "commit_data". No value should be inserted or 733 //! erased between the "insert_check" and "insert_commit" calls. insert_unique_commit(reference value,const insert_commit_data & commit_data)734 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) 735 { 736 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 737 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 738 node_algorithms::insert_unique_commit(this->tree_type::header_ptr(), to_insert, commit_data); 739 this->tree_type::sz_traits().increment(); 740 return iterator(to_insert, this->priv_value_traits_ptr()); 741 } 742 743 //! <b>Requires</b>: value must be an lvalue, "pos" must be 744 //! a valid iterator (or end) and must be the succesor of value 745 //! once inserted according to the predicate 746 //! 747 //! <b>Effects</b>: Inserts x into the container before "pos". 748 //! 749 //! <b>Complexity</b>: Constant time. 750 //! 751 //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee. 752 //! 753 //! <b>Note</b>: This function does not check preconditions so if "pos" is not 754 //! the successor of "value" container ordering invariant will be broken. 755 //! This is a low-level function to be used only for performance reasons 756 //! by advanced users. insert_before(const_iterator pos,reference value)757 iterator insert_before(const_iterator pos, reference value) 758 { 759 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 760 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 761 iterator ret 762 ( node_algorithms::insert_before 763 ( this->tree_type::header_ptr() 764 , pos.pointed_node() 765 , to_insert 766 , this->key_node_prio_comp(this->priv_pcomp()) 767 ) 768 , this->priv_value_traits_ptr()); 769 this->tree_type::sz_traits().increment(); 770 return ret; 771 } 772 773 //! <b>Requires</b>: value must be an lvalue, and it must be no less 774 //! than the greatest inserted key 775 //! 776 //! <b>Effects</b>: Inserts x into the container in the last position. 777 //! 778 //! <b>Complexity</b>: Constant time. 779 //! 780 //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee. 781 //! 782 //! <b>Note</b>: This function does not check preconditions so if value is 783 //! less than the greatest inserted key container ordering invariant will be broken. 784 //! This function is slightly more efficient than using "insert_before". 785 //! This is a low-level function to be used only for performance reasons 786 //! by advanced users. push_back(reference value)787 void push_back(reference value) 788 { 789 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 790 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 791 node_algorithms::push_back 792 (this->tree_type::header_ptr(), to_insert, this->key_node_prio_comp(this->priv_pcomp())); 793 this->tree_type::sz_traits().increment(); 794 } 795 796 //! <b>Requires</b>: value must be an lvalue, and it must be no greater 797 //! than the minimum inserted key 798 //! 799 //! <b>Effects</b>: Inserts x into the container in the first position. 800 //! 801 //! <b>Complexity</b>: Constant time. 802 //! 803 //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee. 804 //! 805 //! <b>Note</b>: This function does not check preconditions so if value is 806 //! greater than the minimum inserted key container ordering invariant will be broken. 807 //! This function is slightly more efficient than using "insert_before". 808 //! This is a low-level function to be used only for performance reasons 809 //! by advanced users. push_front(reference value)810 void push_front(reference value) 811 { 812 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 813 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 814 node_algorithms::push_front 815 (this->tree_type::header_ptr(), to_insert, this->key_node_prio_comp(this->priv_pcomp())); 816 this->tree_type::sz_traits().increment(); 817 } 818 819 //! <b>Effects</b>: Erases the element pointed to by i. 820 //! 821 //! <b>Complexity</b>: Average complexity for erase element is constant time. 822 //! 823 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. 824 //! 825 //! <b>Note</b>: Invalidates the iterators (but not the references) 826 //! to the erased elements. No destructors are called. erase(const_iterator i)827 iterator erase(const_iterator i) 828 { 829 const_iterator ret(i); 830 ++ret; 831 node_ptr to_erase(i.pointed_node()); 832 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(to_erase)); 833 node_algorithms::erase 834 (this->tree_type::header_ptr(), to_erase, this->key_node_prio_comp(this->priv_pcomp())); 835 this->tree_type::sz_traits().decrement(); 836 if(safemode_or_autounlink) 837 node_algorithms::init(to_erase); 838 return ret.unconst(); 839 } 840 841 //! <b>Effects</b>: Erases the range pointed to by b end e. 842 //! 843 //! <b>Complexity</b>: Average complexity for erase range is at most 844 //! O(log(size() + N)), where N is the number of elements in the range. 845 //! 846 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. 847 //! 848 //! <b>Note</b>: Invalidates the iterators (but not the references) 849 //! to the erased elements. No destructors are called. erase(const_iterator b,const_iterator e)850 iterator erase(const_iterator b, const_iterator e) 851 { size_type n; return private_erase(b, e, n); } 852 853 //! <b>Effects</b>: Erases all the elements with the given value. 854 //! 855 //! <b>Returns</b>: The number of erased elements. 856 //! 857 //! <b>Complexity</b>: O(log(size() + N). 858 //! 859 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. 860 //! 861 //! <b>Note</b>: Invalidates the iterators (but not the references) 862 //! to the erased elements. No destructors are called. erase(const key_type & key)863 size_type erase(const key_type &key) 864 { return this->erase(key, this->key_comp()); } 865 866 //! <b>Effects</b>: Erases all the elements with the given key. 867 //! according to the comparison functor "comp". 868 //! 869 //! <b>Returns</b>: The number of erased elements. 870 //! 871 //! <b>Complexity</b>: O(log(size() + N). 872 //! 873 //! <b>Throws</b>: if the internal priority_compare function throws. 874 //! Equivalent guarantee to <i>while(beg != end) erase(beg++);</i> 875 //! 876 //! <b>Note</b>: Invalidates the iterators (but not the references) 877 //! to the erased elements. No destructors are called. 878 template<class KeyType, class KeyTypeKeyCompare> BOOST_INTRUSIVE_DOC1ST(size_type,typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)879 BOOST_INTRUSIVE_DOC1ST(size_type 880 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) 881 erase(const KeyType& key, KeyTypeKeyCompare comp) 882 { 883 std::pair<iterator,iterator> p = this->equal_range(key, comp); 884 size_type n; 885 private_erase(p.first, p.second, n); 886 return n; 887 } 888 889 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 890 //! 891 //! <b>Effects</b>: Erases the element pointed to by i. 892 //! Disposer::operator()(pointer) is called for the removed element. 893 //! 894 //! <b>Complexity</b>: Average complexity for erase element is constant time. 895 //! 896 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. 897 //! 898 //! <b>Note</b>: Invalidates the iterators 899 //! to the erased elements. 900 template<class Disposer> erase_and_dispose(const_iterator i,Disposer disposer)901 iterator erase_and_dispose(const_iterator i, Disposer disposer) 902 { 903 node_ptr to_erase(i.pointed_node()); 904 iterator ret(this->erase(i)); 905 disposer(this->get_value_traits().to_value_ptr(to_erase)); 906 return ret; 907 } 908 909 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 910 template<class Disposer> erase_and_dispose(iterator i,Disposer disposer)911 iterator erase_and_dispose(iterator i, Disposer disposer) 912 { return this->erase_and_dispose(const_iterator(i), disposer); } 913 #endif 914 915 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 916 //! 917 //! <b>Effects</b>: Erases the range pointed to by b end e. 918 //! Disposer::operator()(pointer) is called for the removed elements. 919 //! 920 //! <b>Complexity</b>: Average complexity for erase range is at most 921 //! O(log(size() + N)), where N is the number of elements in the range. 922 //! 923 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee. 924 //! 925 //! <b>Note</b>: Invalidates the iterators 926 //! to the erased elements. 927 template<class Disposer> erase_and_dispose(const_iterator b,const_iterator e,Disposer disposer)928 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) 929 { size_type n; return private_erase(b, e, n, disposer); } 930 931 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 932 //! 933 //! <b>Effects</b>: Erases all the elements with the given value. 934 //! Disposer::operator()(pointer) is called for the removed elements. 935 //! 936 //! <b>Returns</b>: The number of erased elements. 937 //! 938 //! <b>Complexity</b>: O(log(size() + N). 939 //! 940 //! <b>Throws</b>: if the priority_compare function throws then weak guarantee and heap invariants are broken. 941 //! The safest thing would be to clear or destroy the container. 942 //! 943 //! <b>Note</b>: Invalidates the iterators (but not the references) 944 //! to the erased elements. No destructors are called. 945 template<class Disposer> erase_and_dispose(const key_type & key,Disposer disposer)946 size_type erase_and_dispose(const key_type &key, Disposer disposer) 947 { 948 std::pair<iterator,iterator> p = this->equal_range(key); 949 size_type n; 950 private_erase(p.first, p.second, n, disposer); 951 return n; 952 } 953 954 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 955 //! 956 //! <b>Effects</b>: Erases all the elements with the given key. 957 //! according to the comparison functor "comp". 958 //! Disposer::operator()(pointer) is called for the removed elements. 959 //! 960 //! <b>Returns</b>: The number of erased elements. 961 //! 962 //! <b>Complexity</b>: O(log(size() + N). 963 //! 964 //! <b>Throws</b>: if the priority_compare function throws then weak guarantee and heap invariants are broken. 965 //! The safest thing would be to clear or destroy the container. 966 //! 967 //! <b>Note</b>: Invalidates the iterators 968 //! to the erased elements. 969 template<class KeyType, class KeyTypeKeyCompare, class Disposer> BOOST_INTRUSIVE_DOC1ST(size_type,typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)970 BOOST_INTRUSIVE_DOC1ST(size_type 971 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) 972 erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer) 973 { 974 std::pair<iterator,iterator> p = this->equal_range(key, comp); 975 size_type n; 976 private_erase(p.first, p.second, n, disposer); 977 return n; 978 } 979 980 //! <b>Effects</b>: Erases all of the elements. 981 //! 982 //! <b>Complexity</b>: Linear to the number of elements on the container. 983 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. 984 //! 985 //! <b>Throws</b>: Nothing. 986 //! 987 //! <b>Note</b>: Invalidates the iterators (but not the references) 988 //! to the erased elements. No destructors are called. clear()989 void clear() 990 { tree_type::clear(); } 991 992 //! <b>Effects</b>: Erases all of the elements calling disposer(p) for 993 //! each node to be erased. 994 //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)), 995 //! where N is the number of elements in the container. 996 //! 997 //! <b>Throws</b>: Nothing. 998 //! 999 //! <b>Note</b>: Invalidates the iterators (but not the references) 1000 //! to the erased elements. Calls N times to disposer functor. 1001 template<class Disposer> clear_and_dispose(Disposer disposer)1002 void clear_and_dispose(Disposer disposer) 1003 { 1004 node_algorithms::clear_and_dispose(this->tree_type::header_ptr() 1005 , detail::node_disposer<Disposer, value_traits, TreapAlgorithms>(disposer, &this->get_value_traits())); 1006 node_algorithms::init_header(this->tree_type::header_ptr()); 1007 this->tree_type::sz_traits().set_size(0); 1008 } 1009 1010 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1011 //! @copydoc ::boost::intrusive::bstree::merge_unique 1012 template<class T, class ...Options2> void merge_unique(sgtree<T, Options2...> &); 1013 #else 1014 template<class Compare2> merge_unique(treap_impl<ValueTraits,VoidOrKeyOfValue,Compare2,VoidOrPrioComp,SizeType,ConstantTimeSize,HeaderHolder> & source)1015 void merge_unique(treap_impl 1016 <ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source) 1017 #endif 1018 { 1019 node_ptr it (node_algorithms::begin_node(source.header_ptr())) 1020 , itend(node_algorithms::end_node (source.header_ptr())); 1021 1022 while(it != itend){ 1023 node_ptr const p(it); 1024 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p)); 1025 it = node_algorithms::next_node(it); 1026 1027 if( node_algorithms::transfer_unique 1028 ( this->header_ptr(), this->key_node_comp(this->key_comp()) 1029 , this->key_node_prio_comp(this->priv_pcomp()), source.header_ptr(), p) ){ 1030 this->sz_traits().increment(); 1031 source.sz_traits().decrement(); 1032 } 1033 } 1034 } 1035 1036 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1037 //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&) 1038 template<class T, class ...Options2> void merge_equal(sgtree<T, Options2...> &); 1039 #else 1040 template<class Compare2> merge_equal(treap_impl<ValueTraits,VoidOrKeyOfValue,Compare2,VoidOrPrioComp,SizeType,ConstantTimeSize,HeaderHolder> & source)1041 void merge_equal(treap_impl 1042 <ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source) 1043 #endif 1044 { 1045 node_ptr it (node_algorithms::begin_node(source.header_ptr())) 1046 , itend(node_algorithms::end_node (source.header_ptr())); 1047 1048 while(it != itend){ 1049 node_ptr const p(it); 1050 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p)); 1051 it = node_algorithms::next_node(it); 1052 node_algorithms::transfer_equal 1053 ( this->header_ptr(), this->key_node_comp(this->key_comp()) 1054 , this->key_node_prio_comp(this->priv_pcomp()), source.header_ptr(), p); 1055 this->sz_traits().increment(); 1056 source.sz_traits().decrement(); 1057 } 1058 } 1059 1060 //! @copydoc ::boost::intrusive::bstree::check(ExtraChecker)const 1061 template <class ExtraChecker> check(ExtraChecker extra_checker) const1062 void check(ExtraChecker extra_checker) const 1063 { 1064 typedef detail::key_nodeptr_comp<priority_compare, value_traits, key_of_value> nodeptr_prio_comp_t; 1065 tree_type::check(detail::treap_node_extra_checker 1066 <ValueTraits, nodeptr_prio_comp_t, ExtraChecker> 1067 (this->key_node_prio_comp(this->priv_pcomp()), extra_checker)); 1068 } 1069 1070 //! @copydoc ::boost::intrusive::bstree::check()const check() const1071 void check() const 1072 { check(detail::empty_node_checker<ValueTraits>()); } 1073 1074 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1075 //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const 1076 size_type count(const key_type &key) const; 1077 1078 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const 1079 template<class KeyType, class KeyTypeKeyCompare> 1080 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; 1081 1082 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) 1083 iterator lower_bound(const key_type &key); 1084 1085 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) 1086 template<class KeyType, class KeyTypeKeyCompare> 1087 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); 1088 1089 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const 1090 const_iterator lower_bound(const key_type &key) const; 1091 1092 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const 1093 template<class KeyType, class KeyTypeKeyCompare> 1094 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 1095 1096 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) 1097 iterator upper_bound(const key_type &key); 1098 1099 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) 1100 template<class KeyType, class KeyTypeKeyCompare> 1101 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); 1102 1103 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const 1104 const_iterator upper_bound(const key_type &key) const; 1105 1106 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const 1107 template<class KeyType, class KeyTypeKeyCompare> 1108 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 1109 1110 //! @copydoc ::boost::intrusive::bstree::find(const key_type &) 1111 iterator find(const key_type &key); 1112 1113 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) 1114 template<class KeyType, class KeyTypeKeyCompare> 1115 iterator find(const KeyType& key, KeyTypeKeyCompare comp); 1116 1117 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const 1118 const_iterator find(const key_type &key) const; 1119 1120 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const 1121 template<class KeyType, class KeyTypeKeyCompare> 1122 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; 1123 1124 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) 1125 std::pair<iterator,iterator> equal_range(const key_type &key); 1126 1127 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) 1128 template<class KeyType, class KeyTypeKeyCompare> 1129 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); 1130 1131 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const 1132 std::pair<const_iterator, const_iterator> 1133 equal_range(const key_type &key) const; 1134 1135 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const 1136 template<class KeyType, class KeyTypeKeyCompare> 1137 std::pair<const_iterator, const_iterator> 1138 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const; 1139 1140 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) 1141 std::pair<iterator,iterator> bounded_range 1142 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed); 1143 1144 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) 1145 template<class KeyType, class KeyTypeKeyCompare> 1146 std::pair<iterator,iterator> bounded_range 1147 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); 1148 1149 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const 1150 std::pair<const_iterator, const_iterator> 1151 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; 1152 1153 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const 1154 template<class KeyType, class KeyTypeKeyCompare> 1155 std::pair<const_iterator, const_iterator> bounded_range 1156 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; 1157 1158 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference) 1159 static iterator s_iterator_to(reference value); 1160 1161 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference) 1162 static const_iterator s_iterator_to(const_reference value); 1163 1164 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference) 1165 iterator iterator_to(reference value); 1166 1167 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const 1168 const_iterator iterator_to(const_reference value) const; 1169 1170 //! @copydoc ::boost::intrusive::bstree::init_node(reference) 1171 static void init_node(reference value); 1172 1173 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance 1174 pointer unlink_leftmost_without_rebalance(); 1175 1176 //! @copydoc ::boost::intrusive::bstree::replace_node 1177 void replace_node(iterator replace_this, reference with_this); 1178 1179 //! @copydoc ::boost::intrusive::bstree::remove_node 1180 void remove_node(reference value); 1181 1182 friend bool operator< (const treap_impl &x, const treap_impl &y); 1183 1184 friend bool operator==(const treap_impl &x, const treap_impl &y); 1185 1186 friend bool operator!= (const treap_impl &x, const treap_impl &y); 1187 1188 friend bool operator>(const treap_impl &x, const treap_impl &y); 1189 1190 friend bool operator<=(const treap_impl &x, const treap_impl &y); 1191 1192 friend bool operator>=(const treap_impl &x, const treap_impl &y); 1193 1194 friend void swap(treap_impl &x, treap_impl &y); 1195 1196 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1197 1198 /// @cond 1199 private: 1200 template<class Disposer> private_erase(const_iterator b,const_iterator e,size_type & n,Disposer disposer)1201 iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer) 1202 { 1203 for(n = 0; b != e; ++n) 1204 this->erase_and_dispose(b++, disposer); 1205 return b.unconst(); 1206 } 1207 private_erase(const_iterator b,const_iterator e,size_type & n)1208 iterator private_erase(const_iterator b, const_iterator e, size_type &n) 1209 { 1210 for(n = 0; b != e; ++n) 1211 this->erase(b++); 1212 return b.unconst(); 1213 } 1214 /// @endcond 1215 }; 1216 1217 1218 //! Helper metafunction to define a \c treap that yields to the same type when the 1219 //! same options (either explicitly or implicitly) are used. 1220 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1221 template<class T, class ...Options> 1222 #else 1223 template<class T, class O1 = void, class O2 = void 1224 , class O3 = void, class O4 = void 1225 , class O5 = void, class O6 = void> 1226 #endif 1227 struct make_treap 1228 { 1229 typedef typename pack_options 1230 < treap_defaults, 1231 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1232 O1, O2, O3, O4, O5, O6 1233 #else 1234 Options... 1235 #endif 1236 >::type packed_options; 1237 1238 typedef typename detail::get_value_traits 1239 <T, typename packed_options::proto_value_traits>::type value_traits; 1240 1241 typedef treap_impl 1242 < value_traits 1243 , typename packed_options::key_of_value 1244 , typename packed_options::compare 1245 , typename packed_options::priority 1246 , typename packed_options::size_type 1247 , packed_options::constant_time_size 1248 , typename packed_options::header_holder_type 1249 > implementation_defined; 1250 /// @endcond 1251 typedef implementation_defined type; 1252 }; 1253 1254 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1255 1256 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1257 template<class T, class O1, class O2, class O3, class O4, class O5, class O6> 1258 #else 1259 template<class T, class ...Options> 1260 #endif 1261 class treap 1262 : public make_treap<T, 1263 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1264 O1, O2, O3, O4, O5, O6 1265 #else 1266 Options... 1267 #endif 1268 >::type 1269 { 1270 typedef typename make_treap 1271 <T, 1272 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1273 O1, O2, O3, O4, O5, O6 1274 #else 1275 Options... 1276 #endif 1277 >::type Base; 1278 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap) 1279 1280 public: 1281 typedef typename Base::key_compare key_compare; 1282 typedef typename Base::priority_compare priority_compare; 1283 typedef typename Base::value_traits value_traits; 1284 typedef typename Base::iterator iterator; 1285 typedef typename Base::const_iterator const_iterator; 1286 typedef typename Base::reverse_iterator reverse_iterator; 1287 typedef typename Base::const_reverse_iterator const_reverse_iterator; 1288 1289 //Assert if passed value traits are compatible with the type 1290 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); treap()1291 treap() 1292 : Base() 1293 {} 1294 treap(const key_compare & cmp,const priority_compare & pcmp=priority_compare (),const value_traits & v_traits=value_traits ())1295 explicit treap( const key_compare &cmp 1296 , const priority_compare &pcmp = priority_compare() 1297 , const value_traits &v_traits = value_traits()) 1298 : Base(cmp, pcmp, v_traits) 1299 {} 1300 1301 template<class Iterator> treap(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const priority_compare & pcmp=priority_compare (),const value_traits & v_traits=value_traits ())1302 treap( bool unique, Iterator b, Iterator e 1303 , const key_compare &cmp = key_compare() 1304 , const priority_compare &pcmp = priority_compare() 1305 , const value_traits &v_traits = value_traits()) 1306 : Base(unique, b, e, cmp, pcmp, v_traits) 1307 {} 1308 treap(BOOST_RV_REF (treap)x)1309 treap(BOOST_RV_REF(treap) x) 1310 : Base(BOOST_MOVE_BASE(Base, x)) 1311 {} 1312 operator =(BOOST_RV_REF (treap)x)1313 treap& operator=(BOOST_RV_REF(treap) x) 1314 { return static_cast<treap&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 1315 1316 template <class Cloner, class Disposer> clone_from(const treap & src,Cloner cloner,Disposer disposer)1317 void clone_from(const treap &src, Cloner cloner, Disposer disposer) 1318 { Base::clone_from(src, cloner, disposer); } 1319 1320 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (treap)src,Cloner cloner,Disposer disposer)1321 void clone_from(BOOST_RV_REF(treap) src, Cloner cloner, Disposer disposer) 1322 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 1323 container_from_end_iterator(iterator end_iterator)1324 static treap &container_from_end_iterator(iterator end_iterator) 1325 { return static_cast<treap &>(Base::container_from_end_iterator(end_iterator)); } 1326 container_from_end_iterator(const_iterator end_iterator)1327 static const treap &container_from_end_iterator(const_iterator end_iterator) 1328 { return static_cast<const treap &>(Base::container_from_end_iterator(end_iterator)); } 1329 container_from_iterator(iterator it)1330 static treap &container_from_iterator(iterator it) 1331 { return static_cast<treap &>(Base::container_from_iterator(it)); } 1332 container_from_iterator(const_iterator it)1333 static const treap &container_from_iterator(const_iterator it) 1334 { return static_cast<const treap &>(Base::container_from_iterator(it)); } 1335 }; 1336 1337 #endif 1338 1339 } //namespace intrusive 1340 } //namespace boost 1341 1342 #include <boost/intrusive/detail/config_end.hpp> 1343 1344 #endif //BOOST_INTRUSIVE_TREAP_HPP 1345