stl_list.h

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

Generated on Wed Feb 23 02:33:36 2005 for libstdc++-v3 Source by doxygen 1.3.6