1 /////////////////////////////////////////////////////////////////////////////
\r
3 // (C) Copyright Olaf Krzikalla 2004-2006.
\r
4 // (C) Copyright Ion GaztaƱaga 2006-2007
\r
6 // Distributed under the Boost Software License, Version 1.0.
\r
7 // (See accompanying file LICENSE_1_0.txt or copy at
\r
8 // http://www.boost.org/LICENSE_1_0.txt)
\r
10 // See http://www.boost.org/libs/intrusive for documentation.
\r
12 /////////////////////////////////////////////////////////////////////////////
\r
14 #ifndef BOOST_INTRUSIVE_ISLIST_HPP
\r
15 #define BOOST_INTRUSIVE_ISLIST_HPP
\r
17 #include "detail/config_begin.hpp"
\r
18 #include <boost/utility.hpp>
\r
19 #include <boost/static_assert.hpp>
\r
20 #include <boost/assert.hpp>
\r
21 #include <boost/type_traits/is_convertible.hpp>
\r
22 #include "islist_hook.hpp"
\r
23 #include "slist_algorithms.hpp"
\r
24 #include "detail/pointer_type.hpp"
\r
25 #include "detail/pointer_to_other.hpp"
\r
26 #include "linking_policy.hpp"
\r
31 namespace intrusive {
\r
33 //! The class template islist is an intrusive container, that encapsulates
\r
34 //! a singly-linked list. You can use such a list to squeeze the last bit
\r
35 //! of performance from your application. Unfortunately, the little gains
\r
36 //! come with some huge drawbacks. A lot of member functions can't be
\r
37 //! implemented as efficiently as for standard containers. To overcome
\r
38 //! this limitation some other member functions with rather unusual semantics
\r
39 //! have to be introduced.
\r
41 //! The template parameter ValueTraits is called "value traits". It stores
\r
42 //! information and operations about the type to be stored in the container.
\r
44 //! If the user specifies ConstantTimeSize as "true", a member of type SizeType
\r
45 //! will be embedded in the class, that will keep track of the number of stored objects.
\r
46 //! This will allow constant-time O(1) size() member, instead of default O(N) size.
\r
48 //! The iterators of islist are forward iterators. islist provides a static
\r
49 //! function called "previous" to compute the previous iterator of a given iterator.
\r
50 //! This function has linear complexity. To improve the usability esp. with
\r
51 //! the '*_after' functions, ++end() == begin() and previous(begin()) == end()
\r
52 //! are defined. In addition, whenever you have an end iterator, 'after this
\r
53 //! iterator' means 'at the beginning of the list'. To improve the self-documentation
\r
54 //! a "before_begin()" function is defined, returning the end() iterator.
\r
55 template < class ValueTraits
\r
56 , bool ConstantTimeSize = true
\r
57 , class SizeType = std::size_t>
\r
59 : private detail::size_holder<ConstantTimeSize, SizeType>
\r
62 typedef islist<ValueTraits, ConstantTimeSize, SizeType> this_type;
\r
63 typedef typename ValueTraits::node_traits node_traits;
\r
64 typedef detail::size_holder<ConstantTimeSize, SizeType> size_traits;
\r
68 islist (const islist&);
\r
72 islist &operator =(const islist&);
\r
76 typedef typename ValueTraits::value_type value_type;
\r
77 typedef typename ValueTraits::pointer pointer;
\r
78 typedef typename ValueTraits::const_pointer const_pointer;
\r
79 typedef value_type& reference;
\r
80 typedef const value_type& const_reference;
\r
81 typedef SizeType size_type;
\r
82 typedef typename std::iterator_traits
\r
83 <pointer>::difference_type difference_type;
\r
86 class const_iterator;
\r
87 friend class iterator;
\r
88 friend class const_iterator;
\r
91 typedef typename node_traits::node node;
\r
92 typedef typename boost::pointer_to_other
\r
93 <pointer, node>::type node_ptr;
\r
94 typedef typename boost::pointer_to_other
\r
95 <pointer, const node>::type const_node_ptr;
\r
96 typedef slist_algorithms<node_traits> node_algorithms;
\r
97 enum { safemode_or_autounlink =
\r
98 (int)ValueTraits::linking_policy == (int)auto_unlink ||
\r
99 (int)ValueTraits::linking_policy == (int)safe_mode_link };
\r
101 //Constant-time size is incompatible with auto-unlink hooks!
\r
102 BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));
\r
106 node_ptr get_root_node()
\r
107 { return node_ptr(&root); }
\r
109 const_node_ptr get_root_node() const
\r
110 { return const_node_ptr(&root); }
\r
112 static node_ptr uncast(const_node_ptr ptr)
\r
114 using boost::get_pointer;
\r
115 return node_ptr(const_cast<node*>(get_pointer(ptr)));
\r
118 static iterator previous_node(iterator beg, iterator i)
\r
121 (node_algorithms::get_previous_node(beg.list_node(), i.list_node()));
\r
124 static const_iterator previous_node(const_iterator beg, const_iterator i)
\r
126 return const_iterator
\r
127 (node_algorithms::get_previous_node(beg.list_node(), i.list_node()));
\r
130 //This functor compares a stored value
\r
131 //and the one passed as an argument
\r
132 class equal_to_value
\r
134 const value_type &t_;
\r
137 equal_to_value(const value_type &t)
\r
141 bool operator()(const value_type &t)const
\r
142 { return t_ == t; }
\r
147 //!The forward iterator of the container
\r
149 : public detail::slist_iterator<value_type, iterator, node_traits>
\r
152 // gcc warns about an ambiguity between iterator::value_type and
\r
153 // islist<ValueTraits>::value_type, thus I introduce a unique name:
\r
154 typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::value_type private_vt;
\r
155 typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::pointer private_pointer;
\r
156 typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::reference private_reference;
\r
157 typedef detail::slist_iterator<private_vt, iterator, node_traits> inherited;
\r
163 private_pointer operator->() const
\r
164 { return ValueTraits::to_value_ptr(this->list_node()); }
\r
166 private_reference operator*() const
\r
167 { return *ValueTraits::to_value_ptr(this->list_node()); }
\r
169 node_ptr list_node()const
\r
170 { return inherited::list_node(); }
\r
173 explicit iterator (node_ptr node)
\r
177 friend class islist<ValueTraits, ConstantTimeSize, SizeType>;
\r
178 friend class detail::slist_iterator<private_vt, iterator, node_traits>;
\r
179 friend class const_iterator;
\r
182 //!The forward const_iterator of the container
\r
183 class const_iterator
\r
184 : public detail::slist_iterator<const value_type, const_iterator, node_traits>
\r
187 typedef const typename islist<ValueTraits, ConstantTimeSize, SizeType>::value_type private_vt;
\r
188 typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::const_pointer private_pointer;
\r
189 typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::const_reference private_reference;
\r
190 typedef detail::slist_iterator<private_vt, const_iterator, node_traits> inherited;
\r
196 const_iterator(const typename islist::iterator& it)
\r
197 : inherited (it.list_node())
\r
200 const_iterator & operator=(const typename islist::iterator& it)
\r
201 { return inherited::operator=(it.list_node()); }
\r
203 private_pointer operator->()
\r
204 { return ValueTraits::to_value_ptr(this->list_node()); }
\r
206 private_reference operator*()
\r
207 { return *ValueTraits::to_value_ptr(this->list_node()); }
\r
210 explicit const_iterator (const_node_ptr node)
\r
211 : inherited (uncast(node))
\r
214 friend class islist<ValueTraits, ConstantTimeSize, SizeType>;
\r
215 friend class detail::slist_iterator<private_vt, const_iterator, node_traits>;
\r
220 //! <b>Effects</b>: constructs an empty list.
\r
222 //! <b>Complexity</b>: Constant
\r
224 //! <b>Throws</b>: If value_traits::node_traits::node
\r
225 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).
\r
228 size_traits::set_size(size_type(0));
\r
229 node_algorithms::init(node_ptr(&root));
\r
232 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
\r
234 //! <b>Effects</b>: Constructs a list equal to [first,last).
\r
236 //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called.
\r
238 //! <b>Throws</b>: If value_traits::node_traits::node
\r
239 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).
\r
240 template<class Iterator>
\r
241 islist(Iterator b, Iterator e)
\r
243 size_traits::set_size(size_type(0));
\r
244 node_algorithms::init(node_ptr(&root));
\r
245 insert_after(before_begin(), b, e);
\r
248 //! <b>Effects</b>: If it's a safe-mode
\r
249 //! or auto-unlink value, the destructor does nothing
\r
250 //! (ie. no code is generated). Otherwise it detaches all elements from this.
\r
251 //! In this case the objects in the list are not deleted (i.e. no destructors
\r
252 //! are called), but the hooks according to the ValueTraits template parameter
\r
253 //! are set to their default value.
\r
255 //! <b>Complexity</b>: Linear to the number of elements in the list, if
\r
256 //! it's a safe-mode or auto-unlink value. Otherwise constant.
\r
260 //! <b>Effects</b>: Erases all the elements of the container.
\r
262 //! <b>Throws</b>: Nothing.
\r
264 //! <b>Complexity</b>: Linear to the number of elements of the list.
\r
265 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
\r
267 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements.
\r
270 if(safemode_or_autounlink){
\r
271 this->erase_after(this->before_begin(), this->end());
\r
274 node_algorithms::init(node_ptr(&root));
\r
275 size_traits::set_size(size_type(0));
\r
279 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
281 //! <b>Effects</b>: Erases all the elements of the container
\r
282 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
284 //! <b>Throws</b>: Nothing.
\r
286 //! <b>Complexity</b>: Linear to the number of elements of the list.
\r
288 //! <b>Note</b>: Invalidates the iterators to the erased elements.
\r
289 template <class Destroyer>
\r
290 void clear_and_destroy(Destroyer destroyer)
\r
291 { this->erase_after_and_destroy(this->before_begin(), this->end(), destroyer); }
\r
293 //! <b>Requires</b>: value must be an lvalue.
\r
295 //! <b>Effects</b>: Inserts the value in the front of the list.
\r
296 //! No copy constructors are called.
\r
298 //! <b>Throws</b>: Nothing.
\r
300 //! <b>Complexity</b>: Constant.
\r
302 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
303 void push_front(value_type &value)
\r
305 node_ptr to_insert(ValueTraits::to_node_ptr(value));
\r
306 if(safemode_or_autounlink)
\r
307 BOOST_ASSERT(node_algorithms::unique(to_insert));
\r
308 node_algorithms::link_after(get_root_node(), to_insert);
\r
309 size_traits::increment();
\r
312 //! <b>Effects</b>: Erases the first element of the list.
\r
313 //! No destructors are called.
\r
315 //! <b>Throws</b>: Nothing.
\r
317 //! <b>Complexity</b>: Constant.
\r
319 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element.
\r
322 node_ptr to_erase = node_traits::get_next(get_root_node());
\r
323 node_algorithms::unlink_after(get_root_node());
\r
324 size_traits::decrement();
\r
325 if(safemode_or_autounlink)
\r
326 node_algorithms::init(to_erase);
\r
329 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
331 //! <b>Effects</b>: Erases the first element of the list.
\r
332 //! Destroyer::operator()(pointer) is called for the removed element.
\r
334 //! <b>Throws</b>: Nothing.
\r
336 //! <b>Complexity</b>: Constant.
\r
338 //! <b>Note</b>: Invalidates the iterators to the erased element.
\r
339 template<class Destroyer>
\r
340 void pop_front_and_destroy(Destroyer destroyer)
\r
342 node_ptr to_erase = node_traits::get_next(get_root_node());
\r
344 destroyer(ValueTraits::to_value_ptr(to_erase));
\r
347 //! <b>Effects</b>: Returns a reference to the first element of the list.
\r
349 //! <b>Throws</b>: Nothing.
\r
351 //! <b>Complexity</b>: Constant.
\r
353 { return *ValueTraits::to_value_ptr(node_traits::get_next(get_root_node())); }
\r
355 //! <b>Effects</b>: Returns a const_reference to the first element of the list.
\r
357 //! <b>Throws</b>: Nothing.
\r
359 //! <b>Complexity</b>: Constant.
\r
360 const_reference front() const
\r
361 { return *ValueTraits::to_value_ptr(uncast(node_traits::get_next(const_node_ptr(&root)))); }
\r
363 //! <b>Effects</b>: Returns an iterator to the first element contained in the list.
\r
365 //! <b>Throws</b>: Nothing.
\r
367 //! <b>Complexity</b>: Constant.
\r
369 { return iterator (node_traits::get_next(get_root_node())); }
\r
371 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
\r
373 //! <b>Throws</b>: Nothing.
\r
375 //! <b>Complexity</b>: Constant.
\r
376 const_iterator begin() const
\r
377 { return const_iterator (node_traits::get_next(get_root_node())); }
\r
379 //! <b>Effects</b>: Returns an iterator to the end of the list.
\r
381 //! <b>Throws</b>: Nothing.
\r
383 //! <b>Complexity</b>: Constant.
\r
385 { return iterator (get_root_node()); }
\r
387 //! <b>Effects</b>: Returns a const_iterator to the end of the list.
\r
389 //! <b>Throws</b>: Nothing.
\r
391 //! <b>Complexity</b>: Constant.
\r
392 const_iterator end() const
\r
393 { return const_iterator (get_root_node()); }
\r
395 //! <b>Effects</b>: Returns an iterator that points to a position
\r
396 //! before the first element. Equivalent to "end()"
\r
398 //! <b>Throws</b>: Nothing.
\r
400 //! <b>Complexity</b>: Constant.
\r
401 iterator before_begin()
\r
404 //! <b>Effects</b>: Returns an iterator that points to a position
\r
405 //! before the first element. Equivalent to "end()"
\r
407 //! <b>Throws</b>: Nothing.
\r
409 //! <b>Complexity</b>: Constant.
\r
410 const_iterator before_begin() const
\r
413 //! <b>Effects</b>: Returns the number of the elements contained in the list.
\r
415 //! <b>Throws</b>: Nothing.
\r
417 //! <b>Complexity</b>: Linear to the number of elements contained in the list.
\r
418 //! if ConstantTimeSize is false. Constant time otherwise.
\r
420 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
421 size_type size() const
\r
423 if(ConstantTimeSize)
\r
424 return size_traits::get_size();
\r
426 return node_algorithms::count(const_node_ptr(&root)) - 1;
\r
429 //! <b>Effects</b>: Returns true if the list contains no elements.
\r
431 //! <b>Throws</b>: Nothing.
\r
433 //! <b>Complexity</b>: Constant.
\r
435 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
437 { return node_algorithms::unique(get_root_node()); }
\r
439 //! <b>Effects</b>: Swaps the elements of x and *this.
\r
441 //! <b>Throws</b>: Nothing.
\r
443 //! <b>Complexity</b>: Linear to the number of elements of both lists.
\r
445 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
446 void swap(islist& other)
\r
448 node_algorithms::swap_nodes(get_root_node(), &other.root);
\r
449 if(ConstantTimeSize){
\r
450 size_type backup = size_traits::get_size();
\r
451 size_traits::set_size(other.get_size());
\r
452 other.set_size(backup);
\r
456 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
458 //! <b>Effects</b>: Erases all the elements from *this
\r
459 //! calling Destroyer::operator()(pointer), clones all the
\r
460 //! elements from src calling Cloner::operator()(const value_type &)
\r
461 //! and inserts them on *this.
\r
463 //! If cloner throws, all cloned elements are unlinked and destroyed
\r
464 //! calling Destroyer::operator()(pointer).
\r
466 //! <b>Complexity</b>: Linear to erased plus inserted elements.
\r
468 //! <b>Throws</b>: If cloner throws.
\r
469 template <class Cloner, class Destroyer>
\r
470 void clone_from(const islist &src, Cloner cloner, Destroyer destroyer)
\r
472 clone_and_reverse_from(src, cloner, destroyer);
\r
476 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
478 //! <b>Effects</b>: Erases all the elements from *this
\r
479 //! calling Destroyer::operator()(pointer), clones all the
\r
480 //! elements from src calling Cloner::operator()(const value_type &)
\r
481 //! and inserts them on *this in the reverse order than
\r
482 //! the original container.
\r
484 //! If cloner throws, all cloned elements are unlinked and destroyed
\r
485 //! calling Destroyer::operator()(pointer).
\r
487 //! <b>Complexity</b>: Linear to erased plus inserted elements.
\r
489 //! <b>Throws</b>: If cloner throws.
\r
491 //! <b>Note</b>: This function is more efficient than "clone_from".
\r
492 template <class Cloner, class Destroyer>
\r
493 void clone_and_reverse_from(const islist &src, Cloner cloner, Destroyer destroyer)
\r
495 this->clear_and_destroy(destroyer);
\r
497 const_iterator b(src.begin()), e(src.end());
\r
498 for(; b != e; ++b){
\r
499 this->push_front(*cloner(*b));
\r
503 clear_and_destroy(destroyer);
\r
508 //! <b>Requires</b>: value must be an lvalue and prev_p must point to an element
\r
509 //! contained by the list or to end().
\r
511 //! <b>Effects</b>: Inserts the value after the position pointed by prev_p.
\r
512 //! No copy constructor is called.
\r
514 //! <b>Returns</b>: An iterator to the inserted element.
\r
516 //! <b>Throws</b>: Nothing.
\r
518 //! <b>Complexity</b>: Constant.
\r
520 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
521 iterator insert_after(iterator prev_p, value_type &value)
\r
523 node_ptr n = ValueTraits::to_node_ptr(value);
\r
524 if(safemode_or_autounlink)
\r
525 BOOST_ASSERT(node_algorithms::unique(n));
\r
526 node_algorithms::link_after(prev_p.list_node(), n);
\r
527 size_traits::increment();
\r
528 return iterator (n);
\r
531 //! <b>Requires</b>: Dereferencing iterator must yield
\r
532 //! an lvalue of type value_type and prev_p must point to an element
\r
533 //! contained by the list or to the end node.
\r
535 //! <b>Effects</b>: Inserts the [first, last)
\r
536 //! after the position prev_p.
\r
538 //! <b>Throws</b>: Nothing.
\r
540 //! <b>Complexity</b>: Linear to the number of elements inserted.
\r
542 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
543 template<class Iterator>
\r
544 void insert_after(iterator prev_p, Iterator first, Iterator last)
\r
546 for (; first != last; ++first)
\r
547 prev_p = insert_after(prev_p, *first);
\r
550 //! <b>Requires</b>: value must be an lvalue and p must point to an element
\r
551 //! contained by the list or to end().
\r
553 //! <b>Effects</b>: Inserts the value before the position pointed by p.
\r
554 //! No copy constructor is called.
\r
556 //! <b>Throws</b>: Nothing.
\r
558 //! <b>Complexity</b>: Linear to the number of elements before p.
\r
560 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
561 iterator insert(iterator p, value_type &value)
\r
562 { return insert_after(this->previous(p), value); }
\r
564 //! <b>Requires</b>: Dereferencing iterator must yield
\r
565 //! an lvalue of type value_type and p must point to an element
\r
566 //! contained by the list or to the end node.
\r
568 //! <b>Effects</b>: Inserts the pointed by b and e
\r
569 //! before the position p. No copy constructors are called.
\r
571 //! <b>Throws</b>: Nothing.
\r
573 //! <b>Complexity</b>: Linear to the number of elements inserted plus linear
\r
574 //! to the elements before b.
\r
576 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
577 template<class Iterator>
\r
578 void insert(iterator p, Iterator b, Iterator e)
\r
579 { return insert_after(this->previous(p), b, e); }
\r
581 //! <b>Effects</b>: Erases the element after the element pointed by prev of
\r
582 //! the list. No destructors are called.
\r
584 //! <b>Returns</b>: the first element remaining beyond the removed elements,
\r
585 //! or end() if no such element exists.
\r
587 //! <b>Throws</b>: Nothing.
\r
589 //! <b>Complexity</b>: Constant.
\r
591 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
\r
592 //! erased element.
\r
593 iterator erase_after(iterator prev)
\r
595 iterator it(prev); ++it;
\r
596 node_ptr to_erase(it.list_node());
\r
597 node_algorithms::unlink_after(prev.list_node());
\r
598 size_traits::decrement();
\r
599 iterator ret(++prev);
\r
600 if(safemode_or_autounlink)
\r
601 node_algorithms::init(to_erase);
\r
605 //! <b>Effects</b>: Erases the range (before_first, last) from
\r
606 //! the list. No destructors are called.
\r
608 //! <b>Returns</b>: the first element remaining beyond the removed elements,
\r
609 //! or end() if no such element exists.
\r
611 //! <b>Throws</b>: Nothing.
\r
613 //! <b>Complexity</b>: Lineal to the elements (last - before_first).
\r
615 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
\r
616 //! erased element.
\r
617 iterator erase_after(iterator before_first, iterator last)
\r
620 while(++(first = before_first) != last){
\r
621 this->erase_after(before_first);
\r
626 //! <b>Effects</b>: Erases the element pointed by i of the list.
\r
627 //! No destructors are called.
\r
629 //! <b>Returns</b>: the first element remaining beyond the removed element,
\r
630 //! or end() if no such element exists.
\r
632 //! <b>Throws</b>: Nothing.
\r
634 //! <b>Complexity</b>: Linear to the elements before i.
\r
636 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
\r
637 //! erased element.
\r
638 iterator erase(iterator i)
\r
639 { return this->erase_after(this->previous(i)); }
\r
641 //! <b>Requires</b>: first and last must be valid iterator to elements in *this.
\r
643 //! <b>Effects</b>: Erases the range pointed by b and e.
\r
644 //! No destructors are called.
\r
646 //! <b>Returns</b>: the first element remaining beyond the removed elements,
\r
647 //! or end() if no such element exists.
\r
649 //! <b>Throws</b>: Nothing.
\r
651 //! <b>Complexity</b>: Linear to the number of elements erased plus linear
\r
652 //! to the elements before first.
\r
654 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
\r
655 //! erased elements.
\r
656 iterator erase(iterator first, iterator last)
\r
657 { return erase_after(this->previous(first), last); }
\r
659 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
661 //! <b>Effects</b>: Erases the element after the element pointed by prev of
\r
663 //! Destroyer::operator()(pointer) is called for the removed element.
\r
665 //! <b>Returns</b>: the first element remaining beyond the removed elements,
\r
666 //! or end() if no such element exists.
\r
668 //! <b>Throws</b>: Nothing.
\r
670 //! <b>Complexity</b>: Constant.
\r
672 //! <b>Note</b>: Invalidates the iterators to the erased element.
\r
673 template<class Destroyer>
\r
674 iterator erase_after_and_destroy(iterator prev, Destroyer destroyer)
\r
676 iterator it(prev); ++it;
\r
677 node_ptr to_erase(it.list_node());
\r
678 iterator ret(this->erase_after(prev));
\r
679 destroyer(ValueTraits::to_value_ptr(to_erase));
\r
683 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
685 //! <b>Effects</b>: Erases the range (before_first, last) from
\r
687 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
689 //! <b>Returns</b>: the first element remaining beyond the removed elements,
\r
690 //! or end() if no such element exists.
\r
692 //! <b>Throws</b>: Nothing.
\r
694 //! <b>Complexity</b>: Lineal to the elements (last - before_first).
\r
696 //! <b>Note</b>: Invalidates the iterators to the erased element.
\r
697 template<class Destroyer>
\r
698 iterator erase_after_and_destroy(iterator before_first, iterator last, Destroyer destroyer)
\r
701 while(++(first = before_first) != last){
\r
702 this->erase_after_and_destroy(before_first, destroyer);
\r
707 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
709 //! <b>Effects</b>: Erases the element pointed by i of the list.
\r
710 //! No destructors are called.
\r
711 //! Destroyer::operator()(pointer) is called for the removed element.
\r
713 //! <b>Returns</b>: the first element remaining beyond the removed element,
\r
714 //! or end() if no such element exists.
\r
716 //! <b>Throws</b>: Nothing.
\r
718 //! <b>Complexity</b>: Linear to the elements before i.
\r
720 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
\r
721 //! erased element.
\r
722 template<class Destroyer>
\r
723 iterator erase_and_destroy(iterator i, Destroyer destroyer)
\r
724 { return this->erase_after_and_destroy(this->previous(i), destroyer); }
\r
726 //! <b>Requires</b>: first and last must be valid iterator to elements in *this.
\r
727 //! Destroyer::operator()(pointer) shouldn't throw.
\r
729 //! <b>Effects</b>: Erases the range pointed by b and e.
\r
730 //! No destructors are called.
\r
731 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
733 //! <b>Returns</b>: the first element remaining beyond the removed elements,
\r
734 //! or end() if no such element exists.
\r
736 //! <b>Throws</b>: Nothing.
\r
738 //! <b>Complexity</b>: Linear to the number of elements erased plus linear
\r
739 //! to the elements before first.
\r
741 //! <b>Note</b>: Invalidates the iterators (but not the references) to the
\r
742 //! erased elements.
\r
743 template<class Destroyer>
\r
744 iterator erase_and_destroy(iterator first, iterator last, Destroyer destroyer)
\r
745 { return erase_after_and_destroy(this->previous(first), last, destroyer); }
\r
747 //! <b>Requires</b>: Dereferencing iterator must yield
\r
748 //! an lvalue of type value_type.
\r
750 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.
\r
751 //! No destructors or copy constructors are called.
\r
753 //! <b>Throws</b>: Nothing.
\r
755 //! <b>Complexity</b>: Linear to the number of elements inserted plus
\r
756 //! linear to the elements contained in the list if it's a safe-mode
\r
757 //! or auto-unlink value.
\r
758 //! Linear to the number of elements inserted in the list otherwise.
\r
760 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
761 //! to the erased elements.
\r
762 template<class Iterator>
\r
763 void assign(Iterator b, Iterator e)
\r
766 this->insert_after(before_begin(), b, e);
\r
769 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
771 //! <b>Requires</b>: Dereferencing iterator must yield
\r
772 //! an lvalue of type value_type.
\r
774 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.
\r
775 //! No destructors or copy constructors are called.
\r
776 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
778 //! <b>Throws</b>: Nothing.
\r
780 //! <b>Complexity</b>: Linear to the number of elements inserted plus
\r
781 //! linear to the elements contained in the list.
\r
783 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
784 //! to the erased elements.
\r
785 template<class Iterator, class Destroyer>
\r
786 void assign_and_destroy(Iterator b, Iterator e, Destroyer destroyer)
\r
788 this->clear_and_destroy(destroyer);
\r
789 this->insert_after_and_destroy(before_begin(), b, e, destroyer);
\r
792 //! <b>Requires</b>: prev is an iterator to an element or x.end()/x.before_begin() in x.
\r
794 //! <b>Effects</b>: Transfers all the elements of list x to this list, after the
\r
795 //! the element pointed by prev. No destructors or copy constructors are called.
\r
797 //! <b>Returns</b>: The last element inserted of x or prev if x is empty.
\r
798 //! This iterator can be used as new "prev" iterator for a new splice_after call.
\r
799 //! that will splice new values after the previously spliced values.
\r
801 //! <b>Throws</b>: Nothing.
\r
803 //! <b>Complexity</b>: Linear to the elements contained in x
\r
805 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
\r
806 //! list. Iterators of this list and all the references are not invalidated.
\r
807 iterator splice_after(iterator prev, islist &x)
\r
810 iterator last_x(x.previous(x.end()));
\r
811 node_algorithms::transfer_after
\r
813 , x.end().list_node()
\r
814 , last_x.list_node());
\r
815 size_traits::set_size(size_traits::get_size() + x.get_size());
\r
816 x.set_size(size_type(0));
\r
824 //! <b>Requires</b>: prev must point to an element contained by this list or
\r
825 //! to the before_begin() element. prev_ele must point to an element contained in list
\r
826 //! x or must be x.before_begin().
\r
828 //! <b>Effects</b>: Transfers the element after prev_ele, from list x to this list,
\r
829 //! after the element pointed by prev. No destructors or copy constructors are called.
\r
831 //! <b>Throws</b>: Nothing.
\r
833 //! <b>Complexity</b>: Constant.
\r
835 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
\r
836 //! list. Iterators of this list and all the references are not invalidated.
\r
837 void splice_after(iterator prev, islist &x, iterator prev_ele)
\r
839 iterator nxt = prev_ele;
\r
841 if (nxt != prev && prev_ele != prev){
\r
842 node_algorithms::transfer_after
\r
843 (prev.list_node(), prev_ele.list_node(), nxt.list_node());
\r
844 size_traits::increment();
\r
849 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
\r
850 //! before_begin(), and before_first and before_last belong to x and
\r
851 //! ++before_first != x.end() && before_last != x.end().
\r
853 //! <b>Effects</b>: Transfers the range (before_first, before_last] from list x to this
\r
854 //! list, after the element pointed by prev_pos.
\r
855 //! No destructors or copy constructors are called.
\r
857 //! <b>Throws</b>: Nothing.
\r
859 //! <b>Complexity</b>: Linear to the number of elements transferred
\r
860 //! if ConstantTimeSize is true. Constant-time otherwise.
\r
862 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
\r
863 //! list. Iterators of this list and all the references are not invalidated.
\r
864 void splice_after(iterator prev_pos, islist &x, iterator before_first, iterator before_last)
\r
866 if (before_first != before_last){
\r
867 if(ConstantTimeSize){
\r
868 size_type increment = std::distance(before_first, before_last);
\r
869 node_algorithms::transfer_after
\r
870 (prev_pos.list_node(), before_first.list_node(), before_last.list_node());
\r
871 size_traits::set_size(size_traits::get_size() + increment);
\r
872 x.set_size(x.get_size() - increment);
\r
875 node_algorithms::transfer_after
\r
876 (prev_pos.list_node(), before_first.list_node(), before_last.list_node());
\r
881 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be
\r
882 //! before_begin(), and before_first and before_last belong to x and
\r
883 //! ++before_first != x.end() && before_last != x.end() and
\r
884 //! n == std::distance(before_first, before_last).
\r
886 //! <b>Effects</b>: Transfers the range (before_first, before_last] from list x to this
\r
887 //! list, after the element pointed by p. No destructors or copy constructors are called.
\r
889 //! <b>Throws</b>: Nothing.
\r
891 //! <b>Complexity</b>: Constant time.
\r
893 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
\r
894 //! list. Iterators of this list and all the references are not invalidated.
\r
895 void splice_after(iterator prev_pos, islist &x, iterator before_first, iterator before_last, difference_type n)
\r
898 if(ConstantTimeSize){
\r
899 BOOST_ASSERT(std::distance(before_first, before_last) == n);
\r
900 node_algorithms::transfer_after
\r
901 (prev_pos.list_node(), before_first.list_node(), before_last.list_node());
\r
902 size_traits::set_size(size_traits::get_size() + n);
\r
903 x.set_size(x.get_size() - n);
\r
906 node_algorithms::transfer_after
\r
907 (prev_pos.list_node(), before_first.list_node(), before_last.list_node());
\r
912 //! <b>Requires</b>: it is an iterator to an element in x.
\r
914 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the
\r
915 //! the element pointed by it. No destructors or copy constructors are called.
\r
917 //! <b>Returns</b>: The last element inserted of x or the previous element
\r
918 //! of it if x is empty.
\r
919 //! This iterator can be used as new "prev" iterator for a new splice call.
\r
920 //! that will splice new values after the previously spliced values.
\r
922 //! <b>Throws</b>: Nothing.
\r
924 //! <b>Complexity</b>: Linear to the elements contained in x plus linear to
\r
925 //! the elements before it.
\r
927 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
\r
928 //! list. Iterators of this list and all the references are not invalidated.
\r
929 iterator splice(iterator it, islist &x)
\r
930 { return splice_after(this->previous(it), x); }
\r
932 //! <b>Requires</b>: it p must be a valid iterator of *this.
\r
933 //! elem must point to an element contained in list
\r
936 //! <b>Effects</b>: Transfers the element elem, from list x to this list,
\r
937 //! before the element pointed by pos. No destructors or copy constructors are called.
\r
939 //! <b>Throws</b>: Nothing.
\r
941 //! <b>Complexity</b>: Linear to the elements before pos and before elem.
\r
943 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
\r
944 //! list. Iterators of this list and all the references are not invalidated.
\r
945 void splice(iterator pos, islist &x, iterator elem)
\r
946 { return splice_after(this->previous(pos), x, this->previous(elem)); }
\r
948 //! <b>Requires</b>: pos must be a dereferenceable iterator in *this
\r
949 //! and first and last belong to x and first and last a valid range on x.
\r
951 //! <b>Effects</b>: Transfers the range [first, last) from list x to this
\r
952 //! list, before the element pointed by pos.
\r
953 //! No destructors or copy constructors are called.
\r
955 //! <b>Throws</b>: Nothing.
\r
957 //! <b>Complexity</b>: Linear to the sum of elements before pos, first, and last.
\r
958 //! Plus linear to the number of elements transferred if ConstantTimeSize is true.
\r
960 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
\r
961 //! list. Iterators of this list and all the references are not invalidated.
\r
962 void splice(iterator pos, islist &x, iterator first, iterator last)
\r
963 { return splice_after(this->previous(pos), x, this->previous(first), this->previous(last)); }
\r
965 //! <b>Requires</b>: pos must be a dereferenceable iterator in *this
\r
966 //! and first and last belong to x and first and last a valid range on x.
\r
967 //! n == std::distance(first, last).
\r
969 //! <b>Effects</b>: Transfers the range [first, last) from list x to this
\r
970 //! list, before the element pointed by pos.
\r
971 //! No destructors or copy constructors are called.
\r
973 //! <b>Throws</b>: Nothing.
\r
975 //! <b>Complexity</b>: Linear to the sum of elements before pos, first, and last.
\r
977 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
\r
978 //! list. Iterators of this list and all the references are not invalidated.
\r
979 void splice(iterator pos, islist &x, iterator first, iterator last, difference_type n)
\r
980 { return splice_after(this->previous(pos), x, this->previous(first), this->previous(last), n); }
\r
982 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>.
\r
983 //! The sort is stable, that is, the relative order of equivalent elements is preserved.
\r
985 //! <b>Throws</b>: If value_traits::node_traits::node
\r
986 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
987 //! or the predicate throws. Basic guarantee.
\r
989 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
\r
990 //! is the list's size.
\r
992 //! <b>Note</b>: Iterators and references are not invalidated
\r
993 template<class Predicate>
\r
994 void sort(Predicate p)
\r
996 if (!this->empty() &&
\r
997 node_traits::get_next(node_traits::get_next(get_root_node()))
\r
998 != this->get_root_node()) {
\r
1000 islist counter[64];
\r
1002 iterator last_inserted;
\r
1003 while(!this->empty()){
\r
1004 last_inserted = this->begin();
\r
1005 carry.splice_after(carry.before_begin(), *this, this->before_begin());
\r
1007 while(i < fill && !counter[i].empty()) {
\r
1008 last_inserted = carry.merge(counter[i++], p);
\r
1010 BOOST_ASSERT(counter[i].empty());
\r
1012 iterator last_element(previous_node(last_inserted, carry.end()));
\r
1013 if(ConstantTimeSize){
\r
1014 counter[i].splice_after( counter[i].end(), carry
\r
1015 , carry.before_begin(), last_element
\r
1019 counter[i].splice_after( counter[i].end(), carry
\r
1020 , carry.before_begin(), last_element);
\r
1022 //counter[i].splice_after(counter[i].end(), carry, carry.end(), previous_node(last_inserted, carry.end()));
\r
1023 //carry.swap(counter[i]);
\r
1028 for (int i = 1; i < fill; ++i)
\r
1029 last_inserted = counter[i].merge(counter[i-1], p);
\r
1030 //this->swap(counter[fill-1]);
\r
1031 BOOST_ASSERT(this->empty());
\r
1033 iterator last_element(previous_node(last_inserted, counter[--fill].end()));
\r
1034 if(ConstantTimeSize){
\r
1035 this->splice_after( end(), counter[fill], counter[fill].before_begin()
\r
1036 , last_element, counter[fill].size());
\r
1039 this->splice_after( end(), counter[fill], counter[fill].before_begin()
\r
1045 //! <b>Requires</b>: p must be a comparison function that induces a strict weak
\r
1046 //! ordering and both *this and x must be sorted according to that ordering
\r
1047 //! The lists x and *this must be distinct.
\r
1049 //! <b>Effects</b>: This function removes all of x's elements and inserts them
\r
1050 //! in order into *this. The merge is stable; that is, if an element from *this is
\r
1051 //! equivalent to one from x, then the element from *this will precede the one from x.
\r
1053 //! <b>Throws</b>: If value_traits::node_traits::node
\r
1054 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
1055 //! or std::less<value_type> throws. Basic guarantee.
\r
1057 //! <b>Complexity</b>: This function is linear time: it performs at most
\r
1058 //! size() + x.size() - 1 comparisons.
\r
1060 //! <b>Note</b>: Iterators and references are not invalidated.
\r
1062 { this->sort(std::less<value_type>()); }
\r
1064 //! <b>Requires</b>: p must be a comparison function that induces a strict weak
\r
1065 //! ordering and both *this and x must be sorted according to that ordering
\r
1066 //! The lists x and *this must be distinct.
\r
1068 //! <b>Effects</b>: This function removes all of x's elements and inserts them
\r
1069 //! in order into *this. The merge is stable; that is, if an element from *this is
\r
1070 //! equivalent to one from x, then the element from *this will precede the one from x.
\r
1072 //! <b>Returns</b>: An iterator to the last transferred value, end() is x is empty.
\r
1074 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
\r
1076 //! <b>Complexity</b>: This function is linear time: it performs at most
\r
1077 //! size() + x.size() - 1 comparisons.
\r
1079 //! <b>Note</b>: Iterators and references are not invalidated.
\r
1080 template<class Predicate>
\r
1081 iterator merge(islist& x, Predicate p)
\r
1083 iterator a(before_begin()), e(end()), ax(x.before_begin());
\r
1084 iterator last_inserted(e);
\r
1086 while(++(a_next = a) != e && !x.empty()) {
\r
1090 while(++(cx = ix) != ax && p(*cx, *a_next)){
\r
1094 this->splice_after(a, x, ax, ix, n);
\r
1095 last_inserted = ix;
\r
1100 last_inserted = this->splice_after(a, x);
\r
1102 return last_inserted;
\r
1105 //! <b>Effects</b>: This function removes all of x's elements and inserts them
\r
1106 //! in order into *this according to std::less<value_type>. The merge is stable;
\r
1107 //! that is, if an element from *this is equivalent to one from x, then the element
\r
1108 //! from *this will precede the one from x.
\r
1110 //! <b>Throws</b>: if std::less<value_type> throws. Basic guarantee.
\r
1112 //! <b>Complexity</b>: This function is linear time: it performs at most
\r
1113 //! size() + x.size() - 1 comparisons.
\r
1115 //! <b>Note</b>: Iterators and references are not invalidated
\r
1116 void merge(islist& x)
\r
1117 { this->merge(x, std::less<value_type>()); }
\r
1119 //! <b>Effects</b>: Reverses the order of elements in the list.
\r
1121 //! <b>Throws</b>: Nothing.
\r
1123 //! <b>Complexity</b>: This function is linear to the contained elements.
\r
1125 //! <b>Note</b>: Iterators and references are not invalidated
\r
1127 { node_algorithms::reverse(node_ptr(&root)); }
\r
1129 //! <b>Effects</b>: Removes all the elements that compare equal to value.
\r
1130 //! No destructors are called.
\r
1132 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
\r
1134 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
\r
1136 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
\r
1137 //! and iterators to elements that are not removed remain valid. This function is
\r
1138 //! linear time: it performs exactly size() comparisons for equality.
\r
1139 void remove(const value_type &value)
\r
1140 { remove_if(equal_to_value(value)); }
\r
1142 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1144 //! <b>Effects</b>: Removes all the elements that compare equal to value.
\r
1145 //! Destroyer::operator()(pointer) is called for every removed element.
\r
1147 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
\r
1149 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
\r
1151 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
\r
1152 //! and iterators to elements that are not removed remain valid.
\r
1153 template<class Destroyer>
\r
1154 void remove_and_destroy(const value_type &value, Destroyer destroyer)
\r
1155 { remove_and_destroy_if(equal_to_value(value), destroyer); }
\r
1157 //! <b>Effects</b>: Removes all the elements for which a specified
\r
1158 //! predicate is satisfied. No destructors are called.
\r
1160 //! <b>Throws</b>: If pred throws. Basic guarantee.
\r
1162 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.
\r
1164 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
\r
1165 //! and iterators to elements that are not removed remain valid.
\r
1166 template<class Pred>
\r
1167 void remove_if(Pred pred)
\r
1168 { remove_and_destroy_if(pred, detail::null_destroyer()); }
\r
1170 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1172 //! <b>Effects</b>: Removes all the elements for which a specified
\r
1173 //! predicate is satisfied.
\r
1174 //! Destroyer::operator()(pointer) is called for every removed element.
\r
1176 //! <b>Throws</b>: If pred throws. Basic guarantee.
\r
1178 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
\r
1180 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
\r
1181 //! and iterators to elements that are not removed remain valid.
\r
1182 template<class Pred, class Destroyer>
\r
1183 void remove_and_destroy_if(Pred pred, Destroyer destroyer)
\r
1185 iterator bcur(this->before_begin()), cur, e(this->end());
\r
1187 while(++(cur = bcur) != e){
\r
1189 pointer p = cur.operator->();
\r
1190 this->erase_after(bcur);
\r
1199 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
\r
1200 //! elements that are equal from the list. No destructors are called.
\r
1202 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
\r
1204 //! <b>Complexity</b>: Linear time (size()-1) comparisons calls to pred()).
\r
1206 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
\r
1207 //! and iterators to elements that are not removed remain valid.
\r
1209 { unique_and_destroy(std::equal_to<value_type>(), detail::null_destroyer()); }
\r
1211 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
\r
1212 //! elements that satisfy some binary predicate from the list.
\r
1213 //! No destructors are called.
\r
1215 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
\r
1217 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
\r
1219 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
\r
1220 //! and iterators to elements that are not removed remain valid.
\r
1221 template<class BinaryPredicate>
\r
1222 void unique(BinaryPredicate pred)
\r
1223 { unique_and_destroy(pred, detail::null_destroyer()); }
\r
1225 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1227 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
\r
1228 //! elements that satisfy some binary predicate from the list.
\r
1229 //! Destroyer::operator()(pointer) is called for every removed element.
\r
1231 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.
\r
1233 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
\r
1235 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
\r
1236 //! and iterators to elements that are not removed remain valid.
\r
1237 template<class Destroyer>
\r
1238 void unique_and_destroy(Destroyer destroyer)
\r
1239 { unique(std::equal_to<value_type>(), destroyer); }
\r
1241 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1243 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
\r
1244 //! elements that satisfy some binary predicate from the list.
\r
1245 //! Destroyer::operator()(pointer) is called for every removed element.
\r
1247 //! <b>Throws</b>: If the predicate throws. Basic guarantee.
\r
1249 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.
\r
1251 //! <b>Note</b>: The relative order of elements that are not removed is unchanged,
\r
1252 //! and iterators to elements that are not removed remain valid.
\r
1253 template<class BinaryPredicate, class Destroyer>
\r
1254 void unique_and_destroy(BinaryPredicate pred, Destroyer destroyer)
\r
1256 iterator end_n(end());
\r
1257 iterator cur(begin());
\r
1258 iterator cur_next;
\r
1260 if (cur != end_n) {
\r
1261 while(++(cur_next = cur) != end_n) {
\r
1262 if (pred(*cur, *cur_next)){
\r
1263 pointer p = cur_next.operator->();
\r
1264 this->erase_after(cur);
\r
1274 //! <b>Requires</b>: value must be a reference to a value inserted in a list.
\r
1276 //! <b>Effects</b>: This function returns a const_iterator pointing to the element
\r
1278 //! <b>Throws</b>: Nothing.
\r
1280 //! <b>Complexity</b>: Constant time.
\r
1282 //! <b>Note</b>: Iterators and references are not invalidated.
\r
1283 static iterator current(value_type &value)
\r
1285 BOOST_ASSERT (!node_algorithms::unique(ValueTraits::to_node_ptr(value)));
\r
1286 return iterator (ValueTraits::to_node_ptr(value));
\r
1289 //! <b>Requires</b>: value must be a const reference to a value inserted in a list.
\r
1291 //! <b>Effects</b>: This function returns an iterator pointing to the element.
\r
1293 //! <b>Throws</b>: Nothing.
\r
1295 //! <b>Complexity</b>: Constant time.
\r
1297 //! <b>Note</b>: Iterators and references are not invalidated.
\r
1298 static const_iterator current(const value_type &value)
\r
1300 BOOST_ASSERT (!node_algorithms::unique(ValueTraits::to_node_ptr(const_cast<value_type&> (value))));
\r
1301 return const_iterator (ValueTraits::to_node_ptr(const_cast<value_type&> (value)));
\r
1304 //! <b>Returns</b>: The iterator to the element before i in the list.
\r
1305 //! Returns the end-iterator, if either i is the begin-iterator or the
\r
1306 //! list is empty.
\r
1308 //! <b>Throws</b>: Nothing.
\r
1310 //! <b>Complexity</b>: Linear to the number of elements before i.
\r
1311 iterator previous(iterator i)
\r
1314 (node_algorithms::get_previous_node
\r
1315 (before_begin().list_node(), i.list_node()));
\r
1318 //! <b>Returns</b>: The const_iterator to the element before i in the list.
\r
1319 //! Returns the end-const_iterator, if either i is the begin-const_iterator or
\r
1320 //! the list is empty.
\r
1322 //! <b>Throws</b>: Nothing.
\r
1324 //! <b>Complexity</b>: Linear to the number of elements before i.
\r
1325 const_iterator previous(const_iterator i) const
\r
1327 return const_iterator
\r
1328 (node_algorithms::get_previous_node
\r
1329 (before_begin().list_node(), i.list_node()));
\r
1333 template <class V, bool C, class S>
\r
1334 inline bool operator==(const islist<V, C, S>& x, const islist<V, C, S>& y)
\r
1336 if(C && x.size() != y.size()){
\r
1339 typedef typename islist<V, C, S>::const_iterator const_iterator;
\r
1340 const_iterator end1 = x.end();
\r
1342 const_iterator i1 = x.begin();
\r
1343 const_iterator i2 = y.begin();
\r
1345 while (i1 != end1 && *i1 == *i2) {
\r
1349 return i1 == end1;
\r
1352 const_iterator end2 = y.end();
\r
1353 while (i1 != end1 && i2 != end2 && *i1 == *i2) {
\r
1357 return i1 == end1 && i2 == end2;
\r
1361 template <class V, bool C, class S>
\r
1362 inline bool operator<(const islist<V, C, S>& x,
\r
1363 const islist<V, C, S>& y)
\r
1364 { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
\r
1366 template <class V, bool C, class S>
\r
1367 inline bool operator!=(const islist<V, C, S>& x, const islist<V, C, S>& y)
\r
1368 { return !(x == y); }
\r
1370 template <class V, bool C, class S>
\r
1371 inline bool operator>(const islist<V, C, S>& x, const islist<V, C, S>& y)
\r
1374 template <class V, bool C, class S>
\r
1375 inline bool operator<=(const islist<V, C, S>& x, const islist<V, C, S>& y)
\r
1376 { return !(y < x); }
\r
1378 template <class V, bool C, class S>
\r
1379 inline bool operator>=(const islist<V, C, S>& x, const islist<V, C, S>& y)
\r
1380 { return !(x < y); }
\r
1382 template <class V, bool C, class S>
\r
1383 inline void swap(islist<V, C, S>& x, islist<V, C, S>& y)
\r
1386 } //namespace intrusive
\r
1387 } //namespace boost
\r
1389 #include "detail/config_end.hpp"
\r
1391 #endif //BOOST_INTRUSIVE_ISLIST_HPP
\r