OSDN Git Service

2004-03-25 Dhruv Matani <dhruvbird@gmx.net>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_list.h
1 // List implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING.  If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
19 // USA.
20
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction.  Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License.  This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
29
30 /*
31  *
32  * Copyright (c) 1994
33  * Hewlett-Packard Company
34  *
35  * Permission to use, copy, modify, distribute and sell this software
36  * and its documentation for any purpose is hereby granted without fee,
37  * provided that the above copyright notice appear in all copies and
38  * that both that copyright notice and this permission notice appear
39  * in supporting documentation.  Hewlett-Packard Company makes no
40  * representations about the suitability of this software for any
41  * purpose.  It is provided "as is" without express or implied warranty.
42  *
43  *
44  * Copyright (c) 1996,1997
45  * Silicon Graphics Computer Systems, Inc.
46  *
47  * Permission to use, copy, modify, distribute and sell this software
48  * and its documentation for any purpose is hereby granted without fee,
49  * provided that the above copyright notice appear in all copies and
50  * that both that copyright notice and this permission notice appear
51  * in supporting documentation.  Silicon Graphics makes no
52  * representations about the suitability of this software for any
53  * purpose.  It is provided "as is" without express or implied warranty.
54  */
55
56 /** @file stl_list.h
57  *  This is an internal header file, included by other library headers.
58  *  You should not attempt to use it directly.
59  */
60
61 #ifndef _LIST_H
62 #define _LIST_H 1
63
64 #include <bits/concept_check.h>
65
66 namespace __gnu_norm
67 {
68   // Supporting structures are split into common and templated types; the
69   // latter publicly inherits from the former in an effort to reduce code
70   // duplication.  This results in some "needless" static_cast'ing later on,
71   // but it's all safe downcasting.
72
73   /// @if maint Common part of a node in the %list.  @endif
74   struct _List_node_base
75   {
76     _List_node_base* _M_next;   ///< Self-explanatory
77     _List_node_base* _M_prev;   ///< Self-explanatory
78
79     static void
80     swap(_List_node_base& __x, _List_node_base& __y);
81
82     void
83     transfer(_List_node_base * const __first,
84              _List_node_base * const __last);
85
86     void
87     reverse();
88
89     void
90     hook(_List_node_base * const __position);
91
92     void
93     unhook();
94   };
95
96   /// @if maint An actual node in the %list.  @endif
97   template<typename _Tp>
98     struct _List_node : public _List_node_base
99     {
100       _Tp _M_data;                ///< User's data.
101     };
102
103   /**
104    *  @brief A list::iterator.
105    *
106    *  @if maint
107    *  All the functions are op overloads.
108    *  @endif
109   */
110   template<typename _Tp>
111     struct _List_iterator
112     {
113       typedef _List_iterator<_Tp>           _Self;
114       typedef _List_node<_Tp>               _Node;
115
116       typedef ptrdiff_t                     difference_type;
117       typedef bidirectional_iterator_tag    iterator_category;
118       typedef _Tp                           value_type;
119       typedef _Tp*                          pointer;
120       typedef _Tp&                          reference;
121
122       _List_iterator() { }
123
124       _List_iterator(_List_node_base* __x)
125       : _M_node(__x) { }
126
127       // Must downcast from List_node_base to _List_node to get to _M_data.
128       reference
129       operator*() const
130       { return static_cast<_Node*>(_M_node)->_M_data; }
131
132       pointer
133       operator->() const
134       { return &static_cast<_Node*>(_M_node)->_M_data; }
135
136       _Self&
137       operator++()
138       {
139         _M_node = _M_node->_M_next;
140         return *this;
141       }
142
143       _Self
144       operator++(int)
145       {
146         _Self __tmp = *this;
147         _M_node = _M_node->_M_next;
148         return __tmp;
149       }
150
151       _Self&
152       operator--()
153       {
154         _M_node = _M_node->_M_prev;
155         return *this;
156       }
157
158       _Self
159       operator--(int)
160       {
161         _Self __tmp = *this;
162         _M_node = _M_node->_M_prev;
163         return __tmp;
164       }
165
166       bool
167       operator==(const _Self& __x) const
168       { return _M_node == __x._M_node; }
169
170       bool
171       operator!=(const _Self& __x) const
172       { return _M_node != __x._M_node; }
173
174       // The only member points to the %list element.
175       _List_node_base* _M_node;
176     };
177
178   /**
179    *  @brief A list::const_iterator.
180    *
181    *  @if maint
182    *  All the functions are op overloads.
183    *  @endif
184   */
185   template<typename _Tp>
186     struct _List_const_iterator
187     {
188       typedef _List_const_iterator<_Tp>     _Self;
189       typedef const _List_node<_Tp>         _Node;
190       typedef _List_iterator<_Tp>           iterator;
191
192       typedef ptrdiff_t                     difference_type;
193       typedef bidirectional_iterator_tag    iterator_category;
194       typedef _Tp                           value_type;
195       typedef const _Tp*                    pointer;
196       typedef const _Tp&                    reference;
197
198       _List_const_iterator() { }
199
200       _List_const_iterator(const _List_node_base* __x)
201       : _M_node(__x) { }
202
203       _List_const_iterator(const iterator& __x)
204       : _M_node(__x._M_node) { }
205
206       // Must downcast from List_node_base to _List_node to get to
207       // _M_data.
208       reference
209       operator*() const
210       { return static_cast<_Node*>(_M_node)->_M_data; }
211
212       pointer
213       operator->() const
214       { return &static_cast<_Node*>(_M_node)->_M_data; }
215
216       _Self&
217       operator++()
218       {
219         _M_node = _M_node->_M_next;
220         return *this;
221       }
222
223       _Self
224       operator++(int)
225       {
226         _Self __tmp = *this;
227         _M_node = _M_node->_M_next;
228         return __tmp;
229       }
230
231       _Self&
232       operator--()
233       {
234         _M_node = _M_node->_M_prev;
235         return *this;
236       }
237
238       _Self
239       operator--(int)
240       {
241         _Self __tmp = *this;
242         _M_node = _M_node->_M_prev;
243         return __tmp;
244       }
245
246       bool
247       operator==(const _Self& __x) const
248       { return _M_node == __x._M_node; }
249
250       bool
251       operator!=(const _Self& __x) const
252       { return _M_node != __x._M_node; }
253
254       // The only member points to the %list element.
255       const _List_node_base* _M_node;
256     };
257
258   template<typename _Val>
259     inline bool
260     operator==(const _List_iterator<_Val>& __x,
261                const _List_const_iterator<_Val>& __y)
262     { return __x._M_node == __y._M_node; }
263
264   template<typename _Val>
265     inline bool
266     operator!=(const _List_iterator<_Val>& __x,
267                const _List_const_iterator<_Val>& __y)
268     { return __x._M_node != __y._M_node; }
269
270
271   /**
272    *  @if maint
273    *  See bits/stl_deque.h's _Deque_base for an explanation.
274    *  @endif
275   */
276   template<typename _Tp, typename _Alloc>
277     class _List_base
278     {
279     protected:
280       // NOTA BENE
281       // The stored instance is not actually of "allocator_type"'s
282       // type.  Instead we rebind the type to
283       // Allocator<List_node<Tp>>, which according to [20.1.5]/4
284       // should probably be the same.  List_node<Tp> is not the same
285       // size as Tp (it's two pointers larger), and specializations on
286       // Tp may go unused because List_node<Tp> is being bound
287       // instead.
288       //
289       // We put this to the test in the constructors and in
290       // get_allocator, where we use conversions between
291       // allocator_type and _Node_Alloc_type. The conversion is
292       // required by table 32 in [20.1.5].
293       typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
294
295       _Node_Alloc_type;
296
297       struct _List_impl 
298         : public _Node_Alloc_type {
299         _List_node_base _M_node;
300         _List_impl (const _Node_Alloc_type& __a)
301           : _Node_Alloc_type(__a)
302         { }
303       };
304
305       _List_impl _M_impl;
306
307       _List_node<_Tp>*
308       _M_get_node()
309       { return _M_impl._Node_Alloc_type::allocate(1); }
310       
311       void
312       _M_put_node(_List_node<_Tp>* __p)
313       { _M_impl._Node_Alloc_type::deallocate(__p, 1); }
314       
315   public:
316       typedef _Alloc allocator_type;
317
318       allocator_type
319       get_allocator() const
320       { return allocator_type(*static_cast<const _Node_Alloc_type*>(&this->_M_impl)); }
321
322       _List_base(const allocator_type& __a)
323         : _M_impl(__a)
324       { _M_init(); }
325
326       // This is what actually destroys the list.
327       ~_List_base()
328       { _M_clear(); }
329
330       void
331       _M_clear();
332
333       void
334       _M_init()
335       {
336         this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
337         this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
338       }
339     };
340
341   /**
342    *  @brief A standard container with linear time access to elements,
343    *  and fixed time insertion/deletion at any point in the sequence.
344    *
345    *  @ingroup Containers
346    *  @ingroup Sequences
347    *
348    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
349    *  <a href="tables.html#66">reversible container</a>, and a
350    *  <a href="tables.html#67">sequence</a>, including the
351    *  <a href="tables.html#68">optional sequence requirements</a> with the
352    *  %exception of @c at and @c operator[].
353    *
354    *  This is a @e doubly @e linked %list.  Traversal up and down the
355    *  %list requires linear time, but adding and removing elements (or
356    *  @e nodes) is done in constant time, regardless of where the
357    *  change takes place.  Unlike std::vector and std::deque,
358    *  random-access iterators are not provided, so subscripting ( @c
359    *  [] ) access is not allowed.  For algorithms which only need
360    *  sequential access, this lack makes no difference.
361    *
362    *  Also unlike the other standard containers, std::list provides
363    *  specialized algorithms %unique to linked lists, such as
364    *  splicing, sorting, and in-place reversal.
365    *
366    *  @if maint
367    *  A couple points on memory allocation for list<Tp>:
368    *
369    *  First, we never actually allocate a Tp, we allocate
370    *  List_node<Tp>'s and trust [20.1.5]/4 to DTRT.  This is to ensure
371    *  that after elements from %list<X,Alloc1> are spliced into
372    *  %list<X,Alloc2>, destroying the memory of the second %list is a
373    *  valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
374    *
375    *  Second, a %list conceptually represented as
376    *  @code
377    *    A <---> B <---> C <---> D
378    *  @endcode
379    *  is actually circular; a link exists between A and D.  The %list
380    *  class holds (as its only data member) a private list::iterator
381    *  pointing to @e D, not to @e A!  To get to the head of the %list,
382    *  we start at the tail and move forward by one.  When this member
383    *  iterator's next/previous pointers refer to itself, the %list is
384    *  %empty.  @endif
385   */
386   template<typename _Tp, typename _Alloc = allocator<_Tp> >
387     class list : protected _List_base<_Tp, _Alloc>
388     {
389       // concept requirements
390       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
391
392       typedef _List_base<_Tp, _Alloc>                   _Base;
393
394     public:
395       typedef _Tp                                       value_type;
396       typedef value_type*                               pointer;
397       typedef const value_type*                         const_pointer;
398       typedef _List_iterator<_Tp>                       iterator;
399       typedef _List_const_iterator<_Tp>                 const_iterator;
400       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
401       typedef std::reverse_iterator<iterator>           reverse_iterator;
402       typedef value_type&                               reference;
403       typedef const value_type&                         const_reference;
404       typedef size_t                                    size_type;
405       typedef ptrdiff_t                                 difference_type;
406       typedef typename _Base::allocator_type            allocator_type;
407
408     protected:
409       // Note that pointers-to-_Node's can be ctor-converted to
410       // iterator types.
411       typedef _List_node<_Tp>                           _Node;
412
413       /** @if maint
414        *  One data member plus two memory-handling functions.  If the
415        *  _Alloc type requires separate instances, then one of those
416        *  will also be included, accumulated from the topmost parent.
417        *  @endif
418        */
419       using _Base::_M_impl;
420       using _Base::_M_put_node;
421       using _Base::_M_get_node;
422
423       /**
424        *  @if maint
425        *  @param  x  An instance of user data.
426        *
427        *  Allocates space for a new node and constructs a copy of @a x in it.
428        *  @endif
429        */
430       _Node*
431       _M_create_node(const value_type& __x)
432       {
433         _Node* __p = this->_M_get_node();
434         try
435           {
436             std::_Construct(&__p->_M_data, __x);
437           }
438         catch(...)
439           {
440             _M_put_node(__p);
441             __throw_exception_again;
442           }
443         return __p;
444       }
445
446       /**
447        *  @if maint
448        *  Allocates space for a new node and default-constructs a new
449        *  instance of @c value_type in it.
450        *  @endif
451        */
452       _Node*
453       _M_create_node()
454       {
455         _Node* __p = this->_M_get_node();
456         try
457           {
458             std::_Construct(&__p->_M_data);
459           }
460         catch(...)
461           {
462             _M_put_node(__p);
463             __throw_exception_again;
464           }
465         return __p;
466       }
467
468     public:
469       // [23.2.2.1] construct/copy/destroy
470       // (assign() and get_allocator() are also listed in this section)
471       /**
472        *  @brief  Default constructor creates no elements.
473        */
474       explicit
475       list(const allocator_type& __a = allocator_type())
476       : _Base(__a) { }
477
478       /**
479        *  @brief  Create a %list with copies of an exemplar element.
480        *  @param  n  The number of elements to initially create.
481        *  @param  value  An element to copy.
482        *
483        *  This constructor fills the %list with @a n copies of @a value.
484        */
485       list(size_type __n, const value_type& __value,
486            const allocator_type& __a = allocator_type())
487       : _Base(__a)
488       { this->insert(begin(), __n, __value); }
489
490       /**
491        *  @brief  Create a %list with default elements.
492        *  @param  n  The number of elements to initially create.
493        *
494        *  This constructor fills the %list with @a n copies of a
495        *  default-constructed element.
496        */
497       explicit
498       list(size_type __n)
499       : _Base(allocator_type())
500       { this->insert(begin(), __n, value_type()); }
501
502       /**
503        *  @brief  %List copy constructor.
504        *  @param  x  A %list of identical element and allocator types.
505        *
506        *  The newly-created %list uses a copy of the allocation object used
507        *  by @a x.
508        */
509       list(const list& __x)
510       : _Base(__x.get_allocator())
511       { this->insert(begin(), __x.begin(), __x.end()); }
512
513       /**
514        *  @brief  Builds a %list from a range.
515        *  @param  first  An input iterator.
516        *  @param  last  An input iterator.
517        *
518        *  Create a %list consisting of copies of the elements from
519        *  [@a first,@a last).  This is linear in N (where N is
520        *  distance(@a first,@a last)).
521        *
522        *  @if maint
523        *  We don't need any dispatching tricks here, because insert does all of
524        *  that anyway.
525        *  @endif
526        */
527       template<typename _InputIterator>
528         list(_InputIterator __first, _InputIterator __last,
529              const allocator_type& __a = allocator_type())
530         : _Base(__a)
531         { this->insert(begin(), __first, __last); }
532
533       /**
534        *  No explicit dtor needed as the _Base dtor takes care of
535        *  things.  The _Base dtor only erases the elements, and note
536        *  that if the elements themselves are pointers, the pointed-to
537        *  memory is not touched in any way.  Managing the pointer is
538        *  the user's responsibilty.
539        */
540
541       /**
542        *  @brief  %List assignment operator.
543        *  @param  x  A %list of identical element and allocator types.
544        *
545        *  All the elements of @a x are copied, but unlike the copy
546        *  constructor, the allocator object is not copied.
547        */
548       list&
549       operator=(const list& __x);
550
551       /**
552        *  @brief  Assigns a given value to a %list.
553        *  @param  n  Number of elements to be assigned.
554        *  @param  val  Value to be assigned.
555        *
556        *  This function fills a %list with @a n copies of the given
557        *  value.  Note that the assignment completely changes the %list
558        *  and that the resulting %list's size is the same as the number
559        *  of elements assigned.  Old data may be lost.
560        */
561       void
562       assign(size_type __n, const value_type& __val)
563       { _M_fill_assign(__n, __val); }
564
565       /**
566        *  @brief  Assigns a range to a %list.
567        *  @param  first  An input iterator.
568        *  @param  last   An input iterator.
569        *
570        *  This function fills a %list with copies of the elements in the
571        *  range [@a first,@a last).
572        *
573        *  Note that the assignment completely changes the %list and
574        *  that the resulting %list's size is the same as the number of
575        *  elements assigned.  Old data may be lost.
576        */
577       template<typename _InputIterator>
578         void
579         assign(_InputIterator __first, _InputIterator __last)
580         {
581           // Check whether it's an integral type.  If so, it's not an iterator.
582           typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
583           _M_assign_dispatch(__first, __last, _Integral());
584         }
585
586       /// Get a copy of the memory allocation object.
587       allocator_type
588       get_allocator() const
589       { return _Base::get_allocator(); }
590
591       // iterators
592       /**
593        *  Returns a read/write iterator that points to the first element in the
594        *  %list.  Iteration is done in ordinary element order.
595        */
596       iterator
597       begin()
598       { return this->_M_impl._M_node._M_next; }
599
600       /**
601        *  Returns a read-only (constant) iterator that points to the
602        *  first element in the %list.  Iteration is done in ordinary
603        *  element order.
604        */
605       const_iterator
606       begin() const
607       { return this->_M_impl._M_node._M_next; }
608
609       /**
610        *  Returns a read/write iterator that points one past the last
611        *  element in the %list.  Iteration is done in ordinary element
612        *  order.
613        */
614       iterator
615       end() { return &this->_M_impl._M_node; }
616
617       /**
618        *  Returns a read-only (constant) iterator that points one past
619        *  the last element in the %list.  Iteration is done in ordinary
620        *  element order.
621        */
622       const_iterator
623       end() const
624       { return &this->_M_impl._M_node; }
625
626       /**
627        *  Returns a read/write reverse iterator that points to the last
628        *  element in the %list.  Iteration is done in reverse element
629        *  order.
630        */
631       reverse_iterator
632       rbegin()
633       { return reverse_iterator(end()); }
634
635       /**
636        *  Returns a read-only (constant) reverse iterator that points to
637        *  the last element in the %list.  Iteration is done in reverse
638        *  element order.
639        */
640       const_reverse_iterator
641       rbegin() const
642       { return const_reverse_iterator(end()); }
643
644       /**
645        *  Returns a read/write reverse iterator that points to one
646        *  before the first element in the %list.  Iteration is done in
647        *  reverse element order.
648        */
649       reverse_iterator
650       rend()
651       { return reverse_iterator(begin()); }
652
653       /**
654        *  Returns a read-only (constant) reverse iterator that points to one
655        *  before the first element in the %list.  Iteration is done in reverse
656        *  element order.
657        */
658       const_reverse_iterator
659       rend() const
660       { return const_reverse_iterator(begin()); }
661
662       // [23.2.2.2] capacity
663       /**
664        *  Returns true if the %list is empty.  (Thus begin() would equal
665        *  end().)
666        */
667       bool
668       empty() const
669       { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
670
671       /**  Returns the number of elements in the %list.  */
672       size_type
673       size() const
674       { return std::distance(begin(), end()); }
675
676       /**  Returns the size() of the largest possible %list.  */
677       size_type
678       max_size() const
679       { return size_type(-1); }
680
681       /**
682        *  @brief Resizes the %list to the specified number of elements.
683        *  @param new_size Number of elements the %list should contain.
684        *  @param x Data with which new elements should be populated.
685        *
686        *  This function will %resize the %list to the specified number
687        *  of elements.  If the number is smaller than the %list's
688        *  current size the %list is truncated, otherwise the %list is
689        *  extended and new elements are populated with given data.
690        */
691       void
692       resize(size_type __new_size, const value_type& __x);
693
694       /**
695        *  @brief  Resizes the %list to the specified number of elements.
696        *  @param  new_size  Number of elements the %list should contain.
697        *
698        *  This function will resize the %list to the specified number of
699        *  elements.  If the number is smaller than the %list's current
700        *  size the %list is truncated, otherwise the %list is extended
701        *  and new elements are default-constructed.
702        */
703       void
704       resize(size_type __new_size)
705       { this->resize(__new_size, value_type()); }
706
707       // element access
708       /**
709        *  Returns a read/write reference to the data at the first
710        *  element of the %list.
711        */
712       reference
713       front()
714       { return *begin(); }
715
716       /**
717        *  Returns a read-only (constant) reference to the data at the first
718        *  element of the %list.
719        */
720       const_reference
721       front() const
722       { return *begin(); }
723
724       /**
725        *  Returns a read/write reference to the data at the last element
726        *  of the %list.
727        */
728       reference
729       back()
730       { return *(--end()); }
731
732       /**
733        *  Returns a read-only (constant) reference to the data at the last
734        *  element of the %list.
735        */
736       const_reference
737       back() const
738       { return *(--end()); }
739
740       // [23.2.2.3] modifiers
741       /**
742        *  @brief  Add data to the front of the %list.
743        *  @param  x  Data to be added.
744        *
745        *  This is a typical stack operation.  The function creates an
746        *  element at the front of the %list and assigns the given data
747        *  to it.  Due to the nature of a %list this operation can be
748        *  done in constant time, and does not invalidate iterators and
749        *  references.
750        */
751       void
752       push_front(const value_type& __x)
753       { this->_M_insert(begin(), __x); }
754
755       /**
756        *  @brief  Removes first element.
757        *
758        *  This is a typical stack operation.  It shrinks the %list by
759        *  one.  Due to the nature of a %list this operation can be done
760        *  in constant time, and only invalidates iterators/references to
761        *  the element being removed.
762        *
763        *  Note that no data is returned, and if the first element's data
764        *  is needed, it should be retrieved before pop_front() is
765        *  called.
766        */
767       void
768       pop_front()
769       { this->_M_erase(begin()); }
770
771       /**
772        *  @brief  Add data to the end of the %list.
773        *  @param  x  Data to be added.
774        *
775        *  This is a typical stack operation.  The function creates an
776        *  element at the end of the %list and assigns the given data to
777        *  it.  Due to the nature of a %list this operation can be done
778        *  in constant time, and does not invalidate iterators and
779        *  references.
780        */
781       void
782       push_back(const value_type& __x)
783       { this->_M_insert(end(), __x); }
784
785       /**
786        *  @brief  Removes last element.
787        *
788        *  This is a typical stack operation.  It shrinks the %list by
789        *  one.  Due to the nature of a %list this operation can be done
790        *  in constant time, and only invalidates iterators/references to
791        *  the element being removed.
792        *
793        *  Note that no data is returned, and if the last element's data
794        *  is needed, it should be retrieved before pop_back() is called.
795        */
796       void
797       pop_back()
798       { this->_M_erase(this->_M_impl._M_node._M_prev); }
799
800       /**
801        *  @brief  Inserts given value into %list before specified iterator.
802        *  @param  position  An iterator into the %list.
803        *  @param  x  Data to be inserted.
804        *  @return  An iterator that points to the inserted data.
805        *
806        *  This function will insert a copy of the given value before
807        *  the specified location.  Due to the nature of a %list this
808        *  operation can be done in constant time, and does not
809        *  invalidate iterators and references.
810        */
811       iterator
812       insert(iterator __position, const value_type& __x);
813
814       /**
815        *  @brief  Inserts a number of copies of given data into the %list.
816        *  @param  position  An iterator into the %list.
817        *  @param  n  Number of elements to be inserted.
818        *  @param  x  Data to be inserted.
819        *
820        *  This function will insert a specified number of copies of the
821        *  given data before the location specified by @a position.
822        *
823        *  Due to the nature of a %list this operation can be done in
824        *  constant time, and does not invalidate iterators and
825        *  references.
826        */
827       void
828       insert(iterator __position, size_type __n, const value_type& __x)
829       { _M_fill_insert(__position, __n, __x); }
830
831       /**
832        *  @brief  Inserts a range into the %list.
833        *  @param  position  An iterator into the %list.
834        *  @param  first  An input iterator.
835        *  @param  last   An input iterator.
836        *
837        *  This function will insert copies of the data in the range [@a
838        *  first,@a last) into the %list before the location specified by
839        *  @a position.
840        *
841        *  Due to the nature of a %list this operation can be done in
842        *  constant time, and does not invalidate iterators and
843        *  references.
844        */
845       template<typename _InputIterator>
846         void
847         insert(iterator __position, _InputIterator __first,
848                _InputIterator __last)
849         {
850           // Check whether it's an integral type.  If so, it's not an iterator.
851           typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
852           _M_insert_dispatch(__position, __first, __last, _Integral());
853         }
854
855       /**
856        *  @brief  Remove element at given position.
857        *  @param  position  Iterator pointing to element to be erased.
858        *  @return  An iterator pointing to the next element (or end()).
859        *
860        *  This function will erase the element at the given position and thus
861        *  shorten the %list by one.
862        *
863        *  Due to the nature of a %list this operation can be done in
864        *  constant time, and only invalidates iterators/references to
865        *  the element being removed.  The user is also cautioned that
866        *  this function only erases the element, and that if the element
867        *  is itself a pointer, the pointed-to memory is not touched in
868        *  any way.  Managing the pointer is the user's responsibilty.
869        */
870       iterator
871       erase(iterator __position);
872
873       /**
874        *  @brief  Remove a range of elements.
875        *  @param  first  Iterator pointing to the first element to be erased.
876        *  @param  last  Iterator pointing to one past the last element to be
877        *                erased.
878        *  @return  An iterator pointing to the element pointed to by @a last
879        *           prior to erasing (or end()).
880        *
881        *  This function will erase the elements in the range @a
882        *  [first,last) and shorten the %list accordingly.
883        *
884        *  Due to the nature of a %list this operation can be done in
885        *  constant time, and only invalidates iterators/references to
886        *  the element being removed.  The user is also cautioned that
887        *  this function only erases the elements, and that if the
888        *  elements themselves are pointers, the pointed-to memory is not
889        *  touched in any way.  Managing the pointer is the user's
890        *  responsibilty.
891        */
892       iterator
893       erase(iterator __first, iterator __last)
894       {
895         while (__first != __last)
896           __first = erase(__first);
897         return __last;
898       }
899
900       /**
901        *  @brief  Swaps data with another %list.
902        *  @param  x  A %list of the same element and allocator types.
903        *
904        *  This exchanges the elements between two lists in constant
905        *  time.  Note that the global std::swap() function is
906        *  specialized such that std::swap(l1,l2) will feed to this
907        *  function.
908        */
909       void
910       swap(list& __x)
911       { _List_node_base::swap(this->_M_impl._M_node,__x._M_impl._M_node); }
912
913       /**
914        *  Erases all the elements.  Note that this function only erases
915        *  the elements, and that if the elements themselves are
916        *  pointers, the pointed-to memory is not touched in any way.
917        *  Managing the pointer is the user's responsibilty.
918        */
919       void
920       clear()
921       {
922         _Base::_M_clear();
923         _Base::_M_init();
924       }
925
926       // [23.2.2.4] list operations
927       /**
928        *  @brief  Insert contents of another %list.
929        *  @param  position  Iterator referencing the element to insert before.
930        *  @param  x  Source list.
931        *
932        *  The elements of @a x are inserted in constant time in front of
933        *  the element referenced by @a position.  @a x becomes an empty
934        *  list.
935        */
936       void
937       splice(iterator __position, list& __x)
938       {
939         if (!__x.empty())
940           this->_M_transfer(__position, __x.begin(), __x.end());
941       }
942
943       /**
944        *  @brief  Insert element from another %list.
945        *  @param  position  Iterator referencing the element to insert before.
946        *  @param  x  Source list.
947        *  @param  i  Iterator referencing the element to move.
948        *
949        *  Removes the element in list @a x referenced by @a i and
950        *  inserts it into the current list before @a position.
951        */
952       void
953       splice(iterator __position, list&, iterator __i)
954       {
955         iterator __j = __i;
956         ++__j;
957         if (__position == __i || __position == __j)
958           return;
959         this->_M_transfer(__position, __i, __j);
960       }
961
962       /**
963        *  @brief  Insert range from another %list.
964        *  @param  position  Iterator referencing the element to insert before.
965        *  @param  x  Source list.
966        *  @param  first  Iterator referencing the start of range in x.
967        *  @param  last  Iterator referencing the end of range in x.
968        *
969        *  Removes elements in the range [first,last) and inserts them
970        *  before @a position in constant time.
971        *
972        *  Undefined if @a position is in [first,last).
973        */
974       void
975       splice(iterator __position, list&, iterator __first, iterator __last)
976       {
977         if (__first != __last)
978           this->_M_transfer(__position, __first, __last);
979       }
980
981       /**
982        *  @brief  Remove all elements equal to value.
983        *  @param  value  The value to remove.
984        *
985        *  Removes every element in the list equal to @a value.
986        *  Remaining elements stay in list order.  Note that this
987        *  function only erases the elements, and that if the elements
988        *  themselves are pointers, the pointed-to memory is not
989        *  touched in any way.  Managing the pointer is the user's
990        *  responsibilty.
991        */
992       void
993       remove(const _Tp& __value);
994
995       /**
996        *  @brief  Remove all elements satisfying a predicate.
997        *  @param  Predicate  Unary predicate function or object.
998        *
999        *  Removes every element in the list for which the predicate
1000        *  returns true.  Remaining elements stay in list order.  Note
1001        *  that this function only erases the elements, and that if the
1002        *  elements themselves are pointers, the pointed-to memory is
1003        *  not touched in any way.  Managing the pointer is the user's
1004        *  responsibilty.
1005        */
1006       template<typename _Predicate>
1007       void
1008       remove_if(_Predicate);
1009
1010       /**
1011        *  @brief  Remove consecutive duplicate elements.
1012        *
1013        *  For each consecutive set of elements with the same value,
1014        *  remove all but the first one.  Remaining elements stay in
1015        *  list order.  Note that this function only erases the
1016        *  elements, and that if the elements themselves are pointers,
1017        *  the pointed-to memory is not touched in any way.  Managing
1018        *  the pointer is the user's responsibilty.
1019        */
1020       void
1021       unique();
1022
1023       /**
1024        *  @brief  Remove consecutive elements satisfying a predicate.
1025        *  @param  BinaryPredicate  Binary predicate function or object.
1026        *
1027        *  For each consecutive set of elements [first,last) that
1028        *  satisfy predicate(first,i) where i is an iterator in
1029        *  [first,last), remove all but the first one.  Remaining
1030        *  elements stay in list order.  Note that this function only
1031        *  erases the elements, and that if the elements themselves are
1032        *  pointers, the pointed-to memory is not touched in any way.
1033        *  Managing the pointer is the user's responsibilty.
1034        */
1035       template<typename _BinaryPredicate>
1036         void
1037         unique(_BinaryPredicate);
1038
1039       /**
1040        *  @brief  Merge sorted lists.
1041        *  @param  x  Sorted list to merge.
1042        *
1043        *  Assumes that both @a x and this list are sorted according to
1044        *  operator<().  Merges elements of @a x into this list in
1045        *  sorted order, leaving @a x empty when complete.  Elements in
1046        *  this list precede elements in @a x that are equal.
1047        */
1048       void
1049       merge(list& __x);
1050
1051       /**
1052        *  @brief  Merge sorted lists according to comparison function.
1053        *  @param  x  Sorted list to merge.
1054        *  @param StrictWeakOrdering Comparison function definining
1055        *  sort order.
1056        *
1057        *  Assumes that both @a x and this list are sorted according to
1058        *  StrictWeakOrdering.  Merges elements of @a x into this list
1059        *  in sorted order, leaving @a x empty when complete.  Elements
1060        *  in this list precede elements in @a x that are equivalent
1061        *  according to StrictWeakOrdering().
1062        */
1063       template<typename _StrictWeakOrdering>
1064         void
1065         merge(list&, _StrictWeakOrdering);
1066
1067       /**
1068        *  @brief  Reverse the elements in list.
1069        *
1070        *  Reverse the order of elements in the list in linear time.
1071        */
1072       void
1073       reverse()
1074       { this->_M_impl._M_node.reverse(); }
1075
1076       /**
1077        *  @brief  Sort the elements.
1078        *
1079        *  Sorts the elements of this list in NlogN time.  Equivalent
1080        *  elements remain in list order.
1081        */
1082       void
1083       sort();
1084
1085       /**
1086        *  @brief  Sort the elements according to comparison function.
1087        *
1088        *  Sorts the elements of this list in NlogN time.  Equivalent
1089        *  elements remain in list order.
1090        */
1091       template<typename _StrictWeakOrdering>
1092         void
1093         sort(_StrictWeakOrdering);
1094
1095     protected:
1096       // Internal assign functions follow.
1097
1098       // Called by the range assign to implement [23.1.1]/9
1099       template<typename _Integer>
1100         void
1101         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1102         {
1103           _M_fill_assign(static_cast<size_type>(__n),
1104                          static_cast<value_type>(__val));
1105         }
1106
1107       // Called by the range assign to implement [23.1.1]/9
1108       template<typename _InputIterator>
1109         void
1110         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1111                            __false_type);
1112
1113       // Called by assign(n,t), and the range assign when it turns out
1114       // to be the same thing.
1115       void
1116       _M_fill_assign(size_type __n, const value_type& __val);
1117
1118
1119       // Internal insert functions follow.
1120
1121       // Called by the range insert to implement [23.1.1]/9
1122       template<typename _Integer>
1123         void
1124         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1125                            __true_type)
1126         {
1127           _M_fill_insert(__pos, static_cast<size_type>(__n),
1128                          static_cast<value_type>(__x));
1129         }
1130
1131       // Called by the range insert to implement [23.1.1]/9
1132       template<typename _InputIterator>
1133         void
1134         _M_insert_dispatch(iterator __pos,
1135                            _InputIterator __first, _InputIterator __last,
1136                            __false_type)
1137         {
1138           for ( ; __first != __last; ++__first)
1139             _M_insert(__pos, *__first);
1140         }
1141
1142       // Called by insert(p,n,x), and the range insert when it turns out
1143       // to be the same thing.
1144       void
1145       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
1146       {
1147         for ( ; __n > 0; --__n)
1148           _M_insert(__pos, __x);
1149       }
1150
1151
1152       // Moves the elements from [first,last) before position.
1153       void
1154       _M_transfer(iterator __position, iterator __first, iterator __last)
1155       { __position._M_node->transfer(__first._M_node,__last._M_node); }
1156
1157       // Inserts new element at position given and with value given.
1158       void
1159       _M_insert(iterator __position, const value_type& __x)
1160       {
1161         _Node* __tmp = _M_create_node(__x);
1162         __tmp->hook(__position._M_node);
1163       }
1164
1165       // Erases element at position given.
1166       void
1167       _M_erase(iterator __position)
1168       {
1169         __position._M_node->unhook();
1170         _Node* __n = static_cast<_Node*>(__position._M_node);
1171         std::_Destroy(&__n->_M_data);
1172         _M_put_node(__n);
1173       }
1174     };
1175
1176   /**
1177    *  @brief  List equality comparison.
1178    *  @param  x  A %list.
1179    *  @param  y  A %list of the same type as @a x.
1180    *  @return  True iff the size and elements of the lists are equal.
1181    *
1182    *  This is an equivalence relation.  It is linear in the size of
1183    *  the lists.  Lists are considered equivalent if their sizes are
1184    *  equal, and if corresponding elements compare equal.
1185   */
1186   template<typename _Tp, typename _Alloc>
1187     inline bool
1188     operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
1189     {
1190       typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
1191       const_iterator __end1 = __x.end();
1192       const_iterator __end2 = __y.end();
1193
1194       const_iterator __i1 = __x.begin();
1195       const_iterator __i2 = __y.begin();
1196       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
1197         {
1198           ++__i1;
1199           ++__i2;
1200         }
1201       return __i1 == __end1 && __i2 == __end2;
1202     }
1203
1204   /**
1205    *  @brief  List ordering relation.
1206    *  @param  x  A %list.
1207    *  @param  y  A %list of the same type as @a x.
1208    *  @return  True iff @a x is lexicographically less than @a y.
1209    *
1210    *  This is a total ordering relation.  It is linear in the size of the
1211    *  lists.  The elements must be comparable with @c <.
1212    *
1213    *  See std::lexicographical_compare() for how the determination is made.
1214   */
1215   template<typename _Tp, typename _Alloc>
1216     inline bool
1217     operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
1218     { return std::lexicographical_compare(__x.begin(), __x.end(),
1219                                           __y.begin(), __y.end()); }
1220
1221   /// Based on operator==
1222   template<typename _Tp, typename _Alloc>
1223     inline bool
1224     operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
1225     { return !(__x == __y); }
1226
1227   /// Based on operator<
1228   template<typename _Tp, typename _Alloc>
1229     inline bool
1230     operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
1231     { return __y < __x; }
1232
1233   /// Based on operator<
1234   template<typename _Tp, typename _Alloc>
1235     inline bool
1236     operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
1237     { return !(__y < __x); }
1238
1239   /// Based on operator<
1240   template<typename _Tp, typename _Alloc>
1241     inline bool
1242     operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
1243     { return !(__x < __y); }
1244
1245   /// See std::list::swap().
1246   template<typename _Tp, typename _Alloc>
1247     inline void
1248     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
1249     { __x.swap(__y); }
1250 } // namespace __gnu_norm
1251
1252 #endif /* _LIST_H */
1253