stl_list.h

Go to the documentation of this file.
00001 // List implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 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 __GLIBCPP_INTERNAL_LIST_H
00062 #define __GLIBCPP_INTERNAL_LIST_H
00063 
00064 #include <bits/concept_check.h>
00065 
00066 namespace 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   
00080   /// @if maint An actual node in the %list.  @endif
00081   template<typename _Tp>
00082     struct _List_node : public _List_node_base
00083   {
00084     _Tp _M_data;                ///< User's data.
00085   };
00086   
00087   
00088   /**
00089    *  @if maint
00090    *  @brief Common part of a list::iterator.
00091    *
00092    *  A simple type to walk a doubly-linked list.  All operations here should
00093    *  be self-explanatory after taking any decent introductory data structures
00094    *  course.
00095    *  @endif
00096   */
00097   struct _List_iterator_base
00098   {
00099     typedef size_t                        size_type;
00100     typedef ptrdiff_t                     difference_type;
00101     typedef bidirectional_iterator_tag    iterator_category;
00102   
00103     /// The only member points to the %list element.
00104     _List_node_base* _M_node;
00105   
00106     _List_iterator_base(_List_node_base* __x)
00107     : _M_node(__x)
00108     { }
00109   
00110     _List_iterator_base()
00111     : _M_node()
00112     { }
00113   
00114     /// Walk the %list forward.
00115     void
00116     _M_incr()
00117     { _M_node = _M_node->_M_next; }
00118   
00119     /// Walk the %list backward.
00120     void
00121     _M_decr()
00122     { _M_node = _M_node->_M_prev; }
00123   
00124     bool
00125     operator==(const _List_iterator_base& __x) const
00126     { return _M_node == __x._M_node; }
00127   
00128     bool
00129     operator!=(const _List_iterator_base& __x) const
00130     { return _M_node != __x._M_node; }
00131   };
00132   
00133   /**
00134    *  @brief A list::iterator.
00135    *
00136    *  In addition to being used externally, a list holds one of these
00137    *  internally, pointing to the sequence of data.
00138    *
00139    *  @if maint
00140    *  All the functions are op overloads.
00141    *  @endif
00142   */
00143   template<typename _Tp, typename _Ref, typename _Ptr>
00144     struct _List_iterator : public _List_iterator_base
00145   {
00146     typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
00147     typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00148     typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;
00149   
00150     typedef _Tp                                       value_type;
00151     typedef _Ptr                                      pointer;
00152     typedef _Ref                                      reference;
00153     typedef _List_node<_Tp>                           _Node;
00154   
00155     _List_iterator(_Node* __x)
00156     : _List_iterator_base(__x)
00157     { }
00158   
00159     _List_iterator()
00160     : _List_iterator_base()
00161     { }
00162   
00163     _List_iterator(const iterator& __x)
00164     : _List_iterator_base(__x._M_node)
00165     { }
00166   
00167     reference
00168     operator*() const
00169     { return static_cast<_Node*>(_M_node)->_M_data; }
00170     // Must downcast from List_node_base to _List_node to get to _M_data.
00171   
00172     pointer
00173     operator->() const
00174     { return &(operator*()); }
00175   
00176     _Self&
00177     operator++()
00178     {
00179       this->_M_incr();
00180       return *this;
00181     }
00182   
00183     _Self
00184     operator++(int)
00185     {
00186       _Self __tmp = *this;
00187       this->_M_incr();
00188       return __tmp;
00189     }
00190   
00191     _Self&
00192     operator--()
00193     {
00194       this->_M_decr();
00195       return *this;
00196     }
00197   
00198     _Self
00199     operator--(int)
00200     {
00201       _Self __tmp = *this;
00202       this->_M_decr();
00203       return __tmp;
00204     }
00205   };
00206   
00207   
00208   /// @if maint Primary default version.  @endif
00209   /**
00210    *  @if maint
00211    *  See bits/stl_deque.h's _Deque_alloc_base for an explanation.
00212    *  @endif
00213   */
00214   template<typename _Tp, typename _Allocator, bool _IsStatic>
00215     class _List_alloc_base
00216   {
00217   public:
00218     typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00219             allocator_type;
00220   
00221     allocator_type
00222     get_allocator() const { return _M_node_allocator; }
00223   
00224     _List_alloc_base(const allocator_type& __a)
00225     : _M_node_allocator(__a)
00226     { }
00227   
00228   protected:
00229     _List_node<_Tp>*
00230     _M_get_node()
00231     { return _M_node_allocator.allocate(1); }
00232   
00233     void
00234     _M_put_node(_List_node<_Tp>* __p)
00235     { _M_node_allocator.deallocate(__p, 1); }
00236   
00237     // NOTA BENE
00238     // The stored instance is not actually of "allocator_type"'s type.  Instead
00239     // we rebind the type to Allocator<List_node<Tp>>, which according to
00240     // [20.1.5]/4 should probably be the same.  List_node<Tp> is not the same
00241     // size as Tp (it's two pointers larger), and specializations on Tp may go
00242     // unused because List_node<Tp> is being bound instead.
00243     //
00244     // We put this to the test in get_allocator above; if the two types are
00245     // actually different, there had better be a conversion between them.
00246     //
00247     // None of the predefined allocators shipped with the library (as of 3.1)
00248     // use this instantiation anyhow; they're all instanceless.
00249     typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
00250              _M_node_allocator;
00251   
00252     _List_node<_Tp>* _M_node;
00253   };
00254   
00255   /// @if maint Specialization for instanceless allocators.  @endif
00256   template<typename _Tp, typename _Allocator>
00257     class _List_alloc_base<_Tp, _Allocator, true>
00258   {
00259   public:
00260     typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00261             allocator_type;
00262   
00263     allocator_type
00264     get_allocator() const { return allocator_type(); }
00265   
00266     _List_alloc_base(const allocator_type&)
00267     { }
00268   
00269   protected:
00270     // See comment in primary template class about why this is safe for the
00271     // standard predefined classes.
00272     typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
00273             _Alloc_type;
00274   
00275     _List_node<_Tp>*
00276     _M_get_node()
00277     { return _Alloc_type::allocate(1); }
00278   
00279     void
00280     _M_put_node(_List_node<_Tp>* __p)
00281     { _Alloc_type::deallocate(__p, 1); }
00282   
00283     _List_node<_Tp>* _M_node;
00284   };
00285   
00286   
00287   /**
00288    *  @if maint
00289    *  See bits/stl_deque.h's _Deque_base for an explanation.
00290    *  @endif
00291   */
00292   template <typename _Tp, typename _Alloc>
00293     class _List_base
00294     : public _List_alloc_base<_Tp, _Alloc,
00295                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00296   {
00297   public:
00298     typedef _List_alloc_base<_Tp, _Alloc,
00299                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00300             _Base;
00301     typedef typename _Base::allocator_type allocator_type;
00302   
00303     _List_base(const allocator_type& __a)
00304     : _Base(__a)
00305     {
00306       _M_node = _M_get_node();
00307       _M_node->_M_next = _M_node;
00308       _M_node->_M_prev = _M_node;
00309     }
00310   
00311     // This is what actually destroys the list.
00312     ~_List_base()
00313     {
00314       __clear();
00315       _M_put_node(_M_node);
00316     }
00317   
00318     void
00319     __clear();
00320   };
00321   
00322   
00323   /**
00324    *  @brief  A standard container with linear time access to elements, and
00325    *  fixed time insertion/deletion at any point in the sequence.
00326    *
00327    *  @ingroup Containers
00328    *  @ingroup Sequences
00329    *
00330    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00331    *  <a href="tables.html#66">reversible container</a>, and a
00332    *  <a href="tables.html#67">sequence</a>, including the
00333    *  <a href="tables.html#68">optional sequence requirements</a> with the
00334    *  %exception of @c at and @c operator[].
00335    *
00336    *  This is a @e doubly @e linked %list.  Traversal up and down the %list
00337    *  requires linear time, but adding and removing elements (or @e nodes) is
00338    *  done in constant time, regardless of where the change takes place.
00339    *  Unlike std::vector and std::deque, random-access iterators are not
00340    *  provided, so subscripting ( @c [] ) access is not allowed.  For algorithms
00341    *  which only need sequential access, this lack makes no difference.
00342    *
00343    *  Also unlike the other standard containers, std::list provides specialized 
00344    *  algorithms %unique to linked lists, such as splicing, sorting, and
00345    *  in-place reversal.
00346    *
00347    *  @if maint
00348    *  A couple points on memory allocation for list<Tp>:
00349    *
00350    *  First, we never actually allocate a Tp, we allocate List_node<Tp>'s
00351    *  and trust [20.1.5]/4 to DTRT.  This is to ensure that after elements from
00352    *  %list<X,Alloc1> are spliced into %list<X,Alloc2>, destroying the memory of
00353    *  the second %list is a valid operation, i.e., Alloc1 giveth and Alloc2
00354    *  taketh away.
00355    *
00356    *  Second, a %list conceptually represented as
00357    *  @code
00358    *    A <---> B <---> C <---> D
00359    *  @endcode
00360    *  is actually circular; a link exists between A and D.  The %list class
00361    *  holds (as its only data member) a private list::iterator pointing to
00362    *  @e D, not to @e A!  To get to the head of the %list, we start at the tail
00363    *  and move forward by one.  When this member iterator's next/previous
00364    *  pointers refer to itself, the %list is %empty.
00365    *  @endif
00366   */
00367   template<typename _Tp, typename _Alloc = allocator<_Tp> >
00368     class list : protected _List_base<_Tp, _Alloc>
00369   {
00370     // concept requirements
00371     __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00372   
00373     typedef _List_base<_Tp, _Alloc>                       _Base;
00374   
00375   public:
00376     typedef _Tp                                           value_type;
00377     typedef value_type*                                   pointer;
00378     typedef const value_type*                             const_pointer;
00379     typedef _List_iterator<_Tp,_Tp&,_Tp*>                 iterator;
00380     typedef _List_iterator<_Tp,const _Tp&,const _Tp*>     const_iterator;
00381     typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00382     typedef std::reverse_iterator<iterator>                 reverse_iterator;
00383     typedef value_type&                                   reference;
00384     typedef const value_type&                             const_reference;
00385     typedef size_t                                        size_type;
00386     typedef ptrdiff_t                                     difference_type;
00387     typedef typename _Base::allocator_type                allocator_type;
00388   
00389   protected:
00390     // Note that pointers-to-_Node's can be ctor-converted to iterator types.
00391     typedef _List_node<_Tp>                               _Node;
00392   
00393     /** @if maint
00394      *  One data member plus two memory-handling functions.  If the _Alloc
00395      *  type requires separate instances, then one of those will also be
00396      *  included, accumulated from the topmost parent.
00397      *  @endif
00398     */
00399     using _Base::_M_node;
00400     using _Base::_M_put_node;
00401     using _Base::_M_get_node;
00402   
00403     /**
00404      *  @if maint
00405      *  @param  x  An instance of user data.
00406      *
00407      *  Allocates space for a new node and constructs a copy of @a x in it.
00408      *  @endif
00409     */
00410     _Node*
00411     _M_create_node(const value_type& __x)
00412     {
00413       _Node* __p = _M_get_node();
00414       try {
00415         _Construct(&__p->_M_data, __x);
00416       }
00417       catch(...)
00418       {
00419         _M_put_node(__p);
00420         __throw_exception_again;
00421       }
00422       return __p;
00423     }
00424   
00425     /**
00426      *  @if maint
00427      *  Allocates space for a new node and default-constructs a new instance
00428      *  of @c value_type in it.
00429      *  @endif
00430     */
00431     _Node*
00432     _M_create_node()
00433     {
00434       _Node* __p = _M_get_node();
00435       try {
00436         _Construct(&__p->_M_data);
00437       }
00438       catch(...)
00439       {
00440         _M_put_node(__p);
00441         __throw_exception_again;
00442       }
00443       return __p;
00444     }
00445   
00446   public:
00447     // [23.2.2.1] construct/copy/destroy
00448     // (assign() and get_allocator() are also listed in this section)
00449     /**
00450      *  @brief  Default constructor creates no elements.
00451     */
00452     explicit
00453     list(const allocator_type& __a = allocator_type())
00454     : _Base(__a) { }
00455   
00456     /**
00457      *  @brief  Create a %list with copies of an exemplar element.
00458      *  @param  n  The number of elements to initially create.
00459      *  @param  value  An element to copy.
00460      * 
00461      *  This constructor fills the %list with @a n copies of @a value.
00462     */
00463     list(size_type __n, const value_type& __value,
00464          const allocator_type& __a = allocator_type())
00465       : _Base(__a)
00466       { this->insert(begin(), __n, __value); }
00467   
00468     /**
00469      *  @brief  Create a %list with default elements.
00470      *  @param  n  The number of elements to initially create.
00471      * 
00472      *  This constructor fills the %list with @a n copies of a
00473      *  default-constructed element.
00474     */
00475     explicit
00476     list(size_type __n)
00477       : _Base(allocator_type())
00478       { this->insert(begin(), __n, value_type()); }
00479   
00480     /**
00481      *  @brief  %List copy constructor.
00482      *  @param  x  A %list of identical element and allocator types.
00483      * 
00484      *  The newly-created %list uses a copy of the allocation object used
00485      *  by @a x.
00486     */
00487     list(const list& __x)
00488       : _Base(__x.get_allocator())
00489       { this->insert(begin(), __x.begin(), __x.end()); }
00490   
00491     /**
00492      *  @brief  Builds a %list from a range.
00493      *  @param  first  An input iterator.
00494      *  @param  last  An input iterator.
00495      * 
00496      *  Create a %list consisting of copies of the elements from [first,last).
00497      *  This is linear in N (where N is distance(first,last)).
00498      *
00499      *  @if maint
00500      *  We don't need any dispatching tricks here, because insert does all of
00501      *  that anyway.
00502      *  @endif
00503     */
00504     template<typename _InputIterator>
00505       list(_InputIterator __first, _InputIterator __last,
00506            const allocator_type& __a = allocator_type())
00507       : _Base(__a)
00508       { this->insert(begin(), __first, __last); }
00509   
00510     /**
00511      *  The dtor only erases the elements, and note that if the elements
00512      *  themselves are pointers, the pointed-to memory is not touched in any
00513      *  way.  Managing the pointer is the user's responsibilty.
00514     */
00515     ~list() { }
00516   
00517     /**
00518      *  @brief  %List assignment operator.
00519      *  @param  x  A %list of identical element and allocator types.
00520      * 
00521      *  All the elements of @a x are copied, but unlike the copy constructor,
00522      *  the allocator object is not copied.
00523     */
00524     list&
00525     operator=(const list& __x);
00526   
00527     /**
00528      *  @brief  Assigns a given value to a %list.
00529      *  @param  n  Number of elements to be assigned.
00530      *  @param  val  Value to be assigned.
00531      *
00532      *  This function fills a %list with @a n copies of the given value.
00533      *  Note that the assignment completely changes the %list and that the
00534      *  resulting %list's size is the same as the number of elements assigned.
00535      *  Old data may be lost.
00536     */
00537     void
00538     assign(size_type __n, const value_type& __val) { _M_fill_assign(__n, __val); }
00539   
00540     /**
00541      *  @brief  Assigns a range to a %list.
00542      *  @param  first  An input iterator.
00543      *  @param  last   An input iterator.
00544      *
00545      *  This function fills a %list with copies of the elements in the
00546      *  range [first,last).
00547      *
00548      *  Note that the assignment completely changes the %list and that the
00549      *  resulting %list's size is the same as the number of elements assigned.
00550      *  Old data may be lost.
00551     */
00552     template<typename _InputIterator>
00553       void
00554       assign(_InputIterator __first, _InputIterator __last)
00555       {
00556         // Check whether it's an integral type.  If so, it's not an iterator.
00557         typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00558         _M_assign_dispatch(__first, __last, _Integral());
00559       }
00560   
00561     /// Get a copy of the memory allocation object.
00562     allocator_type
00563     get_allocator() const { return _Base::get_allocator(); }
00564   
00565     // iterators
00566     /**
00567      *  Returns a read/write iterator that points to the first element in the
00568      *  %list.  Iteration is done in ordinary element order.
00569     */
00570     iterator
00571     begin() { return static_cast<_Node*>(_M_node->_M_next); }
00572   
00573     /**
00574      *  Returns a read-only (constant) iterator that points to the first element
00575      *  in the %list.  Iteration is done in ordinary element order.
00576     */
00577     const_iterator
00578     begin() const { return static_cast<_Node*>(_M_node->_M_next); }
00579   
00580     /**
00581      *  Returns a read/write iterator that points one past the last element in
00582      *  the %list.  Iteration is done in ordinary element order.
00583     */
00584     iterator
00585     end() { return _M_node; }
00586   
00587     /**
00588      *  Returns a read-only (constant) iterator that points one past the last
00589      *  element in the %list.  Iteration is done in ordinary element order.
00590     */
00591     const_iterator
00592     end() const { return _M_node; }
00593   
00594     /**
00595      *  Returns a read/write reverse iterator that points to the last element in
00596      *  the %list.  Iteration is done in reverse element order.
00597     */
00598     reverse_iterator
00599     rbegin() { return reverse_iterator(end()); }
00600   
00601     /**
00602      *  Returns a read-only (constant) reverse iterator that points to the last
00603      *  element in the %list.  Iteration is done in reverse element order.
00604     */
00605     const_reverse_iterator
00606     rbegin() const { return const_reverse_iterator(end()); }
00607   
00608     /**
00609      *  Returns a read/write reverse iterator that points to one before the
00610      *  first element in the %list.  Iteration is done in reverse element
00611      *  order.
00612     */
00613     reverse_iterator
00614     rend() { return reverse_iterator(begin()); }
00615   
00616     /**
00617      *  Returns a read-only (constant) reverse iterator that points to one
00618      *  before the first element in the %list.  Iteration is done in reverse
00619      *  element order.
00620     */
00621     const_reverse_iterator
00622     rend() const
00623     { return const_reverse_iterator(begin()); }
00624   
00625     // [23.2.2.2] capacity
00626     /**
00627      *  Returns true if the %list is empty.  (Thus begin() would equal end().)
00628     */
00629     bool
00630     empty() const { return _M_node->_M_next == _M_node; }
00631   
00632     /**  Returns the number of elements in the %list.  */
00633     size_type
00634     size() const { return distance(begin(), end()); }
00635   
00636     /**  Returns the size() of the largest possible %list.  */
00637     size_type
00638     max_size() const { return size_type(-1); }
00639   
00640     /**
00641      *  @brief  Resizes the %list to the specified number of elements.
00642      *  @param  new_size  Number of elements the %list should contain.
00643      *  @param  x  Data with which new elements should be populated.
00644      *
00645      *  This function will %resize the %list to the specified number of
00646      *  elements.  If the number is smaller than the %list's current size the
00647      *  %list is truncated, otherwise the %list is extended and new elements
00648      *  are populated with given data.
00649     */
00650     void
00651     resize(size_type __new_size, const value_type& __x);
00652   
00653     /**
00654      *  @brief  Resizes the %list to the specified number of elements.
00655      *  @param  new_size  Number of elements the %list should contain.
00656      *
00657      *  This function will resize the %list to the specified number of
00658      *  elements.  If the number is smaller than the %list's current size the
00659      *  %list is truncated, otherwise the %list is extended and new elements
00660      *  are default-constructed.
00661     */
00662     void
00663     resize(size_type __new_size) { this->resize(__new_size, value_type()); }
00664   
00665     // element access
00666     /**
00667      *  Returns a read/write reference to the data at the first element of the
00668      *  %list.
00669     */
00670     reference
00671     front() { return *begin(); }
00672   
00673     /**
00674      *  Returns a read-only (constant) reference to the data at the first
00675      *  element of the %list.
00676     */
00677     const_reference
00678     front() const { return *begin(); }
00679   
00680     /**
00681      *  Returns a read/write reference to the data at the last element of the
00682      *  %list.
00683     */
00684     reference
00685     back() { return *(--end()); }
00686   
00687     /**
00688      *  Returns a read-only (constant) reference to the data at the last
00689      *  element of the %list.
00690     */
00691     const_reference
00692     back() const { return *(--end()); }
00693   
00694     // [23.2.2.3] modifiers
00695     /**
00696      *  @brief  Add data to the front of the %list.
00697      *  @param  x  Data to be added.
00698      *
00699      *  This is a typical stack operation.  The function creates an element at
00700      *  the front of the %list and assigns the given data to it.  Due to the
00701      *  nature of a %list this operation can be done in constant time, and
00702      *  does not invalidate iterators and references.
00703     */
00704     void
00705     push_front(const value_type& __x) { this->insert(begin(), __x); }
00706   
00707   #ifdef _GLIBCPP_DEPRECATED
00708     /**
00709      *  @brief  Add data to the front of the %list.
00710      *
00711      *  This is a typical stack operation.  The function creates a
00712      *  default-constructed element at the front of the %list.  Due to the
00713      *  nature of a %list this operation can be done in constant time.  You
00714      *  should consider using push_front(value_type()) instead.
00715      *
00716      *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
00717      *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
00718      *        c++config.h.
00719     */
00720     void
00721     push_front() { this->insert(begin(), value_type()); }
00722   #endif
00723   
00724     /**
00725      *  @brief  Removes first element.
00726      *
00727      *  This is a typical stack operation.  It shrinks the %list by one.
00728      *  Due to the nature of a %list this operation can be done in constant
00729      *  time, and only invalidates iterators/references to the element being
00730      *  removed.
00731      *
00732      *  Note that no data is returned, and if the first element's data is
00733      *  needed, it should be retrieved before pop_front() is called.
00734     */
00735     void
00736     pop_front() { this->erase(begin()); }
00737   
00738     /**
00739      *  @brief  Add data to the end of the %list.
00740      *  @param  x  Data to be added.
00741      *
00742      *  This is a typical stack operation.  The function creates an element at
00743      *  the end of the %list and assigns the given data to it.  Due to the
00744      *  nature of a %list this operation can be done in constant time, and
00745      *  does not invalidate iterators and references.
00746     */
00747     void
00748     push_back(const value_type& __x) { this->insert(end(), __x); }
00749   
00750   #ifdef _GLIBCPP_DEPRECATED
00751     /**
00752      *  @brief  Add data to the end of the %list.
00753      *
00754      *  This is a typical stack operation.  The function creates a
00755      *  default-constructed element at the end of the %list.  Due to the nature
00756      *  of a %list this operation can be done in constant time.  You should
00757      *  consider using push_back(value_type()) instead.
00758      *
00759      *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
00760      *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
00761      *        c++config.h.
00762     */
00763     void
00764     push_back() { this->insert(end(), value_type()); }
00765   #endif
00766   
00767     /**
00768      *  @brief  Removes last element.
00769      *
00770      *  This is a typical stack operation.  It shrinks the %list by one.
00771      *  Due to the nature of a %list this operation can be done in constant
00772      *  time, and only invalidates iterators/references to the element being
00773      *  removed.
00774      *
00775      *  Note that no data is returned, and if the last element's data is
00776      *  needed, it should be retrieved before pop_back() is called.
00777     */
00778     void
00779     pop_back()
00780     {
00781       iterator __tmp = end();
00782       this->erase(--__tmp);
00783     }
00784   
00785     /**
00786      *  @brief  Inserts given value into %list before specified iterator.
00787      *  @param  position  An iterator into the %list.
00788      *  @param  x  Data to be inserted.
00789      *  @return  An iterator that points to the inserted data.
00790      *
00791      *  This function will insert a copy of the given value before the specified
00792      *  location.
00793      *  Due to the nature of a %list this operation can be done in constant
00794      *  time, and does not invalidate iterators and references.
00795     */
00796     iterator
00797     insert(iterator __position, const value_type& __x);
00798   
00799   #ifdef _GLIBCPP_DEPRECATED
00800     /**
00801      *  @brief  Inserts an element into the %list.
00802      *  @param  position  An iterator into the %list.
00803      *  @return  An iterator that points to the inserted element.
00804      *
00805      *  This function will insert a default-constructed element before the
00806      *  specified location.  You should consider using
00807      *  insert(position,value_type()) instead.
00808      *  Due to the nature of a %list this operation can be done in constant
00809      *  time, and does not invalidate iterators and references.
00810      *
00811      *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
00812      *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
00813      *        c++config.h.
00814     */
00815     iterator
00816     insert(iterator __position) { return insert(__position, value_type()); }
00817   #endif
00818   
00819     /**
00820      *  @brief  Inserts a number of copies of given data into the %list.
00821      *  @param  position  An iterator into the %list.
00822      *  @param  n  Number of elements to be inserted.
00823      *  @param  x  Data to be inserted.
00824      *
00825      *  This function will insert a specified number of copies of the given data
00826      *  before the location specified by @a position.
00827      *
00828      *  Due to the nature of a %list this operation can be done in constant
00829      *  time, and does not invalidate iterators and references.
00830     */
00831     void
00832     insert(iterator __pos, size_type __n, const value_type& __x)
00833     { _M_fill_insert(__pos, __n, __x); }
00834   
00835     /**
00836      *  @brief  Inserts a range into the %list.
00837      *  @param  pos  An iterator into the %list.
00838      *  @param  first  An input iterator.
00839      *  @param  last   An input iterator.
00840      *
00841      *  This function will insert copies of the data in the range [first,last)
00842      *  into the %list before the location specified by @a pos.
00843      *
00844      *  Due to the nature of a %list this operation can be done in constant
00845      *  time, and does not invalidate iterators and references.
00846     */
00847     template<typename _InputIterator>
00848       void
00849       insert(iterator __pos, _InputIterator __first, _InputIterator __last)
00850       {
00851         // Check whether it's an integral type.  If so, it's not an iterator.
00852         typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00853         _M_insert_dispatch(__pos, __first, __last, _Integral());
00854       }
00855   
00856     /**
00857      *  @brief  Remove element at given position.
00858      *  @param  position  Iterator pointing to element to be erased.
00859      *  @return  An iterator pointing to the next element (or end()).
00860      *
00861      *  This function will erase the element at the given position and thus
00862      *  shorten the %list by one.
00863      *
00864      *  Due to the nature of a %list this operation can be done in constant
00865      *  time, and only invalidates iterators/references to the element being
00866      *  removed.
00867      *  The user is also cautioned that
00868      *  this function only erases the element, and that if the element is itself
00869      *  a pointer, the pointed-to memory is not touched in any way.  Managing
00870      *  the pointer is the user's responsibilty.
00871     */
00872     iterator
00873     erase(iterator __position);
00874   
00875     /**
00876      *  @brief  Remove a range of elements.
00877      *  @param  first  Iterator pointing to the first element to be erased.
00878      *  @param  last  Iterator pointing to one past the last element to be
00879      *                erased.
00880      *  @return  An iterator pointing to the element pointed to by @a last
00881      *           prior to erasing (or end()).
00882      *
00883      *  This function will erase the elements in the range [first,last) and
00884      *  shorten the %list accordingly.
00885      *
00886      *  Due to the nature of a %list this operation can be done in constant
00887      *  time, and only invalidates iterators/references to the element being
00888      *  removed.
00889      *  The user is also cautioned that
00890      *  this function only erases the elements, and that if the elements
00891      *  themselves are pointers, the pointed-to memory is not touched in any
00892      *  way.  Managing the pointer is the user's responsibilty.
00893     */
00894     iterator
00895     erase(iterator __first, iterator __last)
00896     {
00897       while (__first != __last)
00898         erase(__first++);
00899       return __last;
00900     }
00901   
00902     /**
00903      *  @brief  Swaps data with another %list.
00904      *  @param  x  A %list of the same element and allocator types.
00905      *
00906      *  This exchanges the elements between two lists in constant time.
00907      *  (It is only swapping a single pointer, so it should be quite fast.)
00908      *  Note that the global std::swap() function is specialized such that
00909      *  std::swap(l1,l2) will feed to this function.
00910     */
00911     void
00912     swap(list& __x) { std::swap(_M_node, __x._M_node); }
00913   
00914     /**
00915      *  Erases all the elements.  Note that this function only erases the
00916      *  elements, and that if the elements themselves are pointers, the
00917      *  pointed-to memory is not touched in any way.  Managing the pointer is
00918      *  the user's responsibilty.
00919     */
00920     void
00921     clear() { _Base::__clear(); }
00922   
00923     // [23.2.2.4] list operations
00924     /**
00925      *  @doctodo
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      *  @doctodo
00936     */
00937     void
00938     splice(iterator __position, list&, iterator __i)
00939     {
00940       iterator __j = __i;
00941       ++__j;
00942       if (__position == __i || __position == __j) return;
00943       this->_M_transfer(__position, __i, __j);
00944     }
00945   
00946     /**
00947      *  @doctodo
00948     */
00949     void
00950     splice(iterator __position, list&, iterator __first, iterator __last)
00951     {
00952       if (__first != __last)
00953         this->_M_transfer(__position, __first, __last);
00954     }
00955   
00956     /**
00957      *  @doctodo
00958     */
00959     void
00960     remove(const _Tp& __value);
00961   
00962     /**
00963      *  @doctodo
00964     */
00965     template<typename _Predicate>
00966       void
00967       remove_if(_Predicate);
00968   
00969     /**
00970      *  @doctodo
00971     */
00972     void
00973     unique();
00974   
00975     /**
00976      *  @doctodo
00977     */
00978     template<typename _BinaryPredicate>
00979       void
00980       unique(_BinaryPredicate);
00981   
00982     /**
00983      *  @doctodo
00984     */
00985     void
00986     merge(list& __x);
00987   
00988     /**
00989      *  @doctodo
00990     */
00991     template<typename _StrictWeakOrdering>
00992       void
00993       merge(list&, _StrictWeakOrdering);
00994   
00995     /**
00996      *  @doctodo
00997     */
00998     void
00999     reverse() { __List_base_reverse(this->_M_node); }
01000   
01001     /**
01002      *  @doctodo
01003     */
01004     void
01005     sort();
01006   
01007     /**
01008      *  @doctodo
01009     */
01010     template<typename _StrictWeakOrdering>
01011       void
01012       sort(_StrictWeakOrdering);
01013   
01014   protected:
01015     // Internal assign functions follow.
01016   
01017     // called by the range assign to implement [23.1.1]/9
01018     template<typename _Integer>
01019       void
01020       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01021       {
01022         _M_fill_assign(static_cast<size_type>(__n),
01023                        static_cast<value_type>(__val));
01024       }
01025   
01026     // called by the range assign to implement [23.1.1]/9
01027     template<typename _InputIter>
01028       void
01029       _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type);
01030   
01031     // Called by assign(n,t), and the range assign when it turns out to be the
01032     // same thing.
01033     void
01034     _M_fill_assign(size_type __n, const value_type& __val);
01035   
01036   
01037     // Internal insert functions follow.
01038   
01039     // called by the range insert to implement [23.1.1]/9
01040     template<typename _Integer>
01041       void
01042       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
01043                          __true_type)
01044       {
01045         _M_fill_insert(__pos, static_cast<size_type>(__n),
01046                        static_cast<value_type>(__x));
01047       }
01048   
01049     // called by the range insert to implement [23.1.1]/9
01050     template<typename _InputIterator>
01051       void
01052       _M_insert_dispatch(iterator __pos,
01053                          _InputIterator __first, _InputIterator __last,
01054                          __false_type)
01055       {
01056         for ( ; __first != __last; ++__first)
01057           insert(__pos, *__first);
01058       }
01059   
01060     // Called by insert(p,n,x), and the range insert when it turns out to be
01061     // the same thing.
01062     void
01063     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
01064     {
01065       for ( ; __n > 0; --__n)
01066         insert(__pos, __x);
01067     }
01068   
01069   
01070     // Moves the elements from [first,last) before position.
01071     void
01072     _M_transfer(iterator __position, iterator __first, iterator __last)
01073     {
01074       if (__position != __last) {
01075         // Remove [first, last) from its old position.
01076         __last._M_node->_M_prev->_M_next     = __position._M_node;
01077         __first._M_node->_M_prev->_M_next    = __last._M_node;
01078         __position._M_node->_M_prev->_M_next = __first._M_node;
01079   
01080         // Splice [first, last) into its new position.
01081         _List_node_base* __tmp      = __position._M_node->_M_prev;
01082         __position._M_node->_M_prev = __last._M_node->_M_prev;
01083         __last._M_node->_M_prev     = __first._M_node->_M_prev;
01084         __first._M_node->_M_prev    = __tmp;
01085       }
01086     }
01087   };
01088   
01089   
01090   /**
01091    *  @brief  List equality comparison.
01092    *  @param  x  A %list.
01093    *  @param  y  A %list of the same type as @a x.
01094    *  @return  True iff the size and elements of the lists are equal.
01095    *
01096    *  This is an equivalence relation.  It is linear in the size of the
01097    *  lists.  Lists are considered equivalent if their sizes are equal,
01098    *  and if corresponding elements compare equal.
01099   */
01100   template<typename _Tp, typename _Alloc>
01101   inline bool
01102     operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01103     {
01104       typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
01105       const_iterator __end1 = __x.end();
01106       const_iterator __end2 = __y.end();
01107   
01108       const_iterator __i1 = __x.begin();
01109       const_iterator __i2 = __y.begin();
01110       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
01111         ++__i1;
01112         ++__i2;
01113       }
01114       return __i1 == __end1 && __i2 == __end2;
01115     }
01116   
01117   /**
01118    *  @brief  List ordering relation.
01119    *  @param  x  A %list.
01120    *  @param  y  A %list of the same type as @a x.
01121    *  @return  True iff @a x is lexographically less than @a y.
01122    *
01123    *  This is a total ordering relation.  It is linear in the size of the
01124    *  lists.  The elements must be comparable with @c <.
01125    *
01126    *  See std::lexographical_compare() for how the determination is made.
01127   */
01128   template<typename _Tp, typename _Alloc>
01129     inline bool
01130     operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01131     {
01132       return lexicographical_compare(__x.begin(), __x.end(),
01133                                      __y.begin(), __y.end());
01134     }
01135   
01136   /// Based on operator==
01137   template<typename _Tp, typename _Alloc>
01138     inline bool
01139     operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01140     { return !(__x == __y); }
01141   
01142   /// Based on operator<
01143   template<typename _Tp, typename _Alloc>
01144     inline bool
01145     operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01146     { return __y < __x; }
01147   
01148   /// Based on operator<
01149   template<typename _Tp, typename _Alloc>
01150     inline bool
01151     operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01152     { return !(__y < __x); }
01153   
01154   /// Based on operator<
01155   template<typename _Tp, typename _Alloc>
01156     inline bool
01157     operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
01158     { return !(__x < __y); }
01159   
01160   /// See std::list::swap().
01161   template<typename _Tp, typename _Alloc>
01162     inline void
01163     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
01164     { __x.swap(__y); }
01165 } // namespace std
01166 
01167 #endif /* __GLIBCPP_INTERNAL_LIST_H */

Generated on Thu Feb 10 23:22:58 2005 for libstdc++-v3 Source by  doxygen 1.4.0