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