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