OSDN Git Service

2011-05-26 Paolo Carlini <paolo.carlini@oracle.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_list.h
1 // List implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library.  This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 // GNU General Public License for more details.
16
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 // <http://www.gnu.org/licenses/>.
25
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation.  Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose.  It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996,1997
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation.  Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose.  It is provided "as is" without express or implied warranty.
50  */
51
52 /** @file bits/stl_list.h
53  *  This is an internal header file, included by other library headers.
54  *  Do not attempt to use it directly. @headername{list}
55  */
56
57 #ifndef _STL_LIST_H
58 #define _STL_LIST_H 1
59
60 #include <bits/concept_check.h>
61 #include <initializer_list>
62
63 namespace std _GLIBCXX_VISIBILITY(default)
64 {
65   namespace __detail
66   {
67   _GLIBCXX_BEGIN_NAMESPACE_VERSION
68
69     // Supporting structures are split into common and templated
70     // types; the latter publicly inherits from the former in an
71     // effort to reduce code duplication.  This results in some
72     // "needless" static_cast'ing later on, but it's all safe
73     // downcasting.
74
75     /// Common part of a node in the %list. 
76     struct _List_node_base
77     {
78       _List_node_base* _M_next;
79       _List_node_base* _M_prev;
80
81       static void
82       swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
83
84       void
85       _M_transfer(_List_node_base* const __first,
86                   _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
87
88       void
89       _M_reverse() _GLIBCXX_USE_NOEXCEPT;
90
91       void
92       _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
93
94       void
95       _M_unhook() _GLIBCXX_USE_NOEXCEPT;
96     };
97
98   _GLIBCXX_END_NAMESPACE_VERSION
99   } // namespace detail
100
101 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
102
103   /// An actual node in the %list.
104   template<typename _Tp>
105     struct _List_node : public __detail::_List_node_base
106     {
107       ///< User's data.
108       _Tp _M_data;
109
110 #ifdef __GXX_EXPERIMENTAL_CXX0X__
111       template<typename... _Args>
112         _List_node(_Args&&... __args)
113         : __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...) 
114         { }
115 #endif
116     };
117
118   /**
119    *  @brief A list::iterator.
120    *
121    *  All the functions are op overloads.
122   */
123   template<typename _Tp>
124     struct _List_iterator
125     {
126       typedef _List_iterator<_Tp>                _Self;
127       typedef _List_node<_Tp>                    _Node;
128
129       typedef ptrdiff_t                          difference_type;
130       typedef std::bidirectional_iterator_tag    iterator_category;
131       typedef _Tp                                value_type;
132       typedef _Tp*                               pointer;
133       typedef _Tp&                               reference;
134
135       _List_iterator()
136       : _M_node() { }
137
138       explicit
139       _List_iterator(__detail::_List_node_base* __x)
140       : _M_node(__x) { }
141
142       // Must downcast from _List_node_base to _List_node to get to _M_data.
143       reference
144       operator*() const
145       { return static_cast<_Node*>(_M_node)->_M_data; }
146
147       pointer
148       operator->() const
149       { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }
150
151       _Self&
152       operator++()
153       {
154         _M_node = _M_node->_M_next;
155         return *this;
156       }
157
158       _Self
159       operator++(int)
160       {
161         _Self __tmp = *this;
162         _M_node = _M_node->_M_next;
163         return __tmp;
164       }
165
166       _Self&
167       operator--()
168       {
169         _M_node = _M_node->_M_prev;
170         return *this;
171       }
172
173       _Self
174       operator--(int)
175       {
176         _Self __tmp = *this;
177         _M_node = _M_node->_M_prev;
178         return __tmp;
179       }
180
181       bool
182       operator==(const _Self& __x) const
183       { return _M_node == __x._M_node; }
184
185       bool
186       operator!=(const _Self& __x) const
187       { return _M_node != __x._M_node; }
188
189       // The only member points to the %list element.
190       __detail::_List_node_base* _M_node;
191     };
192
193   /**
194    *  @brief A list::const_iterator.
195    *
196    *  All the functions are op overloads.
197   */
198   template<typename _Tp>
199     struct _List_const_iterator
200     {
201       typedef _List_const_iterator<_Tp>          _Self;
202       typedef const _List_node<_Tp>              _Node;
203       typedef _List_iterator<_Tp>                iterator;
204
205       typedef ptrdiff_t                          difference_type;
206       typedef std::bidirectional_iterator_tag    iterator_category;
207       typedef _Tp                                value_type;
208       typedef const _Tp*                         pointer;
209       typedef const _Tp&                         reference;
210
211       _List_const_iterator()
212       : _M_node() { }
213
214       explicit
215       _List_const_iterator(const __detail::_List_node_base* __x)
216       : _M_node(__x) { }
217
218       _List_const_iterator(const iterator& __x)
219       : _M_node(__x._M_node) { }
220
221       // Must downcast from List_node_base to _List_node to get to
222       // _M_data.
223       reference
224       operator*() const
225       { return static_cast<_Node*>(_M_node)->_M_data; }
226
227       pointer
228       operator->() const
229       { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }
230
231       _Self&
232       operator++()
233       {
234         _M_node = _M_node->_M_next;
235         return *this;
236       }
237
238       _Self
239       operator++(int)
240       {
241         _Self __tmp = *this;
242         _M_node = _M_node->_M_next;
243         return __tmp;
244       }
245
246       _Self&
247       operator--()
248       {
249         _M_node = _M_node->_M_prev;
250         return *this;
251       }
252
253       _Self
254       operator--(int)
255       {
256         _Self __tmp = *this;
257         _M_node = _M_node->_M_prev;
258         return __tmp;
259       }
260
261       bool
262       operator==(const _Self& __x) const
263       { return _M_node == __x._M_node; }
264
265       bool
266       operator!=(const _Self& __x) const
267       { return _M_node != __x._M_node; }
268
269       // The only member points to the %list element.
270       const __detail::_List_node_base* _M_node;
271     };
272
273   template<typename _Val>
274     inline bool
275     operator==(const _List_iterator<_Val>& __x,
276                const _List_const_iterator<_Val>& __y)
277     { return __x._M_node == __y._M_node; }
278
279   template<typename _Val>
280     inline bool
281     operator!=(const _List_iterator<_Val>& __x,
282                const _List_const_iterator<_Val>& __y)
283     { return __x._M_node != __y._M_node; }
284
285
286   /// See bits/stl_deque.h's _Deque_base for an explanation.
287   template<typename _Tp, typename _Alloc>
288     class _List_base
289     {
290     protected:
291       // NOTA BENE
292       // The stored instance is not actually of "allocator_type"'s
293       // type.  Instead we rebind the type to
294       // Allocator<List_node<Tp>>, which according to [20.1.5]/4
295       // should probably be the same.  List_node<Tp> is not the same
296       // size as Tp (it's two pointers larger), and specializations on
297       // Tp may go unused because List_node<Tp> is being bound
298       // instead.
299       //
300       // We put this to the test in the constructors and in
301       // get_allocator, where we use conversions between
302       // allocator_type and _Node_alloc_type. The conversion is
303       // required by table 32 in [20.1.5].
304       typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
305         _Node_alloc_type;
306
307       typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
308
309       struct _List_impl 
310       : public _Node_alloc_type
311       {
312         __detail::_List_node_base _M_node;
313
314         _List_impl()
315         : _Node_alloc_type(), _M_node()
316         { }
317
318         _List_impl(const _Node_alloc_type& __a)
319         : _Node_alloc_type(__a), _M_node()
320         { }
321       };
322
323       _List_impl _M_impl;
324
325       _List_node<_Tp>*
326       _M_get_node()
327       { return _M_impl._Node_alloc_type::allocate(1); }
328       
329       void
330       _M_put_node(_List_node<_Tp>* __p)
331       { _M_impl._Node_alloc_type::deallocate(__p, 1); }
332       
333   public:
334       typedef _Alloc allocator_type;
335
336       _Node_alloc_type&
337       _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
338       { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
339
340       const _Node_alloc_type&
341       _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
342       { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
343
344       _Tp_alloc_type
345       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
346       { return _Tp_alloc_type(_M_get_Node_allocator()); }
347
348       allocator_type
349       get_allocator() const _GLIBCXX_NOEXCEPT
350       { return allocator_type(_M_get_Node_allocator()); }
351
352       _List_base()
353       : _M_impl()
354       { _M_init(); }
355
356       _List_base(const allocator_type& __a)
357       : _M_impl(__a)
358       { _M_init(); }
359
360 #ifdef __GXX_EXPERIMENTAL_CXX0X__
361       _List_base(_List_base&& __x)
362       : _M_impl(__x._M_get_Node_allocator())
363       {
364         _M_init();
365         __detail::_List_node_base::swap(this->_M_impl._M_node, 
366                                         __x._M_impl._M_node);   
367       }
368 #endif
369
370       // This is what actually destroys the list.
371       ~_List_base()
372       { _M_clear(); }
373
374       void
375       _M_clear();
376
377       void
378       _M_init()
379       {
380         this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
381         this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
382       }
383     };
384
385   /**
386    *  @brief A standard container with linear time access to elements,
387    *  and fixed time insertion/deletion at any point in the sequence.
388    *
389    *  @ingroup sequences
390    *
391    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
392    *  <a href="tables.html#66">reversible container</a>, and a
393    *  <a href="tables.html#67">sequence</a>, including the
394    *  <a href="tables.html#68">optional sequence requirements</a> with the
395    *  %exception of @c at and @c operator[].
396    *
397    *  This is a @e doubly @e linked %list.  Traversal up and down the
398    *  %list requires linear time, but adding and removing elements (or
399    *  @e nodes) is done in constant time, regardless of where the
400    *  change takes place.  Unlike std::vector and std::deque,
401    *  random-access iterators are not provided, so subscripting ( @c
402    *  [] ) access is not allowed.  For algorithms which only need
403    *  sequential access, this lack makes no difference.
404    *
405    *  Also unlike the other standard containers, std::list provides
406    *  specialized algorithms %unique to linked lists, such as
407    *  splicing, sorting, and in-place reversal.
408    *
409    *  A couple points on memory allocation for list<Tp>:
410    *
411    *  First, we never actually allocate a Tp, we allocate
412    *  List_node<Tp>'s and trust [20.1.5]/4 to DTRT.  This is to ensure
413    *  that after elements from %list<X,Alloc1> are spliced into
414    *  %list<X,Alloc2>, destroying the memory of the second %list is a
415    *  valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
416    *
417    *  Second, a %list conceptually represented as
418    *  @code
419    *    A <---> B <---> C <---> D
420    *  @endcode
421    *  is actually circular; a link exists between A and D.  The %list
422    *  class holds (as its only data member) a private list::iterator
423    *  pointing to @e D, not to @e A!  To get to the head of the %list,
424    *  we start at the tail and move forward by one.  When this member
425    *  iterator's next/previous pointers refer to itself, the %list is
426    *  %empty. 
427   */
428   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
429     class list : protected _List_base<_Tp, _Alloc>
430     {
431       // concept requirements
432       typedef typename _Alloc::value_type                _Alloc_value_type;
433       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
434       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
435
436       typedef _List_base<_Tp, _Alloc>                    _Base;
437       typedef typename _Base::_Tp_alloc_type             _Tp_alloc_type;
438
439     public:
440       typedef _Tp                                        value_type;
441       typedef typename _Tp_alloc_type::pointer           pointer;
442       typedef typename _Tp_alloc_type::const_pointer     const_pointer;
443       typedef typename _Tp_alloc_type::reference         reference;
444       typedef typename _Tp_alloc_type::const_reference   const_reference;
445       typedef _List_iterator<_Tp>                        iterator;
446       typedef _List_const_iterator<_Tp>                  const_iterator;
447       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
448       typedef std::reverse_iterator<iterator>            reverse_iterator;
449       typedef size_t                                     size_type;
450       typedef ptrdiff_t                                  difference_type;
451       typedef _Alloc                                     allocator_type;
452
453     protected:
454       // Note that pointers-to-_Node's can be ctor-converted to
455       // iterator types.
456       typedef _List_node<_Tp>                            _Node;
457
458       using _Base::_M_impl;
459       using _Base::_M_put_node;
460       using _Base::_M_get_node;
461       using _Base::_M_get_Tp_allocator;
462       using _Base::_M_get_Node_allocator;
463
464       /**
465        *  @param  x  An instance of user data.
466        *
467        *  Allocates space for a new node and constructs a copy of @a x in it.
468        */
469 #ifndef __GXX_EXPERIMENTAL_CXX0X__
470       _Node*
471       _M_create_node(const value_type& __x)
472       {
473         _Node* __p = this->_M_get_node();
474         __try
475           {
476             _M_get_Tp_allocator().construct
477               (std::__addressof(__p->_M_data), __x);
478           }
479         __catch(...)
480           {
481             _M_put_node(__p);
482             __throw_exception_again;
483           }
484         return __p;
485       }
486 #else
487       template<typename... _Args>
488         _Node*
489         _M_create_node(_Args&&... __args)
490         {
491           _Node* __p = this->_M_get_node();
492           __try
493             {
494               _M_get_Node_allocator().construct(__p,
495                                                 std::forward<_Args>(__args)...);
496             }
497           __catch(...)
498             {
499               _M_put_node(__p);
500               __throw_exception_again;
501             }
502           return __p;
503         }
504 #endif
505
506     public:
507       // [23.2.2.1] construct/copy/destroy
508       // (assign() and get_allocator() are also listed in this section)
509       /**
510        *  @brief  Default constructor creates no elements.
511        */
512       list()
513       : _Base() { }
514
515       /**
516        *  @brief  Creates a %list with no elements.
517        *  @param  a  An allocator object.
518        */
519       explicit
520       list(const allocator_type& __a)
521       : _Base(__a) { }
522
523 #ifdef __GXX_EXPERIMENTAL_CXX0X__
524       /**
525        *  @brief  Creates a %list with default constructed elements.
526        *  @param  n  The number of elements to initially create.
527        *
528        *  This constructor fills the %list with @a n default
529        *  constructed elements.
530        */
531       explicit
532       list(size_type __n)
533       : _Base()
534       { _M_default_initialize(__n); }
535
536       /**
537        *  @brief  Creates a %list with copies of an exemplar element.
538        *  @param  n  The number of elements to initially create.
539        *  @param  value  An element to copy.
540        *  @param  a  An allocator object.
541        *
542        *  This constructor fills the %list with @a n copies of @a value.
543        */
544       list(size_type __n, const value_type& __value,
545            const allocator_type& __a = allocator_type())
546       : _Base(__a)
547       { _M_fill_initialize(__n, __value); }
548 #else
549       /**
550        *  @brief  Creates a %list with copies of an exemplar element.
551        *  @param  n  The number of elements to initially create.
552        *  @param  value  An element to copy.
553        *  @param  a  An allocator object.
554        *
555        *  This constructor fills the %list with @a n copies of @a value.
556        */
557       explicit
558       list(size_type __n, const value_type& __value = value_type(),
559            const allocator_type& __a = allocator_type())
560       : _Base(__a)
561       { _M_fill_initialize(__n, __value); }
562 #endif
563
564       /**
565        *  @brief  %List copy constructor.
566        *  @param  x  A %list of identical element and allocator types.
567        *
568        *  The newly-created %list uses a copy of the allocation object used
569        *  by @a x.
570        */
571       list(const list& __x)
572       : _Base(__x._M_get_Node_allocator())
573       { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
574
575 #ifdef __GXX_EXPERIMENTAL_CXX0X__
576       /**
577        *  @brief  %List move constructor.
578        *  @param  x  A %list of identical element and allocator types.
579        *
580        *  The newly-created %list contains the exact contents of @a x.
581        *  The contents of @a x are a valid, but unspecified %list.
582        */
583       list(list&& __x)
584       : _Base(std::move(__x)) { }
585
586       /**
587        *  @brief  Builds a %list from an initializer_list
588        *  @param  l  An initializer_list of value_type.
589        *  @param  a  An allocator object.
590        *
591        *  Create a %list consisting of copies of the elements in the
592        *  initializer_list @a l.  This is linear in l.size().
593        */
594       list(initializer_list<value_type> __l,
595            const allocator_type& __a = allocator_type())
596       : _Base(__a)
597       { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
598 #endif
599
600       /**
601        *  @brief  Builds a %list from a range.
602        *  @param  first  An input iterator.
603        *  @param  last  An input iterator.
604        *  @param  a  An allocator object.
605        *
606        *  Create a %list consisting of copies of the elements from
607        *  [@a first,@a last).  This is linear in N (where N is
608        *  distance(@a first,@a last)).
609        */
610       template<typename _InputIterator>
611         list(_InputIterator __first, _InputIterator __last,
612              const allocator_type& __a = allocator_type())
613         : _Base(__a)
614         { 
615           // Check whether it's an integral type.  If so, it's not an iterator.
616           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
617           _M_initialize_dispatch(__first, __last, _Integral());
618         }
619
620       /**
621        *  No explicit dtor needed as the _Base dtor takes care of
622        *  things.  The _Base dtor only erases the elements, and note
623        *  that if the elements themselves are pointers, the pointed-to
624        *  memory is not touched in any way.  Managing the pointer is
625        *  the user's responsibility.
626        */
627
628       /**
629        *  @brief  %List assignment operator.
630        *  @param  x  A %list of identical element and allocator types.
631        *
632        *  All the elements of @a x are copied, but unlike the copy
633        *  constructor, the allocator object is not copied.
634        */
635       list&
636       operator=(const list& __x);
637
638 #ifdef __GXX_EXPERIMENTAL_CXX0X__
639       /**
640        *  @brief  %List move assignment operator.
641        *  @param  x  A %list of identical element and allocator types.
642        *
643        *  The contents of @a x are moved into this %list (without copying).
644        *  @a x is a valid, but unspecified %list
645        */
646       list&
647       operator=(list&& __x)
648       {
649         // NB: DR 1204.
650         // NB: DR 675.
651         this->clear();
652         this->swap(__x);
653         return *this;
654       }
655
656       /**
657        *  @brief  %List initializer list assignment operator.
658        *  @param  l  An initializer_list of value_type.
659        *
660        *  Replace the contents of the %list with copies of the elements
661        *  in the initializer_list @a l.  This is linear in l.size().
662        */
663       list&
664       operator=(initializer_list<value_type> __l)
665       {
666         this->assign(__l.begin(), __l.end());
667         return *this;
668       }
669 #endif
670
671       /**
672        *  @brief  Assigns a given value to a %list.
673        *  @param  n  Number of elements to be assigned.
674        *  @param  val  Value to be assigned.
675        *
676        *  This function fills a %list with @a n copies of the given
677        *  value.  Note that the assignment completely changes the %list
678        *  and that the resulting %list's size is the same as the number
679        *  of elements assigned.  Old data may be lost.
680        */
681       void
682       assign(size_type __n, const value_type& __val)
683       { _M_fill_assign(__n, __val); }
684
685       /**
686        *  @brief  Assigns a range to a %list.
687        *  @param  first  An input iterator.
688        *  @param  last   An input iterator.
689        *
690        *  This function fills a %list with copies of the elements in the
691        *  range [@a first,@a last).
692        *
693        *  Note that the assignment completely changes the %list and
694        *  that the resulting %list's size is the same as the number of
695        *  elements assigned.  Old data may be lost.
696        */
697       template<typename _InputIterator>
698         void
699         assign(_InputIterator __first, _InputIterator __last)
700         {
701           // Check whether it's an integral type.  If so, it's not an iterator.
702           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
703           _M_assign_dispatch(__first, __last, _Integral());
704         }
705
706 #ifdef __GXX_EXPERIMENTAL_CXX0X__
707       /**
708        *  @brief  Assigns an initializer_list to a %list.
709        *  @param  l  An initializer_list of value_type.
710        *
711        *  Replace the contents of the %list with copies of the elements
712        *  in the initializer_list @a l.  This is linear in l.size().
713        */
714       void
715       assign(initializer_list<value_type> __l)
716       { this->assign(__l.begin(), __l.end()); }
717 #endif
718
719       /// Get a copy of the memory allocation object.
720       allocator_type
721       get_allocator() const _GLIBCXX_NOEXCEPT
722       { return _Base::get_allocator(); }
723
724       // iterators
725       /**
726        *  Returns a read/write iterator that points to the first element in the
727        *  %list.  Iteration is done in ordinary element order.
728        */
729       iterator
730       begin() _GLIBCXX_NOEXCEPT
731       { return iterator(this->_M_impl._M_node._M_next); }
732
733       /**
734        *  Returns a read-only (constant) iterator that points to the
735        *  first element in the %list.  Iteration is done in ordinary
736        *  element order.
737        */
738       const_iterator
739       begin() const _GLIBCXX_NOEXCEPT
740       { return const_iterator(this->_M_impl._M_node._M_next); }
741
742       /**
743        *  Returns a read/write iterator that points one past the last
744        *  element in the %list.  Iteration is done in ordinary element
745        *  order.
746        */
747       iterator
748       end() _GLIBCXX_NOEXCEPT
749       { return iterator(&this->_M_impl._M_node); }
750
751       /**
752        *  Returns a read-only (constant) iterator that points one past
753        *  the last element in the %list.  Iteration is done in ordinary
754        *  element order.
755        */
756       const_iterator
757       end() const _GLIBCXX_NOEXCEPT
758       { return const_iterator(&this->_M_impl._M_node); }
759
760       /**
761        *  Returns a read/write reverse iterator that points to the last
762        *  element in the %list.  Iteration is done in reverse element
763        *  order.
764        */
765       reverse_iterator
766       rbegin() _GLIBCXX_NOEXCEPT
767       { return reverse_iterator(end()); }
768
769       /**
770        *  Returns a read-only (constant) reverse iterator that points to
771        *  the last element in the %list.  Iteration is done in reverse
772        *  element order.
773        */
774       const_reverse_iterator
775       rbegin() const _GLIBCXX_NOEXCEPT
776       { return const_reverse_iterator(end()); }
777
778       /**
779        *  Returns a read/write reverse iterator that points to one
780        *  before the first element in the %list.  Iteration is done in
781        *  reverse element order.
782        */
783       reverse_iterator
784       rend() _GLIBCXX_NOEXCEPT
785       { return reverse_iterator(begin()); }
786
787       /**
788        *  Returns a read-only (constant) reverse iterator that points to one
789        *  before the first element in the %list.  Iteration is done in reverse
790        *  element order.
791        */
792       const_reverse_iterator
793       rend() const _GLIBCXX_NOEXCEPT
794       { return const_reverse_iterator(begin()); }
795
796 #ifdef __GXX_EXPERIMENTAL_CXX0X__
797       /**
798        *  Returns a read-only (constant) iterator that points to the
799        *  first element in the %list.  Iteration is done in ordinary
800        *  element order.
801        */
802       const_iterator
803       cbegin() const noexcept
804       { return const_iterator(this->_M_impl._M_node._M_next); }
805
806       /**
807        *  Returns a read-only (constant) iterator that points one past
808        *  the last element in the %list.  Iteration is done in ordinary
809        *  element order.
810        */
811       const_iterator
812       cend() const noexcept
813       { return const_iterator(&this->_M_impl._M_node); }
814
815       /**
816        *  Returns a read-only (constant) reverse iterator that points to
817        *  the last element in the %list.  Iteration is done in reverse
818        *  element order.
819        */
820       const_reverse_iterator
821       crbegin() const noexcept
822       { return const_reverse_iterator(end()); }
823
824       /**
825        *  Returns a read-only (constant) reverse iterator that points to one
826        *  before the first element in the %list.  Iteration is done in reverse
827        *  element order.
828        */
829       const_reverse_iterator
830       crend() const noexcept
831       { return const_reverse_iterator(begin()); }
832 #endif
833
834       // [23.2.2.2] capacity
835       /**
836        *  Returns true if the %list is empty.  (Thus begin() would equal
837        *  end().)
838        */
839       bool
840       empty() const _GLIBCXX_NOEXCEPT
841       { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
842
843       /**  Returns the number of elements in the %list.  */
844       size_type
845       size() const _GLIBCXX_NOEXCEPT
846       { return std::distance(begin(), end()); }
847
848       /**  Returns the size() of the largest possible %list.  */
849       size_type
850       max_size() const _GLIBCXX_NOEXCEPT
851       { return _M_get_Node_allocator().max_size(); }
852
853 #ifdef __GXX_EXPERIMENTAL_CXX0X__
854       /**
855        *  @brief Resizes the %list to the specified number of elements.
856        *  @param new_size Number of elements the %list should contain.
857        *
858        *  This function will %resize the %list to the specified number
859        *  of elements.  If the number is smaller than the %list's
860        *  current size the %list is truncated, otherwise default
861        *  constructed elements are appended.
862        */
863       void
864       resize(size_type __new_size);
865
866       /**
867        *  @brief Resizes the %list to the specified number of elements.
868        *  @param new_size Number of elements the %list should contain.
869        *  @param x Data with which new elements should be populated.
870        *
871        *  This function will %resize the %list to the specified number
872        *  of elements.  If the number is smaller than the %list's
873        *  current size the %list is truncated, otherwise the %list is
874        *  extended and new elements are populated with given data.
875        */
876       void
877       resize(size_type __new_size, const value_type& __x);
878 #else
879       /**
880        *  @brief Resizes the %list to the specified number of elements.
881        *  @param new_size Number of elements the %list should contain.
882        *  @param x Data with which new elements should be populated.
883        *
884        *  This function will %resize the %list to the specified number
885        *  of elements.  If the number is smaller than the %list's
886        *  current size the %list is truncated, otherwise the %list is
887        *  extended and new elements are populated with given data.
888        */
889       void
890       resize(size_type __new_size, value_type __x = value_type());
891 #endif
892
893       // element access
894       /**
895        *  Returns a read/write reference to the data at the first
896        *  element of the %list.
897        */
898       reference
899       front()
900       { return *begin(); }
901
902       /**
903        *  Returns a read-only (constant) reference to the data at the first
904        *  element of the %list.
905        */
906       const_reference
907       front() const
908       { return *begin(); }
909
910       /**
911        *  Returns a read/write reference to the data at the last element
912        *  of the %list.
913        */
914       reference
915       back()
916       { 
917         iterator __tmp = end();
918         --__tmp;
919         return *__tmp;
920       }
921
922       /**
923        *  Returns a read-only (constant) reference to the data at the last
924        *  element of the %list.
925        */
926       const_reference
927       back() const
928       { 
929         const_iterator __tmp = end();
930         --__tmp;
931         return *__tmp;
932       }
933
934       // [23.2.2.3] modifiers
935       /**
936        *  @brief  Add data to the front of the %list.
937        *  @param  x  Data to be added.
938        *
939        *  This is a typical stack operation.  The function creates an
940        *  element at the front of the %list and assigns the given data
941        *  to it.  Due to the nature of a %list this operation can be
942        *  done in constant time, and does not invalidate iterators and
943        *  references.
944        */
945       void
946       push_front(const value_type& __x)
947       { this->_M_insert(begin(), __x); }
948
949 #ifdef __GXX_EXPERIMENTAL_CXX0X__
950       void
951       push_front(value_type&& __x)
952       { this->_M_insert(begin(), std::move(__x)); }
953
954       template<typename... _Args>
955         void
956         emplace_front(_Args&&... __args)
957         { this->_M_insert(begin(), std::forward<_Args>(__args)...); }
958 #endif
959
960       /**
961        *  @brief  Removes first element.
962        *
963        *  This is a typical stack operation.  It shrinks the %list by
964        *  one.  Due to the nature of a %list this operation can be done
965        *  in constant time, and only invalidates iterators/references to
966        *  the element being removed.
967        *
968        *  Note that no data is returned, and if the first element's data
969        *  is needed, it should be retrieved before pop_front() is
970        *  called.
971        */
972       void
973       pop_front()
974       { this->_M_erase(begin()); }
975
976       /**
977        *  @brief  Add data to the end of the %list.
978        *  @param  x  Data to be added.
979        *
980        *  This is a typical stack operation.  The function creates an
981        *  element at the end of the %list and assigns the given data to
982        *  it.  Due to the nature of a %list this operation can be done
983        *  in constant time, and does not invalidate iterators and
984        *  references.
985        */
986       void
987       push_back(const value_type& __x)
988       { this->_M_insert(end(), __x); }
989
990 #ifdef __GXX_EXPERIMENTAL_CXX0X__
991       void
992       push_back(value_type&& __x)
993       { this->_M_insert(end(), std::move(__x)); }
994
995       template<typename... _Args>
996         void
997         emplace_back(_Args&&... __args)
998         { this->_M_insert(end(), std::forward<_Args>(__args)...); }
999 #endif
1000
1001       /**
1002        *  @brief  Removes last element.
1003        *
1004        *  This is a typical stack operation.  It shrinks the %list by
1005        *  one.  Due to the nature of a %list this operation can be done
1006        *  in constant time, and only invalidates iterators/references to
1007        *  the element being removed.
1008        *
1009        *  Note that no data is returned, and if the last element's data
1010        *  is needed, it should be retrieved before pop_back() is called.
1011        */
1012       void
1013       pop_back()
1014       { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
1015
1016 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1017       /**
1018        *  @brief  Constructs object in %list before specified iterator.
1019        *  @param  position  A const_iterator into the %list.
1020        *  @param  args  Arguments.
1021        *  @return  An iterator that points to the inserted data.
1022        *
1023        *  This function will insert an object of type T constructed
1024        *  with T(std::forward<Args>(args)...) before the specified
1025        *  location.  Due to the nature of a %list this operation can
1026        *  be done in constant time, and does not invalidate iterators
1027        *  and references.
1028        */
1029       template<typename... _Args>
1030         iterator
1031         emplace(iterator __position, _Args&&... __args);
1032 #endif
1033
1034       /**
1035        *  @brief  Inserts given value into %list before specified iterator.
1036        *  @param  position  An iterator into the %list.
1037        *  @param  x  Data to be inserted.
1038        *  @return  An iterator that points to the inserted data.
1039        *
1040        *  This function will insert a copy of the given value before
1041        *  the specified location.  Due to the nature of a %list this
1042        *  operation can be done in constant time, and does not
1043        *  invalidate iterators and references.
1044        */
1045       iterator
1046       insert(iterator __position, const value_type& __x);
1047
1048 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1049       /**
1050        *  @brief  Inserts given rvalue into %list before specified iterator.
1051        *  @param  position  An iterator into the %list.
1052        *  @param  x  Data to be inserted.
1053        *  @return  An iterator that points to the inserted data.
1054        *
1055        *  This function will insert a copy of the given rvalue before
1056        *  the specified location.  Due to the nature of a %list this
1057        *  operation can be done in constant time, and does not
1058        *  invalidate iterators and references.
1059         */
1060       iterator
1061       insert(iterator __position, value_type&& __x)
1062       { return emplace(__position, std::move(__x)); }
1063
1064       /**
1065        *  @brief  Inserts the contents of an initializer_list into %list
1066        *          before specified iterator.
1067        *  @param  p  An iterator into the %list.
1068        *  @param  l  An initializer_list of value_type.
1069        *
1070        *  This function will insert copies of the data in the
1071        *  initializer_list @a l into the %list before the location
1072        *  specified by @a p.
1073        *
1074        *  This operation is linear in the number of elements inserted and
1075        *  does not invalidate iterators and references.
1076        */
1077       void
1078       insert(iterator __p, initializer_list<value_type> __l)
1079       { this->insert(__p, __l.begin(), __l.end()); }
1080 #endif
1081
1082       /**
1083        *  @brief  Inserts a number of copies of given data into the %list.
1084        *  @param  position  An iterator into the %list.
1085        *  @param  n  Number of elements to be inserted.
1086        *  @param  x  Data to be inserted.
1087        *
1088        *  This function will insert a specified number of copies of the
1089        *  given data before the location specified by @a position.
1090        *
1091        *  This operation is linear in the number of elements inserted and
1092        *  does not invalidate iterators and references.
1093        */
1094       void
1095       insert(iterator __position, size_type __n, const value_type& __x)
1096       {  
1097         list __tmp(__n, __x, _M_get_Node_allocator());
1098         splice(__position, __tmp);
1099       }
1100
1101       /**
1102        *  @brief  Inserts a range into the %list.
1103        *  @param  position  An iterator into the %list.
1104        *  @param  first  An input iterator.
1105        *  @param  last   An input iterator.
1106        *
1107        *  This function will insert copies of the data in the range [@a
1108        *  first,@a last) into the %list before the location specified by
1109        *  @a position.
1110        *
1111        *  This operation is linear in the number of elements inserted and
1112        *  does not invalidate iterators and references.
1113        */
1114       template<typename _InputIterator>
1115         void
1116         insert(iterator __position, _InputIterator __first,
1117                _InputIterator __last)
1118         {
1119           list __tmp(__first, __last, _M_get_Node_allocator());
1120           splice(__position, __tmp);
1121         }
1122
1123       /**
1124        *  @brief  Remove element at given position.
1125        *  @param  position  Iterator pointing to element to be erased.
1126        *  @return  An iterator pointing to the next element (or end()).
1127        *
1128        *  This function will erase the element at the given position and thus
1129        *  shorten the %list by one.
1130        *
1131        *  Due to the nature of a %list this operation can be done in
1132        *  constant time, and only invalidates iterators/references to
1133        *  the element being removed.  The user is also cautioned that
1134        *  this function only erases the element, and that if the element
1135        *  is itself a pointer, the pointed-to memory is not touched in
1136        *  any way.  Managing the pointer is the user's responsibility.
1137        */
1138       iterator
1139       erase(iterator __position);
1140
1141       /**
1142        *  @brief  Remove a range of elements.
1143        *  @param  first  Iterator pointing to the first element to be erased.
1144        *  @param  last  Iterator pointing to one past the last element to be
1145        *                erased.
1146        *  @return  An iterator pointing to the element pointed to by @a last
1147        *           prior to erasing (or end()).
1148        *
1149        *  This function will erase the elements in the range @a
1150        *  [first,last) and shorten the %list accordingly.
1151        *
1152        *  This operation is linear time in the size of the range and only
1153        *  invalidates iterators/references to the element being removed.
1154        *  The user is also cautioned that this function only erases the
1155        *  elements, and that if the elements themselves are pointers, the
1156        *  pointed-to memory is not touched in any way.  Managing the pointer
1157        *  is the user's responsibility.
1158        */
1159       iterator
1160       erase(iterator __first, iterator __last)
1161       {
1162         while (__first != __last)
1163           __first = erase(__first);
1164         return __last;
1165       }
1166
1167       /**
1168        *  @brief  Swaps data with another %list.
1169        *  @param  x  A %list of the same element and allocator types.
1170        *
1171        *  This exchanges the elements between two lists in constant
1172        *  time.  Note that the global std::swap() function is
1173        *  specialized such that std::swap(l1,l2) will feed to this
1174        *  function.
1175        */
1176       void
1177       swap(list& __x)
1178       {
1179         __detail::_List_node_base::swap(this->_M_impl._M_node, 
1180                                         __x._M_impl._M_node);
1181
1182         // _GLIBCXX_RESOLVE_LIB_DEFECTS
1183         // 431. Swapping containers with unequal allocators.
1184         std::__alloc_swap<typename _Base::_Node_alloc_type>::
1185           _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator());
1186       }
1187
1188       /**
1189        *  Erases all the elements.  Note that this function only erases
1190        *  the elements, and that if the elements themselves are
1191        *  pointers, the pointed-to memory is not touched in any way.
1192        *  Managing the pointer is the user's responsibility.
1193        */
1194       void
1195       clear() _GLIBCXX_NOEXCEPT
1196       {
1197         _Base::_M_clear();
1198         _Base::_M_init();
1199       }
1200
1201       // [23.2.2.4] list operations
1202       /**
1203        *  @brief  Insert contents of another %list.
1204        *  @param  position  Iterator referencing the element to insert before.
1205        *  @param  x  Source list.
1206        *
1207        *  The elements of @a x are inserted in constant time in front of
1208        *  the element referenced by @a position.  @a x becomes an empty
1209        *  list.
1210        *
1211        *  Requires this != @a x.
1212        */
1213       void
1214 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1215       splice(iterator __position, list&& __x)
1216 #else
1217       splice(iterator __position, list& __x)
1218 #endif
1219       {
1220         if (!__x.empty())
1221           {
1222             _M_check_equal_allocators(__x);
1223
1224             this->_M_transfer(__position, __x.begin(), __x.end());
1225           }
1226       }
1227
1228 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1229       void
1230       splice(iterator __position, list& __x)
1231       { splice(__position, std::move(__x)); }
1232 #endif
1233
1234       /**
1235        *  @brief  Insert element from another %list.
1236        *  @param  position  Iterator referencing the element to insert before.
1237        *  @param  x  Source list.
1238        *  @param  i  Iterator referencing the element to move.
1239        *
1240        *  Removes the element in list @a x referenced by @a i and
1241        *  inserts it into the current list before @a position.
1242        */
1243       void
1244 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1245       splice(iterator __position, list&& __x, iterator __i)
1246 #else
1247       splice(iterator __position, list& __x, iterator __i)
1248 #endif
1249       {
1250         iterator __j = __i;
1251         ++__j;
1252         if (__position == __i || __position == __j)
1253           return;
1254
1255         if (this != &__x)
1256           _M_check_equal_allocators(__x);
1257
1258         this->_M_transfer(__position, __i, __j);
1259       }
1260
1261 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1262       void
1263       splice(iterator __position, list& __x, iterator __i)
1264       { splice(__position, std::move(__x), __i); }
1265 #endif
1266
1267       /**
1268        *  @brief  Insert range from another %list.
1269        *  @param  position  Iterator referencing the element to insert before.
1270        *  @param  x  Source list.
1271        *  @param  first  Iterator referencing the start of range in x.
1272        *  @param  last  Iterator referencing the end of range in x.
1273        *
1274        *  Removes elements in the range [first,last) and inserts them
1275        *  before @a position in constant time.
1276        *
1277        *  Undefined if @a position is in [first,last).
1278        */
1279       void
1280 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1281       splice(iterator __position, list&& __x, iterator __first,
1282              iterator __last)
1283 #else
1284       splice(iterator __position, list& __x, iterator __first,
1285              iterator __last)
1286 #endif
1287       {
1288         if (__first != __last)
1289           {
1290             if (this != &__x)
1291               _M_check_equal_allocators(__x);
1292
1293             this->_M_transfer(__position, __first, __last);
1294           }
1295       }
1296
1297 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1298       void
1299       splice(iterator __position, list& __x, iterator __first, iterator __last)
1300       { splice(__position, std::move(__x), __first, __last); }
1301 #endif
1302
1303       /**
1304        *  @brief  Remove all elements equal to value.
1305        *  @param  value  The value to remove.
1306        *
1307        *  Removes every element in the list equal to @a value.
1308        *  Remaining elements stay in list order.  Note that this
1309        *  function only erases the elements, and that if the elements
1310        *  themselves are pointers, the pointed-to memory is not
1311        *  touched in any way.  Managing the pointer is the user's
1312        *  responsibility.
1313        */
1314       void
1315       remove(const _Tp& __value);
1316
1317       /**
1318        *  @brief  Remove all elements satisfying a predicate.
1319        *  @param  Predicate  Unary predicate function or object.
1320        *
1321        *  Removes every element in the list for which the predicate
1322        *  returns true.  Remaining elements stay in list order.  Note
1323        *  that this function only erases the elements, and that if the
1324        *  elements themselves are pointers, the pointed-to memory is
1325        *  not touched in any way.  Managing the pointer is the user's
1326        *  responsibility.
1327        */
1328       template<typename _Predicate>
1329         void
1330         remove_if(_Predicate);
1331
1332       /**
1333        *  @brief  Remove consecutive duplicate elements.
1334        *
1335        *  For each consecutive set of elements with the same value,
1336        *  remove all but the first one.  Remaining elements stay in
1337        *  list order.  Note that this function only erases the
1338        *  elements, and that if the elements themselves are pointers,
1339        *  the pointed-to memory is not touched in any way.  Managing
1340        *  the pointer is the user's responsibility.
1341        */
1342       void
1343       unique();
1344
1345       /**
1346        *  @brief  Remove consecutive elements satisfying a predicate.
1347        *  @param  BinaryPredicate  Binary predicate function or object.
1348        *
1349        *  For each consecutive set of elements [first,last) that
1350        *  satisfy predicate(first,i) where i is an iterator in
1351        *  [first,last), remove all but the first one.  Remaining
1352        *  elements stay in list order.  Note that this function only
1353        *  erases the elements, and that if the elements themselves are
1354        *  pointers, the pointed-to memory is not touched in any way.
1355        *  Managing the pointer is the user's responsibility.
1356        */
1357       template<typename _BinaryPredicate>
1358         void
1359         unique(_BinaryPredicate);
1360
1361       /**
1362        *  @brief  Merge sorted lists.
1363        *  @param  x  Sorted list to merge.
1364        *
1365        *  Assumes that both @a x and this list are sorted according to
1366        *  operator<().  Merges elements of @a x into this list in
1367        *  sorted order, leaving @a x empty when complete.  Elements in
1368        *  this list precede elements in @a x that are equal.
1369        */
1370 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1371       void
1372       merge(list&& __x);
1373
1374       void
1375       merge(list& __x)
1376       { merge(std::move(__x)); }
1377 #else
1378       void
1379       merge(list& __x);
1380 #endif
1381
1382       /**
1383        *  @brief  Merge sorted lists according to comparison function.
1384        *  @param  x  Sorted list to merge.
1385        *  @param StrictWeakOrdering Comparison function defining
1386        *  sort order.
1387        *
1388        *  Assumes that both @a x and this list are sorted according to
1389        *  StrictWeakOrdering.  Merges elements of @a x into this list
1390        *  in sorted order, leaving @a x empty when complete.  Elements
1391        *  in this list precede elements in @a x that are equivalent
1392        *  according to StrictWeakOrdering().
1393        */
1394 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1395       template<typename _StrictWeakOrdering>
1396         void
1397         merge(list&&, _StrictWeakOrdering);
1398
1399       template<typename _StrictWeakOrdering>
1400         void
1401         merge(list& __x, _StrictWeakOrdering __comp)
1402         { merge(std::move(__x), __comp); }
1403 #else
1404       template<typename _StrictWeakOrdering>
1405         void
1406         merge(list&, _StrictWeakOrdering);
1407 #endif
1408
1409       /**
1410        *  @brief  Reverse the elements in list.
1411        *
1412        *  Reverse the order of elements in the list in linear time.
1413        */
1414       void
1415       reverse() _GLIBCXX_NOEXCEPT
1416       { this->_M_impl._M_node._M_reverse(); }
1417
1418       /**
1419        *  @brief  Sort the elements.
1420        *
1421        *  Sorts the elements of this list in NlogN time.  Equivalent
1422        *  elements remain in list order.
1423        */
1424       void
1425       sort();
1426
1427       /**
1428        *  @brief  Sort the elements according to comparison function.
1429        *
1430        *  Sorts the elements of this list in NlogN time.  Equivalent
1431        *  elements remain in list order.
1432        */
1433       template<typename _StrictWeakOrdering>
1434         void
1435         sort(_StrictWeakOrdering);
1436
1437     protected:
1438       // Internal constructor functions follow.
1439
1440       // Called by the range constructor to implement [23.1.1]/9
1441
1442       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1443       // 438. Ambiguity in the "do the right thing" clause
1444       template<typename _Integer>
1445         void
1446         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1447         { _M_fill_initialize(static_cast<size_type>(__n), __x); }
1448
1449       // Called by the range constructor to implement [23.1.1]/9
1450       template<typename _InputIterator>
1451         void
1452         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1453                                __false_type)
1454         {
1455           for (; __first != __last; ++__first)
1456             push_back(*__first);
1457         }
1458
1459       // Called by list(n,v,a), and the range constructor when it turns out
1460       // to be the same thing.
1461       void
1462       _M_fill_initialize(size_type __n, const value_type& __x)
1463       {
1464         for (; __n; --__n)
1465           push_back(__x);
1466       }
1467
1468 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1469       // Called by list(n).
1470       void
1471       _M_default_initialize(size_type __n)
1472       {
1473         for (; __n; --__n)
1474           emplace_back();
1475       }
1476
1477       // Called by resize(sz).
1478       void
1479       _M_default_append(size_type __n);
1480 #endif
1481
1482       // Internal assign functions follow.
1483
1484       // Called by the range assign to implement [23.1.1]/9
1485
1486       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1487       // 438. Ambiguity in the "do the right thing" clause
1488       template<typename _Integer>
1489         void
1490         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1491         { _M_fill_assign(__n, __val); }
1492
1493       // Called by the range assign to implement [23.1.1]/9
1494       template<typename _InputIterator>
1495         void
1496         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1497                            __false_type);
1498
1499       // Called by assign(n,t), and the range assign when it turns out
1500       // to be the same thing.
1501       void
1502       _M_fill_assign(size_type __n, const value_type& __val);
1503
1504
1505       // Moves the elements from [first,last) before position.
1506       void
1507       _M_transfer(iterator __position, iterator __first, iterator __last)
1508       { __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
1509
1510       // Inserts new element at position given and with value given.
1511 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1512       void
1513       _M_insert(iterator __position, const value_type& __x)
1514       {
1515         _Node* __tmp = _M_create_node(__x);
1516         __tmp->_M_hook(__position._M_node);
1517       }
1518 #else
1519      template<typename... _Args>
1520        void
1521        _M_insert(iterator __position, _Args&&... __args)
1522        {
1523          _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
1524          __tmp->_M_hook(__position._M_node);
1525        }
1526 #endif
1527
1528       // Erases element at position given.
1529       void
1530       _M_erase(iterator __position)
1531       {
1532         __position._M_node->_M_unhook();
1533         _Node* __n = static_cast<_Node*>(__position._M_node);
1534 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1535         _M_get_Node_allocator().destroy(__n);
1536 #else
1537         _M_get_Tp_allocator().destroy(std::__addressof(__n->_M_data));
1538 #endif
1539         _M_put_node(__n);
1540       }
1541
1542       // To implement the splice (and merge) bits of N1599.
1543       void
1544       _M_check_equal_allocators(list& __x)
1545       {
1546         if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
1547             _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
1548           __throw_runtime_error(__N("list::_M_check_equal_allocators"));
1549       }
1550     };
1551
1552   /**
1553    *  @brief  List equality comparison.
1554    *  @param  x  A %list.
1555    *  @param  y  A %list of the same type as @a x.
1556    *  @return  True iff the size and elements of the lists are equal.
1557    *
1558    *  This is an equivalence relation.  It is linear in the size of
1559    *  the lists.  Lists are considered equivalent if their sizes are
1560    *  equal, and if corresponding elements compare equal.
1561   */
1562   template<typename _Tp, typename _Alloc>
1563     inline bool
1564     operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1565     {
1566       typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
1567       const_iterator __end1 = __x.end();
1568       const_iterator __end2 = __y.end();
1569
1570       const_iterator __i1 = __x.begin();
1571       const_iterator __i2 = __y.begin();
1572       while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
1573         {
1574           ++__i1;
1575           ++__i2;
1576         }
1577       return __i1 == __end1 && __i2 == __end2;
1578     }
1579
1580   /**
1581    *  @brief  List ordering relation.
1582    *  @param  x  A %list.
1583    *  @param  y  A %list of the same type as @a x.
1584    *  @return  True iff @a x is lexicographically less than @a y.
1585    *
1586    *  This is a total ordering relation.  It is linear in the size of the
1587    *  lists.  The elements must be comparable with @c <.
1588    *
1589    *  See std::lexicographical_compare() for how the determination is made.
1590   */
1591   template<typename _Tp, typename _Alloc>
1592     inline bool
1593     operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1594     { return std::lexicographical_compare(__x.begin(), __x.end(),
1595                                           __y.begin(), __y.end()); }
1596
1597   /// Based on operator==
1598   template<typename _Tp, typename _Alloc>
1599     inline bool
1600     operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1601     { return !(__x == __y); }
1602
1603   /// Based on operator<
1604   template<typename _Tp, typename _Alloc>
1605     inline bool
1606     operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1607     { return __y < __x; }
1608
1609   /// Based on operator<
1610   template<typename _Tp, typename _Alloc>
1611     inline bool
1612     operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1613     { return !(__y < __x); }
1614
1615   /// Based on operator<
1616   template<typename _Tp, typename _Alloc>
1617     inline bool
1618     operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1619     { return !(__x < __y); }
1620
1621   /// See std::list::swap().
1622   template<typename _Tp, typename _Alloc>
1623     inline void
1624     swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
1625     { __x.swap(__y); }
1626
1627 _GLIBCXX_END_NAMESPACE_CONTAINER
1628 } // namespace std
1629
1630 #endif /* _STL_LIST_H */