senf/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