1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2006-2009
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_RBTREE_HPP
13 #define BOOST_INTRUSIVE_RBTREE_HPP
15 #include <boost/intrusive/detail/config_begin.hpp>
22 #include <boost/intrusive/detail/assert.hpp>
23 #include <boost/static_assert.hpp>
24 #include <boost/intrusive/intrusive_fwd.hpp>
25 #include <boost/intrusive/set_hook.hpp>
26 #include <boost/intrusive/detail/rbtree_node.hpp>
27 #include <boost/intrusive/detail/tree_node.hpp>
28 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
29 #include <boost/intrusive/detail/mpl.hpp>
30 #include <boost/intrusive/detail/pointer_to_other.hpp>
31 #include <boost/intrusive/detail/clear_on_destructor_base.hpp>
32 #include <boost/intrusive/detail/function_detector.hpp>
33 #include <boost/intrusive/options.hpp>
34 #include <boost/intrusive/rbtree_algorithms.hpp>
35 #include <boost/intrusive/link_mode.hpp>
36 #include <boost/move/move.hpp>
43 template <class ValueTraits, class Compare, class SizeType, bool ConstantTimeSize>
46 typedef ValueTraits value_traits;
47 typedef Compare compare;
48 typedef SizeType size_type;
49 static const bool constant_time_size = ConstantTimeSize;
56 , base_hook<detail::default_set_hook>
57 , constant_time_size<true>
58 , size_type<std::size_t>
59 , compare<std::less<T> >
65 //! The class template rbtree is an intrusive red-black tree container, that
66 //! is used to construct intrusive set and multiset containers. The no-throw
67 //! guarantee holds only, if the value_compare object
70 //! The template parameter \c T is the type to be managed by the container.
71 //! The user can specify additional options and if no options are provided
72 //! default options are used.
74 //! The container supports the following options:
75 //! \c base_hook<>/member_hook<>/value_traits<>,
76 //! \c constant_time_size<>, \c size_type<> and
78 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
79 template<class T, class ...Options>
81 template<class Config>
84 : private detail::clear_on_destructor_base<rbtree_impl<Config> >
86 template<class C> friend class detail::clear_on_destructor_base;
88 typedef typename Config::value_traits value_traits;
90 static const bool external_value_traits =
91 detail::external_value_traits_is_true<value_traits>::value;
92 typedef typename detail::eval_if_c
93 < external_value_traits
94 , detail::eval_value_traits<value_traits>
95 , detail::identity<value_traits>
96 >::type real_value_traits;
98 typedef typename real_value_traits::pointer pointer;
99 typedef typename real_value_traits::const_pointer const_pointer;
100 typedef typename std::iterator_traits<pointer>::value_type value_type;
101 typedef value_type key_type;
102 typedef typename std::iterator_traits<pointer>::reference reference;
103 typedef typename std::iterator_traits<const_pointer>::reference const_reference;
104 typedef typename std::iterator_traits<pointer>::difference_type difference_type;
105 typedef typename Config::size_type size_type;
106 typedef typename Config::compare value_compare;
107 typedef value_compare key_compare;
108 typedef tree_iterator<rbtree_impl, false> iterator;
109 typedef tree_iterator<rbtree_impl, true> const_iterator;
110 typedef std::reverse_iterator<iterator> reverse_iterator;
111 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
112 typedef typename real_value_traits::node_traits node_traits;
113 typedef typename node_traits::node node;
114 typedef typename node_traits::node_ptr node_ptr;
115 typedef typename node_traits::const_node_ptr const_node_ptr;
116 typedef rbtree_algorithms<node_traits> node_algorithms;
118 static const bool constant_time_size = Config::constant_time_size;
119 static const bool stateful_value_traits = detail::is_stateful_value_traits<real_value_traits>::value;
122 typedef detail::size_holder<constant_time_size, size_type> size_traits;
125 BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree_impl)
127 enum { safemode_or_autounlink =
128 (int)real_value_traits::link_mode == (int)auto_unlink ||
129 (int)real_value_traits::link_mode == (int)safe_link };
131 //Constant-time size is incompatible with auto-unlink hooks!
132 BOOST_STATIC_ASSERT(!(constant_time_size && ((int)real_value_traits::link_mode == (int)auto_unlink)));
134 struct header_plus_size : public size_traits
137 struct node_plus_pred_t : public detail::ebo_functor_holder<value_compare>
139 node_plus_pred_t(const value_compare &comp)
140 : detail::ebo_functor_holder<value_compare>(comp)
142 header_plus_size header_plus_size_;
145 struct data_t : public rbtree_impl::value_traits
147 typedef typename rbtree_impl::value_traits value_traits;
148 data_t(const value_compare & comp, const value_traits &val_traits)
149 : value_traits(val_traits), node_plus_pred_(comp)
151 node_plus_pred_t node_plus_pred_;
154 const value_compare &priv_comp() const
155 { return data_.node_plus_pred_.get(); }
157 value_compare &priv_comp()
158 { return data_.node_plus_pred_.get(); }
160 const value_traits &priv_value_traits() const
163 value_traits &priv_value_traits()
166 const node &priv_header() const
167 { return data_.node_plus_pred_.header_plus_size_.header_; }
170 { return data_.node_plus_pred_.header_plus_size_.header_; }
172 static node_ptr uncast(const_node_ptr ptr)
174 return node_ptr(const_cast<node*>(detail::boost_intrusive_get_pointer(ptr)));
175 //iG pending return node_ptr(boost::const_pointer_cast<node>(ptr));
178 size_traits &priv_size_traits()
179 { return data_.node_plus_pred_.header_plus_size_; }
181 const size_traits &priv_size_traits() const
182 { return data_.node_plus_pred_.header_plus_size_; }
184 const real_value_traits &get_real_value_traits(detail::bool_<false>) const
187 const real_value_traits &get_real_value_traits(detail::bool_<true>) const
188 { return data_.get_value_traits(*this); }
190 real_value_traits &get_real_value_traits(detail::bool_<false>)
193 real_value_traits &get_real_value_traits(detail::bool_<true>)
194 { return data_.get_value_traits(*this); }
197 value_compare &prot_comp()
198 { return priv_comp(); }
200 const node &prot_header_node() const
201 { return priv_header(); }
203 node &prot_header_node()
204 { return priv_header(); }
206 void prot_set_size(size_type s)
207 { this->priv_size_traits().set_size(s); }
213 const real_value_traits &get_real_value_traits() const
214 { return this->get_real_value_traits(detail::bool_<external_value_traits>()); }
216 real_value_traits &get_real_value_traits()
217 { return this->get_real_value_traits(detail::bool_<external_value_traits>()); }
219 typedef typename node_algorithms::insert_commit_data insert_commit_data;
221 //! <b>Effects</b>: Constructs an empty tree.
223 //! <b>Complexity</b>: Constant.
225 //! <b>Throws</b>: If value_traits::node_traits::node
226 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
227 //! or the copy constructorof the value_compare object throws. Basic guarantee.
228 rbtree_impl( const value_compare &cmp = value_compare()
229 , const value_traits &v_traits = value_traits())
230 : data_(cmp, v_traits)
232 node_algorithms::init_header(&priv_header());
233 this->priv_size_traits().set_size(size_type(0));
236 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
237 //! cmp must be a comparison function that induces a strict weak ordering.
239 //! <b>Effects</b>: Constructs an empty tree and inserts elements from
242 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
243 //! comp and otherwise N * log N, where N is the distance between first and last.
245 //! <b>Throws</b>: If value_traits::node_traits::node
246 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
247 //! or the copy constructor/operator() of the value_compare object throws. Basic guarantee.
248 template<class Iterator>
249 rbtree_impl( bool unique, Iterator b, Iterator e
250 , const value_compare &cmp = value_compare()
251 , const value_traits &v_traits = value_traits())
252 : data_(cmp, v_traits)
254 node_algorithms::init_header(&priv_header());
255 this->priv_size_traits().set_size(size_type(0));
257 this->insert_unique(b, e);
259 this->insert_equal(b, e);
262 //! <b>Effects</b>: to-do
264 rbtree_impl(BOOST_RV_REF(rbtree_impl) x)
265 : data_(::boost::move(x.priv_comp()), ::boost::move(x.priv_value_traits()))
267 node_algorithms::init_header(&priv_header());
268 this->priv_size_traits().set_size(size_type(0));
272 //! <b>Effects</b>: to-do
274 rbtree_impl& operator=(BOOST_RV_REF(rbtree_impl) x)
275 { this->swap(x); return *this; }
277 //! <b>Effects</b>: Detaches all elements from this. The objects in the set
278 //! are not deleted (i.e. no destructors are called), but the nodes according to
279 //! the value_traits template parameter are reinitialized and thus can be reused.
281 //! <b>Complexity</b>: Linear to elements contained in *this.
283 //! <b>Throws</b>: Nothing.
287 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the tree.
289 //! <b>Complexity</b>: Constant.
291 //! <b>Throws</b>: Nothing.
293 { return iterator (node_traits::get_left(node_ptr(&priv_header())), this); }
295 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the tree.
297 //! <b>Complexity</b>: Constant.
299 //! <b>Throws</b>: Nothing.
300 const_iterator begin() const
303 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the tree.
305 //! <b>Complexity</b>: Constant.
307 //! <b>Throws</b>: Nothing.
308 const_iterator cbegin() const
309 { return const_iterator (node_traits::get_left(const_node_ptr(&priv_header())), this); }
311 //! <b>Effects</b>: Returns an iterator pointing to the end of the tree.
313 //! <b>Complexity</b>: Constant.
315 //! <b>Throws</b>: Nothing.
317 { return iterator (node_ptr(&priv_header()), this); }
319 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the tree.
321 //! <b>Complexity</b>: Constant.
323 //! <b>Throws</b>: Nothing.
324 const_iterator end() const
327 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the tree.
329 //! <b>Complexity</b>: Constant.
331 //! <b>Throws</b>: Nothing.
332 const_iterator cend() const
333 { return const_iterator (uncast(const_node_ptr(&priv_header())), this); }
335 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
338 //! <b>Complexity</b>: Constant.
340 //! <b>Throws</b>: Nothing.
341 reverse_iterator rbegin()
342 { return reverse_iterator(end()); }
344 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
345 //! of the reversed tree.
347 //! <b>Complexity</b>: Constant.
349 //! <b>Throws</b>: Nothing.
350 const_reverse_iterator rbegin() const
351 { return const_reverse_iterator(end()); }
353 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
354 //! of the reversed tree.
356 //! <b>Complexity</b>: Constant.
358 //! <b>Throws</b>: Nothing.
359 const_reverse_iterator crbegin() const
360 { return const_reverse_iterator(end()); }
362 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
363 //! of the reversed tree.
365 //! <b>Complexity</b>: Constant.
367 //! <b>Throws</b>: Nothing.
368 reverse_iterator rend()
369 { return reverse_iterator(begin()); }
371 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
372 //! of the reversed tree.
374 //! <b>Complexity</b>: Constant.
376 //! <b>Throws</b>: Nothing.
377 const_reverse_iterator rend() const
378 { return const_reverse_iterator(begin()); }
380 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
381 //! of the reversed tree.
383 //! <b>Complexity</b>: Constant.
385 //! <b>Throws</b>: Nothing.
386 const_reverse_iterator crend() const
387 { return const_reverse_iterator(begin()); }
389 //! <b>Precondition</b>: end_iterator must be a valid end iterator
392 //! <b>Effects</b>: Returns a const reference to the rbtree associated to the end iterator
394 //! <b>Throws</b>: Nothing.
396 //! <b>Complexity</b>: Constant.
397 static rbtree_impl &container_from_end_iterator(iterator end_iterator)
398 { return priv_container_from_end_iterator(end_iterator); }
400 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator
403 //! <b>Effects</b>: Returns a const reference to the rbtree associated to the iterator
405 //! <b>Throws</b>: Nothing.
407 //! <b>Complexity</b>: Constant.
408 static const rbtree_impl &container_from_end_iterator(const_iterator end_iterator)
409 { return priv_container_from_end_iterator(end_iterator); }
411 //! <b>Precondition</b>: it must be a valid iterator
414 //! <b>Effects</b>: Returns a const reference to the tree associated to the iterator
416 //! <b>Throws</b>: Nothing.
418 //! <b>Complexity</b>: Logarithmic.
419 static rbtree_impl &container_from_iterator(iterator it)
420 { return priv_container_from_iterator(it); }
422 //! <b>Precondition</b>: it must be a valid end const_iterator
425 //! <b>Effects</b>: Returns a const reference to the tree associated to the end iterator
427 //! <b>Throws</b>: Nothing.
429 //! <b>Complexity</b>: Logarithmic.
430 static const rbtree_impl &container_from_iterator(const_iterator it)
431 { return priv_container_from_iterator(it); }
433 //! <b>Effects</b>: Returns the value_compare object used by the tree.
435 //! <b>Complexity</b>: Constant.
437 //! <b>Throws</b>: If value_compare copy-constructor throws.
438 value_compare value_comp() const
439 { return priv_comp(); }
441 //! <b>Effects</b>: Returns true if the container is empty.
443 //! <b>Complexity</b>: Constant.
445 //! <b>Throws</b>: Nothing.
447 { return node_algorithms::unique(const_node_ptr(&priv_header())); }
449 //! <b>Effects</b>: Returns the number of elements stored in the tree.
451 //! <b>Complexity</b>: Linear to elements contained in *this
452 //! if constant-time size option is disabled. Constant time otherwise.
454 //! <b>Throws</b>: Nothing.
455 size_type size() const
457 if(constant_time_size)
458 return this->priv_size_traits().get_size();
460 return (size_type)node_algorithms::size(const_node_ptr(&priv_header()));
464 //! <b>Effects</b>: Swaps the contents of two rbtrees.
466 //! <b>Complexity</b>: Constant.
468 //! <b>Throws</b>: If the comparison functor's swap call throws.
469 void swap(rbtree_impl& other)
473 swap(priv_comp(), priv_comp());
475 node_algorithms::swap_tree(node_ptr(&priv_header()), node_ptr(&other.priv_header()));
476 if(constant_time_size){
477 size_type backup = this->priv_size_traits().get_size();
478 this->priv_size_traits().set_size(other.priv_size_traits().get_size());
479 other.priv_size_traits().set_size(backup);
483 //! <b>Requires</b>: value must be an lvalue
485 //! <b>Effects</b>: Inserts value into the tree before the upper bound.
487 //! <b>Complexity</b>: Average complexity for insert element is at
488 //! most logarithmic.
490 //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
492 //! <b>Note</b>: Does not affect the validity of iterators and references.
493 //! No copy-constructors are called.
494 iterator insert_equal(reference value)
496 detail::key_nodeptr_comp<value_compare, rbtree_impl>
497 key_node_comp(priv_comp(), this);
498 node_ptr to_insert(get_real_value_traits().to_node_ptr(value));
499 if(safemode_or_autounlink)
500 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
501 iterator ret(node_algorithms::insert_equal_upper_bound
502 (node_ptr(&priv_header()), to_insert, key_node_comp), this);
503 this->priv_size_traits().increment();
507 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
508 //! a valid iterator.
510 //! <b>Effects</b>: Inserts x into the tree, using "hint" as a hint to
511 //! where it will be inserted. If "hint" is the upper_bound
512 //! the insertion takes constant time (two comparisons in the worst case)
514 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
515 //! constant time if t is inserted immediately before hint.
517 //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
519 //! <b>Note</b>: Does not affect the validity of iterators and references.
520 //! No copy-constructors are called.
521 iterator insert_equal(const_iterator hint, reference value)
523 detail::key_nodeptr_comp<value_compare, rbtree_impl>
524 key_node_comp(priv_comp(), this);
525 node_ptr to_insert(get_real_value_traits().to_node_ptr(value));
526 if(safemode_or_autounlink)
527 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
528 iterator ret(node_algorithms::insert_equal
529 (node_ptr(&priv_header()), hint.pointed_node(), to_insert, key_node_comp), this);
530 this->priv_size_traits().increment();
534 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
535 //! of type value_type.
537 //! <b>Effects</b>: Inserts a each element of a range into the tree
538 //! before the upper bound of the key of each element.
540 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
541 //! size of the range. However, it is linear in N if the range is already sorted
544 //! <b>Throws</b>: Nothing.
546 //! <b>Note</b>: Does not affect the validity of iterators and references.
547 //! No copy-constructors are called.
548 template<class Iterator>
549 void insert_equal(Iterator b, Iterator e)
551 iterator iend(this->end());
553 this->insert_equal(iend, *b);
556 //! <b>Requires</b>: value must be an lvalue
558 //! <b>Effects</b>: Inserts value into the tree if the value
559 //! is not already present.
561 //! <b>Complexity</b>: Average complexity for insert element is at
562 //! most logarithmic.
564 //! <b>Throws</b>: Nothing.
566 //! <b>Note</b>: Does not affect the validity of iterators and references.
567 //! No copy-constructors are called.
568 std::pair<iterator, bool> insert_unique(reference value)
570 insert_commit_data commit_data;
571 std::pair<iterator, bool> ret = insert_unique_check(value, priv_comp(), commit_data);
574 return std::pair<iterator, bool> (insert_unique_commit(value, commit_data), true);
577 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
580 //! <b>Effects</b>: Tries to insert x into the tree, using "hint" as a hint
581 //! to where it will be inserted.
583 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
584 //! constant time (two comparisons in the worst case)
585 //! if t is inserted immediately before hint.
587 //! <b>Throws</b>: Nothing.
589 //! <b>Note</b>: Does not affect the validity of iterators and references.
590 //! No copy-constructors are called.
591 iterator insert_unique(const_iterator hint, reference value)
593 insert_commit_data commit_data;
594 std::pair<iterator, bool> ret = insert_unique_check(hint, value, priv_comp(), commit_data);
597 return insert_unique_commit(value, commit_data);
600 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
601 //! of type value_type.
603 //! <b>Effects</b>: Tries to insert each element of a range into the tree.
605 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
606 //! size of the range. However, it is linear in N if the range is already sorted
609 //! <b>Throws</b>: Nothing.
611 //! <b>Note</b>: Does not affect the validity of iterators and references.
612 //! No copy-constructors are called.
613 template<class Iterator>
614 void insert_unique(Iterator b, Iterator e)
617 iterator iend(this->end());
619 this->insert_unique(iend, *b);
623 this->insert_unique(*b);
627 //! <b>Requires</b>: key_value_comp must be a comparison function that induces
628 //! the same strict weak ordering as value_compare. The difference is that
629 //! key_value_comp compares an arbitrary key with the contained values.
631 //! <b>Effects</b>: Checks if a value can be inserted in the container, using
632 //! a user provided key instead of the value itself.
634 //! <b>Returns</b>: If there is an equivalent value
635 //! returns a pair containing an iterator to the already present value
636 //! and false. If the value can be inserted returns true in the returned
637 //! pair boolean and fills "commit_data" that is meant to be used with
638 //! the "insert_commit" function.
640 //! <b>Complexity</b>: Average complexity is at most logarithmic.
642 //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
644 //! <b>Notes</b>: This function is used to improve performance when constructing
645 //! a value_type is expensive: if there is an equivalent value
646 //! the constructed object must be discarded. Many times, the part of the
647 //! node that is used to impose the order is much cheaper to construct
648 //! than the value_type and this function offers the possibility to use that
649 //! part to check if the insertion will be successful.
651 //! If the check is successful, the user can construct the value_type and use
652 //! "insert_commit" to insert the object in constant-time. This gives a total
653 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
655 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
656 //! objects are inserted or erased from the container.
657 template<class KeyType, class KeyValueCompare>
658 std::pair<iterator, bool> insert_unique_check
659 (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
661 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
662 comp(key_value_comp, this);
663 std::pair<node_ptr, bool> ret =
664 (node_algorithms::insert_unique_check
665 (node_ptr(&priv_header()), key, comp, commit_data));
666 return std::pair<iterator, bool>(iterator(ret.first, this), ret.second);
669 //! <b>Requires</b>: key_value_comp must be a comparison function that induces
670 //! the same strict weak ordering as value_compare. The difference is that
671 //! key_value_comp compares an arbitrary key with the contained values.
673 //! <b>Effects</b>: Checks if a value can be inserted in the container, using
674 //! a user provided key instead of the value itself, using "hint"
675 //! as a hint to where it will be inserted.
677 //! <b>Returns</b>: If there is an equivalent value
678 //! returns a pair containing an iterator to the already present value
679 //! and false. If the value can be inserted returns true in the returned
680 //! pair boolean and fills "commit_data" that is meant to be used with
681 //! the "insert_commit" function.
683 //! <b>Complexity</b>: Logarithmic in general, but it's amortized
684 //! constant time if t is inserted immediately before hint.
686 //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
688 //! <b>Notes</b>: This function is used to improve performance when constructing
689 //! a value_type is expensive: if there is an equivalent value
690 //! the constructed object must be discarded. Many times, the part of the
691 //! constructing that is used to impose the order is much cheaper to construct
692 //! than the value_type and this function offers the possibility to use that key
693 //! to check if the insertion will be successful.
695 //! If the check is successful, the user can construct the value_type and use
696 //! "insert_commit" to insert the object in constant-time. This can give a total
697 //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)).
699 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
700 //! objects are inserted or erased from the container.
701 template<class KeyType, class KeyValueCompare>
702 std::pair<iterator, bool> insert_unique_check
703 (const_iterator hint, const KeyType &key
704 ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
706 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
707 comp(key_value_comp, this);
708 std::pair<node_ptr, bool> ret =
709 (node_algorithms::insert_unique_check
710 (node_ptr(&priv_header()), hint.pointed_node(), key, comp, commit_data));
711 return std::pair<iterator, bool>(iterator(ret.first, this), ret.second);
714 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
715 //! must have been obtained from a previous call to "insert_check".
716 //! No objects should have been inserted or erased from the container between
717 //! the "insert_check" that filled "commit_data" and the call to "insert_commit".
719 //! <b>Effects</b>: Inserts the value in the avl_set using the information obtained
720 //! from the "commit_data" that a previous "insert_check" filled.
722 //! <b>Returns</b>: An iterator to the newly inserted object.
724 //! <b>Complexity</b>: Constant time.
726 //! <b>Throws</b>: Nothing.
728 //! <b>Notes</b>: This function has only sense if a "insert_check" has been
729 //! previously executed to fill "commit_data". No value should be inserted or
730 //! erased between the "insert_check" and "insert_commit" calls.
731 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data)
733 node_ptr to_insert(get_real_value_traits().to_node_ptr(value));
734 if(safemode_or_autounlink)
735 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
736 node_algorithms::insert_unique_commit
737 (node_ptr(&priv_header()), to_insert, commit_data);
738 this->priv_size_traits().increment();
739 return iterator(to_insert, this);
742 //! <b>Requires</b>: value must be an lvalue, "pos" must be
743 //! a valid iterator (or end) and must be the succesor of value
744 //! once inserted according to the predicate
746 //! <b>Effects</b>: Inserts x into the tree before "pos".
748 //! <b>Complexity</b>: Constant time.
750 //! <b>Throws</b>: Nothing.
752 //! <b>Note</b>: This function does not check preconditions so if "pos" is not
753 //! the successor of "value" tree ordering invariant will be broken.
754 //! This is a low-level function to be used only for performance reasons
755 //! by advanced users.
756 iterator insert_before(const_iterator pos, reference value)
758 node_ptr to_insert(get_real_value_traits().to_node_ptr(value));
759 if(safemode_or_autounlink)
760 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
761 this->priv_size_traits().increment();
762 return iterator(node_algorithms::insert_before
763 (node_ptr(&priv_header()), pos.pointed_node(), to_insert), this);
766 //! <b>Requires</b>: value must be an lvalue, and it must be no less
767 //! than the greatest inserted key
769 //! <b>Effects</b>: Inserts x into the tree in the last position.
771 //! <b>Complexity</b>: Constant time.
773 //! <b>Throws</b>: Nothing.
775 //! <b>Note</b>: This function does not check preconditions so if value is
776 //! less than the greatest inserted key tree ordering invariant will be broken.
777 //! This function is slightly more efficient than using "insert_before".
778 //! This is a low-level function to be used only for performance reasons
779 //! by advanced users.
780 void push_back(reference value)
782 node_ptr to_insert(get_real_value_traits().to_node_ptr(value));
783 if(safemode_or_autounlink)
784 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
785 this->priv_size_traits().increment();
786 node_algorithms::push_back(node_ptr(&priv_header()), to_insert);
789 //! <b>Requires</b>: value must be an lvalue, and it must be no greater
790 //! than the minimum inserted key
792 //! <b>Effects</b>: Inserts x into the tree in the first position.
794 //! <b>Complexity</b>: Constant time.
796 //! <b>Throws</b>: Nothing.
798 //! <b>Note</b>: This function does not check preconditions so if value is
799 //! greater than the minimum inserted key tree ordering invariant will be broken.
800 //! This function is slightly more efficient than using "insert_before".
801 //! This is a low-level function to be used only for performance reasons
802 //! by advanced users.
803 void push_front(reference value)
805 node_ptr to_insert(get_real_value_traits().to_node_ptr(value));
806 if(safemode_or_autounlink)
807 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert));
808 this->priv_size_traits().increment();
809 node_algorithms::push_front(node_ptr(&priv_header()), to_insert);
812 //! <b>Effects</b>: Erases the element pointed to by pos.
814 //! <b>Complexity</b>: Average complexity for erase element is constant time.
816 //! <b>Throws</b>: Nothing.
818 //! <b>Note</b>: Invalidates the iterators (but not the references)
819 //! to the erased elements. No destructors are called.
820 iterator erase(const_iterator i)
822 const_iterator ret(i);
824 node_ptr to_erase(i.pointed_node());
825 if(safemode_or_autounlink)
826 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!node_algorithms::unique(to_erase));
827 node_algorithms::erase(&priv_header(), to_erase);
828 this->priv_size_traits().decrement();
829 if(safemode_or_autounlink)
830 node_algorithms::init(to_erase);
831 return ret.unconst();
834 //! <b>Effects</b>: Erases the range pointed to by b end e.
836 //! <b>Complexity</b>: Average complexity for erase range is at most
837 //! O(log(size() + N)), where N is the number of elements in the range.
839 //! <b>Throws</b>: Nothing.
841 //! <b>Note</b>: Invalidates the iterators (but not the references)
842 //! to the erased elements. No destructors are called.
843 iterator erase(const_iterator b, const_iterator e)
844 { size_type n; return private_erase(b, e, n); }
846 //! <b>Effects</b>: Erases all the elements with the given value.
848 //! <b>Returns</b>: The number of erased elements.
850 //! <b>Complexity</b>: O(log(size() + N).
852 //! <b>Throws</b>: Nothing.
854 //! <b>Note</b>: Invalidates the iterators (but not the references)
855 //! to the erased elements. No destructors are called.
856 size_type erase(const_reference value)
857 { return this->erase(value, priv_comp()); }
859 //! <b>Effects</b>: Erases all the elements with the given key.
860 //! according to the comparison functor "comp".
862 //! <b>Returns</b>: The number of erased elements.
864 //! <b>Complexity</b>: O(log(size() + N).
866 //! <b>Throws</b>: Nothing.
868 //! <b>Note</b>: Invalidates the iterators (but not the references)
869 //! to the erased elements. No destructors are called.
870 template<class KeyType, class KeyValueCompare>
871 size_type erase(const KeyType& key, KeyValueCompare comp
873 , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
877 std::pair<iterator,iterator> p = this->equal_range(key, comp);
879 private_erase(p.first, p.second, n);
883 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
885 //! <b>Effects</b>: Erases the element pointed to by pos.
886 //! Disposer::operator()(pointer) is called for the removed element.
888 //! <b>Complexity</b>: Average complexity for erase element is constant time.
890 //! <b>Throws</b>: Nothing.
892 //! <b>Note</b>: Invalidates the iterators
893 //! to the erased elements.
894 template<class Disposer>
895 iterator erase_and_dispose(const_iterator i, Disposer disposer)
897 node_ptr to_erase(i.pointed_node());
898 iterator ret(this->erase(i));
899 disposer(get_real_value_traits().to_value_ptr(to_erase));
903 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
904 template<class Disposer>
905 iterator erase_and_dispose(iterator i, Disposer disposer)
906 { return this->erase_and_dispose(const_iterator(i), disposer); }
909 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
911 //! <b>Effects</b>: Erases all the elements with the given value.
912 //! Disposer::operator()(pointer) is called for the removed elements.
914 //! <b>Returns</b>: The number of erased elements.
916 //! <b>Complexity</b>: O(log(size() + N).
918 //! <b>Throws</b>: Nothing.
920 //! <b>Note</b>: Invalidates the iterators (but not the references)
921 //! to the erased elements. No destructors are called.
922 template<class Disposer>
923 size_type erase_and_dispose(const_reference value, Disposer disposer)
925 std::pair<iterator,iterator> p = this->equal_range(value);
927 private_erase(p.first, p.second, n, disposer);
931 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
933 //! <b>Effects</b>: Erases the range pointed to by b end e.
934 //! Disposer::operator()(pointer) is called for the removed elements.
936 //! <b>Complexity</b>: Average complexity for erase range is at most
937 //! O(log(size() + N)), where N is the number of elements in the range.
939 //! <b>Throws</b>: Nothing.
941 //! <b>Note</b>: Invalidates the iterators
942 //! to the erased elements.
943 template<class Disposer>
944 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
945 { size_type n; return private_erase(b, e, n, disposer); }
947 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
949 //! <b>Effects</b>: Erases all the elements with the given key.
950 //! according to the comparison functor "comp".
951 //! Disposer::operator()(pointer) is called for the removed elements.
953 //! <b>Returns</b>: The number of erased elements.
955 //! <b>Complexity</b>: O(log(size() + N).
957 //! <b>Throws</b>: Nothing.
959 //! <b>Note</b>: Invalidates the iterators
960 //! to the erased elements.
961 template<class KeyType, class KeyValueCompare, class Disposer>
962 size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer
964 , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
968 std::pair<iterator,iterator> p = this->equal_range(key, comp);
970 private_erase(p.first, p.second, n, disposer);
974 //! <b>Effects</b>: Erases all of the elements.
976 //! <b>Complexity</b>: Linear to the number of elements on the container.
977 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
979 //! <b>Throws</b>: Nothing.
981 //! <b>Note</b>: Invalidates the iterators (but not the references)
982 //! to the erased elements. No destructors are called.
985 if(safemode_or_autounlink){
986 this->clear_and_dispose(detail::null_disposer());
989 node_algorithms::init_header(&priv_header());
990 this->priv_size_traits().set_size(0);
994 //! <b>Effects</b>: Erases all of the elements calling disposer(p) for
995 //! each node to be erased.
996 //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)),
997 //! where N is the number of elements in the container.
999 //! <b>Throws</b>: Nothing.
1001 //! <b>Note</b>: Invalidates the iterators (but not the references)
1002 //! to the erased elements. Calls N times to disposer functor.
1003 template<class Disposer>
1004 void clear_and_dispose(Disposer disposer)
1006 node_algorithms::clear_and_dispose(node_ptr(&priv_header())
1007 , detail::node_disposer<Disposer, rbtree_impl>(disposer, this));
1008 node_algorithms::init_header(&priv_header());
1009 this->priv_size_traits().set_size(0);
1012 //! <b>Effects</b>: Returns the number of contained elements with the given value
1014 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
1015 //! to number of objects with the given value.
1017 //! <b>Throws</b>: Nothing.
1018 size_type count(const_reference value) const
1019 { return this->count(value, priv_comp()); }
1021 //! <b>Effects</b>: Returns the number of contained elements with the given key
1023 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
1024 //! to number of objects with the given key.
1026 //! <b>Throws</b>: Nothing.
1027 template<class KeyType, class KeyValueCompare>
1028 size_type count(const KeyType &key, KeyValueCompare comp) const
1030 std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp);
1031 return std::distance(ret.first, ret.second);
1034 //! <b>Effects</b>: Returns an iterator to the first element whose
1035 //! key is not less than k or end() if that element does not exist.
1037 //! <b>Complexity</b>: Logarithmic.
1039 //! <b>Throws</b>: Nothing.
1040 iterator lower_bound(const_reference value)
1041 { return this->lower_bound(value, priv_comp()); }
1043 //! <b>Effects</b>: Returns an iterator to the first element whose
1044 //! key is not less than k or end() if that element does not exist.
1046 //! <b>Complexity</b>: Logarithmic.
1048 //! <b>Throws</b>: Nothing.
1049 const_iterator lower_bound(const_reference value) const
1050 { return this->lower_bound(value, priv_comp()); }
1052 //! <b>Effects</b>: Returns an iterator to the first element whose
1053 //! key is not less than k or end() if that element does not exist.
1055 //! <b>Complexity</b>: Logarithmic.
1057 //! <b>Throws</b>: Nothing.
1058 template<class KeyType, class KeyValueCompare>
1059 iterator lower_bound(const KeyType &key, KeyValueCompare comp)
1061 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
1062 key_node_comp(comp, this);
1063 return iterator(node_algorithms::lower_bound
1064 (const_node_ptr(&priv_header()), key, key_node_comp), this);
1067 //! <b>Effects</b>: Returns a const iterator to the first element whose
1068 //! key is not less than k or end() if that element does not exist.
1070 //! <b>Complexity</b>: Logarithmic.
1072 //! <b>Throws</b>: Nothing.
1073 template<class KeyType, class KeyValueCompare>
1074 const_iterator lower_bound(const KeyType &key, KeyValueCompare comp) const
1076 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
1077 key_node_comp(comp, this);
1078 return const_iterator(node_algorithms::lower_bound
1079 (const_node_ptr(&priv_header()), key, key_node_comp), this);
1082 //! <b>Effects</b>: Returns an iterator to the first element whose
1083 //! key is greater than k or end() if that element does not exist.
1085 //! <b>Complexity</b>: Logarithmic.
1087 //! <b>Throws</b>: Nothing.
1088 iterator upper_bound(const_reference value)
1089 { return this->upper_bound(value, priv_comp()); }
1091 //! <b>Effects</b>: Returns an iterator to the first element whose
1092 //! key is greater than k according to comp or end() if that element
1095 //! <b>Complexity</b>: Logarithmic.
1097 //! <b>Throws</b>: Nothing.
1098 template<class KeyType, class KeyValueCompare>
1099 iterator upper_bound(const KeyType &key, KeyValueCompare comp)
1101 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
1102 key_node_comp(comp, this);
1103 return iterator(node_algorithms::upper_bound
1104 (const_node_ptr(&priv_header()), key, key_node_comp), this);
1107 //! <b>Effects</b>: Returns an iterator to the first element whose
1108 //! key is greater than k or end() if that element does not exist.
1110 //! <b>Complexity</b>: Logarithmic.
1112 //! <b>Throws</b>: Nothing.
1113 const_iterator upper_bound(const_reference value) const
1114 { return this->upper_bound(value, priv_comp()); }
1116 //! <b>Effects</b>: Returns an iterator to the first element whose
1117 //! key is greater than k according to comp or end() if that element
1120 //! <b>Complexity</b>: Logarithmic.
1122 //! <b>Throws</b>: Nothing.
1123 template<class KeyType, class KeyValueCompare>
1124 const_iterator upper_bound(const KeyType &key, KeyValueCompare comp) const
1126 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
1127 key_node_comp(comp, this);
1128 return const_iterator(node_algorithms::upper_bound
1129 (const_node_ptr(&priv_header()), key, key_node_comp), this);
1132 //! <b>Effects</b>: Finds an iterator to the first element whose key is
1133 //! k or end() if that element does not exist.
1135 //! <b>Complexity</b>: Logarithmic.
1137 //! <b>Throws</b>: Nothing.
1138 iterator find(const_reference value)
1139 { return this->find(value, priv_comp()); }
1141 //! <b>Effects</b>: Finds an iterator to the first element whose key is
1142 //! k or end() if that element does not exist.
1144 //! <b>Complexity</b>: Logarithmic.
1146 //! <b>Throws</b>: Nothing.
1147 template<class KeyType, class KeyValueCompare>
1148 iterator find(const KeyType &key, KeyValueCompare comp)
1150 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
1151 key_node_comp(comp, this);
1153 (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp), this);
1156 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
1157 //! k or end() if that element does not exist.
1159 //! <b>Complexity</b>: Logarithmic.
1161 //! <b>Throws</b>: Nothing.
1162 const_iterator find(const_reference value) const
1163 { return this->find(value, priv_comp()); }
1165 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
1166 //! k or end() if that element does not exist.
1168 //! <b>Complexity</b>: Logarithmic.
1170 //! <b>Throws</b>: Nothing.
1171 template<class KeyType, class KeyValueCompare>
1172 const_iterator find(const KeyType &key, KeyValueCompare comp) const
1174 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
1175 key_node_comp(comp, this);
1176 return const_iterator
1177 (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp), this);
1180 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
1181 //! an empty range that indicates the position where those elements would be
1182 //! if they there is no elements with key k.
1184 //! <b>Complexity</b>: Logarithmic.
1186 //! <b>Throws</b>: Nothing.
1187 std::pair<iterator,iterator> equal_range(const_reference value)
1188 { return this->equal_range(value, priv_comp()); }
1190 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
1191 //! an empty range that indicates the position where those elements would be
1192 //! if they there is no elements with key k.
1194 //! <b>Complexity</b>: Logarithmic.
1196 //! <b>Throws</b>: Nothing.
1197 template<class KeyType, class KeyValueCompare>
1198 std::pair<iterator,iterator> equal_range(const KeyType &key, KeyValueCompare comp)
1200 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
1201 key_node_comp(comp, this);
1202 std::pair<node_ptr, node_ptr> ret
1203 (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp));
1204 return std::pair<iterator, iterator>(iterator(ret.first, this), iterator(ret.second, this));
1207 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
1208 //! an empty range that indicates the position where those elements would be
1209 //! if they there is no elements with key k.
1211 //! <b>Complexity</b>: Logarithmic.
1213 //! <b>Throws</b>: Nothing.
1214 std::pair<const_iterator, const_iterator>
1215 equal_range(const_reference value) const
1216 { return this->equal_range(value, priv_comp()); }
1218 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
1219 //! an empty range that indicates the position where those elements would be
1220 //! if they there is no elements with key k.
1222 //! <b>Complexity</b>: Logarithmic.
1224 //! <b>Throws</b>: Nothing.
1225 template<class KeyType, class KeyValueCompare>
1226 std::pair<const_iterator, const_iterator>
1227 equal_range(const KeyType &key, KeyValueCompare comp) const
1229 detail::key_nodeptr_comp<KeyValueCompare, rbtree_impl>
1230 key_node_comp(comp, this);
1231 std::pair<node_ptr, node_ptr> ret
1232 (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp));
1233 return std::pair<const_iterator, const_iterator>(const_iterator(ret.first, this), const_iterator(ret.second, this));
1236 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1237 //! Cloner should yield to nodes equivalent to the original nodes.
1239 //! <b>Effects</b>: Erases all the elements from *this
1240 //! calling Disposer::operator()(pointer), clones all the
1241 //! elements from src calling Cloner::operator()(const_reference )
1242 //! and inserts them on *this. Copies the predicate from the source container.
1244 //! If cloner throws, all cloned elements are unlinked and disposed
1245 //! calling Disposer::operator()(pointer).
1247 //! <b>Complexity</b>: Linear to erased plus inserted elements.
1249 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
1250 template <class Cloner, class Disposer>
1251 void clone_from(const rbtree_impl &src, Cloner cloner, Disposer disposer)
1253 this->clear_and_dispose(disposer);
1255 detail::exception_disposer<rbtree_impl, Disposer>
1256 rollback(*this, disposer);
1257 node_algorithms::clone
1258 (const_node_ptr(&src.priv_header())
1259 ,node_ptr(&this->priv_header())
1260 ,detail::node_cloner<Cloner, rbtree_impl>(cloner, this)
1261 ,detail::node_disposer<Disposer, rbtree_impl>(disposer, this));
1262 this->priv_size_traits().set_size(src.priv_size_traits().get_size());
1263 this->priv_comp() = src.priv_comp();
1268 //! <b>Effects</b>: Unlinks the leftmost node from the tree.
1270 //! <b>Complexity</b>: Average complexity is constant time.
1272 //! <b>Throws</b>: Nothing.
1274 //! <b>Notes</b>: This function breaks the tree and the tree can
1275 //! only be used for more unlink_leftmost_without_rebalance calls.
1276 //! This function is normally used to achieve a step by step
1277 //! controlled destruction of the tree.
1278 pointer unlink_leftmost_without_rebalance()
1280 node_ptr to_be_disposed(node_algorithms::unlink_leftmost_without_rebalance
1281 (node_ptr(&priv_header())));
1284 this->priv_size_traits().decrement();
1285 if(safemode_or_autounlink)//If this is commented does not work with normal_link
1286 node_algorithms::init(to_be_disposed);
1287 return get_real_value_traits().to_value_ptr(to_be_disposed);
1290 //! <b>Requires</b>: replace_this must be a valid iterator of *this
1291 //! and with_this must not be inserted in any tree.
1293 //! <b>Effects</b>: Replaces replace_this in its position in the
1294 //! tree with with_this. The tree does not need to be rebalanced.
1296 //! <b>Complexity</b>: Constant.
1298 //! <b>Throws</b>: Nothing.
1300 //! <b>Note</b>: This function will break container ordering invariants if
1301 //! with_this is not equivalent to *replace_this according to the
1302 //! ordering rules. This function is faster than erasing and inserting
1303 //! the node, since no rebalancing or comparison is needed.
1304 void replace_node(iterator replace_this, reference with_this)
1306 node_algorithms::replace_node( get_real_value_traits().to_node_ptr(*replace_this)
1307 , node_ptr(&priv_header())
1308 , get_real_value_traits().to_node_ptr(with_this));
1309 if(safemode_or_autounlink)
1310 node_algorithms::init(replace_this.pointed_node());
1313 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1314 //! appropriate type. Otherwise the behavior is undefined.
1316 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
1317 //! that points to the value
1319 //! <b>Complexity</b>: Constant.
1321 //! <b>Throws</b>: Nothing.
1323 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1325 static iterator s_iterator_to(reference value)
1327 BOOST_STATIC_ASSERT((!stateful_value_traits));
1328 return iterator (value_traits::to_node_ptr(value), 0);
1331 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1332 //! appropriate type. Otherwise the behavior is undefined.
1334 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
1335 //! set that points to the value
1337 //! <b>Complexity</b>: Constant.
1339 //! <b>Throws</b>: Nothing.
1341 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1343 static const_iterator s_iterator_to(const_reference value)
1345 BOOST_STATIC_ASSERT((!stateful_value_traits));
1346 return const_iterator (value_traits::to_node_ptr(const_cast<reference> (value)), 0);
1349 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1350 //! appropriate type. Otherwise the behavior is undefined.
1352 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
1353 //! that points to the value
1355 //! <b>Complexity</b>: Constant.
1357 //! <b>Throws</b>: Nothing.
1358 iterator iterator_to(reference value)
1359 { return iterator (value_traits::to_node_ptr(value), this); }
1361 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1362 //! appropriate type. Otherwise the behavior is undefined.
1364 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
1365 //! set that points to the value
1367 //! <b>Complexity</b>: Constant.
1369 //! <b>Throws</b>: Nothing.
1370 const_iterator iterator_to(const_reference value) const
1371 { return const_iterator (value_traits::to_node_ptr(const_cast<reference> (value)), this); }
1373 //! <b>Requires</b>: value shall not be in a tree.
1375 //! <b>Effects</b>: init_node puts the hook of a value in a well-known default
1378 //! <b>Throws</b>: Nothing.
1380 //! <b>Complexity</b>: Constant time.
1382 //! <b>Note</b>: This function puts the hook in the well-known default state
1383 //! used by auto_unlink and safe hooks.
1384 static void init_node(reference value)
1385 { node_algorithms::init(value_traits::to_node_ptr(value)); }
1387 //! <b>Effects</b>: removes "value" from the container.
1389 //! <b>Throws</b>: Nothing.
1391 //! <b>Complexity</b>: Logarithmic time.
1393 //! <b>Note</b>: This static function is only usable with non-constant
1394 //! time size containers that have stateless comparison functors.
1396 //! If the user calls
1397 //! this function with a constant time size container or stateful comparison
1398 //! functor a compilation error will be issued.
1399 static void remove_node(reference value)
1401 BOOST_STATIC_ASSERT((!constant_time_size));
1402 node_ptr to_remove(value_traits::to_node_ptr(value));
1403 node_algorithms::unlink(to_remove);
1404 if(safemode_or_autounlink)
1405 node_algorithms::init(to_remove);
1410 template<class Disposer>
1411 iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer)
1413 for(n = 0; b != e; ++n)
1414 this->erase_and_dispose(b++, disposer);
1418 iterator private_erase(const_iterator b, const_iterator e, size_type &n)
1420 for(n = 0; b != e; ++n)
1427 static rbtree_impl &priv_container_from_end_iterator(const const_iterator &end_iterator)
1429 header_plus_size *r = detail::parent_from_member<header_plus_size, node>
1430 ( detail::boost_intrusive_get_pointer(end_iterator.pointed_node()), &header_plus_size::header_);
1431 node_plus_pred_t *n = detail::parent_from_member
1432 <node_plus_pred_t, header_plus_size>(r, &node_plus_pred_t::header_plus_size_);
1433 data_t *d = detail::parent_from_member<data_t, node_plus_pred_t>(n, &data_t::node_plus_pred_);
1434 rbtree_impl *rb = detail::parent_from_member<rbtree_impl, data_t>(d, &rbtree_impl::data_);
1438 static rbtree_impl &priv_container_from_iterator(const const_iterator &it)
1439 { return priv_container_from_end_iterator(it.end_iterator_from_it()); }
1442 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1443 template<class T, class ...Options>
1445 template<class Config>
1447 inline bool operator<
1448 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1449 (const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y)
1451 (const rbtree_impl<Config> &x, const rbtree_impl<Config> &y)
1453 { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1455 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1456 template<class T, class ...Options>
1458 template<class Config>
1461 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1462 (const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y)
1464 (const rbtree_impl<Config> &x, const rbtree_impl<Config> &y)
1467 typedef rbtree_impl<Config> tree_type;
1468 typedef typename tree_type::const_iterator const_iterator;
1470 if(tree_type::constant_time_size && x.size() != y.size()){
1473 const_iterator end1 = x.end();
1474 const_iterator i1 = x.begin();
1475 const_iterator i2 = y.begin();
1476 if(tree_type::constant_time_size){
1477 while (i1 != end1 && *i1 == *i2) {
1484 const_iterator end2 = y.end();
1485 while (i1 != end1 && i2 != end2 && *i1 == *i2) {
1489 return i1 == end1 && i2 == end2;
1493 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1494 template<class T, class ...Options>
1496 template<class Config>
1498 inline bool operator!=
1499 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1500 (const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y)
1502 (const rbtree_impl<Config> &x, const rbtree_impl<Config> &y)
1504 { return !(x == y); }
1506 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1507 template<class T, class ...Options>
1509 template<class Config>
1511 inline bool operator>
1512 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1513 (const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y)
1515 (const rbtree_impl<Config> &x, const rbtree_impl<Config> &y)
1519 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1520 template<class T, class ...Options>
1522 template<class Config>
1524 inline bool operator<=
1525 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1526 (const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y)
1528 (const rbtree_impl<Config> &x, const rbtree_impl<Config> &y)
1530 { return !(y < x); }
1532 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1533 template<class T, class ...Options>
1535 template<class Config>
1537 inline bool operator>=
1538 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1539 (const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y)
1541 (const rbtree_impl<Config> &x, const rbtree_impl<Config> &y)
1543 { return !(x < y); }
1545 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1546 template<class T, class ...Options>
1548 template<class Config>
1551 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1552 (rbtree_impl<T, Options...> &x, rbtree_impl<T, Options...> &y)
1554 (rbtree_impl<Config> &x, rbtree_impl<Config> &y)
1559 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1560 template<class T, class O1 = none, class O2 = none
1561 , class O3 = none, class O4 = none
1564 template<class T, class ...Options>
1566 struct make_rbtree_opt
1568 typedef typename pack_options
1570 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1575 >::type packed_options;
1576 typedef typename detail::get_value_traits
1577 <T, typename packed_options::value_traits>::type value_traits;
1581 , typename packed_options::compare
1582 , typename packed_options::size_type
1583 , packed_options::constant_time_size
1588 //! Helper metafunction to define a \c rbtree that yields to the same type when the
1589 //! same options (either explicitly or implicitly) are used.
1590 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1591 template<class T, class ...Options>
1593 template<class T, class O1 = none, class O2 = none
1594 , class O3 = none, class O4 = none>
1600 < typename make_rbtree_opt<T,
1601 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1607 > implementation_defined;
1609 typedef implementation_defined type;
1612 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1614 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1615 template<class T, class O1, class O2, class O3, class O4>
1617 template<class T, class ...Options>
1620 : public make_rbtree<T,
1621 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1628 typedef typename make_rbtree
1630 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1636 BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree)
1639 typedef typename Base::value_compare value_compare;
1640 typedef typename Base::value_traits value_traits;
1641 typedef typename Base::real_value_traits real_value_traits;
1642 typedef typename Base::iterator iterator;
1643 typedef typename Base::const_iterator const_iterator;
1645 //Assert if passed value traits are compatible with the type
1646 BOOST_STATIC_ASSERT((detail::is_same<typename real_value_traits::value_type, T>::value));
1648 rbtree( const value_compare &cmp = value_compare()
1649 , const value_traits &v_traits = value_traits())
1650 : Base(cmp, v_traits)
1653 template<class Iterator>
1654 rbtree( bool unique, Iterator b, Iterator e
1655 , const value_compare &cmp = value_compare()
1656 , const value_traits &v_traits = value_traits())
1657 : Base(unique, b, e, cmp, v_traits)
1660 rbtree(BOOST_RV_REF(rbtree) x)
1661 : Base(::boost::move(static_cast<Base&>(x)))
1664 rbtree& operator=(BOOST_RV_REF(rbtree) x)
1665 { this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; }
1667 static rbtree &container_from_end_iterator(iterator end_iterator)
1668 { return static_cast<rbtree &>(Base::container_from_end_iterator(end_iterator)); }
1670 static const rbtree &container_from_end_iterator(const_iterator end_iterator)
1671 { return static_cast<const rbtree &>(Base::container_from_end_iterator(end_iterator)); }
1673 static rbtree &container_from_it(iterator it)
1674 { return static_cast<rbtree &>(Base::container_from_iterator(it)); }
1676 static const rbtree &container_from_it(const_iterator it)
1677 { return static_cast<const rbtree &>(Base::container_from_iterator(it)); }
1683 } //namespace intrusive
1686 #include <boost/intrusive/detail/config_end.hpp>
1688 #endif //BOOST_INTRUSIVE_RBTREE_HPP