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

Generated on Tue May 23 12:55:30 2006 for libstdc++ source by  doxygen 1.4.4