1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2008-2013
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)
9 // See http://www.boost.org/libs/intrusive for documentation.
11 /////////////////////////////////////////////////////////////////////////////
12 #ifndef BOOST_INTRUSIVE_TREAP_HPP
13 #define BOOST_INTRUSIVE_TREAP_HPP
15 #include <boost/intrusive/detail/config_begin.hpp>
16 #include <boost/intrusive/intrusive_fwd.hpp>
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>
32 #include <boost/static_assert.hpp>
33 #include <boost/move/utility_core.hpp>
34 #include <boost/move/adl_move_swap.hpp>
37 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>
38 #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair
40 #if defined(BOOST_HAS_PRAGMA_ONCE)
52 typedef void priority;
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
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.
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>
73 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
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
82 , typename bstree_impl
83 <ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder>::key_type>::type
88 typedef ValueTraits value_traits;
90 typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType
91 , ConstantTimeSize, BsTreeAlgorithms
92 , HeaderHolder> tree_type;
93 typedef tree_type implementation_defined;
96 , typename tree_type::key_type> get_prio_type;
98 typedef detail::ebo_functor_holder
99 <typename get_prio_type::type> prio_base;
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;
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;
129 typedef detail::key_nodeptr_comp<priority_compare, value_traits, key_of_value> key_node_prio_comp_t;
131 template<class KeyPrioComp>
132 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()); }
139 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_impl)
141 const priority_compare &priv_pcomp() const
142 { return static_cast<const prio_base&>(*this).get(); }
144 priority_compare &priv_pcomp()
145 { return static_cast<prio_base&>(*this).get(); }
150 typedef typename node_algorithms::insert_commit_data insert_commit_data;
152 //! <b>Effects</b>: Constructs an empty container.
154 //! <b>Complexity</b>: Constant.
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.
160 : tree_type(), prio_base(priority_compare())
163 //! <b>Effects</b>: Constructs an empty container.
165 //! <b>Complexity</b>: Constant.
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.
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)
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.
179 //! <b>Effects</b>: Constructs an empty container and inserts elements from
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.
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>
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)
197 this->insert_unique(b, e);
199 this->insert_equal(b, e);
202 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
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()))
208 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
209 treap_impl& operator=(BOOST_RV_REF(treap_impl) x)
210 { this->swap(x); return *this; }
212 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
213 //! @copydoc ::boost::intrusive::bstree::~bstree()
216 //! @copydoc ::boost::intrusive::bstree::begin()
219 //! @copydoc ::boost::intrusive::bstree::begin()const
220 const_iterator begin() const;
222 //! @copydoc ::boost::intrusive::bstree::cbegin()const
223 const_iterator cbegin() const;
225 //! @copydoc ::boost::intrusive::bstree::end()
228 //! @copydoc ::boost::intrusive::bstree::end()const
229 const_iterator end() const;
231 //! @copydoc ::boost::intrusive::bstree::cend()const
232 const_iterator cend() const;
235 //! <b>Effects</b>: Returns an iterator pointing to the highest priority object of the treap.
237 //! <b>Complexity</b>: Constant.
239 //! <b>Throws</b>: Nothing.
241 { return this->tree_type::root(); }
243 //! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the treap..
245 //! <b>Complexity</b>: Constant.
247 //! <b>Throws</b>: Nothing.
248 const_iterator top() const
249 { return this->ctop(); }
251 //! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the treap..
253 //! <b>Complexity</b>: Constant.
255 //! <b>Throws</b>: Nothing.
256 const_iterator ctop() const
257 { return this->tree_type::root(); }
259 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
260 //! @copydoc ::boost::intrusive::bstree::rbegin()
261 reverse_iterator rbegin();
263 //! @copydoc ::boost::intrusive::bstree::rbegin()const
264 const_reverse_iterator rbegin() const;
266 //! @copydoc ::boost::intrusive::bstree::crbegin()const
267 const_reverse_iterator crbegin() const;
269 //! @copydoc ::boost::intrusive::bstree::rend()
270 reverse_iterator rend();
272 //! @copydoc ::boost::intrusive::bstree::rend()const
273 const_reverse_iterator rend() const;
275 //! @copydoc ::boost::intrusive::bstree::crend()const
276 const_reverse_iterator crend() const;
278 //! @copydoc ::boost::intrusive::bstree::root()
281 //! @copydoc ::boost::intrusive::bstree::root()const
282 const_iterator root() const;
284 //! @copydoc ::boost::intrusive::bstree::croot()const
285 const_iterator croot() const;
289 //! <b>Effects</b>: Returns a reverse_iterator pointing to the highest priority object of the
292 //! <b>Complexity</b>: Constant.
294 //! <b>Throws</b>: Nothing.
295 reverse_iterator rtop()
296 { return reverse_iterator(this->top()); }
298 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority objec
299 //! of the reversed treap.
301 //! <b>Complexity</b>: Constant.
303 //! <b>Throws</b>: Nothing.
304 const_reverse_iterator rtop() const
305 { return const_reverse_iterator(this->top()); }
307 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority object
308 //! of the reversed treap.
310 //! <b>Complexity</b>: Constant.
312 //! <b>Throws</b>: Nothing.
313 const_reverse_iterator crtop() const
314 { return const_reverse_iterator(this->top()); }
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);
320 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
321 static const treap_impl &container_from_end_iterator(const_iterator end_iterator);
323 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
324 static treap_impl &container_from_iterator(iterator it);
326 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
327 static const treap_impl &container_from_iterator(const_iterator it);
329 //! @copydoc ::boost::intrusive::bstree::key_comp()const
330 key_compare key_comp() const;
332 //! @copydoc ::boost::intrusive::bstree::value_comp()const
333 value_compare value_comp() const;
335 //! @copydoc ::boost::intrusive::bstree::empty()const
338 //! @copydoc ::boost::intrusive::bstree::size()const
339 size_type size() const;
340 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
342 //! <b>Effects</b>: Returns the priority_compare object used by the container.
344 //! <b>Complexity</b>: Constant.
346 //! <b>Throws</b>: If priority_compare copy-constructor throws.
347 priority_compare priority_comp() const
348 { return this->priv_pcomp(); }
350 //! <b>Effects</b>: Swaps the contents of two treaps.
352 //! <b>Complexity</b>: Constant.
354 //! <b>Throws</b>: If the comparison functor's swap call throws.
355 void swap(treap_impl& other)
358 ::boost::adl_move_swap(this->priv_pcomp(), other.priv_pcomp());
359 tree_type::swap(other);
362 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
363 //! Cloner should yield to nodes equivalent to the original nodes.
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.
370 //! If cloner throws, all cloned elements are unlinked and disposed
371 //! calling Disposer::operator()(pointer).
373 //! <b>Complexity</b>: Linear to erased plus inserted elements.
375 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
376 template <class Cloner, class Disposer>
377 void clone_from(const treap_impl &src, Cloner cloner, Disposer disposer)
379 tree_type::clone_from(src, cloner, disposer);
380 this->priv_pcomp() = src.priv_pcomp();
383 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
384 //! Cloner should yield to nodes equivalent to the original nodes.
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.
391 //! If cloner throws, all cloned elements are unlinked and disposed
392 //! calling Disposer::operator()(pointer).
394 //! <b>Complexity</b>: Linear to erased plus inserted elements.
396 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
397 template <class Cloner, class Disposer>
398 void clone_from(BOOST_RV_REF(treap_impl) src, Cloner cloner, Disposer disposer)
400 tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);
401 this->priv_pcomp() = ::boost::move(src.priv_pcomp());
404 //! <b>Requires</b>: value must be an lvalue
406 //! <b>Effects</b>: Inserts value into the container before the upper bound.
408 //! <b>Complexity</b>: Average complexity for insert element is at
409 //! most logarithmic.
411 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. Strong guarantee.
413 //! <b>Note</b>: Does not affect the validity of iterators and references.
414 //! No copy-constructors are called.
415 iterator insert_equal(reference value)
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));
420 ( node_algorithms::insert_equal_upper_bound
421 ( this->tree_type::header_ptr()
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();
430 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
431 //! a valid iterator.
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)
437 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
438 //! constant time if t is inserted immediately before hint.
440 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. Strong guarantee.
442 //! <b>Note</b>: Does not affect the validity of iterators and references.
443 //! No copy-constructors are called.
444 iterator insert_equal(const_iterator hint, reference value)
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));
449 (node_algorithms::insert_equal
450 ( this->tree_type::header_ptr()
451 , hint.pointed_node()
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();
460 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
461 //! of type value_type.
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.
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
470 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw.
471 //! Strong guarantee.
473 //! <b>Note</b>: Does not affect the validity of iterators and references.
474 //! No copy-constructors are called.
475 template<class Iterator>
476 void insert_equal(Iterator b, Iterator e)
478 iterator iend(this->end());
480 this->insert_equal(iend, *b);
483 //! <b>Requires</b>: value must be an lvalue
485 //! <b>Effects</b>: Inserts value into the container if the value
486 //! is not already present.
488 //! <b>Complexity</b>: Average complexity for insert element is at
489 //! most logarithmic.
491 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw.
492 //! Strong guarantee.
494 //! <b>Note</b>: Does not affect the validity of iterators and references.
495 //! No copy-constructors are called.
496 std::pair<iterator, bool> insert_unique(reference value)
498 insert_commit_data commit_data;
499 std::pair<iterator, bool> ret = this->insert_unique_check(key_of_value()(value), commit_data);
502 return std::pair<iterator, bool> (this->insert_unique_commit(value, commit_data), true);
505 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
508 //! <b>Effects</b>: Tries to insert x into the container, using "hint" as a hint
509 //! to where it will be inserted.
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.
515 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw.
516 //! Strong guarantee.
518 //! <b>Note</b>: Does not affect the validity of iterators and references.
519 //! No copy-constructors are called.
520 iterator insert_unique(const_iterator hint, reference value)
522 insert_commit_data commit_data;
523 std::pair<iterator, bool> ret = this->insert_unique_check(hint, key_of_value()(value), commit_data);
526 return this->insert_unique_commit(value, commit_data);
529 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
530 //! of type value_type.
532 //! <b>Effects</b>: Tries to insert each element of a range into the container.
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
538 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw.
539 //! Strong guarantee.
541 //! <b>Note</b>: Does not affect the validity of iterators and references.
542 //! No copy-constructors are called.
543 template<class Iterator>
544 void insert_unique(Iterator b, Iterator e)
547 iterator iend(this->end());
549 this->insert_unique(iend, *b);
553 this->insert_unique(*b);
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.
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.
566 //! <b>Complexity</b>: Average complexity is at most logarithmic.
568 //! <b>Throws</b>: If the comparison or predicate functions throw. Strong guarantee.
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.
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)).
581 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
582 //! objects are inserted or erased from the container.
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); }
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.
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.
597 //! <b>Complexity</b>: Logarithmic in general, but it's amortized
598 //! constant time if t is inserted immediately before hint.
600 //! <b>Throws</b>: If the comparison or predicate functions throw. Strong guarantee.
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.
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)).
613 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
614 //! objects are inserted or erased from the container.
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); }
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.
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.
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.
634 //! <b>Complexity</b>: Average complexity is at most logarithmic.
636 //! <b>Throws</b>: If the comp or key_value_pcomp
637 //! ordering functions throw. Strong guarantee.
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.
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)).
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>
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)
658 ( const KeyType &key, KeyTypeKeyCompare comp
659 , KeyValuePrioCompare key_value_pcomp, insert_commit_data &commit_data)
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);
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.
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.
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.
684 //! <b>Complexity</b>: Logarithmic in general, but it's amortized
685 //! constant time if t is inserted immediately before hint.
687 //! <b>Throws</b>: If the comp or key_value_pcomp
688 //! ordering functions throw. Strong guarantee.
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.
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)).
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>
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)
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);
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".
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.
725 //! <b>Returns</b>: An iterator to the newly inserted object.
727 //! <b>Complexity</b>: Constant time.
729 //! <b>Throws</b>: Nothing
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.
734 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data)
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());
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
747 //! <b>Effects</b>: Inserts x into the container before "pos".
749 //! <b>Complexity</b>: Constant time.
751 //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
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.
757 iterator insert_before(const_iterator pos, reference value)
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));
762 ( node_algorithms::insert_before
763 ( this->tree_type::header_ptr()
766 , this->key_node_prio_comp(this->priv_pcomp())
768 , this->priv_value_traits_ptr());
769 this->tree_type::sz_traits().increment();
773 //! <b>Requires</b>: value must be an lvalue, and it must be no less
774 //! than the greatest inserted key
776 //! <b>Effects</b>: Inserts x into the container in the last position.
778 //! <b>Complexity</b>: Constant time.
780 //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
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.
787 void push_back(reference value)
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();
796 //! <b>Requires</b>: value must be an lvalue, and it must be no greater
797 //! than the minimum inserted key
799 //! <b>Effects</b>: Inserts x into the container in the first position.
801 //! <b>Complexity</b>: Constant time.
803 //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
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.
810 void push_front(reference value)
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();
819 //! <b>Effects</b>: Erases the element pointed to by i.
821 //! <b>Complexity</b>: Average complexity for erase element is constant time.
823 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
825 //! <b>Note</b>: Invalidates the iterators (but not the references)
826 //! to the erased elements. No destructors are called.
827 iterator erase(const_iterator i)
829 const_iterator ret(i);
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();
841 //! <b>Effects</b>: Erases the range pointed to by b end e.
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.
846 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
848 //! <b>Note</b>: Invalidates the iterators (but not the references)
849 //! to the erased elements. No destructors are called.
850 iterator erase(const_iterator b, const_iterator e)
851 { size_type n; return private_erase(b, e, n); }
853 //! <b>Effects</b>: Erases all the elements with the given value.
855 //! <b>Returns</b>: The number of erased elements.
857 //! <b>Complexity</b>: O(log(size() + N).
859 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
861 //! <b>Note</b>: Invalidates the iterators (but not the references)
862 //! to the erased elements. No destructors are called.
863 size_type erase(const key_type &key)
864 { return this->erase(key, this->key_comp()); }
866 //! <b>Effects</b>: Erases all the elements with the given key.
867 //! according to the comparison functor "comp".
869 //! <b>Returns</b>: The number of erased elements.
871 //! <b>Complexity</b>: O(log(size() + N).
873 //! <b>Throws</b>: if the internal priority_compare function throws.
874 //! Equivalent guarantee to <i>while(beg != end) erase(beg++);</i>
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>
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)
883 std::pair<iterator,iterator> p = this->equal_range(key, comp);
885 private_erase(p.first, p.second, n);
889 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
891 //! <b>Effects</b>: Erases the element pointed to by i.
892 //! Disposer::operator()(pointer) is called for the removed element.
894 //! <b>Complexity</b>: Average complexity for erase element is constant time.
896 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
898 //! <b>Note</b>: Invalidates the iterators
899 //! to the erased elements.
900 template<class Disposer>
901 iterator erase_and_dispose(const_iterator i, Disposer disposer)
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));
909 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
910 template<class Disposer>
911 iterator erase_and_dispose(iterator i, Disposer disposer)
912 { return this->erase_and_dispose(const_iterator(i), disposer); }
915 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
917 //! <b>Effects</b>: Erases the range pointed to by b end e.
918 //! Disposer::operator()(pointer) is called for the removed elements.
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.
923 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
925 //! <b>Note</b>: Invalidates the iterators
926 //! to the erased elements.
927 template<class 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); }
931 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
933 //! <b>Effects</b>: Erases all the elements with the given value.
934 //! Disposer::operator()(pointer) is called for the removed elements.
936 //! <b>Returns</b>: The number of erased elements.
938 //! <b>Complexity</b>: O(log(size() + N).
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.
943 //! <b>Note</b>: Invalidates the iterators (but not the references)
944 //! to the erased elements. No destructors are called.
945 template<class Disposer>
946 size_type erase_and_dispose(const key_type &key, Disposer disposer)
948 std::pair<iterator,iterator> p = this->equal_range(key);
950 private_erase(p.first, p.second, n, disposer);
954 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
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.
960 //! <b>Returns</b>: The number of erased elements.
962 //! <b>Complexity</b>: O(log(size() + N).
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.
967 //! <b>Note</b>: Invalidates the iterators
968 //! to the erased elements.
969 template<class KeyType, class KeyTypeKeyCompare, class Disposer>
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)
974 std::pair<iterator,iterator> p = this->equal_range(key, comp);
976 private_erase(p.first, p.second, n, disposer);
980 //! <b>Effects</b>: Erases all of the elements.
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.
985 //! <b>Throws</b>: Nothing.
987 //! <b>Note</b>: Invalidates the iterators (but not the references)
988 //! to the erased elements. No destructors are called.
990 { tree_type::clear(); }
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.
997 //! <b>Throws</b>: Nothing.
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>
1002 void clear_and_dispose(Disposer disposer)
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);
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...> &);
1014 template<class Compare2>
1015 void merge_unique(treap_impl
1016 <ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
1019 node_ptr it (node_algorithms::begin_node(source.header_ptr()))
1020 , itend(node_algorithms::end_node (source.header_ptr()));
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);
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();
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...> &);
1040 template<class Compare2>
1041 void merge_equal(treap_impl
1042 <ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
1045 node_ptr it (node_algorithms::begin_node(source.header_ptr()))
1046 , itend(node_algorithms::end_node (source.header_ptr()));
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();
1060 //! @copydoc ::boost::intrusive::bstree::check(ExtraChecker)const
1061 template <class ExtraChecker>
1062 void check(ExtraChecker extra_checker) const
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));
1070 //! @copydoc ::boost::intrusive::bstree::check()const
1072 { check(detail::empty_node_checker<ValueTraits>()); }
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;
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;
1082 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)
1083 iterator lower_bound(const key_type &key);
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);
1089 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const
1090 const_iterator lower_bound(const key_type &key) const;
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;
1096 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)
1097 iterator upper_bound(const key_type &key);
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);
1103 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const
1104 const_iterator upper_bound(const key_type &key) const;
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;
1110 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)
1111 iterator find(const key_type &key);
1113 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)
1114 template<class KeyType, class KeyTypeKeyCompare>
1115 iterator find(const KeyType& key, KeyTypeKeyCompare comp);
1117 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const
1118 const_iterator find(const key_type &key) const;
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;
1124 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)
1125 std::pair<iterator,iterator> equal_range(const key_type &key);
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);
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;
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;
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);
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);
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;
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;
1158 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
1159 static iterator s_iterator_to(reference value);
1161 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
1162 static const_iterator s_iterator_to(const_reference value);
1164 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
1165 iterator iterator_to(reference value);
1167 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
1168 const_iterator iterator_to(const_reference value) const;
1170 //! @copydoc ::boost::intrusive::bstree::init_node(reference)
1171 static void init_node(reference value);
1173 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
1174 pointer unlink_leftmost_without_rebalance();
1176 //! @copydoc ::boost::intrusive::bstree::replace_node
1177 void replace_node(iterator replace_this, reference with_this);
1179 //! @copydoc ::boost::intrusive::bstree::remove_node
1180 void remove_node(reference value);
1182 friend bool operator< (const treap_impl &x, const treap_impl &y);
1184 friend bool operator==(const treap_impl &x, const treap_impl &y);
1186 friend bool operator!= (const treap_impl &x, const treap_impl &y);
1188 friend bool operator>(const treap_impl &x, const treap_impl &y);
1190 friend bool operator<=(const treap_impl &x, const treap_impl &y);
1192 friend bool operator>=(const treap_impl &x, const treap_impl &y);
1194 friend void swap(treap_impl &x, treap_impl &y);
1196 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1200 template<class Disposer>
1201 iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer)
1203 for(n = 0; b != e; ++n)
1204 this->erase_and_dispose(b++, disposer);
1208 iterator private_erase(const_iterator b, const_iterator e, size_type &n)
1210 for(n = 0; b != e; ++n)
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>
1223 template<class T, class O1 = void, class O2 = void
1224 , class O3 = void, class O4 = void
1225 , class O5 = void, class O6 = void>
1229 typedef typename pack_options
1231 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1232 O1, O2, O3, O4, O5, O6
1236 >::type packed_options;
1238 typedef typename detail::get_value_traits
1239 <T, typename packed_options::proto_value_traits>::type 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;
1251 typedef implementation_defined type;
1254 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1256 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1257 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
1259 template<class T, class ...Options>
1262 : public make_treap<T,
1263 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1264 O1, O2, O3, O4, O5, O6
1270 typedef typename make_treap
1272 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1273 O1, O2, O3, O4, O5, O6
1278 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap)
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;
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));
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)
1301 template<class Iterator>
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)
1309 treap(BOOST_RV_REF(treap) x)
1310 : Base(BOOST_MOVE_BASE(Base, x))
1313 treap& operator=(BOOST_RV_REF(treap) x)
1314 { return static_cast<treap&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
1316 template <class Cloner, class Disposer>
1317 void clone_from(const treap &src, Cloner cloner, Disposer disposer)
1318 { Base::clone_from(src, cloner, disposer); }
1320 template <class Cloner, class 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); }
1324 static treap &container_from_end_iterator(iterator end_iterator)
1325 { return static_cast<treap &>(Base::container_from_end_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)); }
1330 static treap &container_from_iterator(iterator it)
1331 { return static_cast<treap &>(Base::container_from_iterator(it)); }
1333 static const treap &container_from_iterator(const_iterator it)
1334 { return static_cast<const treap &>(Base::container_from_iterator(it)); }
1339 } //namespace intrusive
1342 #include <boost/intrusive/detail/config_end.hpp>
1344 #endif //BOOST_INTRUSIVE_TREAP_HPP