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