Move include files in debian packge into 'senf' subdirectory
[senf.git] / boost / intrusive / ilist.hpp
1 /////////////////////////////////////////////////////////////////////////////\r
2 //\r
3 // (C) Copyright Olaf Krzikalla 2004-2006.\r
4 // (C) Copyright Ion GaztaƱaga  2006-2007\r
5 //\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
9 //\r
10 // See http://www.boost.org/libs/intrusive for documentation.\r
11 //\r
12 /////////////////////////////////////////////////////////////////////////////\r
13 \r
14 #ifndef BOOST_INTRUSIVE_ILIST_HPP\r
15 #define BOOST_INTRUSIVE_ILIST_HPP\r
16 \r
17 #include "detail/config_begin.hpp"\r
18 #include <boost/utility.hpp>\r
19 #include <boost/assert.hpp>\r
20 #include "ilist_hook.hpp"\r
21 #include "list_algorithms.hpp"\r
22 #include "detail/pointer_type.hpp"\r
23 #include "detail/pointer_to_other.hpp"\r
24 #include "linking_policy.hpp"\r
25 #include <boost/get_pointer.hpp>\r
26 #include <boost/static_assert.hpp>\r
27 #include <iterator>\r
28 #include <algorithm>\r
29 #include <stdexcept>\r
30 #include <functional>\r
31 #include <cstddef>\r
32 #include <iterator>\r
33 \r
34 namespace boost {\r
35 namespace intrusive {\r
36 \r
37 //! The class template ilist is an intrusive container that mimics most of the \r
38 //! interface of std::list as described in the C++ standard.\r
39 //!\r
40 //! The template parameter ValueTraits is called "value traits". It stores\r
41 //! information and operations about the type to be stored in the container.\r
42 //!\r
43 //! If the user specifies ConstantTimeSize as "true", a member of type SizeType\r
44 //! will be embedded in the class, that will keep track of the number of stored objects.\r
45 //! This will allow constant-time O(1) size() member, instead of default O(N) size.\r
46 template< class ValueTraits\r
47         , bool  ConstantTimeSize = true\r
48         , class SizeType         = std::size_t>\r
49 class ilist\r
50    :  private detail::size_holder<ConstantTimeSize, SizeType>\r
51 {\r
52    private:\r
53 \r
54    typedef ilist<ValueTraits, ConstantTimeSize, SizeType>   this_type; \r
55    typedef typename ValueTraits::node_traits                node_traits;\r
56    typedef detail::size_holder<ConstantTimeSize, SizeType>  size_traits;\r
57 \r
58    //! This class is\r
59    //! non-copyable\r
60    ilist (const ilist&);\r
61 \r
62    //! This class is\r
63    //! non-assignable\r
64    ilist &operator =(const ilist&);\r
65 \r
66    //Public typedefs\r
67    public:\r
68    typedef typename ValueTraits::value_type        value_type;\r
69    typedef typename ValueTraits::pointer           pointer;\r
70    typedef typename ValueTraits::const_pointer     const_pointer;\r
71    typedef value_type&                             reference;\r
72    typedef const value_type&                       const_reference;\r
73    typedef SizeType                                size_type;\r
74    typedef typename std::iterator_traits\r
75       <pointer>::difference_type                   difference_type;\r
76 \r
77    //!The bidirectional iterator\r
78    class iterator;\r
79 \r
80    //!The bidirectional const_iterator\r
81    class const_iterator;\r
82 \r
83    //!The bidirectional iterator\r
84    friend class iterator;\r
85 \r
86    //!The bidirectional const_iterator\r
87    friend class const_iterator;\r
88 \r
89    private:\r
90 \r
91    typedef typename node_traits::node              node;\r
92    typedef typename node_traits::node_ptr          node_ptr;\r
93    typedef typename node_traits::const_node_ptr    const_node_ptr;\r
94    typedef list_algorithms<node_traits>            node_algorithms;\r
95    enum { safemode_or_autounlink  = \r
96             (int)ValueTraits::linking_policy == (int)auto_unlink   ||\r
97             (int)ValueTraits::linking_policy == (int)safe_mode_link     };\r
98 \r
99    //Constant-time size is incompatible with auto-unlink hooks!\r
100    BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));\r
101 \r
102    //This functor compares a stored value\r
103    //and the one passed as an argument\r
104    class equal_to_value\r
105    {\r
106       const value_type &t_;\r
107 \r
108       public:\r
109       equal_to_value(const value_type &t)\r
110          :  t_(t)\r
111       {}\r
112 \r
113       bool operator()(const value_type &t)const\r
114       {  return t_ == t;   }\r
115    };\r
116 \r
117    //Const cast emulation for smart pointers\r
118    static node_ptr uncast(const_node_ptr ptr)\r
119    {\r
120       using boost::get_pointer;\r
121       return node_ptr(const_cast<node*>(get_pointer(ptr)));\r
122    }\r
123 \r
124    //This is the root node of the circular list\r
125    node root;\r
126 \r
127    public:\r
128 \r
129    //!The bidirectional iterator of the container\r
130    class iterator\r
131       :  public detail::list_iterator<value_type, iterator, node_traits>\r
132    {\r
133       private:\r
134       // gcc warns about an ambiguity between iterator::value_type and\r
135       // ilist<ValueTraits>::value_type, thus I introduce a unique name:\r
136       typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::value_type  private_vt;\r
137       typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::pointer     private_pointer;\r
138       typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::reference   private_reference;\r
139       typedef detail::list_iterator<private_vt, iterator, node_traits>   inherited;\r
140 \r
141       public:\r
142       iterator()\r
143       {}\r
144 \r
145       private_pointer     operator->() const\r
146       { return  ValueTraits::to_value_ptr(this->list_node()); }\r
147 \r
148       private_reference   operator*() const\r
149       { return *ValueTraits::to_value_ptr(this->list_node()); }\r
150 \r
151       private:\r
152       explicit iterator(node_ptr node)\r
153          :  inherited (node)\r
154       {}\r
155       friend class ilist<ValueTraits, ConstantTimeSize, SizeType>;\r
156       friend class detail::list_iterator<private_vt, iterator, node_traits>;\r
157       friend class const_iterator;\r
158    };\r
159 \r
160    //!The bidirectional const_iterator of the container\r
161    class const_iterator\r
162       :  public detail::list_iterator<const value_type, const_iterator, node_traits>\r
163    {\r
164       private:\r
165       // gcc warns about an ambiguity between const_iterator::value_type and\r
166       // ilist<ValueTraits>::value_type, thus I introduce a unique name:\r
167       typedef const typename ilist<ValueTraits, ConstantTimeSize, SizeType>::value_type  private_vt;\r
168       typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::const_pointer     private_pointer;\r
169       typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::const_reference   private_reference;\r
170       typedef detail::list_iterator<private_vt, const_iterator, node_traits>   inherited;\r
171       \r
172       public: \r
173       const_iterator()\r
174       {}\r
175 \r
176       const_iterator(const typename ilist::iterator& it)\r
177          :  inherited (it.list_node())\r
178       {}\r
179 \r
180       const_iterator & operator=(const typename ilist::iterator& it)\r
181       {  return inherited::operator=(it.list_node());  }\r
182 \r
183       private_pointer   operator->() const\r
184       { return  ValueTraits::to_value_ptr(this->list_node()); }\r
185 \r
186       private_reference operator*() const\r
187       { return *ValueTraits::to_value_ptr(this->list_node()); }\r
188 \r
189       private:\r
190       explicit const_iterator(const_node_ptr node)\r
191          :  inherited (uncast(node))\r
192       {}\r
193       friend class ilist<ValueTraits, ConstantTimeSize, SizeType>;\r
194       friend class detail::list_iterator<private_vt, const_iterator, node_traits>;\r
195    };\r
196 \r
197    //!The bidirectional reverse iterator of the container\r
198    typedef std::reverse_iterator<iterator> reverse_iterator;\r
199 \r
200    //!The bidirectional const_reverse iterator of the container\r
201    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;\r
202 \r
203    public:\r
204 \r
205    //! <b>Effects</b>: constructs an empty list. \r
206    //! \r
207    //! <b>Complexity</b>: Constant \r
208    //! \r
209    //! <b>Throws</b>: If value_traits::node_traits::node\r
210    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks).\r
211    ilist()\r
212    {  \r
213       size_traits::set_size(size_type(0));\r
214       node_algorithms::init(node_ptr(&root));  \r
215    }\r
216 \r
217    //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.\r
218    //! \r
219    //! <b>Effects</b>: Constructs a list equal to the range [first,last).\r
220    //! \r
221    //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called.  \r
222    //! \r
223    //! <b>Throws</b>: If value_traits::node_traits::node\r
224    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks).\r
225    template<class Iterator>\r
226    ilist(Iterator b, Iterator e)\r
227    {\r
228       size_traits::set_size(size_type(0));\r
229       node_algorithms::init(node_ptr(&root));\r
230       this->insert(this->end(), b, e);\r
231    }\r
232 \r
233    //! <b>Effects</b>: If it's not a safe-mode or an auto-unlink value_type \r
234    //!   the destructor does nothing\r
235    //!   (ie. no code is generated). Otherwise it detaches all elements from this. \r
236    //!   In this case the objects in the list are not deleted (i.e. no destructors \r
237    //!   are called), but the hooks according to the ValueTraits template parameter\r
238    //!   are set to their default value.\r
239    //! \r
240    //! <b>Complexity</b>: Linear to the number of elements in the list, if \r
241    //!   it's a safe-mode or auto-unlink value . Otherwise constant. \r
242    ~ilist() \r
243    {\r
244       if(safemode_or_autounlink){\r
245          this->clear(); \r
246       }\r
247    }\r
248 \r
249    //! <b>Requires</b>: value must be an lvalue.\r
250    //! \r
251    //! <b>Effects</b>: Inserts the value in the back of the list.\r
252    //!   No copy constructors are called.\r
253    //! \r
254    //! <b>Throws</b>: Nothing.\r
255    //! \r
256    //! <b>Complexity</b>: Constant.\r
257    //! \r
258    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
259    void push_back(value_type &value) \r
260    {\r
261       node_ptr to_insert = ValueTraits::to_node_ptr(value);\r
262       if(safemode_or_autounlink)\r
263          BOOST_ASSERT(node_algorithms::unique(to_insert));\r
264       node_algorithms::link_before(node_ptr(&root), to_insert);\r
265       size_traits::increment();\r
266    }\r
267 \r
268    //! <b>Requires</b>: value must be an lvalue.\r
269    //! \r
270    //! <b>Effects</b>: Inserts the value in the front of the list.\r
271    //!   No copy constructors are called.\r
272    //! \r
273    //! <b>Throws</b>: Nothing.\r
274    //! \r
275    //! <b>Complexity</b>: Constant.\r
276    //! \r
277    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
278    void push_front(value_type &value) \r
279    {\r
280       node_ptr to_insert = ValueTraits::to_node_ptr(value);\r
281       if(safemode_or_autounlink)\r
282          BOOST_ASSERT(node_algorithms::unique(to_insert));\r
283       node_algorithms::link_before(node_traits::get_next(const_node_ptr(&root)), to_insert); \r
284       size_traits::increment();\r
285    }\r
286 \r
287    //! <b>Effects</b>: Erases the last element of the list.\r
288    //!   No destructors are called.\r
289    //! \r
290    //! <b>Throws</b>: Nothing.\r
291    //! \r
292    //! <b>Complexity</b>: Constant.\r
293    //! \r
294    //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element.\r
295    void pop_back() \r
296    {\r
297       node_ptr to_erase = node_traits::get_previous(const_node_ptr(&root));\r
298       node_algorithms::unlink(to_erase);\r
299       size_traits::decrement();\r
300       if(safemode_or_autounlink)\r
301          node_algorithms::init(to_erase);\r
302    }\r
303 \r
304    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
305    //!\r
306    //! <b>Effects</b>: Erases the last element of the list.\r
307    //!   No destructors are called.\r
308    //!   Destroyer::operator()(pointer) is called for the removed element.\r
309    //! \r
310    //! <b>Throws</b>: Nothing.\r
311    //! \r
312    //! <b>Complexity</b>: Constant.\r
313    //! \r
314    //! <b>Note</b>: Invalidates the iterators to the erased element.\r
315    template<class Destroyer>\r
316    void pop_back_and_destroy(Destroyer destroyer)\r
317    {\r
318       node_ptr to_erase = node_traits::get_previous(const_node_ptr(&root));\r
319       node_algorithms::unlink(to_erase);\r
320       size_traits::decrement();\r
321       if(safemode_or_autounlink)\r
322          node_algorithms::init(to_erase);\r
323       destroyer(ValueTraits::to_value_ptr(to_erase));\r
324    }\r
325 \r
326    //! <b>Effects</b>: Erases the first element of the list.\r
327    //!   No destructors are called.\r
328    //! \r
329    //! <b>Throws</b>: Nothing.\r
330    //! \r
331    //! <b>Complexity</b>: Constant.\r
332    //! \r
333    //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element.\r
334    void pop_front() \r
335    { \r
336       node_ptr to_erase = node_traits::get_next(const_node_ptr(&root));\r
337       node_algorithms::unlink(to_erase);\r
338       size_traits::decrement();\r
339       if(safemode_or_autounlink)\r
340          node_algorithms::init(to_erase);\r
341    }\r
342 \r
343    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
344    //!\r
345    //! <b>Effects</b>: Erases the first element of the list.\r
346    //!   No destructors are called.\r
347    //!   Destroyer::operator()(pointer) is called for the removed element.\r
348    //! \r
349    //! <b>Throws</b>: Nothing.\r
350    //! \r
351    //! <b>Complexity</b>: Constant.\r
352    //! \r
353    //! <b>Note</b>: Invalidates the iterators to the erased element.\r
354    template<class Destroyer>\r
355    void pop_front_and_destroy(Destroyer destroyer)\r
356    { \r
357       node_ptr to_erase = node_traits::get_next(const_node_ptr(&root));\r
358       node_algorithms::unlink(to_erase);\r
359       size_traits::decrement();\r
360       if(safemode_or_autounlink)\r
361          node_algorithms::init(to_erase);\r
362       destroyer(ValueTraits::to_value_ptr(to_erase));\r
363    }\r
364 \r
365    //! <b>Effects</b>: Returns a reference to the first element of the list.\r
366    //! \r
367    //! <b>Throws</b>: Nothing.\r
368    //! \r
369    //! <b>Complexity</b>: Constant.\r
370    reference front() \r
371    { return *ValueTraits::to_value_ptr(node_traits::get_next(const_node_ptr(&root))); }\r
372 \r
373    //! <b>Effects</b>: Returns a const_reference to the first element of the list.\r
374    //! \r
375    //! <b>Throws</b>: Nothing.\r
376    //! \r
377    //! <b>Complexity</b>: Constant.\r
378    const_reference front() const \r
379    { return *ValueTraits::to_value_ptr(uncast(node_traits::get_next(const_node_ptr(&root)))); }\r
380 \r
381    //! <b>Effects</b>: Returns a reference to the last element of the list.\r
382    //! \r
383    //! <b>Throws</b>: Nothing.\r
384    //! \r
385    //! <b>Complexity</b>: Constant.\r
386    reference back() \r
387    { return *ValueTraits::to_value_ptr(node_traits::get_previous(const_node_ptr(&root))); }\r
388 \r
389    //! <b>Effects</b>: Returns a const_reference to the last element of the list.\r
390    //! \r
391    //! <b>Throws</b>: Nothing.\r
392    //! \r
393    //! <b>Complexity</b>: Constant.\r
394    const_reference back() const \r
395    { return *ValueTraits::to_value_ptr(uncast(node_traits::get_previous(const_node_ptr(&root)))); }\r
396 \r
397    //! <b>Effects</b>: Returns an iterator to the first element contained in the list.\r
398    //! \r
399    //! <b>Throws</b>: Nothing.\r
400    //! \r
401    //! <b>Complexity</b>: Constant.\r
402    iterator begin() \r
403    { return iterator(node_traits::get_next(const_node_ptr(&root))); }\r
404 \r
405    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.\r
406    //! \r
407    //! <b>Throws</b>: Nothing.\r
408    //! \r
409    //! <b>Complexity</b>: Constant.\r
410    const_iterator begin() const \r
411    { return const_iterator(node_traits::get_next(const_node_ptr(&root))); }\r
412 \r
413    //! <b>Effects</b>: Returns an iterator to the end of the list.\r
414    //! \r
415    //! <b>Throws</b>: Nothing.\r
416    //! \r
417    //! <b>Complexity</b>: Constant.\r
418    iterator end() \r
419    { return iterator(node_ptr(&root)); }\r
420 \r
421    //! <b>Effects</b>: Returns a const_iterator to the end of the list.\r
422    //! \r
423    //! <b>Throws</b>: Nothing.\r
424    //! \r
425    //! <b>Complexity</b>: Constant.\r
426    const_iterator end() const \r
427    { return const_iterator(const_node_ptr(&root)); }\r
428 \r
429    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning \r
430    //! of the reversed list. \r
431    //! \r
432    //! <b>Throws</b>: Nothing.\r
433    //! \r
434    //! <b>Complexity</b>: Constant.\r
435    reverse_iterator rbegin()\r
436    { return reverse_iterator(end()); }\r
437 \r
438    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning \r
439    //! of the reversed list. \r
440    //! \r
441    //! <b>Throws</b>: Nothing.\r
442    //! \r
443    //! <b>Complexity</b>: Constant.\r
444    const_reverse_iterator rbegin() const \r
445    { return const_reverse_iterator(end()); }\r
446 \r
447    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end\r
448    //! of the reversed list. \r
449    //! \r
450    //! <b>Throws</b>: Nothing.\r
451    //! \r
452    //! <b>Complexity</b>: Constant.\r
453    reverse_iterator rend()      \r
454    { return reverse_iterator(begin()); }\r
455 \r
456    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end\r
457    //! of the reversed list. \r
458    //! \r
459    //! <b>Throws</b>: Nothing.\r
460    //! \r
461    //! <b>Complexity</b>: Constant.\r
462    const_reverse_iterator rend() const  \r
463    { return const_reverse_iterator(begin()); }\r
464 \r
465    //! <b>Effects</b>: Returns the number of the elements contained in the list.\r
466    //! \r
467    //! <b>Throws</b>: Nothing.\r
468    //! \r
469    //! <b>Complexity</b>: Linear to the number of elements contained in the list.\r
470    //!   if ConstantTimeSize is false. Constant time otherwise.\r
471    //! \r
472    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
473    size_type size() const\r
474    {\r
475       if(ConstantTimeSize)\r
476          return size_traits::get_size();\r
477       else\r
478          return node_algorithms::count(const_node_ptr(&root)) - 1; \r
479    }\r
480 \r
481    //! <b>Effects</b>: Returns true if the list contains no elements.\r
482    //! \r
483    //! <b>Throws</b>: Nothing.\r
484    //! \r
485    //! <b>Complexity</b>: Constant.\r
486    //! \r
487    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
488    bool empty() const\r
489    { return node_algorithms::unique(const_node_ptr(&root)); }\r
490 \r
491    //! <b>Effects</b>: Swaps the elements of x and *this.\r
492    //! \r
493    //! <b>Throws</b>: Nothing.\r
494    //! \r
495    //! <b>Complexity</b>: Constant.\r
496    //! \r
497    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
498    void swap(ilist& other)\r
499    {\r
500       node_algorithms::swap_nodes(node_ptr(&root), node_ptr(&other.root)); \r
501       if(ConstantTimeSize){\r
502          size_type backup = size_traits::get_size();\r
503          size_traits::set_size(other.get_size());\r
504          other.set_size(backup);\r
505       }\r
506    }\r
507 \r
508    //! <b>Effects</b>: Erases the element pointed by i of the list.\r
509    //!   No destructors are called.\r
510    //!\r
511    //! <b>Returns</b>: the first element remaining beyond the removed element,\r
512    //!   or end() if no such element exists.\r
513    //!\r
514    //! <b>Throws</b>: Nothing.\r
515    //! \r
516    //! <b>Complexity</b>: Constant.\r
517    //! \r
518    //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
519    //!   erased element.\r
520    iterator erase(iterator i)\r
521    {\r
522       iterator erase = i;\r
523       ++i;\r
524       node_ptr to_erase = erase.list_node();\r
525       node_algorithms::unlink(to_erase);\r
526       size_traits::decrement();\r
527       if(safemode_or_autounlink)\r
528          node_algorithms::init(to_erase);\r
529       return i;\r
530    }\r
531 \r
532    //! <b>Requires</b>: first and last must be valid iterator to elements in *this.\r
533    //!\r
534    //! <b>Effects</b>: Erases the element range pointed by b and e\r
535    //! No destructors are called.\r
536    //!\r
537    //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
538    //!   or end() if no such element exists.\r
539    //! \r
540    //! <b>Throws</b>: Nothing.\r
541    //! \r
542    //! <b>Complexity</b>: Linear to the number of elements erased if it's a safe-mode\r
543    //!   or auto-unlink value. Constant time otherwise.\r
544    //! \r
545    //! <b>Note</b>: Invalidates the iterators (but not the references) to the \r
546    //!   erased elements.\r
547    iterator erase(iterator b, iterator e)\r
548    {\r
549       if(safemode_or_autounlink || ConstantTimeSize){\r
550          while(b != e){\r
551             b = this->erase(b);\r
552          }\r
553          return b;\r
554       }\r
555       else{\r
556          node_algorithms::unlink(b.list_node(), e.list_node());\r
557          return e;\r
558       }\r
559    }\r
560 \r
561    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
562    //!\r
563    //! <b>Effects</b>: Erases the element pointed by i of the list.\r
564    //!   No destructors are called.\r
565    //!   Destroyer::operator()(pointer) is called for the removed element.\r
566    //!\r
567    //! <b>Returns</b>: the first element remaining beyond the removed element,\r
568    //!   or end() if no such element exists.\r
569    //!\r
570    //! <b>Throws</b>: Nothing.\r
571    //! \r
572    //! <b>Complexity</b>: Constant.\r
573    //! \r
574    //! <b>Note</b>: Invalidates the iterators to the erased element.\r
575    template <class Destroyer>\r
576    iterator erase_and_destroy(iterator i, Destroyer destroyer)\r
577    {\r
578       iterator erase = i;\r
579       ++i;\r
580       node_ptr to_erase = erase.list_node();\r
581       node_algorithms::unlink(to_erase);\r
582       size_traits::decrement();\r
583       if(safemode_or_autounlink)\r
584          node_algorithms::init(to_erase);\r
585       destroyer(ValueTraits::to_value_ptr(to_erase));\r
586       return i;\r
587    }\r
588 \r
589    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
590    //!\r
591    //! <b>Effects</b>: Erases the element range pointed by b and e\r
592    //!   No destructors are called.\r
593    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
594    //!\r
595    //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
596    //!   or end() if no such element exists.\r
597    //! \r
598    //! <b>Throws</b>: Nothing.\r
599    //! \r
600    //! <b>Complexity</b>: Linear to the number of elements erased.\r
601    //! \r
602    //! <b>Note</b>: Invalidates the iterators to the erased elements.\r
603    template <class Destroyer>\r
604    iterator erase_and_destroy(iterator b, iterator e, Destroyer destroyer)\r
605    {\r
606       while(b != e){\r
607          b = this->erase_and_destroy(b, destroyer);\r
608       }\r
609       return b;\r
610    }\r
611 \r
612    //! <b>Effects</b>: Erases all the elements of the container.\r
613    //!   No destructors are called.\r
614    //! \r
615    //! <b>Throws</b>: Nothing.\r
616    //! \r
617    //! <b>Complexity</b>: Linear to the number of elements of the list.\r
618    //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.\r
619    //! \r
620    //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements.\r
621    void clear()\r
622    {\r
623       if(safemode_or_autounlink){\r
624          this->erase(this->begin(), this->end()); \r
625       }\r
626       else{\r
627          node_algorithms::init(node_ptr(&root));\r
628          size_traits::set_size(size_type(0));\r
629       }\r
630    }\r
631 \r
632    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
633    //!\r
634    //! <b>Effects</b>: Erases all the elements of the container.\r
635    //!   No destructors are called.\r
636    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
637    //! \r
638    //! <b>Throws</b>: Nothing.\r
639    //! \r
640    //! <b>Complexity</b>: Linear to the number of elements of the list.\r
641    //! \r
642    //! <b>Note</b>: Invalidates the iterators to the erased elements.\r
643    template <class Destroyer>\r
644    void clear_and_destroy(Destroyer destroyer)\r
645    {  this->erase_and_destroy(this->begin(), this->end(), destroyer);   }\r
646 \r
647    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
648    //!\r
649    //! <b>Effects</b>: Erases all the elements from *this\r
650    //!   calling Destroyer::operator()(pointer), clones all the \r
651    //!   elements from src calling Cloner::operator()(const value_type &)\r
652    //!   and inserts them on *this.\r
653    //!\r
654    //!   If cloner throws, all cloned elements are unlinked and destroyed\r
655    //!   calling Destroyer::operator()(pointer).\r
656    //!   \r
657    //! <b>Complexity</b>: Linear to erased plus inserted elements.\r
658    //! \r
659    //! <b>Throws</b>: If cloner throws. Basic guarantee.\r
660    template <class Cloner, class Destroyer>\r
661    void clone_from(const ilist &src, Cloner cloner, Destroyer destroyer)\r
662    {\r
663       this->clear_and_destroy(destroyer);\r
664       try{\r
665          const_iterator b(src.begin()), e(src.end());\r
666          for(; b != e; ++b){\r
667             this->push_back(*cloner(*b));\r
668          }\r
669       }\r
670       catch(...){\r
671          clear_and_destroy(destroyer);\r
672          throw;\r
673       }\r
674    }\r
675 \r
676    //! <b>Requires</b>: value must be an lvalue and p must be a valid iterator of *this.\r
677    //!\r
678    //! <b>Effects</b>: Inserts the value before the position pointed by p.\r
679    //!\r
680    //! <b>Returns</b>: An iterator to the inserted element.\r
681    //! \r
682    //! <b>Throws</b>: Nothing.\r
683    //! \r
684    //! <b>Complexity</b>: Constant time. No copy constructors are called.\r
685    //! \r
686    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
687    iterator insert(iterator p, value_type &value)\r
688    {\r
689       node_ptr to_insert = ValueTraits::to_node_ptr(value);\r
690       if(safemode_or_autounlink)\r
691          BOOST_ASSERT(node_algorithms::unique(to_insert));\r
692       node_algorithms::link_before(p.list_node(), to_insert);\r
693       size_traits::increment();\r
694       return iterator(to_insert);\r
695    }\r
696 \r
697    //! <b>Requires</b>: Dereferencing iterator must yield \r
698    //!   an lvalue of type value_type and p must be a valid iterator of *this.\r
699    //! \r
700    //! <b>Effects</b>: Inserts the range pointed by b and e before the position p.\r
701    //!   No copy constructors are called.\r
702    //! \r
703    //! <b>Throws</b>: Nothing.\r
704    //! \r
705    //! <b>Complexity</b>: Linear to the number of elements inserted.\r
706    //! \r
707    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
708    template<class Iterator>\r
709    void insert(iterator p, Iterator b, Iterator e)\r
710    {\r
711       for (; b != e; ++b)\r
712          this->insert(p, *b);\r
713    }\r
714 \r
715    //! <b>Requires</b>: Dereferencing iterator must yield \r
716    //!   an lvalue of type value_type.\r
717    //! \r
718    //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.\r
719    //!   No destructors or copy constructors are called.\r
720    //! \r
721    //! <b>Throws</b>: Nothing.\r
722    //! \r
723    //! <b>Complexity</b>: Linear to the number of elements inserted plus\r
724    //!   linear to the elements contained in the list if it's a safe-mode\r
725    //!   or auto-unlink value.\r
726    //!   Linear to the number of elements inserted in the list otherwise.\r
727    //! \r
728    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
729    //!   to the erased elements.\r
730    template<class Iterator>\r
731    void assign(Iterator b, Iterator e)\r
732    {\r
733       this->clear();\r
734       this->insert(this->end(), b, e);\r
735    }\r
736 \r
737    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
738    //!\r
739    //! <b>Requires</b>: Dereferencing iterator must yield \r
740    //!   an lvalue of type value_type.\r
741    //! \r
742    //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.\r
743    //!   No destructors or copy constructors are called.\r
744    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
745    //! \r
746    //! <b>Throws</b>: Nothing.\r
747    //! \r
748    //! <b>Complexity</b>: Linear to the number of elements inserted plus\r
749    //!   linear to the elements contained in the list.\r
750    //! \r
751    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
752    //!   to the erased elements.\r
753    template<class Iterator, class Destroyer>\r
754    void assign_and_destroy(Iterator b, Iterator e, Destroyer destroyer)\r
755    {\r
756       this->clear(destroyer);\r
757       this->insert(this->end(), b, e);\r
758    }\r
759 \r
760    //! <b>Requires</b>: p must be a valid iterator of *this.\r
761    //!\r
762    //! <b>Effects</b>: Transfers all the elements of list x to this list, before the\r
763    //!   the element pointed by p. No destructors or copy constructors are called.\r
764    //!\r
765    //! <b>Throws</b>: Nothing.\r
766    //!\r
767    //! <b>Complexity</b>: Constant.\r
768    //! \r
769    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of\r
770    //!    this list. Iterators of this list and all the references are not invalidated.\r
771    void splice(iterator p, ilist& x)\r
772    {\r
773       if(!x.empty()){\r
774          node_algorithms::transfer\r
775             (p.list_node(), x.begin().list_node(), x.end().list_node());\r
776          size_traits::set_size(size_traits::get_size() + x.get_size());\r
777          x.set_size(size_type(0));\r
778       }\r
779    }\r
780 \r
781    //! <b>Requires</b>: p must be a valid iterator of *this.\r
782    //!   new_ele must point to an element contained in list x.\r
783    //! \r
784    //! <b>Effects</b>: Transfers the value pointed by new_ele, from list x to this list, \r
785    //!   before the the element pointed by p. No destructors or copy constructors are called.\r
786    //!   If p == new_ele or p == ++new_ele, this function is a null operation. \r
787    //! \r
788    //! <b>Throws</b>: Nothing.\r
789    //! \r
790    //! <b>Complexity</b>: Constant.\r
791    //! \r
792    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
793    //!   list. Iterators of this list and all the references are not invalidated.\r
794    void splice(iterator p, ilist&x, iterator new_ele)\r
795    {\r
796       node_algorithms::transfer(p.list_node(), new_ele.list_node());\r
797       x.decrement();\r
798       size_traits::increment();\r
799    }\r
800 \r
801    //! <b>Requires</b>: p must be a valid iterator of *this.\r
802    //!   start and end must point to elements contained in list x.\r
803    //! \r
804    //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, \r
805    //!   before the the element pointed by p. No destructors or copy constructors are called.\r
806    //! \r
807    //! <b>Throws</b>: Nothing.\r
808    //! \r
809    //! <b>Complexity</b>: Linear to the number of elements transferred\r
810    //!   if ConstantTimeSize is true. Constant-time otherwise.\r
811    //! \r
812    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
813    //!   list. Iterators of this list and all the references are not invalidated.\r
814    void splice(iterator p, ilist&x, iterator start, iterator end)\r
815    {\r
816       if(start != end){\r
817          if(ConstantTimeSize){\r
818             size_type increment = std::distance(start, end);\r
819             node_algorithms::transfer(p.list_node(), start.list_node(), end.list_node());\r
820             size_traits::set_size(size_traits::get_size() + increment);\r
821             x.set_size(x.get_size() - increment);\r
822          }\r
823          else{\r
824             node_algorithms::transfer(p.list_node(), start.list_node(), end.list_node());\r
825          }\r
826       }\r
827    }\r
828 \r
829    //! <b>Requires</b>: p must be a valid iterator of *this.\r
830    //!   start and end must point to elements contained in list x.\r
831    //!   n == std::distance(start, end)\r
832    //! \r
833    //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, \r
834    //!   before the the element pointed by p. No destructors or copy constructors are called.\r
835    //! \r
836    //! <b>Throws</b>: Nothing.\r
837    //! \r
838    //! <b>Complexity</b>: Constant.\r
839    //! \r
840    //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
841    //!   list. Iterators of this list and all the references are not invalidated.\r
842    void splice(iterator p, ilist&x, iterator start, iterator end, difference_type n)\r
843    {\r
844       if(n){\r
845          if(ConstantTimeSize){\r
846             BOOST_ASSERT(n == std::distance(start, end));\r
847             node_algorithms::transfer(p.list_node(), start.list_node(), end.list_node());\r
848             size_traits::set_size(size_traits::get_size() + n);\r
849             x.set_size(x.get_size() - n);\r
850          }\r
851          else{\r
852             node_algorithms::transfer(p.list_node(), start.list_node(), end.list_node());\r
853          }\r
854       }\r
855    }\r
856 \r
857    //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. \r
858    //!   The sort is stable, that is, the relative order of equivalent elements is preserved.\r
859    //! \r
860    //! <b>Throws</b>: If value_traits::node_traits::node\r
861    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
862    //!   or std::less<value_type> throws. Basic guarantee.\r
863    //!\r
864    //! <b>Notes</b>: Iterators and references are not invalidated.\r
865    //! \r
866    //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N\r
867    //!   is the list's size.\r
868    void sort() \r
869    {  sort(std::less<value_type>());  }\r
870 \r
871    //! <b>Requires</b>: p must be a comparison function that induces a strict weak ordering\r
872    //! \r
873    //! <b>Effects</b>: This function sorts the list *this according to p. The sort is \r
874    //!   stable, that is, the relative order of equivalent elements is preserved.\r
875    //! \r
876    //! <b>Throws</b>: If value_traits::node_traits::node\r
877    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
878    //!   or the predicate throws. Basic guarantee.\r
879    //!\r
880    //! <b>Notes</b>: This won't throw if ilist_base_hook<>::value_traits or\r
881    //!   ilist_member_hook::::value_traits are used as value traits.\r
882    //!   Iterators and references are not invalidated.\r
883    //! \r
884    //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N\r
885    //!   is the list's size.\r
886    template<class Predicate>\r
887    void sort(Predicate p)\r
888    {\r
889       if(node_traits::get_next(const_node_ptr(&root)) \r
890          != node_traits::get_previous(const_node_ptr(&root))){\r
891          ilist carry;\r
892          ilist counter[64];\r
893          int fill = 0;\r
894          while(!this->empty()){\r
895             carry.splice(carry.begin(), *this, this->begin());\r
896             int i = 0;\r
897             while(i < fill && !counter[i].empty()) {\r
898                carry.merge(counter[i++], p);\r
899             }\r
900             carry.swap(counter[i]);\r
901             if(i == fill)\r
902                ++fill;\r
903          }\r
904          for (int i = 1; i < fill; ++i)\r
905             counter[i].merge(counter[i-1], p);\r
906          this->swap(counter[fill-1]);\r
907       }\r
908    }\r
909 \r
910    //! <b>Effects</b>: This function removes all of x's elements and inserts them\r
911    //!   in order into *this according to std::less<value_type>. The merge is stable; \r
912    //!   that is, if an element from *this is equivalent to one from x, then the element \r
913    //!   from *this will precede the one from x. \r
914    //! \r
915    //! <b>Throws</b>: If std::less<value_type> throws. Basic guarantee.\r
916    //! \r
917    //! <b>Complexity</b>: This function is linear time: it performs at most\r
918    //!   size() + x.size() - 1 comparisons.\r
919    //! \r
920    //! <b>Note</b>: Iterators and references are not invalidated\r
921    void merge(ilist& x)\r
922    { merge(x, std::less<value_type>()); }\r
923 \r
924    //! <b>Requires</b>: p must be a comparison function that induces a strict weak\r
925    //!   ordering and both *this and x must be sorted according to that ordering\r
926    //!   The lists x and *this must be distinct. \r
927    //! \r
928    //! <b>Effects</b>: This function removes all of x's elements and inserts them\r
929    //!   in order into *this. The merge is stable; that is, if an element from *this is \r
930    //!   equivalent to one from x, then the element from *this will precede the one from x. \r
931    //! \r
932    //! <b>Throws</b>: If the predicate throws. Basic guarantee.\r
933    //! \r
934    //! <b>Complexity</b>: This function is linear time: it performs at most\r
935    //!   size() + x.size() - 1 comparisons.\r
936    //! \r
937    //! <b>Note</b>: Iterators and references are not invalidated.\r
938    template<class Predicate>\r
939    void merge(ilist& x, Predicate p)\r
940    {\r
941       iterator e = this->end();\r
942       iterator bx = x.begin();\r
943       iterator ex = x.end();\r
944 \r
945       for (iterator b = this->begin(); b != e; ++b) {\r
946          size_type n(0);\r
947          iterator ix(bx);\r
948          while(ix != ex && p(*ix, *b)){\r
949             ++ix; ++n;\r
950          }\r
951          this->splice(b, x, bx, ix, n);\r
952          bx = ix;\r
953       }\r
954       //Now transfer the rest at the end of the container\r
955       this->splice(e, x);\r
956    }\r
957 \r
958    //! <b>Effects</b>: Reverses the order of elements in the list. \r
959    //! \r
960    //! <b>Throws</b>: Nothing.\r
961    //! \r
962    //! <b>Complexity</b>: This function is linear time.\r
963    //! \r
964    //! <b>Note</b>: Iterators and references are not invalidated\r
965    void reverse()\r
966    {  node_algorithms::reverse(node_ptr(&root));   }\r
967 \r
968    //! <b>Effects</b>: Removes all the elements that compare equal to value.\r
969    //!   No destructors are called.\r
970    //! \r
971    //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
972    //! \r
973    //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.\r
974    //! \r
975    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
976    //!   and iterators to elements that are not removed remain valid.\r
977    void remove(const value_type &value)\r
978    {  remove_if(equal_to_value(value));  }\r
979 \r
980    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
981    //!\r
982    //! <b>Effects</b>: Removes all the elements that compare equal to value.\r
983    //!   Destroyer::operator()(pointer) is called for every removed element.\r
984    //!\r
985    //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
986    //! \r
987    //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.\r
988    //! \r
989    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
990    //!   and iterators to elements that are not removed remain valid.\r
991    template<class Destroyer>\r
992    void remove_and_destroy(const value_type &value, Destroyer destroyer)\r
993    {  remove_and_destroy_if(equal_to_value(value), destroyer);  }\r
994 \r
995    //! <b>Effects</b>: Removes all the elements for which a specified\r
996    //!   predicate is satisfied. No destructors are called.\r
997    //! \r
998    //! <b>Throws</b>: If pred throws. Basic guarantee.\r
999    //! \r
1000    //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.\r
1001    //! \r
1002    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1003    //!   and iterators to elements that are not removed remain valid.\r
1004    template<class Pred>\r
1005    void remove_if(Pred pred)\r
1006    {  remove_and_destroy_if(pred, detail::null_destroyer());   }\r
1007 \r
1008    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1009    //!\r
1010    //! <b>Effects</b>: Removes all the elements for which a specified\r
1011    //!   predicate is satisfied.\r
1012    //!   Destroyer::operator()(pointer) is called for every removed element.\r
1013    //!\r
1014    //! <b>Throws</b>: If pred throws. Basic guarantee.\r
1015    //! \r
1016    //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.\r
1017    //!\r
1018    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1019    //!   and iterators to elements that are not removed remain valid.\r
1020    template<class Pred, class Destroyer>\r
1021    void remove_and_destroy_if(Pred pred, Destroyer destroyer)\r
1022    {\r
1023       iterator first = begin();\r
1024       iterator last = end();\r
1025       while(first != last) {\r
1026          iterator next = first;\r
1027          ++next;\r
1028          if(pred(*first)){\r
1029             pointer p = first.operator->();\r
1030             this->erase(first);\r
1031             destroyer(p);\r
1032          }\r
1033          first = next;\r
1034       }\r
1035    }\r
1036 \r
1037    //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
1038    //!   elements that are equal from the list. No destructors are called.\r
1039    //! \r
1040    //! <b>Throws</b>: If std::equal_to<value_type throws. Basic guarantee.\r
1041    //! \r
1042    //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()).\r
1043    //! \r
1044    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1045    //!   and iterators to elements that are not removed remain valid.\r
1046    void unique()\r
1047    {  unique_and_destroy(std::equal_to<value_type>(), detail::null_destroyer());  }\r
1048 \r
1049    //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
1050    //!   elements that satisfy some binary predicate from the list.\r
1051    //!   No destructors are called.\r
1052    //! \r
1053    //! <b>Throws</b>: If pred throws. Basic guarantee.\r
1054    //! \r
1055    //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons).\r
1056    //! \r
1057    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1058    //!   and iterators to elements that are not removed remain valid.\r
1059    template<class BinaryPredicate>\r
1060    void unique(BinaryPredicate pred)\r
1061    {  unique_and_destroy(pred, detail::null_destroyer());  }\r
1062 \r
1063    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1064    //!\r
1065    //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
1066    //!   elements that are equal from the list.\r
1067    //!   Destroyer::operator()(pointer) is called for every removed element.\r
1068    //! \r
1069    //! <b>Throws</b>: If std::equal_to<value_type throws. Basic guarantee.\r
1070    //! \r
1071    //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.\r
1072    //! \r
1073    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1074    //!   and iterators to elements that are not removed remain valid.\r
1075    template<class Destroyer>\r
1076    void unique_and_destroy(Destroyer destroyer)\r
1077    {  unique_and_destroy(std::equal_to<value_type>(), destroyer);  }\r
1078 \r
1079    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1080    //!\r
1081    //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
1082    //!   elements that satisfy some binary predicate from the list.\r
1083    //!   Destroyer::operator()(pointer) is called for every removed element.\r
1084    //! \r
1085    //! <b>Throws</b>: If pred throws. Basic guarantee.\r
1086    //! \r
1087    //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.\r
1088    //! \r
1089    //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
1090    //!   and iterators to elements that are not removed remain valid.\r
1091    template<class BinaryPredicate, class Destroyer>\r
1092    void unique_and_destroy(BinaryPredicate pred, Destroyer destroyer)\r
1093    {\r
1094                 if(!this->empty()){\r
1095                         iterator first = begin();\r
1096                         iterator after = first;\r
1097          ++after;\r
1098                         while(after != this->end()){\r
1099             if(pred(*first, *after)){\r
1100                pointer p = after.operator->();\r
1101                after = erase(after);\r
1102                destroyer(p);\r
1103             }\r
1104                                 else{\r
1105                                         first = after++;\r
1106             }\r
1107          }\r
1108       }\r
1109    }\r
1110 \r
1111    //! <b>Requires</b>: value must be a reference to a value inserted in a list.\r
1112    //! \r
1113    //! <b>Effects</b>: This function returns a const_iterator pointing to the element\r
1114    //! \r
1115    //! <b>Throws</b>: Nothing.\r
1116    //! \r
1117    //! <b>Complexity</b>: Constant time.\r
1118    //! \r
1119    //! <b>Note</b>: Iterators and references are not invalidated.\r
1120    static iterator current(value_type &value)\r
1121    { \r
1122       BOOST_ASSERT(!node_algorithms::unique(ValueTraits::to_node_ptr(value)));\r
1123       return iterator(ValueTraits::to_node_ptr(value)); \r
1124    }\r
1125 \r
1126    //! <b>Requires</b>: value must be a const reference to a value inserted in a list.\r
1127    //! \r
1128    //! <b>Effects</b>: This function returns an iterator pointing to the element.\r
1129    //! \r
1130    //! <b>Throws</b>: Nothing.\r
1131    //! \r
1132    //! <b>Complexity</b>: Constant time.\r
1133    //! \r
1134    //! <b>Note</b>: Iterators and references are not invalidated.\r
1135    static const_iterator current(const value_type &value) \r
1136    { \r
1137       BOOST_ASSERT(!node_algorithms::unique(ValueTraits::to_node_ptr(const_cast<value_type&> (value))));\r
1138       return const_iterator(ValueTraits::to_node_ptr(const_cast<value_type&> (value))); \r
1139    }\r
1140 };\r
1141 \r
1142 template <class V, bool C, class S>\r
1143 inline bool operator==(const ilist<V, C, S>& x, const ilist<V, C, S>& y)\r
1144 {\r
1145    if(C && x.size() != y.size()){\r
1146       return false;\r
1147    }\r
1148    typedef typename ilist<V, C, S>::const_iterator const_iterator;\r
1149    const_iterator end1 = x.end();\r
1150 \r
1151    const_iterator i1 = x.begin();\r
1152    const_iterator i2 = y.begin();\r
1153    if(C){\r
1154       while (i1 != end1 && *i1 == *i2) {\r
1155          ++i1;\r
1156          ++i2;\r
1157       }\r
1158       return i1 == end1;\r
1159    }\r
1160    else{\r
1161       const_iterator end2 = y.end();\r
1162       while (i1 != end1 && i2 != end2 && *i1 == *i2) {\r
1163          ++i1;\r
1164          ++i2;\r
1165       }\r
1166       return i1 == end1 && i2 == end2;\r
1167    }\r
1168 }\r
1169 \r
1170 template <class V, bool C, class S>\r
1171 inline bool operator<(const ilist<V, C, S>& x,\r
1172                       const ilist<V, C, S>& y)\r
1173 {  return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());  }\r
1174 \r
1175 template <class V, bool C, class S>\r
1176 inline bool operator!=(const ilist<V, C, S>& x, const ilist<V, C, S>& y) \r
1177 {  return !(x == y); }\r
1178 \r
1179 template <class V, bool C, class S>\r
1180 inline bool operator>(const ilist<V, C, S>& x, const ilist<V, C, S>& y) \r
1181 {  return y < x;  }\r
1182 \r
1183 template <class V, bool C, class S>\r
1184 inline bool operator<=(const ilist<V, C, S>& x, const ilist<V, C, S>& y) \r
1185 {  return !(y < x);  }\r
1186 \r
1187 template <class V, bool C, class S>\r
1188 inline bool operator>=(const ilist<V, C, S>& x, const ilist<V, C, S>& y) \r
1189 {  return !(x < y);  }\r
1190 \r
1191 template <class V, bool C, class S>\r
1192 inline void swap(ilist<V, C, S>& x, ilist<V, C, S>& y)\r
1193 {  x.swap(y);  }\r
1194 \r
1195 } //namespace intrusive \r
1196 } //namespace boost \r
1197 \r
1198 #include "detail/config_end.hpp"\r
1199 \r
1200 #endif //BOOST_INTRUSIVE_ILIST_HPP\r