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 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 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     _List_impl (const _Node_Alloc_type& __a)
00304     : _Node_Alloc_type(__a)
00305     { }
00306       };
00307 
00308       _List_impl _M_impl;
00309 
00310       _List_node<_Tp>*
00311       _M_get_node()
00312       { return _M_impl._Node_Alloc_type::allocate(1); }
00313       
00314       void
00315       _M_put_node(_List_node<_Tp>* __p)
00316       { _M_impl._Node_Alloc_type::deallocate(__p, 1); }
00317       
00318   public:
00319       typedef _Alloc allocator_type;
00320 
00321       allocator_type
00322       get_allocator() const
00323       { return allocator_type(*static_cast<
00324                   const _Node_Alloc_type*>(&this->_M_impl)); }
00325 
00326       _List_base(const allocator_type& __a)
00327       : _M_impl(__a)
00328       { _M_init(); }
00329 
00330       // This is what actually destroys the list.
00331       ~_List_base()
00332       { _M_clear(); }
00333 
00334       void
00335       _M_clear();
00336 
00337       void
00338       _M_init()
00339       {
00340         this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
00341         this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
00342       }
00343     };
00344 
00345   /**
00346    *  @brief A standard container with linear time access to elements,
00347    *  and fixed time insertion/deletion at any point in the sequence.
00348    *
00349    *  @ingroup Containers
00350    *  @ingroup Sequences
00351    *
00352    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00353    *  <a href="tables.html#66">reversible container</a>, and a
00354    *  <a href="tables.html#67">sequence</a>, including the
00355    *  <a href="tables.html#68">optional sequence requirements</a> with the
00356    *  %exception of @c at and @c operator[].
00357    *
00358    *  This is a @e doubly @e linked %list.  Traversal up and down the
00359    *  %list requires linear time, but adding and removing elements (or
00360    *  @e nodes) is done in constant time, regardless of where the
00361    *  change takes place.  Unlike std::vector and std::deque,
00362    *  random-access iterators are not provided, so subscripting ( @c
00363    *  [] ) access is not allowed.  For algorithms which only need
00364    *  sequential access, this lack makes no difference.
00365    *
00366    *  Also unlike the other standard containers, std::list provides
00367    *  specialized algorithms %unique to linked lists, such as
00368    *  splicing, sorting, and in-place reversal.
00369    *
00370    *  @if maint
00371    *  A couple points on memory allocation for list<Tp>:
00372    *
00373    *  First, we never actually allocate a Tp, we allocate
00374    *  List_node<Tp>'s and trust [20.1.5]/4 to DTRT.  This is to ensure
00375    *  that after elements from %list<X,Alloc1> are spliced into
00376    *  %list<X,Alloc2>, destroying the memory of the second %list is a
00377    *  valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
00378    *
00379    *  Second, a %list conceptually represented as
00380    *  @code
00381    *    A <---> B <---> C <---> D
00382    *  @endcode
00383    *  is actually circular; a link exists between A and D.  The %list
00384    *  class holds (as its only data member) a private list::iterator
00385    *  pointing to @e D, not to @e A!  To get to the head of the %list,
00386    *  we start at the tail and move forward by one.  When this member
00387    *  iterator's next/previous pointers refer to itself, the %list is
00388    *  %empty.  @endif
00389   */
00390   template<typename _Tp, typename _Alloc = allocator<_Tp> >
00391     class list : protected _List_base<_Tp, _Alloc>
00392     {
00393       // concept requirements
00394       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00395 
00396       typedef _List_base<_Tp, _Alloc>                   _Base;
00397 
00398     public:
00399       typedef _Tp                                        value_type;
00400       typedef typename _Alloc::pointer                   pointer;
00401       typedef typename _Alloc::const_pointer             const_pointer;
00402       typedef typename _Alloc::reference                 reference;
00403       typedef typename _Alloc::const_reference           const_reference;
00404       typedef _List_iterator<_Tp>                        iterator;
00405       typedef _List_const_iterator<_Tp>                  const_iterator;
00406       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
00407       typedef std::reverse_iterator<iterator>            reverse_iterator;
00408       typedef size_t                                     size_type;
00409       typedef ptrdiff_t                                  difference_type;
00410       typedef typename _Base::allocator_type             allocator_type;
00411 
00412     protected:
00413       // Note that pointers-to-_Node's can be ctor-converted to
00414       // iterator types.
00415       typedef _List_node<_Tp>               _Node;
00416 
00417       /** @if maint
00418        *  One data member plus two memory-handling functions.  If the
00419        *  _Alloc type requires separate instances, then one of those
00420        *  will also be included, accumulated from the topmost parent.
00421        *  @endif
00422        */
00423       using _Base::_M_impl;
00424       using _Base::_M_put_node;
00425       using _Base::_M_get_node;
00426 
00427       /**
00428        *  @if maint
00429        *  @param  x  An instance of user data.
00430        *
00431        *  Allocates space for a new node and constructs a copy of @a x in it.
00432        *  @endif
00433        */
00434       _Node*
00435       _M_create_node(const value_type& __x)
00436       {
00437     _Node* __p = this->_M_get_node();
00438     try
00439       {
00440         this->get_allocator().construct(&__p->_M_data, __x);
00441       }
00442     catch(...)
00443       {
00444         _M_put_node(__p);
00445         __throw_exception_again;
00446       }
00447     return __p;
00448       }
00449 
00450     public:
00451       // [23.2.2.1] construct/copy/destroy
00452       // (assign() and get_allocator() are also listed in this section)
00453       /**
00454        *  @brief  Default constructor creates no elements.
00455        */
00456       explicit
00457       list(const allocator_type& __a = allocator_type())
00458       : _Base(__a) { }
00459 
00460       /**
00461        *  @brief  Create a %list with copies of an exemplar element.
00462        *  @param  n  The number of elements to initially create.
00463        *  @param  value  An element to copy.
00464        *
00465        *  This constructor fills the %list with @a n copies of @a value.
00466        */
00467       list(size_type __n, const value_type& __value,
00468        const allocator_type& __a = allocator_type())
00469       : _Base(__a)
00470       { this->insert(begin(), __n, __value); }
00471 
00472       /**
00473        *  @brief  Create a %list with default elements.
00474        *  @param  n  The number of elements to initially create.
00475        *
00476        *  This constructor fills the %list with @a n copies of a
00477        *  default-constructed element.
00478        */
00479       explicit
00480       list(size_type __n)
00481       : _Base(allocator_type())
00482       { this->insert(begin(), __n, value_type()); }
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 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 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() { return &this->_M_impl._M_node; }
00598 
00599       /**
00600        *  Returns a read-only (constant) iterator that points one past
00601        *  the last element in the %list.  Iteration is done in ordinary
00602        *  element order.
00603        */
00604       const_iterator
00605       end() const
00606       { return &this->_M_impl._M_node; }
00607 
00608       /**
00609        *  Returns a read/write reverse iterator that points to the last
00610        *  element in the %list.  Iteration is done in reverse element
00611        *  order.
00612        */
00613       reverse_iterator
00614       rbegin()
00615       { return reverse_iterator(end()); }
00616 
00617       /**
00618        *  Returns a read-only (constant) reverse iterator that points to
00619        *  the last element in the %list.  Iteration is done in reverse
00620        *  element order.
00621        */
00622       const_reverse_iterator
00623       rbegin() const
00624       { return const_reverse_iterator(end()); }
00625 
00626       /**
00627        *  Returns a read/write reverse iterator that points to one
00628        *  before the first element in the %list.  Iteration is done in
00629        *  reverse element order.
00630        */
00631       reverse_iterator
00632       rend()
00633       { return reverse_iterator(begin()); }
00634 
00635       /**
00636        *  Returns a read-only (constant) reverse iterator that points to one
00637        *  before the first element in the %list.  Iteration is done in reverse
00638        *  element order.
00639        */
00640       const_reverse_iterator
00641       rend() const
00642       { return const_reverse_iterator(begin()); }
00643 
00644       // [23.2.2.2] capacity
00645       /**
00646        *  Returns true if the %list is empty.  (Thus begin() would equal
00647        *  end().)
00648        */
00649       bool
00650       empty() const
00651       { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
00652 
00653       /**  Returns the number of elements in the %list.  */
00654       size_type
00655       size() const
00656       { return std::distance(begin(), end()); }
00657 
00658       /**  Returns the size() of the largest possible %list.  */
00659       size_type
00660       max_size() const
00661       { return size_type(-1); }
00662 
00663       /**
00664        *  @brief Resizes the %list to the specified number of elements.
00665        *  @param new_size Number of elements the %list should contain.
00666        *  @param x Data with which new elements should be populated.
00667        *
00668        *  This function will %resize the %list to the specified number
00669        *  of elements.  If the number is smaller than the %list's
00670        *  current size the %list is truncated, otherwise the %list is
00671        *  extended and new elements are populated with given data.
00672        */
00673       void
00674       resize(size_type __new_size, const value_type& __x);
00675 
00676       /**
00677        *  @brief  Resizes the %list to the specified number of elements.
00678        *  @param  new_size  Number of elements the %list should contain.
00679        *
00680        *  This function will resize the %list to the specified number of
00681        *  elements.  If the number is smaller than the %list's current
00682        *  size the %list is truncated, otherwise the %list is extended
00683        *  and new elements are default-constructed.
00684        */
00685       void
00686       resize(size_type __new_size)
00687       { this->resize(__new_size, value_type()); }
00688 
00689       // element access
00690       /**
00691        *  Returns a read/write reference to the data at the first
00692        *  element of the %list.
00693        */
00694       reference
00695       front()
00696       { return *begin(); }
00697 
00698       /**
00699        *  Returns a read-only (constant) reference to the data at the first
00700        *  element of the %list.
00701        */
00702       const_reference
00703       front() const
00704       { return *begin(); }
00705 
00706       /**
00707        *  Returns a read/write reference to the data at the last element
00708        *  of the %list.
00709        */
00710       reference
00711       back()
00712       { 
00713     iterator __tmp = end();
00714     --__tmp;
00715     return *__tmp;
00716       }
00717 
00718       /**
00719        *  Returns a read-only (constant) reference to the data at the last
00720        *  element of the %list.
00721        */
00722       const_reference
00723       back() const
00724       { 
00725     const_iterator __tmp = end();
00726     --__tmp;
00727     return *__tmp;
00728       }
00729 
00730       // [23.2.2.3] modifiers
00731       /**
00732        *  @brief  Add data to the front of the %list.
00733        *  @param  x  Data to be added.
00734        *
00735        *  This is a typical stack operation.  The function creates an
00736        *  element at the front of the %list and assigns the given data
00737        *  to it.  Due to the nature of a %list this operation can be
00738        *  done in constant time, and does not invalidate iterators and
00739        *  references.
00740        */
00741       void
00742       push_front(const value_type& __x)
00743       { this->_M_insert(begin(), __x); }
00744 
00745       /**
00746        *  @brief  Removes first element.
00747        *
00748        *  This is a typical stack operation.  It shrinks the %list by
00749        *  one.  Due to the nature of a %list this operation can be done
00750        *  in constant time, and only invalidates iterators/references to
00751        *  the element being removed.
00752        *
00753        *  Note that no data is returned, and if the first element's data
00754        *  is needed, it should be retrieved before pop_front() is
00755        *  called.
00756        */
00757       void
00758       pop_front()
00759       { this->_M_erase(begin()); }
00760 
00761       /**
00762        *  @brief  Add data to the end of the %list.
00763        *  @param  x  Data to be added.
00764        *
00765        *  This is a typical stack operation.  The function creates an
00766        *  element at the end of the %list and assigns the given data to
00767        *  it.  Due to the nature of a %list this operation can be done
00768        *  in constant time, and does not invalidate iterators and
00769        *  references.
00770        */
00771       void
00772       push_back(const value_type& __x)
00773       { this->_M_insert(end(), __x); }
00774 
00775       /**
00776        *  @brief  Removes last element.
00777        *
00778        *  This is a typical stack operation.  It shrinks the %list by
00779        *  one.  Due to the nature of a %list this operation can be done
00780        *  in constant time, and only invalidates iterators/references to
00781        *  the element being removed.
00782        *
00783        *  Note that no data is returned, and if the last element's data
00784        *  is needed, it should be retrieved before pop_back() is called.
00785        */
00786       void
00787       pop_back()
00788       { this->_M_erase(this->_M_impl._M_node._M_prev); }
00789 
00790       /**
00791        *  @brief  Inserts given value into %list before specified iterator.
00792        *  @param  position  An iterator into the %list.
00793        *  @param  x  Data to be inserted.
00794        *  @return  An iterator that points to the inserted data.
00795        *
00796        *  This function will insert a copy of the given value before
00797        *  the specified location.  Due to the nature of a %list this
00798        *  operation can be done in constant time, and does not
00799        *  invalidate iterators and references.
00800        */
00801       iterator
00802       insert(iterator __position, const value_type& __x);
00803 
00804       /**
00805        *  @brief  Inserts a number of copies of given data into the %list.
00806        *  @param  position  An iterator into the %list.
00807        *  @param  n  Number of elements to be inserted.
00808        *  @param  x  Data to be inserted.
00809        *
00810        *  This function will insert a specified number of copies of the
00811        *  given data before the location specified by @a position.
00812        *
00813        *  Due to the nature of a %list this operation can be done in
00814        *  constant time, and does not invalidate iterators and
00815        *  references.
00816        */
00817       void
00818       insert(iterator __position, size_type __n, const value_type& __x)
00819       { _M_fill_insert(__position, __n, __x); }
00820 
00821       /**
00822        *  @brief  Inserts a range into the %list.
00823        *  @param  position  An iterator into the %list.
00824        *  @param  first  An input iterator.
00825        *  @param  last   An input iterator.
00826        *
00827        *  This function will insert copies of the data in the range [@a
00828        *  first,@a last) into the %list before the location specified by
00829        *  @a position.
00830        *
00831        *  Due to the nature of a %list this operation can be done in
00832        *  constant time, and does not invalidate iterators and
00833        *  references.
00834        */
00835       template<typename _InputIterator>
00836         void
00837         insert(iterator __position, _InputIterator __first,
00838            _InputIterator __last)
00839         {
00840       // Check whether it's an integral type.  If so, it's not an iterator.
00841       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00842       _M_insert_dispatch(__position, __first, __last, _Integral());
00843     }
00844 
00845       /**
00846        *  @brief  Remove element at given position.
00847        *  @param  position  Iterator pointing to element to be erased.
00848        *  @return  An iterator pointing to the next element (or end()).
00849        *
00850        *  This function will erase the element at the given position and thus
00851        *  shorten the %list by one.
00852        *
00853        *  Due to the nature of a %list this operation can be done in
00854        *  constant time, and only invalidates iterators/references to
00855        *  the element being removed.  The user is also cautioned that
00856        *  this function only erases the element, and that if the element
00857        *  is itself a pointer, the pointed-to memory is not touched in
00858        *  any way.  Managing the pointer is the user's responsibilty.
00859        */
00860       iterator
00861       erase(iterator __position);
00862 
00863       /**
00864        *  @brief  Remove a range of elements.
00865        *  @param  first  Iterator pointing to the first element to be erased.
00866        *  @param  last  Iterator pointing to one past the last element to be
00867        *                erased.
00868        *  @return  An iterator pointing to the element pointed to by @a last
00869        *           prior to erasing (or end()).
00870        *
00871        *  This function will erase the elements in the range @a
00872        *  [first,last) and shorten the %list accordingly.
00873        *
00874        *  Due to the nature of a %list this operation can be done in
00875        *  constant time, and only invalidates iterators/references to
00876        *  the element being removed.  The user is also cautioned that
00877        *  this function only erases the elements, and that if the
00878        *  elements themselves are pointers, the pointed-to memory is not
00879        *  touched in any way.  Managing the pointer is the user's
00880        *  responsibilty.
00881        */
00882       iterator
00883       erase(iterator __first, iterator __last)
00884       {
00885     while (__first != __last)
00886       __first = erase(__first);
00887     return __last;
00888       }
00889 
00890       /**
00891        *  @brief  Swaps data with another %list.
00892        *  @param  x  A %list of the same element and allocator types.
00893        *
00894        *  This exchanges the elements between two lists in constant
00895        *  time.  Note that the global std::swap() function is
00896        *  specialized such that std::swap(l1,l2) will feed to this
00897        *  function.
00898        */
00899       void
00900       swap(list& __x)
00901       { _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node); }
00902 
00903       /**
00904        *  Erases all the elements.  Note that this function only erases
00905        *  the elements, and that if the elements themselves are
00906        *  pointers, the pointed-to memory is not touched in any way.
00907        *  Managing the pointer is the user's responsibilty.
00908        */
00909       void
00910       clear()
00911       {
00912         _Base::_M_clear();
00913         _Base::_M_init();
00914       }
00915 
00916       // [23.2.2.4] list operations
00917       /**
00918        *  @brief  Insert contents of another %list.
00919        *  @param  position  Iterator referencing the element to insert before.
00920        *  @param  x  Source list.
00921        *
00922        *  The elements of @a x are inserted in constant time in front of
00923        *  the element referenced by @a position.  @a x becomes an empty
00924        *  list.
00925        */
00926       void
00927       splice(iterator __position, list& __x)
00928       {
00929     if (!__x.empty())
00930       this->_M_transfer(__position, __x.begin(), __x.end());
00931       }
00932 
00933       /**
00934        *  @brief  Insert element from another %list.
00935        *  @param  position  Iterator referencing the element to insert before.
00936        *  @param  x  Source list.
00937        *  @param  i  Iterator referencing the element to move.
00938        *
00939        *  Removes the element in list @a x referenced by @a i and
00940        *  inserts it into the current list before @a position.
00941        */
00942       void
00943       splice(iterator __position, list&, iterator __i)
00944       {
00945     iterator __j = __i;
00946     ++__j;
00947     if (__position == __i || __position == __j)
00948       return;
00949     this->_M_transfer(__position, __i, __j);
00950       }
00951 
00952       /**
00953        *  @brief  Insert range from another %list.
00954        *  @param  position  Iterator referencing the element to insert before.
00955        *  @param  x  Source list.
00956        *  @param  first  Iterator referencing the start of range in x.
00957        *  @param  last  Iterator referencing the end of range in x.
00958        *
00959        *  Removes elements in the range [first,last) and inserts them
00960        *  before @a position in constant time.
00961        *
00962        *  Undefined if @a position is in [first,last).
00963        */
00964       void
00965       splice(iterator __position, list&, iterator __first, iterator __last)
00966       {
00967     if (__first != __last)
00968       this->_M_transfer(__position, __first, __last);
00969       }
00970 
00971       /**
00972        *  @brief  Remove all elements equal to value.
00973        *  @param  value  The value to remove.
00974        *
00975        *  Removes every element in the list equal to @a value.
00976        *  Remaining elements stay in list order.  Note that this
00977        *  function only erases the elements, and that if the elements
00978        *  themselves are pointers, the pointed-to memory is not
00979        *  touched in any way.  Managing the pointer is the user's
00980        *  responsibilty.
00981        */
00982       void
00983       remove(const _Tp& __value);
00984 
00985       /**
00986        *  @brief  Remove all elements satisfying a predicate.
00987        *  @param  Predicate  Unary predicate function or object.
00988        *
00989        *  Removes every element in the list for which the predicate
00990        *  returns true.  Remaining elements stay in list order.  Note
00991        *  that this function only erases the elements, and that if the
00992        *  elements themselves are pointers, the pointed-to memory is
00993        *  not touched in any way.  Managing the pointer is the user's
00994        *  responsibilty.
00995        */
00996       template<typename _Predicate>
00997       void
00998       remove_if(_Predicate);
00999 
01000       /**
01001        *  @brief  Remove consecutive duplicate elements.
01002        *
01003        *  For each consecutive set of elements with the same value,
01004        *  remove all but the first one.  Remaining elements stay in
01005        *  list order.  Note that this function only erases the
01006        *  elements, and that if the elements themselves are pointers,
01007        *  the pointed-to memory is not touched in any way.  Managing
01008        *  the pointer is the user's responsibilty.
01009        */
01010       void
01011       unique();
01012 
01013       /**
01014        *  @brief  Remove consecutive elements satisfying a predicate.
01015        *  @param  BinaryPredicate  Binary predicate function or object.
01016        *
01017        *  For each consecutive set of elements [first,last) that
01018        *  satisfy predicate(first,i) where i is an iterator in
01019        *  [first,last), remove all but the first one.  Remaining
01020        *  elements stay in list order.  Note that this function only
01021        *  erases the elements, and that if the elements themselves are
01022        *  pointers, the pointed-to memory is not touched in any way.
01023        *  Managing the pointer is the user's responsibilty.
01024        */
01025       template<typename _BinaryPredicate>
01026         void
01027         unique(_BinaryPredicate);
01028 
01029       /**
01030        *  @brief  Merge sorted lists.
01031        *  @param  x  Sorted list to merge.
01032        *
01033        *  Assumes that both @a x and this list are sorted according to
01034        *  operator<().  Merges elements of @a x into this list in
01035        *  sorted order, leaving @a x empty when complete.  Elements in
01036        *  this list precede elements in @a x that are equal.
01037        */
01038       void
01039       merge(list& __x);
01040 
01041       /**
01042        *  @brief  Merge sorted lists according to comparison function.
01043        *  @param  x  Sorted list to merge.
01044        *  @param StrictWeakOrdering Comparison function definining
01045        *  sort order.
01046        *
01047        *  Assumes that both @a x and this list are sorted according to
01048        *  StrictWeakOrdering.  Merges elements of @a x into this list
01049        *  in sorted order, leaving @a x empty when complete.  Elements
01050        *  in this list precede elements in @a x that are equivalent
01051        *  according to StrictWeakOrdering().
01052        */
01053       template<typename _StrictWeakOrdering>
01054         void
01055         merge(list&, _StrictWeakOrdering);
01056 
01057       /**
01058        *  @brief  Reverse the elements in list.
01059        *
01060        *  Reverse the order of elements in the list in linear time.
01061        */
01062       void
01063       reverse()
01064       { this->_M_impl._M_node.reverse(); }
01065 
01066       /**
01067        *  @brief  Sort the elements.
01068        *
01069        *  Sorts the elements of this list in NlogN time.  Equivalent
01070        *  elements remain in list order.
01071        */
01072       void
01073       sort();
01074 
01075       /**
01076        *  @brief  Sort the elements according to comparison function.
01077        *
01078        *  Sorts the elements of this list in NlogN time.  Equivalent
01079        *  elements remain in list order.
01080        */
01081       template<typename _StrictWeakOrdering>
01082         void
01083         sort(_StrictWeakOrdering);
01084 
01085     protected:
01086       // Internal assign functions follow.
01087 
01088       // Called by the range assign to implement [23.1.1]/9
01089       template<typename _Integer>
01090         void
01091         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01092         {
01093       _M_fill_assign(static_cast<size_type>(__n),
01094              static_cast<value_type>(__val));
01095     }
01096 
01097       // Called by the range assign to implement [23.1.1]/9
01098       template<typename _InputIterator>
01099         void
01100         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01101                __false_type);
01102 
01103       // Called by assign(n,t), and the range assign when it turns out
01104       // to be the same thing.
01105       void
01106       _M_fill_assign(size_type __n, const value_type& __val);
01107 
01108 
01109       // Internal insert functions follow.
01110 
01111       // Called by the range insert to implement [23.1.1]/9
01112       template<typename _Integer>
01113         void
01114         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
01115                __true_type)
01116         {
01117       _M_fill_insert(__pos, static_cast<size_type>(__n),
01118              static_cast<value_type>(__x));
01119     }
01120 
01121       // Called by the range insert to implement [23.1.1]/9
01122       template<typename _InputIterator>
01123         void
01124         _M_insert_dispatch(iterator __pos,
01125                _InputIterator __first, _InputIterator __last,
01126                __false_type)
01127         {
01128       for (; __first != __last; ++__first)
01129         _M_insert(__pos, *__first);
01130     }
01131 
01132       // Called by insert(p,n,x), and the range insert when it turns out
01133       // to be the same thing.
01134       void
01135       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
01136       {
01137     for (; __n > 0; --__n)
01138       _M_insert(__pos, __x);
01139       }
01140 
01141 
01142       // Moves the elements from [first,last) before position.
01143       void
01144       _M_transfer(iterator __position, iterator __first, iterator __last)
01145       { __position._M_node->transfer(__first._M_node, __last._M_node); }
01146 
01147       // Inserts new element at position given and with value given.
01148       void
01149       _M_insert(iterator __position, const value_type& __x)
01150       {
01151         _Node* __tmp = _M_create_node(__x);
01152         __tmp->hook(__position._M_node);
01153       }
01154 
01155       // Erases element at position given.
01156       void
01157       _M_erase(iterator __position)
01158       {
01159         __position._M_node->unhook();
01160         _Node* __n = static_cast<_Node*>(__position._M_node);
01161         this->get_allocator().destroy(&__n->_M_data);
01162         _M_put_node(__n);
01163       }
01164     };
01165 
01166   /**
01167    *  @brief  List equality comparison.
01168    *  @param  x  A %list.
01169    *  @param  y  A %list of the same type as @a x.
01170    *  @return  True iff the size and elements of the lists are equal.
01171    *
01172    *  This is an equivalence relation.  It is linear in the size of
01173    *  the lists.  Lists are considered equivalent if their sizes are
01174    *  equal, and if corresponding elements compare equal.
01175   */
01176   template<typename _Tp, typename _Alloc>
01177     inline bool
01178     operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01179     {
01180       typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
01181       const_iterator __end1 = __x.end();
01182       const_iterator __end2 = __y.end();
01183 
01184       const_iterator __i1 = __x.begin();
01185       const_iterator __i2 = __y.begin();
01186       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
01187     {
01188       ++__i1;
01189       ++__i2;
01190     }
01191       return __i1 == __end1 && __i2 == __end2;
01192     }
01193 
01194   /**
01195    *  @brief  List ordering relation.
01196    *  @param  x  A %list.
01197    *  @param  y  A %list of the same type as @a x.
01198    *  @return  True iff @a x is lexicographically less than @a y.
01199    *
01200    *  This is a total ordering relation.  It is linear in the size of the
01201    *  lists.  The elements must be comparable with @c <.
01202    *
01203    *  See std::lexicographical_compare() for how the determination is made.
01204   */
01205   template<typename _Tp, typename _Alloc>
01206     inline bool
01207     operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01208     { return std::lexicographical_compare(__x.begin(), __x.end(),
01209                       __y.begin(), __y.end()); }
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 !(__x == __y); }
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 __y < __x; }
01222 
01223   /// Based on operator<
01224   template<typename _Tp, typename _Alloc>
01225     inline bool
01226     operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01227     { return !(__y < __x); }
01228 
01229   /// Based on operator<
01230   template<typename _Tp, typename _Alloc>
01231     inline bool
01232     operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
01233     { return !(__x < __y); }
01234 
01235   /// See std::list::swap().
01236   template<typename _Tp, typename _Alloc>
01237     inline void
01238     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
01239     { __x.swap(__y); }
01240 } // namespace std
01241 
01242 #endif /* _LIST_H */
01243 

Generated on Sat Apr 2 13:54:44 2005 for libstdc++ source by  doxygen 1.4.0