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 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.
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) throw ();
83 
84  void
85  _M_transfer(_List_node_base* const __first,
86  _List_node_base* const __last) throw ();
87 
88  void
89  _M_reverse() throw ();
90 
91  void
92  _M_hook(_List_node_base* const __position) throw ();
93 
94  void
95  _M_unhook() throw ();
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>
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>
125  {
126  typedef _List_iterator<_Tp> _Self;
127  typedef _List_node<_Tp> _Node;
128 
129  typedef ptrdiff_t difference_type;
131  typedef _Tp value_type;
132  typedef _Tp* pointer;
133  typedef _Tp& reference;
134 
136  : _M_node() { }
137 
138  explicit
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>
200  {
202  typedef const _List_node<_Tp> _Node;
204 
205  typedef ptrdiff_t difference_type;
207  typedef _Tp value_type;
208  typedef const _Tp* pointer;
209  typedef const _Tp& reference;
210 
212  : _M_node() { }
213 
214  explicit
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>
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  {
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 
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()
338  { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
339 
340  const _Node_alloc_type&
341  _M_get_Node_allocator() const
342  { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
343 
344  _Tp_alloc_type
345  _M_get_Tp_allocator() const
346  { return _Tp_alloc_type(_M_get_Node_allocator()); }
347 
348  allocator_type
349  get_allocator() const
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 
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;
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  */
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  */
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&
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&
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
716  { this->assign(__l.begin(), __l.end()); }
717 #endif
718 
719  /// Get a copy of the memory allocation object.
720  allocator_type
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
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
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()
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
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  */
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
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  */
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
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
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
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
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
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
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
846  { return std::distance(begin(), end()); }
847 
848  /** Returns the size() of the largest possible %list. */
849  size_type
850  max_size() const
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
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
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
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
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
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
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
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
1625  { __x.swap(__y); }
1626 
1627 _GLIBCXX_END_NAMESPACE_CONTAINER
1628 } // namespace std
1629 
1630 #endif /* _STL_LIST_H */
void assign(initializer_list< value_type > __l)
Assigns an initializer_list to a list.
Definition: stl_list.h:715
reference back()
Definition: stl_list.h:915
const_iterator end() const
Definition: stl_list.h:757
list(size_type __n)
Creates a list with default constructed elements.
Definition: stl_list.h:532
void pop_back()
Removes last element.
Definition: stl_list.h:1013
Common part of a node in the list.
Definition: stl_list.h:76
iterator begin()
Definition: stl_list.h:730
iterator insert(iterator __position, value_type &&__x)
Inserts given rvalue into list before specified iterator.
Definition: stl_list.h:1061
iterator erase(iterator __first, iterator __last)
Remove a range of elements.
Definition: stl_list.h:1160
void splice(iterator __position, list &&__x, iterator __first, iterator __last)
Insert range from another list.
Definition: stl_list.h:1281
void insert(iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the list.
Definition: stl_list.h:1116
const_iterator cend() const
Definition: stl_list.h:812
void insert(iterator __p, initializer_list< value_type > __l)
Inserts the contents of an initializer_list into list before specified iterator.
Definition: stl_list.h:1078
iterator erase(iterator __position)
Remove element at given position.
Definition: list.tcc:110
list(const list &__x)
List copy constructor.
Definition: stl_list.h:571
A list::const_iterator.
Definition: stl_list.h:199
list(const allocator_type &__a)
Creates a list with no elements.
Definition: stl_list.h:520
void splice(iterator __position, list &&__x)
Insert contents of another list.
Definition: stl_list.h:1215
list & operator=(list &&__x)
List move assignment operator.
Definition: stl_list.h:647
reference front()
Definition: stl_list.h:899
_Tp _M_data
< User's data.
Definition: stl_list.h:108
void sort()
Sort the elements.
Definition: list.tcc:355
void merge(list &&__x)
Merge sorted lists.
Definition: list.tcc:289
void resize(size_type __new_size)
Resizes the list to the specified number of elements.
Definition: list.tcc:140
const_reference back() const
Definition: stl_list.h:927
reverse_iterator rbegin()
Definition: stl_list.h:766
const_reverse_iterator crbegin() const
Definition: stl_list.h:821
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a list.
Definition: stl_list.h:699
list(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a list from an initializer_list.
Definition: stl_list.h:594
void remove_if(_Predicate)
Remove all elements satisfying a predicate.
Definition: list.tcc:393
void splice(iterator __position, list &&__x, iterator __i)
Insert element from another list.
Definition: stl_list.h:1245
list(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a list from a range.
Definition: stl_list.h:611
void push_back(const value_type &__x)
Add data to the end of the list.
Definition: stl_list.h:987
void push_front(const value_type &__x)
Add data to the front of the list.
Definition: stl_list.h:946
void assign(size_type __n, const value_type &__val)
Assigns a given value to a list.
Definition: stl_list.h:682
_Node * _M_create_node(_Args &&...__args)
Definition: stl_list.h:489
iterator emplace(iterator __position, _Args &&...__args)
Constructs object in list before specified iterator.
Bidirectional iterators support a superset of forward iterator operations.
size_type size() const
Definition: stl_list.h:845
void swap(list &__x)
Swaps data with another list.
Definition: stl_list.h:1177
iterator insert(iterator __position, const value_type &__x)
Inserts given value into list before specified iterator.
Definition: list.tcc:100
See bits/stl_deque.h's _Deque_base for an explanation.
Definition: stl_list.h:288
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
void insert(iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the list.
Definition: stl_list.h:1095
initializer_list
void clear()
Definition: stl_list.h:1195
iterator end()
Definition: stl_list.h:748
size_type max_size() const
Definition: stl_list.h:850
An actual node in the list.
Definition: stl_list.h:105
reverse_iterator rend()
Definition: stl_list.h:784
list & operator=(const list &__x)
List assignment operator.
Definition: list.tcc:186
const_reverse_iterator crend() const
Definition: stl_list.h:830
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
const_iterator cbegin() const
Definition: stl_list.h:803
const_reference front() const
Definition: stl_list.h:907
list()
Default constructor creates no elements.
Definition: stl_list.h:512
list(list &&__x)
List move constructor.
Definition: stl_list.h:583
list & operator=(initializer_list< value_type > __l)
List initializer list assignment operator.
Definition: stl_list.h:664
void reverse()
Reverse the elements in list.
Definition: stl_list.h:1415
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: stl_list.h:429
const_reverse_iterator rbegin() const
Definition: stl_list.h:775
list(size_type __n, const value_type &__value, const allocator_type &__a=allocator_type())
Creates a list with copies of an exemplar element.
Definition: stl_list.h:544
allocator_type get_allocator() const
Get a copy of the memory allocation object.
Definition: stl_list.h:721
const_iterator begin() const
Definition: stl_list.h:739
Common iterator class.
void pop_front()
Removes first element.
Definition: stl_list.h:973
_Tp && forward(typename std::remove_reference< _Tp >::type &__t)
forward (as per N3143)
Definition: move.h:62
const_reverse_iterator rend() const
Definition: stl_list.h:793
void unique()
Remove consecutive duplicate elements.
Definition: list.tcc:268
A list::iterator.
Definition: stl_list.h:124
bool empty() const
Definition: stl_list.h:840