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