stl_list.h

Go to the documentation of this file.
00001 // List implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1996,1997
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00056 /** @file stl_list.h
00057  *  This is an internal header file, included by other library headers.
00058  *  You should not attempt to use it directly.
00059  */
00060 
00061 #ifndef _LIST_H
00062 #define _LIST_H 1
00063 
00064 #include <bits/concept_check.h>
00065 
00066 namespace _GLIBCXX_STD
00067 {
00068   // Supporting structures are split into common and templated types; the
00069   // latter publicly inherits from the former in an effort to reduce code
00070   // duplication.  This results in some "needless" static_cast'ing later on,
00071   // but it's all safe downcasting.
00072 
00073   /// @if maint Common part of a node in the %list.  @endif
00074   struct _List_node_base
00075   {
00076     _List_node_base* _M_next;   ///< Self-explanatory
00077     _List_node_base* _M_prev;   ///< Self-explanatory
00078 
00079     static void
00080     swap(_List_node_base& __x, _List_node_base& __y);
00081 
00082     void
00083     transfer(_List_node_base * const __first,
00084          _List_node_base * const __last);
00085 
00086     void
00087     reverse();
00088 
00089     void
00090     hook(_List_node_base * const __position);
00091 
00092     void
00093     unhook();
00094   };
00095 
00096   /// @if maint An actual node in the %list.  @endif
00097   template<typename _Tp>
00098     struct _List_node : public _List_node_base
00099     {
00100       _Tp _M_data;                ///< User's data.
00101     };
00102 
00103   /**
00104    *  @brief A list::iterator.
00105    *
00106    *  @if maint
00107    *  All the functions are op overloads.
00108    *  @endif
00109   */
00110   template<typename _Tp>
00111     struct _List_iterator
00112     {
00113       typedef _List_iterator<_Tp>                _Self;
00114       typedef _List_node<_Tp>                    _Node;
00115 
00116       typedef ptrdiff_t                          difference_type;
00117       typedef std::bidirectional_iterator_tag    iterator_category;
00118       typedef _Tp                                value_type;
00119       typedef _Tp*                               pointer;
00120       typedef _Tp&                               reference;
00121 
00122       _List_iterator()
00123       : _M_node() { }
00124 
00125       explicit
00126       _List_iterator(_List_node_base* __x)
00127       : _M_node(__x) { }
00128 
00129       // Must downcast from List_node_base to _List_node to get to _M_data.
00130       reference
00131       operator*() const
00132       { return static_cast<_Node*>(_M_node)->_M_data; }
00133 
00134       pointer
00135       operator->() const
00136       { return &static_cast<_Node*>(_M_node)->_M_data; }
00137 
00138       _Self&
00139       operator++()
00140       {
00141     _M_node = _M_node->_M_next;
00142     return *this;
00143       }
00144 
00145       _Self
00146       operator++(int)
00147       {
00148     _Self __tmp = *this;
00149     _M_node = _M_node->_M_next;
00150     return __tmp;
00151       }
00152 
00153       _Self&
00154       operator--()
00155       {
00156     _M_node = _M_node->_M_prev;
00157     return *this;
00158       }
00159 
00160       _Self
00161       operator--(int)
00162       {
00163     _Self __tmp = *this;
00164     _M_node = _M_node->_M_prev;
00165     return __tmp;
00166       }
00167 
00168       bool
00169       operator==(const _Self& __x) const
00170       { return _M_node == __x._M_node; }
00171 
00172       bool
00173       operator!=(const _Self& __x) const
00174       { return _M_node != __x._M_node; }
00175 
00176       // The only member points to the %list element.
00177       _List_node_base* _M_node;
00178     };
00179 
00180   /**
00181    *  @brief A list::const_iterator.
00182    *
00183    *  @if maint
00184    *  All the functions are op overloads.
00185    *  @endif
00186   */
00187   template<typename _Tp>
00188     struct _List_const_iterator
00189     {
00190       typedef _List_const_iterator<_Tp>          _Self;
00191       typedef const _List_node<_Tp>              _Node;
00192       typedef _List_iterator<_Tp>                iterator;
00193 
00194       typedef ptrdiff_t                          difference_type;
00195       typedef std::bidirectional_iterator_tag    iterator_category;
00196       typedef _Tp                                value_type;
00197       typedef const _Tp*                         pointer;
00198       typedef const _Tp&                         reference;
00199 
00200       _List_const_iterator()
00201       : _M_node() { }
00202 
00203       explicit
00204       _List_const_iterator(const _List_node_base* __x)
00205       : _M_node(__x) { }
00206 
00207       _List_const_iterator(const iterator& __x)
00208       : _M_node(__x._M_node) { }
00209 
00210       // Must downcast from List_node_base to _List_node to get to
00211       // _M_data.
00212       reference
00213       operator*() const
00214       { return static_cast<_Node*>(_M_node)->_M_data; }
00215 
00216       pointer
00217       operator->() const
00218       { return &static_cast<_Node*>(_M_node)->_M_data; }
00219 
00220       _Self&
00221       operator++()
00222       {
00223     _M_node = _M_node->_M_next;
00224     return *this;
00225       }
00226 
00227       _Self
00228       operator++(int)
00229       {
00230     _Self __tmp = *this;
00231     _M_node = _M_node->_M_next;
00232     return __tmp;
00233       }
00234 
00235       _Self&
00236       operator--()
00237       {
00238     _M_node = _M_node->_M_prev;
00239     return *this;
00240       }
00241 
00242       _Self
00243       operator--(int)
00244       {
00245     _Self __tmp = *this;
00246     _M_node = _M_node->_M_prev;
00247     return __tmp;
00248       }
00249 
00250       bool
00251       operator==(const _Self& __x) const
00252       { return _M_node == __x._M_node; }
00253 
00254       bool
00255       operator!=(const _Self& __x) const
00256       { return _M_node != __x._M_node; }
00257 
00258       // The only member points to the %list element.
00259       const _List_node_base* _M_node;
00260     };
00261 
00262   template<typename _Val>
00263     inline bool
00264     operator==(const _List_iterator<_Val>& __x,
00265            const _List_const_iterator<_Val>& __y)
00266     { return __x._M_node == __y._M_node; }
00267 
00268   template<typename _Val>
00269     inline bool
00270     operator!=(const _List_iterator<_Val>& __x,
00271                const _List_const_iterator<_Val>& __y)
00272     { return __x._M_node != __y._M_node; }
00273 
00274 
00275   /**
00276    *  @if maint
00277    *  See bits/stl_deque.h's _Deque_base for an explanation.
00278    *  @endif
00279   */
00280   template<typename _Tp, typename _Alloc>
00281     class _List_base
00282     {
00283     protected:
00284       // NOTA BENE
00285       // The stored instance is not actually of "allocator_type"'s
00286       // type.  Instead we rebind the type to
00287       // Allocator<List_node<Tp>>, which according to [20.1.5]/4
00288       // should probably be the same.  List_node<Tp> is not the same
00289       // size as Tp (it's two pointers larger), and specializations on
00290       // Tp may go unused because List_node<Tp> is being bound
00291       // instead.
00292       //
00293       // We put this to the test in the constructors and in
00294       // get_allocator, where we use conversions between
00295       // allocator_type and _Node_alloc_type. The conversion is
00296       // required by table 32 in [20.1.5].
00297       typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
00298         _Node_alloc_type;
00299 
00300       typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
00301 
00302       struct _List_impl 
00303       : public _Node_alloc_type
00304       {
00305     _List_node_base _M_node;
00306 
00307     _List_impl(const _Node_alloc_type& __a)
00308     : _Node_alloc_type(__a), _M_node()
00309     { }
00310       };
00311 
00312       _List_impl _M_impl;
00313 
00314       _List_node<_Tp>*
00315       _M_get_node()
00316       { return _M_impl._Node_alloc_type::allocate(1); }
00317       
00318       void
00319       _M_put_node(_List_node<_Tp>* __p)
00320       { _M_impl._Node_alloc_type::deallocate(__p, 1); }
00321       
00322   public:
00323       typedef _Alloc allocator_type;
00324 
00325       _Tp_alloc_type
00326       _M_get_Tp_allocator() const
00327       { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
00328 
00329       allocator_type
00330       get_allocator() const
00331       { return _M_get_Tp_allocator(); }
00332 
00333       _List_base(const allocator_type& __a)
00334       : _M_impl(__a)
00335       { _M_init(); }
00336 
00337       // This is what actually destroys the list.
00338       ~_List_base()
00339       { _M_clear(); }
00340 
00341       void
00342       _M_clear();
00343 
00344       void
00345       _M_init()
00346       {
00347         this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
00348         this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
00349       }
00350     };
00351 
00352   /**
00353    *  @brief A standard container with linear time access to elements,
00354    *  and fixed time insertion/deletion at any point in the sequence.
00355    *
00356    *  @ingroup Containers
00357    *  @ingroup Sequences
00358    *
00359    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00360    *  <a href="tables.html#66">reversible container</a>, and a
00361    *  <a href="tables.html#67">sequence</a>, including the
00362    *  <a href="tables.html#68">optional sequence requirements</a> with the
00363    *  %exception of @c at and @c operator[].
00364    *
00365    *  This is a @e doubly @e linked %list.  Traversal up and down the
00366    *  %list requires linear time, but adding and removing elements (or
00367    *  @e nodes) is done in constant time, regardless of where the
00368    *  change takes place.  Unlike std::vector and std::deque,
00369    *  random-access iterators are not provided, so subscripting ( @c
00370    *  [] ) access is not allowed.  For algorithms which only need
00371    *  sequential access, this lack makes no difference.
00372    *
00373    *  Also unlike the other standard containers, std::list provides
00374    *  specialized algorithms %unique to linked lists, such as
00375    *  splicing, sorting, and in-place reversal.
00376    *
00377    *  @if maint
00378    *  A couple points on memory allocation for list<Tp>:
00379    *
00380    *  First, we never actually allocate a Tp, we allocate
00381    *  List_node<Tp>'s and trust [20.1.5]/4 to DTRT.  This is to ensure
00382    *  that after elements from %list<X,Alloc1> are spliced into
00383    *  %list<X,Alloc2>, destroying the memory of the second %list is a
00384    *  valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
00385    *
00386    *  Second, a %list conceptually represented as
00387    *  @code
00388    *    A <---> B <---> C <---> D
00389    *  @endcode
00390    *  is actually circular; a link exists between A and D.  The %list
00391    *  class holds (as its only data member) a private list::iterator
00392    *  pointing to @e D, not to @e A!  To get to the head of the %list,
00393    *  we start at the tail and move forward by one.  When this member
00394    *  iterator's next/previous pointers refer to itself, the %list is
00395    *  %empty.  @endif
00396   */
00397   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
00398     class list : protected _List_base<_Tp, _Alloc>
00399     {
00400       // concept requirements
00401       typedef typename _Alloc::value_type                _Alloc_value_type;
00402       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00403       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00404 
00405       typedef _List_base<_Tp, _Alloc>                    _Base;
00406       typedef typename _Base::_Tp_alloc_type         _Tp_alloc_type;
00407 
00408     public:
00409       typedef _Tp                                        value_type;
00410       typedef typename _Tp_alloc_type::pointer           pointer;
00411       typedef typename _Tp_alloc_type::const_pointer     const_pointer;
00412       typedef typename _Tp_alloc_type::reference         reference;
00413       typedef typename _Tp_alloc_type::const_reference   const_reference;
00414       typedef _List_iterator<_Tp>                        iterator;
00415       typedef _List_const_iterator<_Tp>                  const_iterator;
00416       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
00417       typedef std::reverse_iterator<iterator>            reverse_iterator;
00418       typedef size_t                                     size_type;
00419       typedef ptrdiff_t                                  difference_type;
00420       typedef _Alloc                                     allocator_type;
00421 
00422     protected:
00423       // Note that pointers-to-_Node's can be ctor-converted to
00424       // iterator types.
00425       typedef _List_node<_Tp>                _Node;
00426 
00427       /** @if maint
00428        *  One data member plus two memory-handling functions.  If the
00429        *  _Alloc type requires separate instances, then one of those
00430        *  will also be included, accumulated from the topmost parent.
00431        *  @endif
00432        */
00433       using _Base::_M_impl;
00434       using _Base::_M_put_node;
00435       using _Base::_M_get_node;
00436       using _Base::_M_get_Tp_allocator;
00437 
00438       /**
00439        *  @if maint
00440        *  @param  x  An instance of user data.
00441        *
00442        *  Allocates space for a new node and constructs a copy of @a x in it.
00443        *  @endif
00444        */
00445       _Node*
00446       _M_create_node(const value_type& __x)
00447       {
00448     _Node* __p = this->_M_get_node();
00449     try
00450       {
00451         _M_get_Tp_allocator().construct(&__p->_M_data, __x);
00452       }
00453     catch(...)
00454       {
00455         _M_put_node(__p);
00456         __throw_exception_again;
00457       }
00458     return __p;
00459       }
00460 
00461     public:
00462       // [23.2.2.1] construct/copy/destroy
00463       // (assign() and get_allocator() are also listed in this section)
00464       /**
00465        *  @brief  Default constructor creates no elements.
00466        */
00467       explicit
00468       list(const allocator_type& __a = allocator_type())
00469       : _Base(__a) { }
00470 
00471       /**
00472        *  @brief  Create a %list with copies of an exemplar element.
00473        *  @param  n  The number of elements to initially create.
00474        *  @param  value  An element to copy.
00475        *
00476        *  This constructor fills the %list with @a n copies of @a value.
00477        */
00478       explicit
00479       list(size_type __n, const value_type& __value = value_type(),
00480        const allocator_type& __a = allocator_type())
00481       : _Base(__a)
00482       { this->insert(begin(), __n, __value); }
00483 
00484       /**
00485        *  @brief  %List copy constructor.
00486        *  @param  x  A %list of identical element and allocator types.
00487        *
00488        *  The newly-created %list uses a copy of the allocation object used
00489        *  by @a x.
00490        */
00491       list(const list& __x)
00492       : _Base(__x.get_allocator())
00493       { this->insert(begin(), __x.begin(), __x.end()); }
00494 
00495       /**
00496        *  @brief  Builds a %list from a range.
00497        *  @param  first  An input iterator.
00498        *  @param  last  An input iterator.
00499        *
00500        *  Create a %list consisting of copies of the elements from
00501        *  [@a first,@a last).  This is linear in N (where N is
00502        *  distance(@a first,@a last)).
00503        *
00504        *  @if maint
00505        *  We don't need any dispatching tricks here, because insert does all of
00506        *  that anyway.
00507        *  @endif
00508        */
00509       template<typename _InputIterator>
00510         list(_InputIterator __first, _InputIterator __last,
00511          const allocator_type& __a = allocator_type())
00512         : _Base(__a)
00513         { this->insert(begin(), __first, __last); }
00514 
00515       /**
00516        *  No explicit dtor needed as the _Base dtor takes care of
00517        *  things.  The _Base dtor only erases the elements, and note
00518        *  that if the elements themselves are pointers, the pointed-to
00519        *  memory is not touched in any way.  Managing the pointer is
00520        *  the user's responsibilty.
00521        */
00522 
00523       /**
00524        *  @brief  %List assignment operator.
00525        *  @param  x  A %list of identical element and allocator types.
00526        *
00527        *  All the elements of @a x are copied, but unlike the copy
00528        *  constructor, the allocator object is not copied.
00529        */
00530       list&
00531       operator=(const list& __x);
00532 
00533       /**
00534        *  @brief  Assigns a given value to a %list.
00535        *  @param  n  Number of elements to be assigned.
00536        *  @param  val  Value to be assigned.
00537        *
00538        *  This function fills a %list with @a n copies of the given
00539        *  value.  Note that the assignment completely changes the %list
00540        *  and that the resulting %list's size is the same as the number
00541        *  of elements assigned.  Old data may be lost.
00542        */
00543       void
00544       assign(size_type __n, const value_type& __val)
00545       { _M_fill_assign(__n, __val); }
00546 
00547       /**
00548        *  @brief  Assigns a range to a %list.
00549        *  @param  first  An input iterator.
00550        *  @param  last   An input iterator.
00551        *
00552        *  This function fills a %list with copies of the elements in the
00553        *  range [@a first,@a last).
00554        *
00555        *  Note that the assignment completely changes the %list and
00556        *  that the resulting %list's size is the same as the number of
00557        *  elements assigned.  Old data may be lost.
00558        */
00559       template<typename _InputIterator>
00560         void
00561         assign(_InputIterator __first, _InputIterator __last)
00562         {
00563       // Check whether it's an integral type.  If so, it's not an iterator.
00564       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00565       _M_assign_dispatch(__first, __last, _Integral());
00566     }
00567 
00568       /// Get a copy of the memory allocation object.
00569       allocator_type
00570       get_allocator() const
00571       { return _Base::get_allocator(); }
00572 
00573       // iterators
00574       /**
00575        *  Returns a read/write iterator that points to the first element in the
00576        *  %list.  Iteration is done in ordinary element order.
00577        */
00578       iterator
00579       begin()
00580       { return iterator(this->_M_impl._M_node._M_next); }
00581 
00582       /**
00583        *  Returns a read-only (constant) iterator that points to the
00584        *  first element in the %list.  Iteration is done in ordinary
00585        *  element order.
00586        */
00587       const_iterator
00588       begin() const
00589       { return const_iterator(this->_M_impl._M_node._M_next); }
00590 
00591       /**
00592        *  Returns a read/write iterator that points one past the last
00593        *  element in the %list.  Iteration is done in ordinary element
00594        *  order.
00595        */
00596       iterator
00597       end()
00598       { return iterator(&this->_M_impl._M_node); }
00599 
00600       /**
00601        *  Returns a read-only (constant) iterator that points one past
00602        *  the last element in the %list.  Iteration is done in ordinary
00603        *  element order.
00604        */
00605       const_iterator
00606       end() const
00607       { return const_iterator(&this->_M_impl._M_node); }
00608 
00609       /**
00610        *  Returns a read/write reverse iterator that points to the last
00611        *  element in the %list.  Iteration is done in reverse element
00612        *  order.
00613        */
00614       reverse_iterator
00615       rbegin()
00616       { return reverse_iterator(end()); }
00617 
00618       /**
00619        *  Returns a read-only (constant) reverse iterator that points to
00620        *  the last element in the %list.  Iteration is done in reverse
00621        *  element order.
00622        */
00623       const_reverse_iterator
00624       rbegin() const
00625       { return const_reverse_iterator(end()); }
00626 
00627       /**
00628        *  Returns a read/write reverse iterator that points to one
00629        *  before the first element in the %list.  Iteration is done in
00630        *  reverse element order.
00631        */
00632       reverse_iterator
00633       rend()
00634       { return reverse_iterator(begin()); }
00635 
00636       /**
00637        *  Returns a read-only (constant) reverse iterator that points to one
00638        *  before the first element in the %list.  Iteration is done in reverse
00639        *  element order.
00640        */
00641       const_reverse_iterator
00642       rend() const
00643       { return const_reverse_iterator(begin()); }
00644 
00645       // [23.2.2.2] capacity
00646       /**
00647        *  Returns true if the %list is empty.  (Thus begin() would equal
00648        *  end().)
00649        */
00650       bool
00651       empty() const
00652       { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
00653 
00654       /**  Returns the number of elements in the %list.  */
00655       size_type
00656       size() const
00657       { return std::distance(begin(), end()); }
00658 
00659       /**  Returns the size() of the largest possible %list.  */
00660       size_type
00661       max_size() const
00662       { return size_type(-1); }
00663 
00664       /**
00665        *  @brief Resizes the %list to the specified number of elements.
00666        *  @param new_size Number of elements the %list should contain.
00667        *  @param x Data with which new elements should be populated.
00668        *
00669        *  This function will %resize the %list to the specified number
00670        *  of elements.  If the number is smaller than the %list's
00671        *  current size the %list is truncated, otherwise the %list is
00672        *  extended and new elements are populated with given data.
00673        */
00674       void
00675       resize(size_type __new_size, value_type __x = value_type());
00676 
00677       // element access
00678       /**
00679        *  Returns a read/write reference to the data at the first
00680        *  element of the %list.
00681        */
00682       reference
00683       front()
00684       { return *begin(); }
00685 
00686       /**
00687        *  Returns a read-only (constant) reference to the data at the first
00688        *  element of the %list.
00689        */
00690       const_reference
00691       front() const
00692       { return *begin(); }
00693 
00694       /**
00695        *  Returns a read/write reference to the data at the last element
00696        *  of the %list.
00697        */
00698       reference
00699       back()
00700       { 
00701     iterator __tmp = end();
00702     --__tmp;
00703     return *__tmp;
00704       }
00705 
00706       /**
00707        *  Returns a read-only (constant) reference to the data at the last
00708        *  element of the %list.
00709        */
00710       const_reference
00711       back() const
00712       { 
00713     const_iterator __tmp = end();
00714     --__tmp;
00715     return *__tmp;
00716       }
00717 
00718       // [23.2.2.3] modifiers
00719       /**
00720        *  @brief  Add data to the front of the %list.
00721        *  @param  x  Data to be added.
00722        *
00723        *  This is a typical stack operation.  The function creates an
00724        *  element at the front of the %list and assigns the given data
00725        *  to it.  Due to the nature of a %list this operation can be
00726        *  done in constant time, and does not invalidate iterators and
00727        *  references.
00728        */
00729       void
00730       push_front(const value_type& __x)
00731       { this->_M_insert(begin(), __x); }
00732 
00733       /**
00734        *  @brief  Removes first element.
00735        *
00736        *  This is a typical stack operation.  It shrinks the %list by
00737        *  one.  Due to the nature of a %list this operation can be done
00738        *  in constant time, and only invalidates iterators/references to
00739        *  the element being removed.
00740        *
00741        *  Note that no data is returned, and if the first element's data
00742        *  is needed, it should be retrieved before pop_front() is
00743        *  called.
00744        */
00745       void
00746       pop_front()
00747       { this->_M_erase(begin()); }
00748 
00749       /**
00750        *  @brief  Add data to the end of the %list.
00751        *  @param  x  Data to be added.
00752        *
00753        *  This is a typical stack operation.  The function creates an
00754        *  element at the end of the %list and assigns the given data to
00755        *  it.  Due to the nature of a %list this operation can be done
00756        *  in constant time, and does not invalidate iterators and
00757        *  references.
00758        */
00759       void
00760       push_back(const value_type& __x)
00761       { this->_M_insert(end(), __x); }
00762 
00763       /**
00764        *  @brief  Removes last element.
00765        *
00766        *  This is a typical stack operation.  It shrinks the %list by
00767        *  one.  Due to the nature of a %list this operation can be done
00768        *  in constant time, and only invalidates iterators/references to
00769        *  the element being removed.
00770        *
00771        *  Note that no data is returned, and if the last element's data
00772        *  is needed, it should be retrieved before pop_back() is called.
00773        */
00774       void
00775       pop_back()
00776       { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
00777 
00778       /**
00779        *  @brief  Inserts given value into %list before specified iterator.
00780        *  @param  position  An iterator into the %list.
00781        *  @param  x  Data to be inserted.
00782        *  @return  An iterator that points to the inserted data.
00783        *
00784        *  This function will insert a copy of the given value before
00785        *  the specified location.  Due to the nature of a %list this
00786        *  operation can be done in constant time, and does not
00787        *  invalidate iterators and references.
00788        */
00789       iterator
00790       insert(iterator __position, const value_type& __x);
00791 
00792       /**
00793        *  @brief  Inserts a number of copies of given data into the %list.
00794        *  @param  position  An iterator into the %list.
00795        *  @param  n  Number of elements to be inserted.
00796        *  @param  x  Data to be inserted.
00797        *
00798        *  This function will insert a specified number of copies of the
00799        *  given data before the location specified by @a position.
00800        *
00801        *  Due to the nature of a %list this operation can be done in
00802        *  constant time, and does not invalidate iterators and
00803        *  references.
00804        */
00805       void
00806       insert(iterator __position, size_type __n, const value_type& __x)
00807       { _M_fill_insert(__position, __n, __x); }
00808 
00809       /**
00810        *  @brief  Inserts a range into the %list.
00811        *  @param  position  An iterator into the %list.
00812        *  @param  first  An input iterator.
00813        *  @param  last   An input iterator.
00814        *
00815        *  This function will insert copies of the data in the range [@a
00816        *  first,@a last) into the %list before the location specified by
00817        *  @a position.
00818        *
00819        *  Due to the nature of a %list this operation can be done in
00820        *  constant time, and does not invalidate iterators and
00821        *  references.
00822        */
00823       template<typename _InputIterator>
00824         void
00825         insert(iterator __position, _InputIterator __first,
00826            _InputIterator __last)
00827         {
00828       // Check whether it's an integral type.  If so, it's not an iterator.
00829       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00830       _M_insert_dispatch(__position, __first, __last, _Integral());
00831     }
00832 
00833       /**
00834        *  @brief  Remove element at given position.
00835        *  @param  position  Iterator pointing to element to be erased.
00836        *  @return  An iterator pointing to the next element (or end()).
00837        *
00838        *  This function will erase the element at the given position and thus
00839        *  shorten the %list by one.
00840        *
00841        *  Due to the nature of a %list this operation can be done in
00842        *  constant time, and only invalidates iterators/references to
00843        *  the element being removed.  The user is also cautioned that
00844        *  this function only erases the element, and that if the element
00845        *  is itself a pointer, the pointed-to memory is not touched in
00846        *  any way.  Managing the pointer is the user's responsibilty.
00847        */
00848       iterator
00849       erase(iterator __position);
00850 
00851       /**
00852        *  @brief  Remove a range of elements.
00853        *  @param  first  Iterator pointing to the first element to be erased.
00854        *  @param  last  Iterator pointing to one past the last element to be
00855        *                erased.
00856        *  @return  An iterator pointing to the element pointed to by @a last
00857        *           prior to erasing (or end()).
00858        *
00859        *  This function will erase the elements in the range @a
00860        *  [first,last) and shorten the %list accordingly.
00861        *
00862        *  Due to the nature of a %list this operation can be done in
00863        *  constant time, and only invalidates iterators/references to
00864        *  the element being removed.  The user is also cautioned that
00865        *  this function only erases the elements, and that if the
00866        *  elements themselves are pointers, the pointed-to memory is not
00867        *  touched in any way.  Managing the pointer is the user's
00868        *  responsibilty.
00869        */
00870       iterator
00871       erase(iterator __first, iterator __last)
00872       {
00873     while (__first != __last)
00874       __first = erase(__first);
00875     return __last;
00876       }
00877 
00878       /**
00879        *  @brief  Swaps data with another %list.
00880        *  @param  x  A %list of the same element and allocator types.
00881        *
00882        *  This exchanges the elements between two lists in constant
00883        *  time.  Note that the global std::swap() function is
00884        *  specialized such that std::swap(l1,l2) will feed to this
00885        *  function.
00886        */
00887       void
00888       swap(list& __x)
00889       { _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node); }
00890 
00891       /**
00892        *  Erases all the elements.  Note that this function only erases
00893        *  the elements, and that if the elements themselves are
00894        *  pointers, the pointed-to memory is not touched in any way.
00895        *  Managing the pointer is the user's responsibilty.
00896        */
00897       void
00898       clear()
00899       {
00900         _Base::_M_clear();
00901         _Base::_M_init();
00902       }
00903 
00904       // [23.2.2.4] list operations
00905       /**
00906        *  @brief  Insert contents of another %list.
00907        *  @param  position  Iterator referencing the element to insert before.
00908        *  @param  x  Source list.
00909        *
00910        *  The elements of @a x are inserted in constant time in front of
00911        *  the element referenced by @a position.  @a x becomes an empty
00912        *  list.
00913        */
00914       void
00915       splice(iterator __position, list& __x)
00916       {
00917     if (!__x.empty())
00918       this->_M_transfer(__position, __x.begin(), __x.end());
00919       }
00920 
00921       /**
00922        *  @brief  Insert element from another %list.
00923        *  @param  position  Iterator referencing the element to insert before.
00924        *  @param  x  Source list.
00925        *  @param  i  Iterator referencing the element to move.
00926        *
00927        *  Removes the element in list @a x referenced by @a i and
00928        *  inserts it into the current list before @a position.
00929        */
00930       void
00931       splice(iterator __position, list&, iterator __i)
00932       {
00933     iterator __j = __i;
00934     ++__j;
00935     if (__position == __i || __position == __j)
00936       return;
00937     this->_M_transfer(__position, __i, __j);
00938       }
00939 
00940       /**
00941        *  @brief  Insert range from another %list.
00942        *  @param  position  Iterator referencing the element to insert before.
00943        *  @param  x  Source list.
00944        *  @param  first  Iterator referencing the start of range in x.
00945        *  @param  last  Iterator referencing the end of range in x.
00946        *
00947        *  Removes elements in the range [first,last) and inserts them
00948        *  before @a position in constant time.
00949        *
00950        *  Undefined if @a position is in [first,last).
00951        */
00952       void
00953       splice(iterator __position, list&, iterator __first, iterator __last)
00954       {
00955     if (__first != __last)
00956       this->_M_transfer(__position, __first, __last);
00957       }
00958 
00959       /**
00960        *  @brief  Remove all elements equal to value.
00961        *  @param  value  The value to remove.
00962        *
00963        *  Removes every element in the list equal to @a value.
00964        *  Remaining elements stay in list order.  Note that this
00965        *  function only erases the elements, and that if the elements
00966        *  themselves are pointers, the pointed-to memory is not
00967        *  touched in any way.  Managing the pointer is the user's
00968        *  responsibilty.
00969        */
00970       void
00971       remove(const _Tp& __value);
00972 
00973       /**
00974        *  @brief  Remove all elements satisfying a predicate.
00975        *  @param  Predicate  Unary predicate function or object.
00976        *
00977        *  Removes every element in the list for which the predicate
00978        *  returns true.  Remaining elements stay in list order.  Note
00979        *  that this function only erases the elements, and that if the
00980        *  elements themselves are pointers, the pointed-to memory is
00981        *  not touched in any way.  Managing the pointer is the user's
00982        *  responsibilty.
00983        */
00984       template<typename _Predicate>
00985       void
00986       remove_if(_Predicate);
00987 
00988       /**
00989        *  @brief  Remove consecutive duplicate elements.
00990        *
00991        *  For each consecutive set of elements with the same value,
00992        *  remove all but the first one.  Remaining elements stay in
00993        *  list order.  Note that this function only erases the
00994        *  elements, and that if the elements themselves are pointers,
00995        *  the pointed-to memory is not touched in any way.  Managing
00996        *  the pointer is the user's responsibilty.
00997        */
00998       void
00999       unique();
01000 
01001       /**
01002        *  @brief  Remove consecutive elements satisfying a predicate.
01003        *  @param  BinaryPredicate  Binary predicate function or object.
01004        *
01005        *  For each consecutive set of elements [first,last) that
01006        *  satisfy predicate(first,i) where i is an iterator in
01007        *  [first,last), remove all but the first one.  Remaining
01008        *  elements stay in list order.  Note that this function only
01009        *  erases the elements, and that if the elements themselves are
01010        *  pointers, the pointed-to memory is not touched in any way.
01011        *  Managing the pointer is the user's responsibilty.
01012        */
01013       template<typename _BinaryPredicate>
01014         void
01015         unique(_BinaryPredicate);
01016 
01017       /**
01018        *  @brief  Merge sorted lists.
01019        *  @param  x  Sorted list to merge.
01020        *
01021        *  Assumes that both @a x and this list are sorted according to
01022        *  operator<().  Merges elements of @a x into this list in
01023        *  sorted order, leaving @a x empty when complete.  Elements in
01024        *  this list precede elements in @a x that are equal.
01025        */
01026       void
01027       merge(list& __x);
01028 
01029       /**
01030        *  @brief  Merge sorted lists according to comparison function.
01031        *  @param  x  Sorted list to merge.
01032        *  @param StrictWeakOrdering Comparison function definining
01033        *  sort order.
01034        *
01035        *  Assumes that both @a x and this list are sorted according to
01036        *  StrictWeakOrdering.  Merges elements of @a x into this list
01037        *  in sorted order, leaving @a x empty when complete.  Elements
01038        *  in this list precede elements in @a x that are equivalent
01039        *  according to StrictWeakOrdering().
01040        */
01041       template<typename _StrictWeakOrdering>
01042         void
01043         merge(list&, _StrictWeakOrdering);
01044 
01045       /**
01046        *  @brief  Reverse the elements in list.
01047        *
01048        *  Reverse the order of elements in the list in linear time.
01049        */
01050       void
01051       reverse()
01052       { this->_M_impl._M_node.reverse(); }
01053 
01054       /**
01055        *  @brief  Sort the elements.
01056        *
01057        *  Sorts the elements of this list in NlogN time.  Equivalent
01058        *  elements remain in list order.
01059        */
01060       void
01061       sort();
01062 
01063       /**
01064        *  @brief  Sort the elements according to comparison function.
01065        *
01066        *  Sorts the elements of this list in NlogN time.  Equivalent
01067        *  elements remain in list order.
01068        */
01069       template<typename _StrictWeakOrdering>
01070         void
01071         sort(_StrictWeakOrdering);
01072 
01073     protected:
01074       // Internal assign functions follow.
01075 
01076       // Called by the range assign to implement [23.1.1]/9
01077       template<typename _Integer>
01078         void
01079         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01080         {
01081       _M_fill_assign(static_cast<size_type>(__n),
01082              static_cast<value_type>(__val));
01083     }
01084 
01085       // Called by the range assign to implement [23.1.1]/9
01086       template<typename _InputIterator>
01087         void
01088         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01089                __false_type);
01090 
01091       // Called by assign(n,t), and the range assign when it turns out
01092       // to be the same thing.
01093       void
01094       _M_fill_assign(size_type __n, const value_type& __val);
01095 
01096 
01097       // Internal insert functions follow.
01098 
01099       // Called by the range insert to implement [23.1.1]/9
01100       template<typename _Integer>
01101         void
01102         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
01103                __true_type)
01104         {
01105       _M_fill_insert(__pos, static_cast<size_type>(__n),
01106              static_cast<value_type>(__x));
01107     }
01108 
01109       // Called by the range insert to implement [23.1.1]/9
01110       template<typename _InputIterator>
01111         void
01112         _M_insert_dispatch(iterator __pos,
01113                _InputIterator __first, _InputIterator __last,
01114                __false_type)
01115         {
01116       for (; __first != __last; ++__first)
01117         _M_insert(__pos, *__first);
01118     }
01119 
01120       // Called by insert(p,n,x), and the range insert when it turns out
01121       // to be the same thing.
01122       void
01123       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
01124       {
01125     for (; __n > 0; --__n)
01126       _M_insert(__pos, __x);
01127       }
01128 
01129 
01130       // Moves the elements from [first,last) before position.
01131       void
01132       _M_transfer(iterator __position, iterator __first, iterator __last)
01133       { __position._M_node->transfer(__first._M_node, __last._M_node); }
01134 
01135       // Inserts new element at position given and with value given.
01136       void
01137       _M_insert(iterator __position, const value_type& __x)
01138       {
01139         _Node* __tmp = _M_create_node(__x);
01140         __tmp->hook(__position._M_node);
01141       }
01142 
01143       // Erases element at position given.
01144       void
01145       _M_erase(iterator __position)
01146       {
01147         __position._M_node->unhook();
01148         _Node* __n = static_cast<_Node*>(__position._M_node);
01149         _M_get_Tp_allocator().destroy(&__n->_M_data);
01150         _M_put_node(__n);
01151       }
01152     };
01153 
01154   /**
01155    *  @brief  List equality comparison.
01156    *  @param  x  A %list.
01157    *  @param  y  A %list of the same type as @a x.
01158    *  @return  True iff the size and elements of the lists are equal.
01159    *
01160    *  This is an equivalence relation.  It is linear in the size of
01161    *  the lists.  Lists are considered equivalent if their sizes are
01162    *  equal, and if corresponding elements compare equal.
01163   */
01164   template<typename _Tp, typename _Alloc>
01165     inline bool
01166     operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01167     {
01168       typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
01169       const_iterator __end1 = __x.end();
01170       const_iterator __end2 = __y.end();
01171 
01172       const_iterator __i1 = __x.begin();
01173       const_iterator __i2 = __y.begin();
01174       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
01175     {
01176       ++__i1;
01177       ++__i2;
01178     }
01179       return __i1 == __end1 && __i2 == __end2;
01180     }
01181 
01182   /**
01183    *  @brief  List ordering relation.
01184    *  @param  x  A %list.
01185    *  @param  y  A %list of the same type as @a x.
01186    *  @return  True iff @a x is lexicographically less than @a y.
01187    *
01188    *  This is a total ordering relation.  It is linear in the size of the
01189    *  lists.  The elements must be comparable with @c <.
01190    *
01191    *  See std::lexicographical_compare() for how the determination is made.
01192   */
01193   template<typename _Tp, typename _Alloc>
01194     inline bool
01195     operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01196     { return std::lexicographical_compare(__x.begin(), __x.end(),
01197                       __y.begin(), __y.end()); }
01198 
01199   /// Based on operator==
01200   template<typename _Tp, typename _Alloc>
01201     inline bool
01202     operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01203     { return !(__x == __y); }
01204 
01205   /// Based on operator<
01206   template<typename _Tp, typename _Alloc>
01207     inline bool
01208     operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01209     { return __y < __x; }
01210 
01211   /// Based on operator<
01212   template<typename _Tp, typename _Alloc>
01213     inline bool
01214     operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01215     { return !(__y < __x); }
01216 
01217   /// Based on operator<
01218   template<typename _Tp, typename _Alloc>
01219     inline bool
01220     operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01221     { return !(__x < __y); }
01222 
01223   /// See std::list::swap().
01224   template<typename _Tp, typename _Alloc>
01225     inline void
01226     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
01227     { __x.swap(__y); }
01228 } // namespace std
01229 
01230 #endif /* _LIST_H */
01231 

Generated on Tue Dec 2 03:59:28 2008 for libstdc++ by  doxygen 1.5.7.1