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