1 /////////////////////////////////////////////////////////////////////////////
\r
3 // (C) Copyright Ion Gaztañaga 2006-2007
\r
5 // Distributed under the Boost Software License, Version 1.0.
\r
6 // (See accompanying file LICENSE_1_0.txt or copy at
\r
7 // http://www.boost.org/LICENSE_1_0.txt)
\r
9 // See http://www.boost.org/libs/intrusive for documentation.
\r
11 /////////////////////////////////////////////////////////////////////////////
\r
12 #ifndef BOOST_INTRUSIVE_IRBTREE_HPP
\r
13 #define BOOST_INTRUSIVE_IRBTREE_HPP
\r
15 #include "config_begin.hpp"
\r
16 #include <functional>
\r
18 #include <boost/utility.hpp>
\r
19 #include <boost/compressed_pair.hpp>
\r
21 #include <boost/assert.hpp>
\r
22 #include <boost/static_assert.hpp>
\r
23 #include "pointer_type.hpp"
\r
24 #include "pointer_to_other.hpp"
\r
25 #include "../iset_hook.hpp"
\r
26 #include "rbtree_node.hpp"
\r
27 #include "ebo_holder.hpp"
\r
28 #include "../rbtree_algorithms.hpp"
\r
29 #include "../linking_policy.hpp"
\r
34 namespace intrusive {
\r
37 //! The class template irbtree is an intrusive red-black tree container, that
\r
38 //! is used to construct intrusive set and tree containers. The no-throw
\r
39 //! guarantee holds only, if the Compare object
\r
41 template < class ValueTraits
\r
42 , class Compare = std::less<typename ValueTraits::value_type>
\r
43 , bool ConstantTimeSize = true
\r
44 , class SizeType = std::size_t
\r
47 : private detail::size_holder<ConstantTimeSize, SizeType>
\r
50 typedef irbtree<ValueTraits, Compare
\r
51 ,ConstantTimeSize, SizeType> this_type;
\r
52 typedef typename ValueTraits::node_traits node_traits;
\r
53 typedef detail::size_holder<ConstantTimeSize, SizeType> size_traits;
\r
56 irbtree (const irbtree&);
\r
57 irbtree operator =(const irbtree&);
\r
60 typedef typename ValueTraits::value_type value_type;
\r
61 typedef typename ValueTraits::pointer pointer;
\r
62 typedef typename ValueTraits::const_pointer const_pointer;
\r
63 typedef value_type& reference;
\r
64 typedef const value_type& const_reference;
\r
65 typedef SizeType size_type;
\r
66 typedef typename std::iterator_traits
\r
67 <pointer>::difference_type difference_type;
\r
68 typedef value_type key_type;
\r
69 typedef Compare value_compare;
\r
71 class const_iterator;
\r
72 friend class iterator;
\r
73 friend class const_iterator;
\r
76 typedef typename node_traits::node node;
\r
77 typedef typename boost::pointer_to_other
\r
78 <pointer, node>::type node_ptr;
\r
79 typedef typename boost::pointer_to_other
\r
80 <node_ptr, const node>::type const_node_ptr;
\r
81 typedef rbtree_algorithms<node_traits> node_algorithms;
\r
82 enum { safemode_or_autounlink =
\r
83 (int)ValueTraits::linking_policy == (int)auto_unlink ||
\r
84 (int)ValueTraits::linking_policy == (int)safe_mode_link };
\r
86 //Constant-time size is incompatible with auto-unlink hooks!
\r
87 BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));
\r
89 template<class KeyValueCompare>
\r
90 struct key_node_ptr_compare
\r
91 : private ebo_holder<KeyValueCompare>
\r
93 typedef ebo_holder<KeyValueCompare> base_t;
\r
94 key_node_ptr_compare(KeyValueCompare kcomp)
\r
98 template<class KeyType>
\r
99 bool operator()(node_ptr node, const KeyType &key) const
\r
100 { return base_t::get()(*ValueTraits::to_value_ptr(node), key); }
\r
102 template<class KeyType>
\r
103 bool operator()(const KeyType &key, node_ptr node) const
\r
104 { return base_t::get()(key, *ValueTraits::to_value_ptr(node)); }
\r
106 bool operator()(node_ptr node1, node_ptr node2) const
\r
108 return base_t::get()
\r
109 (*ValueTraits::to_value_ptr(node1), *ValueTraits::to_value_ptr(node2));
\r
113 //Use boost::compressed_pair to get EBO if possible
\r
114 boost::compressed_pair<node, Compare> members_;
\r
116 const Compare &priv_comp() const
\r
117 { return members_.second(); }
\r
119 Compare &priv_comp()
\r
120 { return members_.second(); }
\r
122 const node &priv_header() const
\r
123 { return members_.first(); }
\r
125 node &priv_header()
\r
126 { return members_.first(); }
\r
129 struct value_to_node_cloner
\r
130 : private ebo_holder<F>
\r
132 typedef ebo_holder<F> base_t;
\r
133 value_to_node_cloner(F f)
\r
137 node_ptr operator()(node_ptr p)
\r
138 { return ValueTraits::to_node_ptr(*base_t::get()(*ValueTraits::to_value_ptr(p))); }
\r
142 struct value_to_node_destroyer
\r
143 : private ebo_holder<F>
\r
145 typedef ebo_holder<F> base_t;
\r
146 value_to_node_destroyer(F f)
\r
150 void operator()(node_ptr p)
\r
151 { base_t::get()(ValueTraits::to_value_ptr(p)); }
\r
154 static node_ptr uncast(const_node_ptr ptr)
\r
156 using boost::get_pointer;
\r
157 return node_ptr(const_cast<node*>(get_pointer(ptr)));
\r
161 typedef typename node_algorithms::insert_commit_data insert_commit_data;
\r
164 : public detail::rbtree_iterator <value_type, iterator, node_traits>
\r
167 typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::value_type private_vt;
\r
168 typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::pointer private_pointer;
\r
169 typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::reference private_reference;
\r
170 typedef detail::rbtree_iterator<private_vt, iterator, node_traits> inherited;
\r
176 private_pointer operator->() const
\r
177 { return ValueTraits::to_value_ptr(this->tree_node()); }
\r
179 private_reference operator*() const
\r
180 { return *ValueTraits::to_value_ptr(this->tree_node()); }
\r
183 explicit iterator(node_ptr node)
\r
187 friend class irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>;
\r
188 friend class detail::rbtree_iterator<private_vt, iterator, node_traits>;
\r
189 friend class const_iterator;
\r
192 class const_iterator
\r
193 : public detail::rbtree_iterator<const value_type, const_iterator, node_traits>
\r
196 typedef const typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::value_type private_vt;
\r
197 typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::const_pointer private_pointer;
\r
198 typedef typename irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>::const_reference private_reference;
\r
199 typedef detail::rbtree_iterator<private_vt, const_iterator, node_traits> inherited;
\r
205 const_iterator(const typename irbtree::iterator& it)
\r
206 : inherited (it.tree_node())
\r
209 const_iterator & operator=(const typename irbtree::iterator& it)
\r
210 { return inherited::operator=(it.tree_node()); }
\r
212 private_pointer operator->()
\r
213 { return ValueTraits::to_value_ptr(this->tree_node()); }
\r
215 private_reference operator*()
\r
216 { return *ValueTraits::to_value_ptr(this->tree_node()); }
\r
219 explicit const_iterator (const_node_ptr p)
\r
220 : inherited (uncast(p))
\r
223 friend class irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType>;
\r
224 friend class detail::rbtree_iterator<private_vt, const_iterator, node_traits>;
\r
227 typedef std::reverse_iterator<iterator> reverse_iterator;
\r
228 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
\r
232 //! <b>Effects</b>: Constructs an empty tree.
\r
234 //! <b>Complexity</b>: Constant.
\r
236 //! <b>Throws</b>: Nothing unless the copy constructor of the Compare object throws.
\r
237 irbtree(Compare cmp = Compare())
\r
240 node_algorithms::init_header(&priv_header());
\r
241 size_traits::set_size(size_type(0));
\r
244 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
\r
245 //! cmp must be a comparison function that induces a strict weak ordering.
\r
247 //! <b>Effects</b>: Constructs an empty tree and inserts elements from
\r
250 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
\r
251 //! comp and otherwise N * log N, where N is last first.
\r
253 //! <b>Throws</b>: Nothing unless the copy constructor of the Compare object throws.
\r
254 template<class Iterator>
\r
255 irbtree(bool unique, Iterator b, Iterator e, Compare cmp = Compare())
\r
258 node_algorithms::init_header(&priv_header());
\r
259 size_traits::set_size(size_type(0));
\r
261 this->insert_unique(b, e);
\r
263 this->insert_equal(b, e);
\r
266 //! <b>Effects</b>: Detaches all elements from this. The objects in the set
\r
267 //! are not deleted (i.e. no destructors are called), but the nodes according to
\r
268 //! the ValueTraits template parameter are reinitialized and thus can be reused.
\r
270 //! <b>Complexity</b>: Linear to elements contained in *this.
\r
272 //! <b>Throws</b>: Nothing.
\r
276 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the tree.
\r
278 //! <b>Complexity</b>: Constant.
\r
280 //! <b>Throws</b>: Nothing.
\r
282 { return iterator (node_traits::get_left(node_ptr(&priv_header()))); }
\r
284 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the tree.
\r
286 //! <b>Complexity</b>: Constant.
\r
288 //! <b>Throws</b>: Nothing.
\r
289 const_iterator begin() const
\r
290 { return const_iterator (node_traits::get_left(const_node_ptr(&priv_header()))); }
\r
292 //! <b>Effects</b>: Returns an iterator pointing to the end of the tree.
\r
294 //! <b>Complexity</b>: Constant.
\r
296 //! <b>Throws</b>: Nothing.
\r
298 { return iterator (node_ptr(&priv_header())); }
\r
300 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the tree.
\r
302 //! <b>Complexity</b>: Constant.
\r
304 //! <b>Throws</b>: Nothing.
\r
305 const_iterator end() const
\r
306 { return const_iterator (const_node_ptr(&priv_header())); }
\r
308 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
\r
311 //! <b>Complexity</b>: Constant.
\r
313 //! <b>Throws</b>: Nothing.
\r
314 reverse_iterator rbegin()
\r
315 { return reverse_iterator(end()); }
\r
317 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
\r
318 //! of the reversed tree.
\r
320 //! <b>Complexity</b>: Constant.
\r
322 //! <b>Throws</b>: Nothing.
\r
323 const_reverse_iterator rbegin() const
\r
324 { return const_reverse_iterator(end()); }
\r
326 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
\r
327 //! of the reversed tree.
\r
329 //! <b>Complexity</b>: Constant.
\r
331 //! <b>Throws</b>: Nothing.
\r
332 reverse_iterator rend()
\r
333 { return reverse_iterator(begin()); }
\r
335 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
\r
336 //! of the reversed tree.
\r
338 //! <b>Complexity</b>: Constant.
\r
340 //! <b>Throws</b>: Nothing.
\r
341 const_reverse_iterator rend() const
\r
342 { return const_reverse_iterator(begin()); }
\r
344 //! <b>Effects</b>: Returns the value_compare object used by the tree.
\r
346 //! <b>Complexity</b>: Constant.
\r
348 //! <b>Throws</b>: If value_compare copy-constructor throws.
\r
349 value_compare value_comp() const
\r
350 { return priv_comp(); }
\r
352 //! <b>Effects</b>: Returns true is the container is empty.
\r
354 //! <b>Complexity</b>: Constant.
\r
356 //! <b>Throws</b>: Nothing.
\r
358 { return node_algorithms::unique(const_node_ptr(&priv_header())); }
\r
360 //! <b>Effects</b>: Returns the number of elements stored in the tree.
\r
362 //! <b>Complexity</b>: Linear to elements contained in *this.
\r
364 //! <b>Throws</b>: Nothing.
\r
365 size_type size() const
\r
367 if(ConstantTimeSize)
\r
368 return size_traits::get_size();
\r
370 return empty() ? 0 : node_algorithms::count(node_traits::get_parent(const_node_ptr(&priv_header())));
\r
373 //! <b>Effects</b>: Swaps the contents of two multisets.
\r
375 //! <b>Complexity</b>: Constant.
\r
377 //! <b>Throws</b>: If the comparison functor's unspecified swap call throws.
\r
378 void swap(irbtree& other)
\r
382 swap(priv_comp(), priv_comp());
\r
383 //These can't throw
\r
384 node_algorithms::swap_tree(node_ptr(&priv_header()), node_ptr(&other.priv_header()));
\r
385 if(ConstantTimeSize){
\r
386 size_type backup = size_traits::get_size();
\r
387 size_traits::set_size(other.get_size());
\r
388 other.set_size(backup);
\r
392 //! <b>Requires</b>: value must be an lvalue
\r
394 //! <b>Effects</b>: Inserts value into the tree before the upper bound.
\r
396 //! <b>Complexity</b>: Average complexity for insert element is at
\r
397 //! most logarithmic.
\r
399 //! <b>Throws</b>: Nothing.
\r
401 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
402 //! No copy-constructors are called.
\r
403 iterator insert_equal_upper_bound(value_type &value)
\r
405 key_node_ptr_compare<value_compare> key_node_comp(priv_comp());
\r
406 node_ptr to_insert(ValueTraits::to_node_ptr(value));
\r
407 if(safemode_or_autounlink)
\r
408 BOOST_ASSERT(node_algorithms::unique(to_insert));
\r
409 size_traits::increment();
\r
410 return iterator(node_algorithms::insert_equal_upper_bound
\r
411 (node_ptr(&priv_header()), to_insert, key_node_comp));
\r
414 //! <b>Requires</b>: value must be an lvalue
\r
416 //! <b>Effects</b>: Inserts value into the tree before the lower bound.
\r
418 //! <b>Complexity</b>: Average complexity for insert element is at
\r
419 //! most logarithmic.
\r
421 //! <b>Throws</b>: Nothing.
\r
423 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
424 //! No copy-constructors are called.
\r
425 iterator insert_equal_lower_bound(value_type &value)
\r
427 key_node_ptr_compare<value_compare> key_node_comp(priv_comp());
\r
428 node_ptr to_insert(ValueTraits::to_node_ptr(value));
\r
429 if(safemode_or_autounlink)
\r
430 BOOST_ASSERT(node_algorithms::unique(to_insert));
\r
431 size_traits::increment();
\r
432 return iterator(node_algorithms::insert_equal_lower_bound
\r
433 (node_ptr(&priv_header()), to_insert, key_node_comp));
\r
436 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
\r
437 //! a valid iterator.
\r
439 //! <b>Effects</b>: Inserts x into the tree, using "hint" as a hint to
\r
440 //! where it will be inserted. If "hint" is the upper_bound
\r
441 //! the insertion takes constant time (two comparisons in the worst case)
\r
443 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
\r
444 //! constant time if t is inserted immediately before hint.
\r
446 //! <b>Throws</b>: Nothing.
\r
448 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
449 //! No copy-constructors are called.
\r
450 iterator insert_equal(const_iterator hint, value_type &value)
\r
452 key_node_ptr_compare<value_compare> key_node_comp(priv_comp());
\r
453 node_ptr to_insert(ValueTraits::to_node_ptr(value));
\r
454 if(safemode_or_autounlink)
\r
455 BOOST_ASSERT(node_algorithms::unique(to_insert));
\r
456 size_traits::increment();
\r
457 return iterator(node_algorithms::insert_equal
\r
458 (node_ptr(&priv_header()), hint.tree_node(), to_insert, key_node_comp));
\r
461 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
\r
462 //! of type value_type.
\r
464 //! <b>Effects</b>: Inserts a each element of a range into the tree
\r
465 //! before the upper bound of the key of each element.
\r
467 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
\r
468 //! size of the range. However, it is linear in N if the range is already sorted
\r
469 //! by value_comp().
\r
471 //! <b>Throws</b>: Nothing.
\r
473 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
474 //! No copy-constructors are called.
\r
475 template<class Iterator>
\r
476 void insert_equal(Iterator b, Iterator e)
\r
479 iterator end(this->end());
\r
480 for (; b != e; ++b)
\r
481 this->insert_equal(end, *b);
\r
484 for (; b != e; ++b)
\r
485 this->insert_equal_upper_bound(*b);
\r
489 //! <b>Requires</b>: value must be an lvalue
\r
491 //! <b>Effects</b>: Inserts value into the tree if the value
\r
492 //! is not already present.
\r
494 //! <b>Complexity</b>: Average complexity for insert element is at
\r
495 //! most logarithmic.
\r
497 //! <b>Throws</b>: Nothing.
\r
499 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
500 //! No copy-constructors are called.
\r
501 std::pair<iterator, bool> insert_unique(value_type &value)
\r
503 insert_commit_data commit_data;
\r
504 std::pair<iterator, bool> ret = insert_unique_check(value, commit_data);
\r
507 return std::pair<iterator, bool> (insert_unique_commit(value, commit_data), true);
\r
510 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
\r
511 //! a valid iterator
\r
513 //! <b>Effects</b>: Tries to insert x into the tree, using "hint" as a hint
\r
514 //! to where it will be inserted.
\r
516 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
\r
517 //! constant time (two comparisons in the worst case)
\r
518 //! if t is inserted immediately before hint.
\r
520 //! <b>Throws</b>: Nothing.
\r
522 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
523 //! No copy-constructors are called.
\r
524 iterator insert_unique(const_iterator hint, value_type &value)
\r
526 insert_commit_data commit_data;
\r
527 std::pair<iterator, bool> ret = insert_unique_check(hint, value, commit_data);
\r
530 return insert_unique_commit(value, commit_data);
\r
533 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
\r
534 //! of type value_type.
\r
536 //! <b>Effects</b>: Tries to insert each element of a range into the tree.
\r
538 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
\r
539 //! size of the range. However, it is linear in N if the range is already sorted
\r
540 //! by value_comp().
\r
542 //! <b>Throws</b>: Nothing.
\r
544 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
545 //! No copy-constructors are called.
\r
546 template<class Iterator>
\r
547 void insert_unique(Iterator b, Iterator e)
\r
550 iterator end(this->end());
\r
551 for (; b != e; ++b)
\r
552 this->insert_unique(end, *b);
\r
555 for (; b != e; ++b)
\r
556 this->insert_unique(*b);
\r
560 std::pair<iterator, bool> insert_unique_check
\r
561 (const value_type &value, insert_commit_data &commit_data)
\r
562 { return insert_unique_check(value, priv_comp(), commit_data); }
\r
564 template<class KeyType, class KeyValueCompare>
\r
565 std::pair<iterator, bool> insert_unique_check
\r
566 (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
\r
568 key_node_ptr_compare<KeyValueCompare> comp(key_value_comp);
\r
569 std::pair<node_ptr, bool> ret =
\r
570 (node_algorithms::insert_unique_check
\r
571 (node_ptr(&priv_header()), key, comp, commit_data));
\r
572 return std::pair<iterator, bool>(iterator(ret.first), ret.second);
\r
575 std::pair<iterator, bool> insert_unique_check
\r
576 (const_iterator hint, const value_type &value, insert_commit_data &commit_data)
\r
577 { return insert_unique_check(hint, value, priv_comp(), commit_data); }
\r
579 template<class KeyType, class KeyValueCompare>
\r
580 std::pair<iterator, bool> insert_unique_check
\r
581 (const_iterator hint, const KeyType &key
\r
582 ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
\r
584 key_node_ptr_compare<KeyValueCompare> comp(key_value_comp);
\r
585 std::pair<node_ptr, bool> ret =
\r
586 (node_algorithms::insert_unique_check
\r
587 (node_ptr(&priv_header()), hint.tree_node(), key, comp, commit_data));
\r
588 return std::pair<iterator, bool>(iterator(ret.first), ret.second);
\r
591 iterator insert_unique_commit(value_type &value, const insert_commit_data &commit_data)
\r
593 node_ptr to_insert(ValueTraits::to_node_ptr(value));
\r
594 if(safemode_or_autounlink)
\r
595 BOOST_ASSERT(node_algorithms::unique(to_insert));
\r
596 size_traits::increment();
\r
597 node_algorithms::insert_unique_commit
\r
598 (node_ptr(&priv_header()), to_insert, commit_data);
\r
599 return iterator(to_insert);
\r
602 //! <b>Effects</b>: Erases the element pointed to by pos.
\r
604 //! <b>Complexity</b>: Average complexity for erase element is constant time.
\r
606 //! <b>Throws</b>: Nothing.
\r
608 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
609 //! to the erased elements. No destructors are called.
\r
610 iterator erase(iterator i)
\r
614 node_ptr to_erase(i.tree_node());
\r
615 if(safemode_or_autounlink)
\r
616 BOOST_ASSERT(!node_algorithms::unique(to_erase));
\r
617 node_algorithms::erase(&priv_header(), to_erase);
\r
618 size_traits::decrement();
\r
619 if(safemode_or_autounlink)
\r
620 node_algorithms::init(to_erase);
\r
624 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
626 //! <b>Complexity</b>: Average complexity for erase range is at most
\r
627 //! O(log(size() + N)), where N is the number of elements in the range.
\r
629 //! <b>Throws</b>: Nothing.
\r
631 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
632 //! to the erased elements. No destructors are called.
\r
633 iterator erase(iterator b, iterator e)
\r
634 { size_type n; return private_erase(b, e, n); }
\r
636 //! <b>Effects</b>: Erases all the elements with the given value.
\r
638 //! <b>Returns</b>: The number of erased elements.
\r
640 //! <b>Complexity</b>: O(log(size() + N).
\r
642 //! <b>Throws</b>: Nothing.
\r
644 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
645 //! to the erased elements. No destructors are called.
\r
646 size_type erase(const value_type &value)
\r
647 { return this->erase(value, priv_comp()); }
\r
649 //! <b>Effects</b>: Erases all the elements with the given key.
\r
650 //! according to the comparison functor "comp".
\r
652 //! <b>Returns</b>: The number of erased elements.
\r
654 //! <b>Complexity</b>: O(log(size() + N).
\r
656 //! <b>Throws</b>: Nothing.
\r
658 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
659 //! to the erased elements. No destructors are called.
\r
660 template<class KeyType, class KeyValueCompare>
\r
661 size_type erase(const KeyType& key, KeyValueCompare comp)
\r
663 std::pair<iterator,iterator> p = this->equal_range(key, comp);
\r
665 private_erase(p.first, p.second, n);
\r
669 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
671 //! <b>Effects</b>: Erases the element pointed to by pos.
\r
672 //! Destroyer::operator()(pointer) is called for the removed element.
\r
674 //! <b>Complexity</b>: Average complexity for erase element is constant time.
\r
676 //! <b>Throws</b>: Nothing.
\r
678 //! <b>Note</b>: Invalidates the iterators
\r
679 //! to the erased elements.
\r
680 template<class Destroyer>
\r
681 iterator erase_and_destroy(iterator i, Destroyer destroyer)
\r
683 node_ptr to_erase(i.tree_node());
\r
684 iterator ret(this->erase(i));
\r
685 destroyer(ValueTraits::to_value_ptr(to_erase));
\r
689 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
691 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
692 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
694 //! <b>Complexity</b>: Average complexity for erase range is at most
\r
695 //! O(log(size() + N)), where N is the number of elements in the range.
\r
697 //! <b>Throws</b>: Nothing.
\r
699 //! <b>Note</b>: Invalidates the iterators
\r
700 //! to the erased elements.
\r
701 template<class Destroyer>
\r
702 iterator erase_and_destroy(iterator b, iterator e, Destroyer destroyer)
\r
703 { size_type n; return private_erase(b, e, n, destroyer); }
\r
705 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
707 //! <b>Effects</b>: Erases all the elements with the given value.
\r
708 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
710 //! <b>Returns</b>: The number of erased elements.
\r
712 //! <b>Complexity</b>: O(log(size() + N).
\r
714 //! <b>Throws</b>: Nothing.
\r
716 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
717 //! to the erased elements. No destructors are called.
\r
718 template<class Destroyer>
\r
719 size_type erase_and_destroy(const value_type &value, Destroyer destroyer)
\r
721 std::pair<iterator,iterator> p = this->equal_range(value);
\r
723 private_erase(p.first, p.second, n, destroyer);
\r
727 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
729 //! <b>Effects</b>: Erases all the elements with the given key.
\r
730 //! according to the comparison functor "comp".
\r
731 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
733 //! <b>Returns</b>: The number of erased elements.
\r
735 //! <b>Complexity</b>: O(log(size() + N).
\r
737 //! <b>Throws</b>: Nothing.
\r
739 //! <b>Note</b>: Invalidates the iterators
\r
740 //! to the erased elements.
\r
741 template<class KeyType, class KeyValueCompare, class Destroyer>
\r
742 size_type erase_and_destroy(const KeyType& key, KeyValueCompare comp, Destroyer destroyer)
\r
744 std::pair<iterator,iterator> p = this->equal_range(key, comp);
\r
746 private_erase(p.first, p.second, n, destroyer);
\r
750 //! <b>Effects</b>: Erases all of the elements.
\r
752 //! <b>Complexity</b>: Linear to the number of elements on the container.
\r
753 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
\r
755 //! <b>Throws</b>: Nothing.
\r
757 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
758 //! to the erased elements. No destructors are called.
\r
761 if(safemode_or_autounlink){
\r
764 (node_algorithms::unlink_leftmost_without_rebalance
\r
765 (node_ptr(&priv_header())));
\r
768 size_traits::decrement();
\r
769 if(safemode_or_autounlink)
\r
770 node_algorithms::init(leftmost);
\r
774 node_algorithms::init_header(&priv_header());
\r
775 size_traits::set_size(0);
\r
779 //! <b>Effects</b>: Erases all of the elements calling destroyer(p) for
\r
780 //! each node to be erased.
\r
781 //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)),
\r
782 //! where N is the number of elements in the container.
\r
784 //! <b>Throws</b>: Nothing.
\r
786 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
787 //! to the erased elements. Calls N times to destroyer functor.
\r
788 template<class Destroyer>
\r
789 void clear_and_destroy(Destroyer destroyer)
\r
793 (node_algorithms::unlink_leftmost_without_rebalance
\r
794 (node_ptr(&priv_header())));
\r
797 size_traits::decrement();
\r
798 if(safemode_or_autounlink)
\r
799 node_algorithms::init(leftmost);
\r
800 destroyer(ValueTraits::to_value_ptr(leftmost));
\r
804 //! <b>Effects</b>: Returns the number of contained elements with the given value
\r
806 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
\r
807 //! to number of objects with the given value.
\r
809 //! <b>Throws</b>: Nothing.
\r
810 size_type count(const value_type &value) const
\r
811 { return this->count(value, priv_comp()); }
\r
813 //! <b>Effects</b>: Returns the number of contained elements with the given key
\r
815 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
\r
816 //! to number of objects with the given key.
\r
818 //! <b>Throws</b>: Nothing.
\r
819 template<class KeyType, class KeyValueCompare>
\r
820 size_type count(const KeyType &key, KeyValueCompare comp) const
\r
822 std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp);
\r
823 return std::distance(ret.first, ret.second);
\r
826 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
827 //! key is not less than k or end() if that element does not exist.
\r
829 //! <b>Complexity</b>: Logarithmic.
\r
831 //! <b>Throws</b>: Nothing.
\r
832 iterator lower_bound(const value_type &value)
\r
833 { return this->lower_bound(value, priv_comp()); }
\r
835 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
836 //! key is not less than k or end() if that element does not exist.
\r
838 //! <b>Complexity</b>: Logarithmic.
\r
840 //! <b>Throws</b>: Nothing.
\r
841 const_iterator lower_bound(const value_type &value) const
\r
842 { return this->lower_bound(value, priv_comp()); }
\r
844 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
845 //! key is not less than k or end() if that element does not exist.
\r
847 //! <b>Complexity</b>: Logarithmic.
\r
849 //! <b>Throws</b>: Nothing.
\r
850 template<class KeyType, class KeyValueCompare>
\r
851 iterator lower_bound(const KeyType &key, KeyValueCompare comp)
\r
853 key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);
\r
854 return iterator(node_algorithms::lower_bound
\r
855 (const_node_ptr(&priv_header()), key, key_node_comp));
\r
858 //! <b>Effects</b>: Returns a const iterator to the first element whose
\r
859 //! key is not less than k or end() if that element does not exist.
\r
861 //! <b>Complexity</b>: Logarithmic.
\r
863 //! <b>Throws</b>: Nothing.
\r
864 template<class KeyType, class KeyValueCompare>
\r
865 const_iterator lower_bound(const KeyType &key, KeyValueCompare comp) const
\r
867 key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);
\r
868 return const_iterator(node_algorithms::lower_bound
\r
869 (const_node_ptr(&priv_header()), key, key_node_comp));
\r
872 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
873 //! key is greater than k or end() if that element does not exist.
\r
875 //! <b>Complexity</b>: Logarithmic.
\r
877 //! <b>Throws</b>: Nothing.
\r
878 iterator upper_bound(const value_type &value)
\r
879 { return this->upper_bound(value, priv_comp()); }
\r
881 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
882 //! key is greater than k according to comp or end() if that element
\r
883 //! does not exist.
\r
885 //! <b>Complexity</b>: Logarithmic.
\r
887 //! <b>Throws</b>: Nothing.
\r
888 template<class KeyType, class KeyValueCompare>
\r
889 iterator upper_bound(const KeyType &key, KeyValueCompare comp)
\r
891 key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);
\r
892 return iterator(node_algorithms::upper_bound
\r
893 (const_node_ptr(&priv_header()), key, key_node_comp));
\r
896 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
897 //! key is greater than k or end() if that element does not exist.
\r
899 //! <b>Complexity</b>: Logarithmic.
\r
901 //! <b>Throws</b>: Nothing.
\r
902 const_iterator upper_bound(const value_type &value) const
\r
903 { return this->upper_bound(value, priv_comp()); }
\r
905 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
906 //! key is greater than k according to comp or end() if that element
\r
907 //! does not exist.
\r
909 //! <b>Complexity</b>: Logarithmic.
\r
911 //! <b>Throws</b>: Nothing.
\r
912 template<class KeyType, class KeyValueCompare>
\r
913 const_iterator upper_bound(const KeyType &key, KeyValueCompare comp) const
\r
915 key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);
\r
916 return const_iterator(node_algorithms::upper_bound
\r
917 (const_node_ptr(&priv_header()), key, key_node_comp));
\r
920 //! <b>Effects</b>: Finds an iterator to the first element whose key is
\r
921 //! k or end() if that element does not exist.
\r
923 //! <b>Complexity</b>: Logarithmic.
\r
925 //! <b>Throws</b>: Nothing.
\r
926 iterator find(const value_type &value)
\r
927 { return this->find(value, priv_comp()); }
\r
929 //! <b>Effects</b>: Finds an iterator to the first element whose key is
\r
930 //! k or end() if that element does not exist.
\r
932 //! <b>Complexity</b>: Logarithmic.
\r
934 //! <b>Throws</b>: Nothing.
\r
935 template<class KeyType, class KeyValueCompare>
\r
936 iterator find(const KeyType &key, KeyValueCompare comp)
\r
938 key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);
\r
940 (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp));
\r
943 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
\r
944 //! k or end() if that element does not exist.
\r
946 //! <b>Complexity</b>: Logarithmic.
\r
948 //! <b>Throws</b>: Nothing.
\r
949 const_iterator find(const value_type &value) const
\r
950 { return this->find(value, priv_comp()); }
\r
952 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
\r
953 //! k or end() if that element does not exist.
\r
955 //! <b>Complexity</b>: Logarithmic.
\r
957 //! <b>Throws</b>: Nothing.
\r
958 template<class KeyType, class KeyValueCompare>
\r
959 const_iterator find(const KeyType &key, KeyValueCompare comp) const
\r
961 key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);
\r
962 return const_iterator
\r
963 (node_algorithms::find(const_node_ptr(&priv_header()), key, key_node_comp));
\r
966 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
\r
967 //! an empty range that indicates the position where those elements would be
\r
968 //! if they there is no elements with key k.
\r
970 //! <b>Complexity</b>: Logarithmic.
\r
972 //! <b>Throws</b>: Nothing.
\r
973 std::pair<iterator,iterator> equal_range(const value_type &value)
\r
974 { return this->equal_range(value, priv_comp()); }
\r
976 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
\r
977 //! an empty range that indicates the position where those elements would be
\r
978 //! if they there is no elements with key k.
\r
980 //! <b>Complexity</b>: Logarithmic.
\r
982 //! <b>Throws</b>: Nothing.
\r
983 template<class KeyType, class KeyValueCompare>
\r
984 std::pair<iterator,iterator> equal_range(const KeyType &key, KeyValueCompare comp)
\r
986 key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);
\r
987 std::pair<node_ptr, node_ptr> ret
\r
988 (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp));
\r
989 return std::pair<iterator, iterator>(iterator(ret.first), iterator(ret.second));
\r
992 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
\r
993 //! an empty range that indicates the position where those elements would be
\r
994 //! if they there is no elements with key k.
\r
996 //! <b>Complexity</b>: Logarithmic.
\r
998 //! <b>Throws</b>: Nothing.
\r
999 std::pair<const_iterator, const_iterator>
\r
1000 equal_range(const value_type &value) const
\r
1001 { return this->equal_range(value, priv_comp()); }
\r
1003 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
\r
1004 //! an empty range that indicates the position where those elements would be
\r
1005 //! if they there is no elements with key k.
\r
1007 //! <b>Complexity</b>: Logarithmic.
\r
1009 //! <b>Throws</b>: Nothing.
\r
1010 template<class KeyType, class KeyValueCompare>
\r
1011 std::pair<const_iterator, const_iterator>
\r
1012 equal_range(const KeyType &key, KeyValueCompare comp) const
\r
1014 key_node_ptr_compare<KeyValueCompare> key_node_comp(comp);
\r
1015 std::pair<node_ptr, node_ptr> ret
\r
1016 (node_algorithms::equal_range(const_node_ptr(&priv_header()), key, key_node_comp));
\r
1017 return std::pair<const_iterator, const_iterator>(const_iterator(ret.first), const_iterator(ret.second));
\r
1020 template <class Cloner, class Destroyer>
\r
1021 void clone_from(const irbtree &src, Cloner cloner, Destroyer destroyer)
\r
1023 this->clear_and_destroy(destroyer);
\r
1025 node_algorithms::clone_tree
\r
1026 (const_node_ptr(&src.priv_header())
\r
1027 ,node_ptr(&this->priv_header())
\r
1028 ,value_to_node_cloner<Cloner>(cloner)
\r
1029 ,value_to_node_destroyer<Destroyer>(destroyer));
\r
1030 size_traits::set_size(src.get_size());
\r
1034 pointer unlink_leftmost_without_rebalance()
\r
1036 node_ptr to_destroy(node_algorithms::unlink_leftmost_without_rebalance
\r
1037 (node_ptr(&priv_header())));
\r
1040 size_traits::decrement();
\r
1041 if(safemode_or_autounlink)
\r
1042 node_algorithms::init(to_destroy);
\r
1043 return ValueTraits::to_value_ptr(to_destroy);
\r
1046 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
\r
1047 //! appropriate type. Otherwise the behavior is undefined.
\r
1049 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
\r
1050 //! that points to the value
\r
1052 //! <b>Complexity</b>: Constant.
\r
1054 //! <b>Throws</b>: Nothing.
\r
1055 static iterator current(value_type &value)
\r
1056 { return iterator (ValueTraits::to_node_ptr(value)); }
\r
1058 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
\r
1059 //! appropriate type. Otherwise the behavior is undefined.
\r
1061 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
\r
1062 //! set that points to the value
\r
1064 //! <b>Complexity</b>: Constant.
\r
1066 //! <b>Throws</b>: Nothing.
\r
1067 static const_iterator current(const value_type &value)
\r
1068 { return const_iterator (ValueTraits::to_node_ptr(const_cast<value_type&> (value))); }
\r
1070 //! <b>Requires</b>: value shall not be in a tree of the appropriate type.
\r
1072 //! <b>Effects</b>: init_node post-constructs the node data in x used by multisets of
\r
1073 //! the appropriate type. For the accessors multiset_derived_node and multiset_member_node
\r
1074 //! init_node has no effect, since the constructors of multiset_node_d and multiset_node_m
\r
1075 //! have already initialized the node data.
\r
1077 //! <b>Throws</b>: Nothing.
\r
1079 //! <b>Complexity</b>: Constant time.
\r
1081 //! <b>Note</b>: This function is meant to be used mainly with the member value_traits,
\r
1082 //! where no implicit node initialization during construction occurs.
\r
1083 static void init_node(reference value)
\r
1084 { node_algorithms::init(node_ptr(&*ValueTraits::to_node_ptr(value))); }
\r
1086 //! <b>Effects</b>: removes x from a tree of the appropriate type. It has no effect,
\r
1087 //! if x is not in such a tree.
\r
1089 //! <b>Throws</b>: Nothing.
\r
1091 //! <b>Complexity</b>: Constant time.
\r
1093 //! <b>Note</b>: This static function is only usable with the "safe mode"
\r
1094 //! hook and non-constant time size lists. Otherwise, the user must use
\r
1095 //! the non-static "erase(value_type &)" member. If the user calls
\r
1096 //! this function with a non "safe mode" or constant time size list
\r
1097 //! a compilation error will be issued.
\r
1099 static void remove_node(T& value)
\r
1101 //This function is only usable for safe mode hooks and non-constant
\r
1103 //BOOST_STATIC_ASSERT((!(safemode_or_autounlink && ConstantTimeSize)));
\r
1104 BOOST_STATIC_ASSERT((!ConstantTimeSize));
\r
1105 BOOST_STATIC_ASSERT((boost::is_convertible<T, value_type>::value));
\r
1106 node_ptr to_remove(ValueTraits::to_node_ptr(value));
\r
1107 node_algorithms::unlink_and_rebalance(to_remove);
\r
1108 if(safemode_or_autounlink)
\r
1109 node_algorithms::init(to_remove);
\r
1113 template<class Destroyer>
\r
1114 iterator private_erase(iterator b, iterator e, size_type &n, Destroyer destroyer)
\r
1116 for(n = 0; b != e; ++n)
\r
1117 this->erase_and_destroy(b++, destroyer);
\r
1121 iterator private_erase(iterator b, iterator e, size_type &n)
\r
1123 for(n = 0; b != e; ++n)
\r
1129 template <class V, class P, bool C, class S>
\r
1130 inline bool operator==(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y)
\r
1132 if(C && x.size() != y.size()){
\r
1135 typedef typename irbtree<V, P, C, S>::const_iterator const_iterator;
\r
1136 const_iterator end1 = x.end();
\r
1138 const_iterator i1 = x.begin();
\r
1139 const_iterator i2 = y.begin();
\r
1141 while (i1 != end1 && *i1 == *i2) {
\r
1145 return i1 == end1;
\r
1148 const_iterator end2 = y.end();
\r
1149 while (i1 != end1 && i2 != end2 && *i1 == *i2) {
\r
1153 return i1 == end1 && i2 == end2;
\r
1157 template <class V, class P, bool C, class S>
\r
1158 inline bool operator<(const irbtree<V, P, C, S>& x,
\r
1159 const irbtree<V, P, C, S>& y)
\r
1160 { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
\r
1162 template <class V, class P, bool C, class S>
\r
1163 inline bool operator!=(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y)
\r
1164 { return !(x == y); }
\r
1166 template <class V, class P, bool C, class S>
\r
1167 inline bool operator>(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y)
\r
1170 template <class V, class P, bool C, class S>
\r
1171 inline bool operator<=(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y)
\r
1172 { return !(y < x); }
\r
1174 template <class V, class P, bool C, class S>
\r
1175 inline bool operator>=(const irbtree<V, P, C, S>& x, const irbtree<V, P, C, S>& y)
\r
1176 { return !(x < y); }
\r
1178 template <class V, class P, bool C, class S>
\r
1179 inline void swap(irbtree<V, P, C, S>& x, irbtree<V, P, C, S>& y)
\r
1182 } //namespace detail
\r
1183 } //namespace intrusive
\r
1184 } //namespace boost
\r
1186 #include "config_end.hpp"
\r
1188 #endif //BOOST_INTRUSIVE_IRBTREE_HPP
\r