libstdc++
stl_list.h
Go to the documentation of this file.
1 // List implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2025 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 #include <debug/assertions.h>
63 #if __cplusplus >= 201103L
64 #include <initializer_list>
65 #include <bits/allocated_ptr.h>
66 #include <bits/ptr_traits.h>
67 #include <ext/aligned_buffer.h>
68 #endif
69 #if __glibcxx_containers_ranges // C++ >= 23
70 # include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
71 # include <bits/ranges_util.h> // ranges::subrange
72 #endif
73 
74 #if __cplusplus < 201103L
75 # undef _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
76 # define _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 0
77 #elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
78 # define _GLIBCXX_USE_ALLOC_PTR_FOR_LIST 1
79 #endif
80 
81 namespace std _GLIBCXX_VISIBILITY(default)
82 {
83 _GLIBCXX_BEGIN_NAMESPACE_VERSION
84 
85  namespace __detail
86  {
87  // Supporting structures are split into common and templated
88  // types; the latter publicly inherits from the former in an
89  // effort to reduce code duplication. This results in some
90  // "needless" static_cast'ing later on, but it's all safe
91  // downcasting.
92 
93  /// Common part of a node in the %list.
95  {
96  typedef _List_node_base* _Base_ptr;
97 
98  _List_node_base* _M_next;
99  _List_node_base* _M_prev;
100 
101  static void
102  swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
103 
104  void
105  _M_transfer(_List_node_base* const __first,
106  _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
107 
108  void
109  _M_reverse() _GLIBCXX_USE_NOEXCEPT;
110 
111  void
112  _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
113 
114  void
115  _M_unhook() _GLIBCXX_USE_NOEXCEPT;
116 
117  _List_node_base* _M_base() { return this; }
118  const _List_node_base* _M_base() const { return this; }
119  };
120 
121  struct _List_size
122  {
123 #if _GLIBCXX_USE_CXX11_ABI
124  // Store the size here so that std::list::size() is fast.
125  size_t _M_size;
126 #endif
127  };
128 
129  /// The %list node header.
130  struct _List_node_header : public _List_node_base, _List_size
131  {
132  _List_node_header() _GLIBCXX_NOEXCEPT
133  { _M_init(); }
134 
135 #if __cplusplus >= 201103L
136  _List_node_header(_List_node_header&& __x) noexcept
137  : _List_node_base(__x), _List_size(__x)
138  {
139  if (__x._M_base()->_M_next == __x._M_base())
140  this->_M_next = this->_M_prev = this;
141  else
142  {
143  this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base();
144  __x._M_init();
145  }
146  }
147 
148  void
149  _M_move_nodes(_List_node_header&& __x)
150  {
151  _List_node_base* const __xnode = __x._M_base();
152  if (__xnode->_M_next == __xnode)
153  _M_init();
154  else
155  {
156  _List_node_base* const __node = this->_M_base();
157  __node->_M_next = __xnode->_M_next;
158  __node->_M_prev = __xnode->_M_prev;
159  __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;
160  _List_size::operator=(__x);
161  __x._M_init();
162  }
163  }
164 #endif
165 
166  void
167  _M_init() _GLIBCXX_NOEXCEPT
168  {
169  this->_M_next = this->_M_prev = this;
170  _List_size::operator=(_List_size());
171  }
172 
173  using _List_node_base::_M_base;
174 #if ! _GLIBCXX_INLINE_VERSION
175  _List_node_base* _M_base() { return this; } // XXX GLIBCXX_ABI Deprecated
176 #endif
177  };
178 
179  } // namespace detail
180 
181 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
182 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
183 _GLIBCXX_BEGIN_NAMESPACE_CXX11
184  template<typename _Tp, typename _Allocator> class list;
185 _GLIBCXX_END_NAMESPACE_CXX11
186 _GLIBCXX_END_NAMESPACE_CONTAINER
187 
188 namespace __list
189 {
190  // The base class for a list node. Contains the pointers connecting nodes.
191  template<typename _VoidPtr>
192  struct _Node_base
193  {
194  using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
195  _Base_ptr _M_next;
196  _Base_ptr _M_prev;
197 
198  static void
199  swap(_Node_base& __x, _Node_base& __y) noexcept;
200 
201  void
202  _M_transfer(_Base_ptr const __first, _Base_ptr const __last) noexcept;
203 
204  void
205  _M_hook(_Base_ptr const __position) noexcept
206  {
207  auto __self = this->_M_base();
208  this->_M_next = __position;
209  this->_M_prev = __position->_M_prev;
210  __position->_M_prev->_M_next = __self;
211  __position->_M_prev = __self;
212  }
213 
214  void
215  _M_unhook() noexcept
216  {
217  auto const __next_node = this->_M_next;
218  auto const __prev_node = this->_M_prev;
219  __prev_node->_M_next = __next_node;
220  __next_node->_M_prev = __prev_node;
221  }
222 
223  // This is not const-correct, but it's only used in a const access path
224  // by std::list::empty(), where it doesn't escape, and by
225  // std::list::end() const, where the pointer is used to initialize a
226  // const_iterator and so constness is restored.
227  // The standard allows pointer_to to be potentially-throwing,
228  // but we have to assume it doesn't throw to implement std::list.
229  _Base_ptr
230  _M_base() const noexcept
231  {
232  return pointer_traits<_Base_ptr>::
233  pointer_to(const_cast<_Node_base&>(*this));
234  }
235  };
236 
237  using ::std::__detail::_List_size;
238 
239  // The special sentinel node contained by a std::list.
240  // begin()->_M_node->_M_prev and end()->_M_node point to this header.
241  // This is not a complete node, as it doesn't contain a value.
242  template<typename _VoidPtr>
243  struct _Node_header
244  : public _Node_base<_VoidPtr>, _List_size
245  {
246  _Node_header() noexcept
247  { _M_init(); }
248 
249  _Node_header(_Node_header&& __x) noexcept
250  : _Node_base<_VoidPtr>(__x), _List_size(__x)
251  {
252  if (__x._M_base()->_M_next == __x._M_base())
253  this->_M_next = this->_M_prev = this->_M_base();
254  else
255  {
256  this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base();
257  __x._M_init();
258  }
259  }
260 
261  void
262  _M_move_nodes(_Node_header&& __x) noexcept
263  {
264  auto const __xnode = __x._M_base();
265  if (__xnode->_M_next == __xnode)
266  _M_init();
267  else
268  {
269  auto const __node = this->_M_base();
270  __node->_M_next = __xnode->_M_next;
271  __node->_M_prev = __xnode->_M_prev;
272  __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;
273  _List_size::operator=(__x);
274  __x._M_init();
275  }
276  }
277 
278  void
279  _M_init() noexcept
280  {
281  this->_M_next = this->_M_prev = this->_M_base();
282  _List_size::operator=(_List_size());
283  }
284 
285  void _M_reverse() noexcept;
286  };
287 
288  // The node type used for allocators with fancy pointers.
289  template<typename _ValPtr>
290  struct _Node : public __list::_Node_base<__ptr_rebind<_ValPtr, void>>
291  {
292  using value_type = typename pointer_traits<_ValPtr>::element_type;
293  using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
294 
295  _Node() noexcept { }
296  ~_Node() { }
297  _Node(_Node&&) = delete;
298 
299  union _Uninit_storage
300  {
301  _Uninit_storage() noexcept { }
302  ~_Uninit_storage() { }
303 
304  value_type _M_data;
305  };
306  _Uninit_storage _M_u;
307 
308  value_type*
309  _M_valptr() noexcept { return std::__addressof(_M_u._M_data); }
310 
311  value_type const*
312  _M_valptr() const noexcept { return std::__addressof(_M_u._M_data); }
313 
314  _Node_ptr
315  _M_node_ptr()
316  { return pointer_traits<_Node_ptr>::pointer_to(*this); }
317  };
318 
319  template<bool _Const, typename _Ptr> class _Iterator;
320 
321  template<bool _Const, typename _Ptr>
322  class _Iterator
323  {
324  using _Node = __list::_Node<_Ptr>;
325  using _Base_ptr
326  = typename __list::_Node_base<__ptr_rebind<_Ptr, void>>::_Base_ptr;
327 
328  template<typename _Tp>
329  using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;
330 
331  public:
332  using value_type = typename pointer_traits<_Ptr>::element_type;
333  using difference_type = ptrdiff_t;
334  using iterator_category = bidirectional_iterator_tag;
335  using pointer = __maybe_const<value_type>*;
336  using reference = __maybe_const<value_type>&;
337 
338  constexpr _Iterator() noexcept : _M_node() { }
339 
340  _Iterator(const _Iterator&) = default;
341  _Iterator& operator=(const _Iterator&) = default;
342 
343 #ifdef __glibcxx_concepts
344  constexpr
345  _Iterator(const _Iterator<false, _Ptr>& __i) requires _Const
346 #else
347  template<bool _OtherConst,
348  typename = __enable_if_t<_Const && !_OtherConst>>
349  constexpr
350  _Iterator(const _Iterator<_OtherConst, _Ptr>& __i)
351 #endif
352  : _M_node(__i._M_node) { }
353 
354  constexpr explicit
355  _Iterator(_Base_ptr __x) noexcept
356  : _M_node(__x) { }
357 
358  // Must downcast from _Node_base to _Node to get to value.
359  [[__nodiscard__]]
360  constexpr reference
361  operator*() const noexcept
362  { return static_cast<_Node&>(*_M_node)._M_u._M_data; }
363 
364  [[__nodiscard__]]
365  constexpr pointer
366  operator->() const noexcept
367  { return std::__addressof(operator*()); }
368 
369  _GLIBCXX14_CONSTEXPR _Iterator&
370  operator++() noexcept
371  {
372  _M_node = _M_node->_M_next;
373  return *this;
374  }
375 
376  _GLIBCXX14_CONSTEXPR _Iterator
377  operator++(int) noexcept
378  {
379  auto __tmp = *this;
380  _M_node = _M_node->_M_next;
381  return __tmp;
382  }
383 
384  _GLIBCXX14_CONSTEXPR _Iterator&
385  operator--() noexcept
386  {
387  _M_node = _M_node->_M_prev;
388  return *this;
389  }
390 
391  _GLIBCXX14_CONSTEXPR _Iterator
392  operator--(int) noexcept
393  {
394  auto __tmp = *this;
395  _M_node = _M_node->_M_prev;
396  return __tmp;
397  }
398 
399  [[__nodiscard__]]
400  friend constexpr bool
401  operator==(const _Iterator& __x, const _Iterator& __y) noexcept
402  { return __x._M_node == __y._M_node; }
403 
404 #if __cpp_impl_three_way_comparison < 201907L
405  [[__nodiscard__]]
406  friend constexpr bool
407  operator!=(const _Iterator& __x, const _Iterator& __y) noexcept
408  { return __x._M_node != __y._M_node; }
409 #endif
410 
411  private:
412  template<typename _Tp, typename _Allocator>
413  friend class _GLIBCXX_STD_C::list;
414 
415  friend _Iterator<!_Const, _Ptr>;
416 
417  constexpr _Iterator<false, _Ptr>
418  _M_const_cast() const noexcept
419  { return _Iterator<false, _Ptr>(_M_node); }
420 
421  _Base_ptr _M_node;
422  };
423 } // namespace __list
424 #endif // USE_ALLOC_PTR_FOR_LIST
425 
426 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
427  template<typename _Tp> struct _List_node;
428  template<typename _Tp> struct _List_iterator;
429  template<typename _Tp> struct _List_const_iterator;
430 _GLIBCXX_END_NAMESPACE_CONTAINER
431 
432 namespace __list
433 {
434  // Determine the node and iterator types used by std::list.
435  template<typename _Tp, typename _Ptr>
436  struct _Node_traits;
437 
438 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST <= 9000
439  // Specialization for the simple case where the allocator's pointer type
440  // is the same type as value_type*.
441  // For ABI compatibility we can't change the types used for this case.
442  template<typename _Tp>
443  struct _Node_traits<_Tp, _Tp*>
444  {
445  typedef __detail::_List_node_base _Node_base;
446  typedef __detail::_List_node_header _Node_header;
447  typedef _GLIBCXX_STD_C::_List_node<_Tp> _Node;
448  typedef _GLIBCXX_STD_C::_List_iterator<_Tp> _Iterator;
449  typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _Const_iterator;
450  };
451 #endif
452 
453 #if ! _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
454  // Always use the T* specialization.
455  template<typename _Tp, typename _Ptr>
456  struct _Node_traits
457  : _Node_traits<_Tp, _Tp*>
458  { };
459 #else
460  // Primary template used when the allocator uses fancy pointers.
461  template<typename _Tp, typename _Ptr>
462  struct _Node_traits
463  {
464  private:
465  using _VoidPtr = __ptr_rebind<_Ptr, void>;
466  using _ValPtr = __ptr_rebind<_Ptr, _Tp>;
467 
468  public:
469  using _Node_base = __list::_Node_base<_VoidPtr>;
470  using _Node_header = __list::_Node_header<_VoidPtr>;
471  using _Node = __list::_Node<_ValPtr>;
472  using _Iterator = __list::_Iterator<false, _ValPtr>;
473  using _Const_iterator = __list::_Iterator<true, _ValPtr>;
474  };
475 #endif // USE_ALLOC_PTR_FOR_LIST
476 
477  // Used by std::list::sort to hold nodes being sorted.
478  template<typename _NodeBaseT>
479  struct _Scratch_list
480  : _NodeBaseT
481  {
482  typedef _NodeBaseT _Base;
483  typedef typename _Base::_Base_ptr _Base_ptr;
484 
485  _Scratch_list() { this->_M_next = this->_M_prev = this->_M_base(); }
486 
487  bool empty() const { return this->_M_next == this->_M_base(); }
488 
489  void swap(_Base& __l) { _Base::swap(*this, __l); }
490 
491  template<typename _Iter, typename _Cmp>
492  struct _Ptr_cmp
493  {
494  _Cmp _M_cmp;
495 
496  bool
497  operator()(_Base_ptr __lhs, _Base_ptr __rhs) /* not const */
498  { return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); }
499  };
500 
501  template<typename _Iter>
502  struct _Ptr_cmp<_Iter, void>
503  {
504  bool
505  operator()(_Base_ptr __lhs, _Base_ptr __rhs) const
506  { return *_Iter(__lhs) < *_Iter(__rhs); }
507  };
508 
509  // Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp.
510  template<typename _Cmp>
511  void
512  merge(_Base& __x, _Cmp __comp)
513  {
514  _Base_ptr __first1 = this->_M_next;
515  _Base_ptr const __last1 = this->_M_base();
516  _Base_ptr __first2 = __x._M_next;
517  _Base_ptr const __last2 = __x._M_base();
518 
519  while (__first1 != __last1 && __first2 != __last2)
520  {
521  if (__comp(__first2, __first1))
522  {
523  _Base_ptr __next = __first2->_M_next;
524  __first1->_M_transfer(__first2, __next);
525  __first2 = __next;
526  }
527  else
528  __first1 = __first1->_M_next;
529  }
530  if (__first2 != __last2)
531  this->_M_transfer(__first2, __last2);
532  }
533 
534  // Splice the node at __i into *this.
535  void _M_take_one(_Base_ptr __i)
536  { this->_M_transfer(__i, __i->_M_next); }
537 
538  // Splice all nodes from *this after __i.
539  void _M_put_all(_Base_ptr __i)
540  {
541  if (!empty())
542  __i->_M_transfer(this->_M_next, this->_M_base());
543  }
544  };
545 } // namespace __list
546 
547 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
548 
549  /// An actual node in the %list.
550  template<typename _Tp>
552  {
553  typedef _List_node* _Node_ptr;
554 
555 #if __cplusplus >= 201103L
556  __gnu_cxx::__aligned_membuf<_Tp> _M_storage;
557  _Tp* _M_valptr() { return _M_storage._M_ptr(); }
558  _Tp const* _M_valptr() const { return _M_storage._M_ptr(); }
559 #else
560  _Tp _M_data;
561  _Tp* _M_valptr() { return std::__addressof(_M_data); }
562  _Tp const* _M_valptr() const { return std::__addressof(_M_data); }
563 #endif
564 
565  _Node_ptr _M_node_ptr() { return this; }
566  };
567 
568  /**
569  * @brief A list::iterator.
570  *
571  * All the functions are op overloads.
572  */
573  template<typename _Tp>
575  {
576  typedef _List_node<_Tp> _Node;
577 
578  typedef ptrdiff_t difference_type;
580  typedef _Tp value_type;
581  typedef _Tp* pointer;
582  typedef _Tp& reference;
583 
584  _List_iterator() _GLIBCXX_NOEXCEPT
585  : _M_node() { }
586 
587  explicit
588  _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
589  : _M_node(__x) { }
590 
592  _M_const_cast() const _GLIBCXX_NOEXCEPT
593  { return *this; }
594 
595  // Must downcast from _List_node_base to _List_node to get to value.
596  _GLIBCXX_NODISCARD
597  reference
598  operator*() const _GLIBCXX_NOEXCEPT
599  { return *static_cast<_Node*>(_M_node)->_M_valptr(); }
600 
601  _GLIBCXX_NODISCARD
602  pointer
603  operator->() const _GLIBCXX_NOEXCEPT
604  { return static_cast<_Node*>(_M_node)->_M_valptr(); }
605 
607  operator++() _GLIBCXX_NOEXCEPT
608  {
609  _M_node = _M_node->_M_next;
610  return *this;
611  }
612 
614  operator++(int) _GLIBCXX_NOEXCEPT
615  {
616  _List_iterator __tmp = *this;
617  _M_node = _M_node->_M_next;
618  return __tmp;
619  }
620 
622  operator--() _GLIBCXX_NOEXCEPT
623  {
624  _M_node = _M_node->_M_prev;
625  return *this;
626  }
627 
629  operator--(int) _GLIBCXX_NOEXCEPT
630  {
631  _List_iterator __tmp = *this;
632  _M_node = _M_node->_M_prev;
633  return __tmp;
634  }
635 
636  _GLIBCXX_NODISCARD
637  friend bool
638  operator==(const _List_iterator& __x,
639  const _List_iterator& __y) _GLIBCXX_NOEXCEPT
640  { return __x._M_node == __y._M_node; }
641 
642 #if __cpp_impl_three_way_comparison < 201907L
643  _GLIBCXX_NODISCARD
644  friend bool
645  operator!=(const _List_iterator& __x,
646  const _List_iterator& __y) _GLIBCXX_NOEXCEPT
647  { return __x._M_node != __y._M_node; }
648 #endif
649 
650  // The only member points to the %list element.
651  __detail::_List_node_base* _M_node;
652  };
653 
654  /**
655  * @brief A list::const_iterator.
656  *
657  * All the functions are op overloads.
658  */
659  template<typename _Tp>
661  {
662  typedef const _List_node<_Tp> _Node;
664 
665  typedef ptrdiff_t difference_type;
667  typedef _Tp value_type;
668  typedef const _Tp* pointer;
669  typedef const _Tp& reference;
670 
671  _List_const_iterator() _GLIBCXX_NOEXCEPT
672  : _M_node() { }
673 
674  explicit
676  _GLIBCXX_NOEXCEPT
677  : _M_node(__x) { }
678 
679  _List_const_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT
680  : _M_node(__x._M_node) { }
681 
682  iterator
683  _M_const_cast() const _GLIBCXX_NOEXCEPT
684  { return iterator(const_cast<__detail::_List_node_base*>(_M_node)); }
685 
686  // Must downcast from List_node_base to _List_node to get to value.
687  _GLIBCXX_NODISCARD
688  reference
689  operator*() const _GLIBCXX_NOEXCEPT
690  { return *static_cast<_Node*>(_M_node)->_M_valptr(); }
691 
692  _GLIBCXX_NODISCARD
693  pointer
694  operator->() const _GLIBCXX_NOEXCEPT
695  { return static_cast<_Node*>(_M_node)->_M_valptr(); }
696 
698  operator++() _GLIBCXX_NOEXCEPT
699  {
700  _M_node = _M_node->_M_next;
701  return *this;
702  }
703 
705  operator++(int) _GLIBCXX_NOEXCEPT
706  {
707  _List_const_iterator __tmp = *this;
708  _M_node = _M_node->_M_next;
709  return __tmp;
710  }
711 
713  operator--() _GLIBCXX_NOEXCEPT
714  {
715  _M_node = _M_node->_M_prev;
716  return *this;
717  }
718 
720  operator--(int) _GLIBCXX_NOEXCEPT
721  {
722  _List_const_iterator __tmp = *this;
723  _M_node = _M_node->_M_prev;
724  return __tmp;
725  }
726 
727  _GLIBCXX_NODISCARD
728  friend bool
729  operator==(const _List_const_iterator& __x,
730  const _List_const_iterator& __y) _GLIBCXX_NOEXCEPT
731  { return __x._M_node == __y._M_node; }
732 
733 #if __cpp_impl_three_way_comparison < 201907L
734  _GLIBCXX_NODISCARD
735  friend bool
736  operator!=(const _List_const_iterator& __x,
737  const _List_const_iterator& __y) _GLIBCXX_NOEXCEPT
738  { return __x._M_node != __y._M_node; }
739 #endif
740 
741  // The only member points to the %list element.
742  const __detail::_List_node_base* _M_node;
743  };
744 
745 _GLIBCXX_BEGIN_NAMESPACE_CXX11
746  /// See bits/stl_deque.h's _Deque_base for an explanation.
747  template<typename _Tp, typename _Alloc>
749  {
750  protected:
752  rebind<_Tp>::other _Tp_alloc_type;
754 
755  typedef __list::_Node_traits<_Tp, typename _Tp_alloc_traits::pointer>
756  _Node_traits;
757  typedef typename _Tp_alloc_traits::template
758  rebind<typename _Node_traits::_Node>::other _Node_alloc_type;
760 
761 #if __cplusplus < 201103L || ! _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
762  typedef _List_node<_Tp>* _Node_ptr;
763 #else
764  using _Node_ptr = typename _Node_alloc_traits::pointer;
765 #endif
766 
767  struct _List_impl
768  : public _Node_alloc_type
769  {
770  typename _Node_traits::_Node_header _M_node;
771 
772  _List_impl() _GLIBCXX_NOEXCEPT_IF(
774  : _Node_alloc_type()
775  { }
776 
777  _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
778  : _Node_alloc_type(__a)
779  { }
780 
781 #if __cplusplus >= 201103L
782  _List_impl(_List_impl&&) = default;
783 
784  _List_impl(_Node_alloc_type&& __a, _List_impl&& __x)
785  : _Node_alloc_type(std::move(__a)), _M_node(std::move(__x._M_node))
786  { }
787 
788  _List_impl(_Node_alloc_type&& __a) noexcept
789  : _Node_alloc_type(std::move(__a))
790  { }
791 #endif
792  };
793 
794  _List_impl _M_impl;
795 
796 #if _GLIBCXX_USE_CXX11_ABI
797  size_t _M_get_size() const { return _M_impl._M_node._M_size; }
798 
799  void _M_set_size(size_t __n) { _M_impl._M_node._M_size = __n; }
800 
801  void _M_inc_size(size_t __n) { _M_impl._M_node._M_size += __n; }
802 
803  void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; }
804 #else
805  // dummy implementations used when the size is not stored
806  size_t _M_get_size() const { return 0; }
807  void _M_set_size(size_t) { }
808  void _M_inc_size(size_t) { }
809  void _M_dec_size(size_t) { }
810 #endif
811 
812  typename _Node_alloc_traits::pointer
813  _M_get_node()
814  { return _Node_alloc_traits::allocate(_M_impl, 1); }
815 
816  void
817  _M_put_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
818  {
819 #if __cplusplus < 201103L || _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
820  _Node_alloc_traits::deallocate(_M_impl, __p, 1);
821 #else
822 #pragma GCC diagnostic push
823 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
824  using __alloc_pointer = typename _Node_alloc_traits::pointer;
826  _Node_alloc_traits::deallocate(_M_impl, __p, 1);
827  else
828  {
829  // When not using the allocator's pointer type internally we must
830  // convert __p to __alloc_pointer so it can be deallocated.
832  _Node_alloc_traits::deallocate(_M_impl, __ap, 1);
833  }
834 #pragma GCC diagnostic pop
835 #endif
836  }
837 
838  void
839  _M_destroy_node(_Node_ptr __p)
840  {
841  // Destroy the element
842 #if __cplusplus < 201103L
843  _Tp_alloc_type(_M_impl).destroy(__p->_M_valptr());
844 #else
845  _Node_alloc_traits::destroy(_M_impl, __p->_M_valptr());
846  // Only destroy the node if the pointers require it.
847  using _Node = typename _Node_traits::_Node;
848  using _Base_ptr = typename _Node_traits::_Node_base::_Base_ptr;
849 #pragma GCC diagnostic push
850 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
852  __p->~_Node();
853 #pragma GCC diagnostic pop
854 #endif
855  this->_M_put_node(__p);
856  }
857 
858  public:
859  typedef _Alloc allocator_type;
860 
861  _Node_alloc_type&
862  _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
863  { return _M_impl; }
864 
865  const _Node_alloc_type&
866  _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
867  { return _M_impl; }
868 
869 #if __cplusplus >= 201103L
870  _List_base() = default;
871 #else
872  _List_base() { }
873 #endif
874 
875  _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
876  : _M_impl(__a)
877  { }
878 
879 #if __cplusplus >= 201103L
880  _List_base(_List_base&&) = default;
881 
882  // Used when allocator is_always_equal.
883  _List_base(_Node_alloc_type&& __a, _List_base&& __x)
884  : _M_impl(std::move(__a), std::move(__x._M_impl))
885  { }
886 
887  // Used when allocator !is_always_equal.
888  _List_base(_Node_alloc_type&& __a)
889  : _M_impl(std::move(__a))
890  { }
891 
892  void
893  _M_move_nodes(_List_base&& __x)
894  { _M_impl._M_node._M_move_nodes(std::move(__x._M_impl._M_node)); }
895 #endif
896 
897  // This is what actually destroys the list.
898  ~_List_base() _GLIBCXX_NOEXCEPT
899  { _M_clear(); }
900 
901  void
902  _M_clear() _GLIBCXX_NOEXCEPT;
903 
904  void
905  _M_init() _GLIBCXX_NOEXCEPT
906  { this->_M_impl._M_node._M_init(); }
907 
908 #if !_GLIBCXX_INLINE_VERSION
909  // XXX GLIBCXX_ABI Deprecated
910  // These members are unused by std::list now, but we keep them here
911  // so that an explicit instantiation of std::list will define them.
912  // This ensures that explicit instantiations still define these symbols,
913  // so that explicit instantiation declarations of std::list that were
914  // compiled with old versions of GCC can still find these old symbols.
915 
916  // Use 'if constexpr' so that the functions don't do anything for
917  // specializations using _Node_traits<T, fancy-pointer>, because any
918  // old code referencing these symbols wasn't using the fancy-pointer
919  // specializations.
920 
921 #pragma GCC diagnostic push
922 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
923 
924 # if __cplusplus >= 201103L
925  _List_base(_List_base&& __x, _Node_alloc_type&& __a)
926  : _M_impl(std::move(__a))
927  {
928 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
930 #endif
931  if (__x._M_get_Node_allocator() == _M_get_Node_allocator())
932  _M_move_nodes(std::move(__x));
933  // else caller must move individual elements.
934  }
935 # endif
936 
937  static size_t
938  _S_distance(const __detail::_List_node_base* __first,
939  const __detail::_List_node_base* __last)
940  {
941 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
943  return 0;
944  else
945 #endif
946  {
947  size_t __n = 0;
948  while (__first != __last)
949  {
950  __first = __first->_M_next;
951  ++__n;
952  }
953  return __n;
954  }
955  }
956 
957 #if _GLIBCXX_USE_CXX11_ABI
958  size_t
959  _M_distance(const __detail::_List_node_base* __first,
960  const __detail::_List_node_base* __last) const
961  { return _S_distance(__first, __last); }
962 
963  // return the stored size
964  size_t _M_node_count() const { return _M_get_size(); }
965 #else
966  size_t _M_distance(const void*, const void*) const { return 0; }
967 
968  // count the number of nodes
969  size_t _M_node_count() const
970  {
971  return _S_distance(_M_impl._M_node._M_next, _M_impl._M_node._M_base());
972  }
973 #endif
974 #pragma GCC diagnostic pop
975 #endif // ! INLINE_VERSION
976  };
977 
978  /**
979  * @brief A standard container with linear time access to elements,
980  * and fixed time insertion/deletion at any point in the sequence.
981  *
982  * @ingroup sequences
983  *
984  * @tparam _Tp Type of element.
985  * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
986  *
987  * Meets the requirements of a <a href="tables.html#65">container</a>, a
988  * <a href="tables.html#66">reversible container</a>, and a
989  * <a href="tables.html#67">sequence</a>, including the
990  * <a href="tables.html#68">optional sequence requirements</a> with the
991  * %exception of @c at and @c operator[].
992  *
993  * This is a @e doubly @e linked %list. Traversal up and down the
994  * %list requires linear time, but adding and removing elements (or
995  * @e nodes) is done in constant time, regardless of where the
996  * change takes place. Unlike std::vector and std::deque,
997  * random-access iterators are not provided, so subscripting ( @c
998  * [] ) access is not allowed. For algorithms which only need
999  * sequential access, this lack makes no difference.
1000  *
1001  * Also unlike the other standard containers, std::list provides
1002  * specialized algorithms %unique to linked lists, such as
1003  * splicing, sorting, and in-place reversal.
1004  *
1005  * A couple points on memory allocation for list<Tp>:
1006  *
1007  * First, we never actually allocate a Tp, we allocate
1008  * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure
1009  * that after elements from %list<X,Alloc1> are spliced into
1010  * %list<X,Alloc2>, destroying the memory of the second %list is a
1011  * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
1012  *
1013  * Second, a %list conceptually represented as
1014  * @code
1015  * A <---> B <---> C <---> D
1016  * @endcode
1017  * is actually circular; a link exists between A and D. The %list
1018  * class holds (as its only data member) a private list::iterator
1019  * pointing to @e D, not to @e A! To get to the head of the %list,
1020  * we start at the tail and move forward by one. When this member
1021  * iterator's next/previous pointers refer to itself, the %list is
1022  * %empty.
1023  */
1024  template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
1025  class list : protected _List_base<_Tp, _Alloc>
1026  {
1027 #ifdef _GLIBCXX_CONCEPT_CHECKS
1028  // concept requirements
1029  typedef typename _Alloc::value_type _Alloc_value_type;
1030 # if __cplusplus < 201103L
1031  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
1032 # endif
1033  __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
1034 #endif
1035 
1036 #if __cplusplus >= 201103L
1037  static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
1038  "std::list must have a non-const, non-volatile value_type");
1039 # if __cplusplus > 201703L || defined __STRICT_ANSI__
1041  "std::list must have the same value_type as its allocator");
1042 # endif
1043 #endif
1044 
1046  typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
1047  typedef typename _Base::_Tp_alloc_traits _Tp_alloc_traits;
1048  typedef typename _Base::_Node_alloc_type _Node_alloc_type;
1050  typedef typename _Base::_Node_traits _Node_traits;
1051 
1052  public:
1053  typedef _Tp value_type;
1054  typedef typename _Tp_alloc_traits::pointer pointer;
1055  typedef typename _Tp_alloc_traits::const_pointer const_pointer;
1056  typedef typename _Tp_alloc_traits::reference reference;
1057  typedef typename _Tp_alloc_traits::const_reference const_reference;
1058  typedef typename _Node_traits::_Iterator iterator;
1059  typedef typename _Node_traits::_Const_iterator const_iterator;
1062  typedef size_t size_type;
1063  typedef ptrdiff_t difference_type;
1064  typedef _Alloc allocator_type;
1065 
1066  protected:
1067  // Note that pointers-to-_Node's can be ctor-converted to
1068  // iterator types.
1069  typedef typename _Node_alloc_traits::pointer _Node_ptr;
1070 
1071  using _Base::_M_impl;
1072  using _Base::_M_put_node;
1073  using _Base::_M_get_node;
1074  using _Base::_M_get_Node_allocator;
1075 
1076  /**
1077  * @param __args An instance of user data.
1078  *
1079  * Allocates space for a new node and constructs a copy of
1080  * @a __args in it.
1081  */
1082 #if __cplusplus < 201103L
1083  _Node_ptr
1084  _M_create_node(const value_type& __x)
1085  {
1086  _Node_ptr __p = this->_M_get_node();
1087  __try
1088  {
1089  _Tp_alloc_type __alloc(_M_get_Node_allocator());
1090  __alloc.construct(__p->_M_valptr(), __x);
1091  }
1092  __catch(...)
1093  {
1094  _M_put_node(__p);
1095  __throw_exception_again;
1096  }
1097  return __p;
1098  }
1099 #else
1100  template<typename... _Args>
1101  _Node_ptr
1102  _M_create_node(_Args&&... __args)
1103  {
1104  auto& __alloc = _M_get_Node_allocator();
1105  auto __guard = std::__allocate_guarded_obj(__alloc);
1106  _Node_alloc_traits::construct(__alloc, __guard->_M_valptr(),
1107  std::forward<_Args>(__args)...);
1108  return __guard.release();
1109  }
1110 #endif
1111 
1112  public:
1113  // [23.2.2.1] construct/copy/destroy
1114  // (assign() and get_allocator() are also listed in this section)
1115 
1116  /**
1117  * @brief Creates a %list with no elements.
1118  */
1119 #if __cplusplus >= 201103L
1120  list() = default;
1121 #else
1122  list() { }
1123 #endif
1124 
1125  /**
1126  * @brief Creates a %list with no elements.
1127  * @param __a An allocator object.
1128  */
1129  explicit
1130  list(const allocator_type& __a) _GLIBCXX_NOEXCEPT
1131  : _Base(_Node_alloc_type(__a)) { }
1132 
1133 #if __cplusplus >= 201103L
1134  /**
1135  * @brief Creates a %list with default constructed elements.
1136  * @param __n The number of elements to initially create.
1137  * @param __a An allocator object.
1138  *
1139  * This constructor fills the %list with @a __n default
1140  * constructed elements.
1141  */
1142  explicit
1143  list(size_type __n, const allocator_type& __a = allocator_type())
1144  : _Base(_Node_alloc_type(__a))
1145  { _M_default_initialize(__n); }
1146 
1147  /**
1148  * @brief Creates a %list with copies of an exemplar element.
1149  * @param __n The number of elements to initially create.
1150  * @param __value An element to copy.
1151  * @param __a An allocator object.
1152  *
1153  * This constructor fills the %list with @a __n copies of @a __value.
1154  */
1155  list(size_type __n, const value_type& __value,
1156  const allocator_type& __a = allocator_type())
1157  : _Base(_Node_alloc_type(__a))
1158  { _M_fill_initialize(__n, __value); }
1159 #else
1160  /**
1161  * @brief Creates a %list with copies of an exemplar element.
1162  * @param __n The number of elements to initially create.
1163  * @param __value An element to copy.
1164  * @param __a An allocator object.
1165  *
1166  * This constructor fills the %list with @a __n copies of @a __value.
1167  */
1168  explicit
1169  list(size_type __n, const value_type& __value = value_type(),
1170  const allocator_type& __a = allocator_type())
1171  : _Base(_Node_alloc_type(__a))
1172  { _M_fill_initialize(__n, __value); }
1173 #endif
1174 
1175  /**
1176  * @brief %List copy constructor.
1177  * @param __x A %list of identical element and allocator types.
1178  *
1179  * The newly-created %list uses a copy of the allocation object used
1180  * by @a __x (unless the allocator traits dictate a different object).
1181  */
1182  list(const list& __x)
1184  _S_select_on_copy(__x._M_get_Node_allocator()))
1185  { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
1186 
1187 #if __cplusplus >= 201103L
1188  /**
1189  * @brief %List move constructor.
1190  *
1191  * The newly-created %list contains the exact contents of the moved
1192  * instance. The contents of the moved instance are a valid, but
1193  * unspecified %list.
1194  */
1195  list(list&&) = default;
1196 
1197  /**
1198  * @brief Builds a %list from an initializer_list
1199  * @param __l An initializer_list of value_type.
1200  * @param __a An allocator object.
1201  *
1202  * Create a %list consisting of copies of the elements in the
1203  * initializer_list @a __l. This is linear in __l.size().
1204  */
1206  const allocator_type& __a = allocator_type())
1207  : _Base(_Node_alloc_type(__a))
1208  { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
1209 
1210  list(const list& __x, const __type_identity_t<allocator_type>& __a)
1211  : _Base(_Node_alloc_type(__a))
1212  { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
1213 
1214  private:
1215  list(list&& __x, const allocator_type& __a, true_type) noexcept
1216  : _Base(_Node_alloc_type(__a), std::move(__x))
1217  { }
1218 
1219  list(list&& __x, const allocator_type& __a, false_type)
1220  : _Base(_Node_alloc_type(__a))
1221  {
1222  if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator())
1223  this->_M_move_nodes(std::move(__x));
1224  else
1225  insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()),
1226  std::__make_move_if_noexcept_iterator(__x.end()));
1227  }
1228 
1229  public:
1230  list(list&& __x, const __type_identity_t<allocator_type>& __a)
1231  noexcept(_Node_alloc_traits::_S_always_equal())
1232  : list(std::move(__x), __a,
1233  typename _Node_alloc_traits::is_always_equal{})
1234  { }
1235 #endif
1236 
1237  /**
1238  * @brief Builds a %list from a range.
1239  * @param __first An input iterator.
1240  * @param __last An input iterator.
1241  * @param __a An allocator object.
1242  *
1243  * Create a %list consisting of copies of the elements from
1244  * [@a __first,@a __last). This is linear in N (where N is
1245  * distance(@a __first,@a __last)).
1246  */
1247 #if __cplusplus >= 201103L
1248  template<typename _InputIterator,
1249  typename = std::_RequireInputIter<_InputIterator>>
1250  list(_InputIterator __first, _InputIterator __last,
1251  const allocator_type& __a = allocator_type())
1252  : _Base(_Node_alloc_type(__a))
1253  { _M_initialize_dispatch(__first, __last, __false_type()); }
1254 #else
1255  template<typename _InputIterator>
1256  list(_InputIterator __first, _InputIterator __last,
1257  const allocator_type& __a = allocator_type())
1258  : _Base(_Node_alloc_type(__a))
1259  {
1260  // Check whether it's an integral type. If so, it's not an iterator.
1261  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1262  _M_initialize_dispatch(__first, __last, _Integral());
1263  }
1264 #endif
1265 
1266 #if __glibcxx_containers_ranges // C++ >= 23
1267  /**
1268  * @brief Construct a list from a range.
1269  * @since C++23
1270  */
1271  template<__detail::__container_compatible_range<_Tp> _Rg>
1272  list(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
1273  : _Base(_Node_alloc_type(__a))
1274  {
1275  auto __first = ranges::begin(__rg);
1276  const auto __last = ranges::end(__rg);
1277  for (; __first != __last; ++__first)
1278  emplace_back(*__first);
1279  }
1280 #endif
1281 
1282 #if __cplusplus >= 201103L
1283  /**
1284  * No explicit dtor needed as the _Base dtor takes care of
1285  * things. The _Base dtor only erases the elements, and note
1286  * that if the elements themselves are pointers, the pointed-to
1287  * memory is not touched in any way. Managing the pointer is
1288  * the user's responsibility.
1289  */
1290  ~list() = default;
1291 #endif
1292 
1293  /**
1294  * @brief %List assignment operator.
1295  * @param __x A %list of identical element and allocator types.
1296  *
1297  * All the elements of @a __x are copied.
1298  *
1299  * Whether the allocator is copied depends on the allocator traits.
1300  */
1301  list&
1302  operator=(const list& __x);
1303 
1304 #if __cplusplus >= 201103L
1305 #pragma GCC diagnostic push
1306 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1307  /**
1308  * @brief %List move assignment operator.
1309  * @param __x A %list of identical element and allocator types.
1310  *
1311  * The contents of @a __x are moved into this %list (without copying).
1312  *
1313  * Afterwards @a __x is a valid, but unspecified %list
1314  *
1315  * Whether the allocator is moved depends on the allocator traits.
1316  */
1317  list&
1319  noexcept(_Node_alloc_traits::_S_nothrow_move())
1320  {
1321  constexpr bool __move_storage =
1322  _Node_alloc_traits::_S_propagate_on_move_assign()
1323  || _Node_alloc_traits::_S_always_equal();
1324  if constexpr (!__move_storage)
1325  {
1326  if (__x._M_get_Node_allocator() != this->_M_get_Node_allocator())
1327  {
1328  // The rvalue's allocator cannot be moved, or is not equal,
1329  // so we need to individually move each element.
1330  _M_assign_dispatch(std::make_move_iterator(__x.begin()),
1331  std::make_move_iterator(__x.end()),
1332  __false_type{});
1333  return *this;
1334  }
1335  }
1336 
1337  this->clear();
1338  this->_M_move_nodes(std::move(__x));
1339 
1340  if constexpr (_Node_alloc_traits::_S_propagate_on_move_assign())
1341  this->_M_get_Node_allocator()
1342  = std::move(__x._M_get_Node_allocator());
1343 
1344  return *this;
1345  }
1346 #pragma GCC diagnostic pop
1347 
1348  /**
1349  * @brief %List initializer list assignment operator.
1350  * @param __l An initializer_list of value_type.
1351  *
1352  * Replace the contents of the %list with copies of the elements
1353  * in the initializer_list @a __l. This is linear in l.size().
1354  */
1355  list&
1357  {
1358  this->assign(__l.begin(), __l.end());
1359  return *this;
1360  }
1361 #endif
1362 
1363 #if __glibcxx_containers_ranges // C++ >= 23
1364  /**
1365  * @brief Assign a range to a list.
1366  * @since C++23
1367  */
1368  template<__detail::__container_compatible_range<_Tp> _Rg>
1369  void
1370  assign_range(_Rg&& __rg)
1371  {
1372  static_assert(assignable_from<_Tp&, ranges::range_reference_t<_Rg>>);
1373 
1374  iterator __first1 = begin();
1375  const iterator __last1 = end();
1376  auto __first2 = ranges::begin(__rg);
1377  const auto __last2 = ranges::end(__rg);
1378  for (; __first1 != __last1 && __first2 != __last2;
1379  ++__first1, (void)++__first2)
1380  *__first1 = *__first2;
1381  if (__first2 == __last2)
1382  erase(__first1, __last1);
1383  else
1384  insert_range(__last1,
1385  ranges::subrange(std::move(__first2), __last2));
1386  }
1387 #endif
1388 
1389  /**
1390  * @brief Assigns a given value to a %list.
1391  * @param __n Number of elements to be assigned.
1392  * @param __val Value to be assigned.
1393  *
1394  * This function fills a %list with @a __n copies of the given
1395  * value. Note that the assignment completely changes the %list
1396  * and that the resulting %list's size is the same as the number
1397  * of elements assigned.
1398  */
1399  void
1400  assign(size_type __n, const value_type& __val)
1401  { _M_fill_assign(__n, __val); }
1402 
1403  /**
1404  * @brief Assigns a range to a %list.
1405  * @param __first An input iterator.
1406  * @param __last An input iterator.
1407  *
1408  * This function fills a %list with copies of the elements in the
1409  * range [@a __first,@a __last).
1410  *
1411  * Note that the assignment completely changes the %list and
1412  * that the resulting %list's size is the same as the number of
1413  * elements assigned.
1414  */
1415 #if __cplusplus >= 201103L
1416  template<typename _InputIterator,
1417  typename = std::_RequireInputIter<_InputIterator>>
1418  void
1419  assign(_InputIterator __first, _InputIterator __last)
1420  { _M_assign_dispatch(__first, __last, __false_type()); }
1421 #else
1422  template<typename _InputIterator>
1423  void
1424  assign(_InputIterator __first, _InputIterator __last)
1425  {
1426  // Check whether it's an integral type. If so, it's not an iterator.
1427  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1428  _M_assign_dispatch(__first, __last, _Integral());
1429  }
1430 #endif
1431 
1432 #if __cplusplus >= 201103L
1433  /**
1434  * @brief Assigns an initializer_list to a %list.
1435  * @param __l An initializer_list of value_type.
1436  *
1437  * Replace the contents of the %list with copies of the elements
1438  * in the initializer_list @a __l. This is linear in __l.size().
1439  */
1440  void
1442  { this->_M_assign_dispatch(__l.begin(), __l.end(), __false_type()); }
1443 #endif
1444 
1445  /// Get a copy of the memory allocation object.
1446  allocator_type
1447  get_allocator() const _GLIBCXX_NOEXCEPT
1448  { return allocator_type(_Base::_M_get_Node_allocator()); }
1449 
1450  // iterators
1451  /**
1452  * Returns a read/write iterator that points to the first element in the
1453  * %list. Iteration is done in ordinary element order.
1454  */
1455  _GLIBCXX_NODISCARD
1456  iterator
1457  begin() _GLIBCXX_NOEXCEPT
1458  { return iterator(this->_M_impl._M_node._M_next); }
1459 
1460  /**
1461  * Returns a read-only (constant) iterator that points to the
1462  * first element in the %list. Iteration is done in ordinary
1463  * element order.
1464  */
1465  _GLIBCXX_NODISCARD
1466  const_iterator
1467  begin() const _GLIBCXX_NOEXCEPT
1468  { return const_iterator(this->_M_impl._M_node._M_next); }
1469 
1470  /**
1471  * Returns a read/write iterator that points one past the last
1472  * element in the %list. Iteration is done in ordinary element
1473  * order.
1474  */
1475  _GLIBCXX_NODISCARD
1476  iterator
1477  end() _GLIBCXX_NOEXCEPT
1478  { return iterator(this->_M_impl._M_node._M_base()); }
1479 
1480  /**
1481  * Returns a read-only (constant) iterator that points one past
1482  * the last element in the %list. Iteration is done in ordinary
1483  * element order.
1484  */
1485  _GLIBCXX_NODISCARD
1486  const_iterator
1487  end() const _GLIBCXX_NOEXCEPT
1488  { return const_iterator(this->_M_impl._M_node._M_base()); }
1489 
1490  /**
1491  * Returns a read/write reverse iterator that points to the last
1492  * element in the %list. Iteration is done in reverse element
1493  * order.
1494  */
1495  _GLIBCXX_NODISCARD
1497  rbegin() _GLIBCXX_NOEXCEPT
1498  { return reverse_iterator(end()); }
1499 
1500  /**
1501  * Returns a read-only (constant) reverse iterator that points to
1502  * the last element in the %list. Iteration is done in reverse
1503  * element order.
1504  */
1505  _GLIBCXX_NODISCARD
1506  const_reverse_iterator
1507  rbegin() const _GLIBCXX_NOEXCEPT
1508  { return const_reverse_iterator(end()); }
1509 
1510  /**
1511  * Returns a read/write reverse iterator that points to one
1512  * before the first element in the %list. Iteration is done in
1513  * reverse element order.
1514  */
1515  _GLIBCXX_NODISCARD
1517  rend() _GLIBCXX_NOEXCEPT
1518  { return reverse_iterator(begin()); }
1519 
1520  /**
1521  * Returns a read-only (constant) reverse iterator that points to one
1522  * before the first element in the %list. Iteration is done in reverse
1523  * element order.
1524  */
1525  _GLIBCXX_NODISCARD
1526  const_reverse_iterator
1527  rend() const _GLIBCXX_NOEXCEPT
1528  { return const_reverse_iterator(begin()); }
1529 
1530 #if __cplusplus >= 201103L
1531  /**
1532  * Returns a read-only (constant) iterator that points to the
1533  * first element in the %list. Iteration is done in ordinary
1534  * element order.
1535  */
1536  [[__nodiscard__]]
1537  const_iterator
1538  cbegin() const noexcept
1539  { return const_iterator(this->_M_impl._M_node._M_next); }
1540 
1541  /**
1542  * Returns a read-only (constant) iterator that points one past
1543  * the last element in the %list. Iteration is done in ordinary
1544  * element order.
1545  */
1546  [[__nodiscard__]]
1547  const_iterator
1548  cend() const noexcept
1549  { return const_iterator(this->_M_impl._M_node._M_base()); }
1550 
1551  /**
1552  * Returns a read-only (constant) reverse iterator that points to
1553  * the last element in the %list. Iteration is done in reverse
1554  * element order.
1555  */
1556  [[__nodiscard__]]
1557  const_reverse_iterator
1558  crbegin() const noexcept
1559  { return const_reverse_iterator(end()); }
1560 
1561  /**
1562  * Returns a read-only (constant) reverse iterator that points to one
1563  * before the first element in the %list. Iteration is done in reverse
1564  * element order.
1565  */
1566  [[__nodiscard__]]
1567  const_reverse_iterator
1568  crend() const noexcept
1569  { return const_reverse_iterator(begin()); }
1570 #endif
1571 
1572  // [23.2.2.2] capacity
1573  /**
1574  * Returns true if the %list is empty. (Thus begin() would equal
1575  * end().)
1576  */
1577  _GLIBCXX_NODISCARD bool
1578  empty() const _GLIBCXX_NOEXCEPT
1579  {
1580  return this->_M_impl._M_node._M_next == this->_M_impl._M_node._M_base();
1581  }
1582 
1583  /** Returns the number of elements in the %list. */
1584  _GLIBCXX_NODISCARD
1585  size_type
1586  size() const _GLIBCXX_NOEXCEPT
1587  {
1588 #if _GLIBCXX_USE_CXX11_ABI
1589  return this->_M_get_size(); // return the stored size
1590 #else
1591  return std::distance(begin(), end()); // count the number of nodes
1592 #endif
1593  }
1594 
1595  /** Returns the size() of the largest possible %list. */
1596  _GLIBCXX_NODISCARD
1597  size_type
1598  max_size() const _GLIBCXX_NOEXCEPT
1599  { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); }
1600 
1601 #if __cplusplus >= 201103L
1602  /**
1603  * @brief Resizes the %list to the specified number of elements.
1604  * @param __new_size Number of elements the %list should contain.
1605  *
1606  * This function will %resize the %list to the specified number
1607  * of elements. If the number is smaller than the %list's
1608  * current size the %list is truncated, otherwise default
1609  * constructed elements are appended.
1610  */
1611  void
1612  resize(size_type __new_size);
1613 
1614  /**
1615  * @brief Resizes the %list to the specified number of elements.
1616  * @param __new_size Number of elements the %list should contain.
1617  * @param __x Data with which new elements should be populated.
1618  *
1619  * This function will %resize the %list to the specified number
1620  * of elements. If the number is smaller than the %list's
1621  * current size the %list is truncated, otherwise the %list is
1622  * extended and new elements are populated with given data.
1623  */
1624  void
1625  resize(size_type __new_size, const value_type& __x);
1626 #else
1627  /**
1628  * @brief Resizes the %list to the specified number of elements.
1629  * @param __new_size Number of elements the %list should contain.
1630  * @param __x Data with which new elements should be populated.
1631  *
1632  * This function will %resize the %list to the specified number
1633  * of elements. If the number is smaller than the %list's
1634  * current size the %list is truncated, otherwise the %list is
1635  * extended and new elements are populated with given data.
1636  */
1637  void
1638  resize(size_type __new_size, value_type __x = value_type());
1639 #endif
1640 
1641  // element access
1642  /**
1643  * Returns a read/write reference to the data at the first
1644  * element of the %list.
1645  */
1646  _GLIBCXX_NODISCARD
1647  reference
1648  front() _GLIBCXX_NOEXCEPT
1649  {
1650  __glibcxx_requires_nonempty();
1651  return *begin();
1652  }
1653 
1654  /**
1655  * Returns a read-only (constant) reference to the data at the first
1656  * element of the %list.
1657  */
1658  _GLIBCXX_NODISCARD
1659  const_reference
1660  front() const _GLIBCXX_NOEXCEPT
1661  {
1662  __glibcxx_requires_nonempty();
1663  return *begin();
1664  }
1665 
1666  /**
1667  * Returns a read/write reference to the data at the last element
1668  * of the %list.
1669  */
1670  _GLIBCXX_NODISCARD
1671  reference
1672  back() _GLIBCXX_NOEXCEPT
1673  {
1674  __glibcxx_requires_nonempty();
1675  iterator __tmp = end();
1676  --__tmp;
1677  return *__tmp;
1678  }
1679 
1680  /**
1681  * Returns a read-only (constant) reference to the data at the last
1682  * element of the %list.
1683  */
1684  _GLIBCXX_NODISCARD
1685  const_reference
1686  back() const _GLIBCXX_NOEXCEPT
1687  {
1688  __glibcxx_requires_nonempty();
1689  const_iterator __tmp = end();
1690  --__tmp;
1691  return *__tmp;
1692  }
1693 
1694  // [23.2.2.3] modifiers
1695  /**
1696  * @brief Add data to the front of the %list.
1697  * @param __x Data to be added.
1698  *
1699  * This is a typical stack operation. The function creates an
1700  * element at the front of the %list and assigns the given data
1701  * to it. Due to the nature of a %list this operation can be
1702  * done in constant time, and does not invalidate iterators and
1703  * references.
1704  */
1705  void
1706  push_front(const value_type& __x)
1707  { this->_M_insert(begin(), __x); }
1708 
1709 #if __cplusplus >= 201103L
1710  void
1711  push_front(value_type&& __x)
1712  { this->_M_insert(begin(), std::move(__x)); }
1713 
1714  template<typename... _Args>
1715 #if __cplusplus > 201402L
1716  reference
1717 #else
1718  void
1719 #endif
1720  emplace_front(_Args&&... __args)
1721  {
1722  this->_M_insert(begin(), std::forward<_Args>(__args)...);
1723 #if __cplusplus > 201402L
1724  return front();
1725 #endif
1726  }
1727 #endif
1728 
1729 #if __glibcxx_containers_ranges // C++ >= 23
1730  /**
1731  * @brief Insert a range at the beginning of a list.
1732  * @param __rg An input range of elements that can be converted to
1733  * the list's value type.
1734  *
1735  * Inserts the elements of `__rg` at the beginning of the list.
1736  * No iterators to existing elements are invalidated by this function.
1737  * If the insertion fails due to an exception, no elements will be added
1738  * and so the list will be unchanged.
1739  *
1740  * @since C++23
1741  */
1742  template<__detail::__container_compatible_range<_Tp> _Rg>
1743  void
1744  prepend_range(_Rg&& __rg)
1745  {
1746  list __tmp(from_range, std::forward<_Rg>(__rg), get_allocator());
1747  if (!__tmp.empty())
1748  splice(begin(), __tmp);
1749  }
1750 
1751  /**
1752  * @brief Insert a range at the end of a list.
1753  * @param __rg An input range of elements that can be converted to
1754  * the list's value type.
1755  *
1756  * Inserts the elements of `__rg` at the end of the list.
1757  * No iterators to existing elements are invalidated by this function.
1758  * If the insertion fails due to an exception, no elements will be added
1759  * and so the list will be unchanged.
1760  *
1761  * @since C++23
1762  */
1763  template<__detail::__container_compatible_range<_Tp> _Rg>
1764  void
1765  append_range(_Rg&& __rg)
1766  {
1767  list __tmp(from_range, std::forward<_Rg>(__rg), get_allocator());
1768  if (!__tmp.empty())
1769  splice(end(), __tmp);
1770  }
1771 #endif
1772 
1773  /**
1774  * @brief Removes first element.
1775  *
1776  * This is a typical stack operation. It shrinks the %list by
1777  * one. Due to the nature of a %list this operation can be done
1778  * in constant time, and only invalidates iterators/references to
1779  * the element being removed.
1780  *
1781  * Note that no data is returned, and if the first element's data
1782  * is needed, it should be retrieved before pop_front() is
1783  * called.
1784  */
1785  void
1786  pop_front() _GLIBCXX_NOEXCEPT
1787  {
1788  __glibcxx_requires_nonempty();
1789  this->_M_erase(begin());
1790  }
1791 
1792  /**
1793  * @brief Add data to the end of the %list.
1794  * @param __x Data to be added.
1795  *
1796  * This is a typical stack operation. The function creates an
1797  * element at the end of the %list and assigns the given data to
1798  * it. Due to the nature of a %list this operation can be done
1799  * in constant time, and does not invalidate iterators and
1800  * references.
1801  */
1802  void
1803  push_back(const value_type& __x)
1804  { this->_M_insert(end(), __x); }
1805 
1806 #if __cplusplus >= 201103L
1807  void
1808  push_back(value_type&& __x)
1809  { this->_M_insert(end(), std::move(__x)); }
1810 
1811  template<typename... _Args>
1812 #if __cplusplus > 201402L
1813  reference
1814 #else
1815  void
1816 #endif
1817  emplace_back(_Args&&... __args)
1818  {
1819  this->_M_insert(end(), std::forward<_Args>(__args)...);
1820 #if __cplusplus > 201402L
1821  return back();
1822 #endif
1823  }
1824 #endif
1825 
1826  /**
1827  * @brief Removes last element.
1828  *
1829  * This is a typical stack operation. It shrinks the %list by
1830  * one. Due to the nature of a %list this operation can be done
1831  * in constant time, and only invalidates iterators/references to
1832  * the element being removed.
1833  *
1834  * Note that no data is returned, and if the last element's data
1835  * is needed, it should be retrieved before pop_back() is called.
1836  */
1837  void
1838  pop_back() _GLIBCXX_NOEXCEPT
1839  {
1840  __glibcxx_requires_nonempty();
1841  this->_M_erase(iterator(this->_M_impl._M_node._M_prev));
1842  }
1843 
1844 #if __cplusplus >= 201103L
1845  /**
1846  * @brief Constructs object in %list before specified iterator.
1847  * @param __position A const_iterator into the %list.
1848  * @param __args Arguments.
1849  * @return An iterator that points to the inserted data.
1850  *
1851  * This function will insert an object of type T constructed
1852  * with T(std::forward<Args>(args)...) before the specified
1853  * location. Due to the nature of a %list this operation can
1854  * be done in constant time, and does not invalidate iterators
1855  * and references.
1856  */
1857  template<typename... _Args>
1858  iterator
1859  emplace(const_iterator __position, _Args&&... __args);
1860 #endif
1861 
1862  /**
1863  * @brief Inserts given value into %list before specified iterator.
1864  * @param __position An iterator into the %list.
1865  * @param __x Data to be inserted.
1866  * @return An iterator that points to the inserted data.
1867  *
1868  * This function will insert a copy of the given value before
1869  * the specified location. Due to the nature of a %list this
1870  * operation can be done in constant time, and does not
1871  * invalidate iterators and references.
1872  *
1873  * @{
1874  */
1875 #if __cplusplus >= 201103L
1876  iterator
1877  insert(const_iterator __position, const value_type& __x);
1878 
1879  iterator
1880  insert(const_iterator __position, value_type&& __x)
1881  { return emplace(__position, std::move(__x)); }
1882 #else
1883  iterator
1884  insert(iterator __position, const value_type& __x);
1885 #endif
1886  /// @}
1887 
1888 #if __cplusplus >= 201103L
1889  /**
1890  * @brief Inserts the contents of an initializer_list into %list
1891  * before specified const_iterator.
1892  * @param __p A const_iterator into the %list.
1893  * @param __l An initializer_list of value_type.
1894  * @return An iterator pointing to the first element inserted
1895  * (or `__p`).
1896  *
1897  * This function will insert copies of the data in the
1898  * initializer_list `__l` into the %list before the location
1899  * specified by `__p`.
1900  *
1901  * This operation is linear in the number of elements inserted and
1902  * does not invalidate iterators and references.
1903  */
1904  iterator
1905  insert(const_iterator __p, initializer_list<value_type> __l)
1906  { return this->insert(__p, __l.begin(), __l.end()); }
1907 #endif
1908 
1909  /**
1910  * @brief Inserts a number of copies of given data into the %list.
1911  * @param __position An iterator into the %list.
1912  * @param __n Number of elements to be inserted.
1913  * @param __x Data to be inserted.
1914  * @return Since C++11, an iterator pointing to the first element
1915  * inserted (or `__position`). In C++98 this returns void.
1916  *
1917  * This function will insert a specified number of copies of the
1918  * given data before the location specified by `__position`.
1919  *
1920  * This operation is linear in the number of elements inserted and
1921  * does not invalidate iterators and references.
1922  */
1923 #if __cplusplus >= 201103L
1924  iterator
1925  insert(const_iterator __position, size_type __n, const value_type& __x);
1926 #else
1927  void
1928  insert(iterator __position, size_type __n, const value_type& __x)
1929  {
1930  list __tmp(__n, __x, get_allocator());
1931  splice(__position, __tmp);
1932  }
1933 #endif
1934 
1935  /**
1936  * @brief Inserts a range into the %list.
1937  * @param __position An iterator into the %list.
1938  * @param __first An input iterator.
1939  * @param __last An input iterator.
1940  * @return Since C++11, an iterator pointing to the first element
1941  * inserted (or `__position`). In C++98 this returns void.
1942  *
1943  * This function will insert copies of the data in the range
1944  * `[__first,__last)` into the %list before the location specified by
1945  * `__position`.
1946  *
1947  * This operation is linear in the number of elements inserted and
1948  * does not invalidate iterators and references.
1949  */
1950 #if __cplusplus >= 201103L
1951  template<typename _InputIterator,
1952  typename = std::_RequireInputIter<_InputIterator>>
1953  iterator
1954  insert(const_iterator __position, _InputIterator __first,
1955  _InputIterator __last);
1956 #else
1957  template<typename _InputIterator>
1958  void
1959  insert(iterator __position, _InputIterator __first,
1960  _InputIterator __last)
1961  {
1962  list __tmp(__first, __last, get_allocator());
1963  splice(__position, __tmp);
1964  }
1965 #endif
1966 
1967 #if __glibcxx_containers_ranges // C++ >= 23
1968  /**
1969  * @brief Insert a range into a list.
1970  * @param __position An iterator.
1971  * @param __rg An input range of elements that can be converted to
1972  * the list's value type.
1973  * @return An iterator pointing to the first element inserted,
1974  * or `__position` if the range is empty.
1975  *
1976  * Inserts the elements of `__rg` before `__position`.
1977  * No iterators to existing elements are invalidated by this function.
1978  * If the insertion fails due to an exception, no elements will be added
1979  * and so the list will be unchanged.
1980  *
1981  * @since C++23
1982  */
1983  template<__detail::__container_compatible_range<_Tp> _Rg>
1984  iterator
1985  insert_range(const_iterator __position, _Rg&& __rg)
1986  {
1987  list __tmp(from_range, std::forward<_Rg>(__rg), get_allocator());
1988  if (!__tmp.empty())
1989  {
1990  auto __it = __tmp.begin();
1991  splice(__position, __tmp);
1992  return __it;
1993  }
1994  return __position._M_const_cast();
1995  }
1996 #endif
1997 
1998  /**
1999  * @brief Remove element at given position.
2000  * @param __position Iterator pointing to element to be erased.
2001  * @return An iterator pointing to the next element (or end()).
2002  *
2003  * This function will erase the element at the given position and thus
2004  * shorten the %list by one.
2005  *
2006  * Due to the nature of a %list this operation can be done in
2007  * constant time, and only invalidates iterators/references to
2008  * the element being removed. The user is also cautioned that
2009  * this function only erases the element, and that if the element
2010  * is itself a pointer, the pointed-to memory is not touched in
2011  * any way. Managing the pointer is the user's responsibility.
2012  */
2013  iterator
2014 #if __cplusplus >= 201103L
2015  erase(const_iterator __position) noexcept;
2016 #else
2017  erase(iterator __position);
2018 #endif
2019 
2020  /**
2021  * @brief Remove a range of elements.
2022  * @param __first Iterator pointing to the first element to be erased.
2023  * @param __last Iterator pointing to one past the last element to be
2024  * erased.
2025  * @return An iterator pointing to the element pointed to by @a last
2026  * prior to erasing (or end()).
2027  *
2028  * This function will erase the elements in the range @a
2029  * [first,last) and shorten the %list accordingly.
2030  *
2031  * This operation is linear time in the size of the range and only
2032  * invalidates iterators/references to the element being removed.
2033  * The user is also cautioned that this function only erases the
2034  * elements, and that if the elements themselves are pointers, the
2035  * pointed-to memory is not touched in any way. Managing the pointer
2036  * is the user's responsibility.
2037  */
2038  iterator
2039 #if __cplusplus >= 201103L
2040  erase(const_iterator __first, const_iterator __last) noexcept
2041 #else
2042  erase(iterator __first, iterator __last)
2043 #endif
2044  {
2045  while (__first != __last)
2046  __first = erase(__first);
2047  return __last._M_const_cast();
2048  }
2049 
2050  /**
2051  * @brief Swaps data with another %list.
2052  * @param __x A %list of the same element and allocator types.
2053  *
2054  * This exchanges the elements between two lists in constant
2055  * time. Note that the global std::swap() function is
2056  * specialized such that std::swap(l1,l2) will feed to this
2057  * function.
2058  *
2059  * Whether the allocators are swapped depends on the allocator traits.
2060  */
2061  void
2062  swap(list& __x) _GLIBCXX_NOEXCEPT
2063  {
2064  _Node_traits::_Node_base::swap(this->_M_impl._M_node,
2065  __x._M_impl._M_node);
2066 
2067  size_t __xsize = __x._M_get_size();
2068  __x._M_set_size(this->_M_get_size());
2069  this->_M_set_size(__xsize);
2070 
2071  _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
2072  __x._M_get_Node_allocator());
2073  }
2074 
2075  /**
2076  * Erases all the elements. Note that this function only erases
2077  * the elements, and that if the elements themselves are
2078  * pointers, the pointed-to memory is not touched in any way.
2079  * Managing the pointer is the user's responsibility.
2080  */
2081  void
2082  clear() _GLIBCXX_NOEXCEPT
2083  {
2084  _Base::_M_clear();
2085  _Base::_M_init();
2086  }
2087 
2088  // [23.2.2.4] list operations
2089  /**
2090  * @brief Insert contents of another %list.
2091  * @param __position Iterator referencing the element to insert before.
2092  * @param __x Source list.
2093  *
2094  * The elements of @a __x are inserted in constant time in front of
2095  * the element referenced by @a __position. @a __x becomes an empty
2096  * list.
2097  *
2098  * Requires this != @a __x.
2099  */
2100  void
2101 #if __cplusplus >= 201103L
2102  splice(const_iterator __position, list&& __x) noexcept
2103 #else
2104  splice(iterator __position, list& __x)
2105 #endif
2106  {
2107  if (!__x.empty())
2108  {
2109  _M_check_equal_allocators(__x);
2110 
2111  this->_M_transfer(__position._M_const_cast(),
2112  __x.begin(), __x.end());
2113 
2114  this->_M_inc_size(__x._M_get_size());
2115  __x._M_set_size(0);
2116  }
2117  }
2118 
2119 #if __cplusplus >= 201103L
2120  void
2121  splice(const_iterator __position, list& __x) noexcept
2122  { splice(__position, std::move(__x)); }
2123 #endif
2124 
2125  /**
2126  * @brief Insert element from another %list.
2127  * @param __position Iterator referencing the element to insert before.
2128  * @param __x Source list.
2129  * @param __i Iterator referencing the element to move.
2130  *
2131  * Removes the element in list @a __x referenced by @a __i and
2132  * inserts it into the current list before @a __position.
2133  *
2134  * @{
2135  */
2136 #if __cplusplus >= 201103L
2137  void
2138  splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
2139 #else
2140  void
2141  splice(iterator __position, list& __x, iterator __i)
2142 #endif
2143  {
2144  iterator __j = __i._M_const_cast();
2145  ++__j;
2146  if (__position == __i || __position == __j)
2147  return;
2148 
2149  if (this != std::__addressof(__x))
2150  _M_check_equal_allocators(__x);
2151 
2152  this->_M_transfer(__position._M_const_cast(),
2153  __i._M_const_cast(), __j);
2154 
2155  this->_M_inc_size(1);
2156  __x._M_dec_size(1);
2157  }
2158 
2159 #if __cplusplus >= 201103L
2160  void
2161  splice(const_iterator __position, list& __x, const_iterator __i) noexcept
2162  { splice(__position, std::move(__x), __i); }
2163 #endif
2164  /// @}
2165 
2166  /**
2167  * @brief Insert range from another %list.
2168  * @param __position Iterator referencing the element to insert before.
2169  * @param __x Source list.
2170  * @param __first Iterator referencing the start of range in x.
2171  * @param __last Iterator referencing the end of range in x.
2172  *
2173  * Removes elements in the range [__first,__last) and inserts them
2174  * before @a __position in constant time.
2175  *
2176  * Undefined if @a __position is in [__first,__last).
2177  */
2178 #if __cplusplus >= 201103L
2179  void
2180  splice(const_iterator __position, list&& __x, const_iterator __first,
2181  const_iterator __last) noexcept
2182 #else
2183  void
2184  splice(iterator __position, list& __x, iterator __first,
2185  iterator __last)
2186 #endif
2187  {
2188  if (__first != __last)
2189  {
2190  if (this != std::__addressof(__x))
2191  _M_check_equal_allocators(__x);
2192 
2193 #if _GLIBCXX_USE_CXX11_ABI
2194  size_t __n = std::distance(__first, __last);
2195  this->_M_inc_size(__n);
2196  __x._M_dec_size(__n);
2197 #endif
2198 
2199  this->_M_transfer(__position._M_const_cast(),
2200  __first._M_const_cast(),
2201  __last._M_const_cast());
2202  }
2203  }
2204 
2205 #if __cplusplus >= 201103L
2206  /**
2207  * @brief Insert range from another %list.
2208  * @param __position Const_iterator referencing the element to
2209  * insert before.
2210  * @param __x Source list.
2211  * @param __first Const_iterator referencing the start of range in x.
2212  * @param __last Const_iterator referencing the end of range in x.
2213  *
2214  * Removes elements in the range [__first,__last) and inserts them
2215  * before @a __position in constant time.
2216  *
2217  * Undefined if @a __position is in [__first,__last).
2218  */
2219  void
2220  splice(const_iterator __position, list& __x, const_iterator __first,
2221  const_iterator __last) noexcept
2222  { splice(__position, std::move(__x), __first, __last); }
2223 #endif
2224 
2225  private:
2226 #ifdef __glibcxx_list_remove_return_type // C++ >= 20 && HOSTED
2227  typedef size_type __remove_return_type;
2228 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
2229  __attribute__((__abi_tag__("__cxx20")))
2230 #else
2231  typedef void __remove_return_type;
2232 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
2233 #endif
2234  public:
2235 
2236  /**
2237  * @brief Remove all elements equal to value.
2238  * @param __value The value to remove.
2239  *
2240  * Removes every element in the list equal to @a value.
2241  * Remaining elements stay in list order. Note that this
2242  * function only erases the elements, and that if the elements
2243  * themselves are pointers, the pointed-to memory is not
2244  * touched in any way. Managing the pointer is the user's
2245  * responsibility.
2246  */
2247  _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
2248  __remove_return_type
2249  remove(const _Tp& __value);
2250 
2251  /**
2252  * @brief Remove all elements satisfying a predicate.
2253  * @tparam _Predicate Unary predicate function or object.
2254  *
2255  * Removes every element in the list for which the predicate
2256  * returns true. Remaining elements stay in list order. Note
2257  * that this function only erases the elements, and that if the
2258  * elements themselves are pointers, the pointed-to memory is
2259  * not touched in any way. Managing the pointer is the user's
2260  * responsibility.
2261  */
2262  template<typename _Predicate>
2263  __remove_return_type
2264  remove_if(_Predicate);
2265 
2266  /**
2267  * @brief Remove consecutive duplicate elements.
2268  *
2269  * For each consecutive set of elements with the same value,
2270  * remove all but the first one. Remaining elements stay in
2271  * list order. Note that this function only erases the
2272  * elements, and that if the elements themselves are pointers,
2273  * the pointed-to memory is not touched in any way. Managing
2274  * the pointer is the user's responsibility.
2275  */
2276  _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
2277  __remove_return_type
2278  unique();
2279 
2280  /**
2281  * @brief Remove consecutive elements satisfying a predicate.
2282  * @tparam _BinaryPredicate Binary predicate function or object.
2283  *
2284  * For each consecutive set of elements [first,last) that
2285  * satisfy predicate(first,i) where i is an iterator in
2286  * [first,last), remove all but the first one. Remaining
2287  * elements stay in list order. Note that this function only
2288  * erases the elements, and that if the elements themselves are
2289  * pointers, the pointed-to memory is not touched in any way.
2290  * Managing the pointer is the user's responsibility.
2291  */
2292  template<typename _BinaryPredicate>
2293  __remove_return_type
2294  unique(_BinaryPredicate);
2295 
2296 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
2297 
2298  /**
2299  * @brief Merge sorted lists.
2300  * @param __x Sorted list to merge.
2301  *
2302  * Assumes that both @a __x and this list are sorted according to
2303  * operator<(). Merges elements of @a __x into this list in
2304  * sorted order, leaving @a __x empty when complete. Elements in
2305  * this list precede elements in @a __x that are equal.
2306  */
2307 #if __cplusplus >= 201103L
2308  void
2309  merge(list&& __x);
2310 
2311  void
2312  merge(list& __x)
2313  { merge(std::move(__x)); }
2314 #else
2315  void
2316  merge(list& __x);
2317 #endif
2318 
2319  /**
2320  * @brief Merge sorted lists according to comparison function.
2321  * @tparam _StrictWeakOrdering Comparison function defining
2322  * sort order.
2323  * @param __x Sorted list to merge.
2324  * @param __comp Comparison functor.
2325  *
2326  * Assumes that both @a __x and this list are sorted according to
2327  * StrictWeakOrdering. Merges elements of @a __x into this list
2328  * in sorted order, leaving @a __x empty when complete. Elements
2329  * in this list precede elements in @a __x that are equivalent
2330  * according to StrictWeakOrdering().
2331  */
2332 #if __cplusplus >= 201103L
2333  template<typename _StrictWeakOrdering>
2334  void
2335  merge(list&& __x, _StrictWeakOrdering __comp);
2336 
2337  template<typename _StrictWeakOrdering>
2338  void
2339  merge(list& __x, _StrictWeakOrdering __comp)
2340  { merge(std::move(__x), __comp); }
2341 #else
2342  template<typename _StrictWeakOrdering>
2343  void
2344  merge(list& __x, _StrictWeakOrdering __comp);
2345 #endif
2346 
2347  /**
2348  * @brief Reverse the elements in list.
2349  *
2350  * Reverse the order of elements in the list in linear time.
2351  */
2352  void
2353  reverse() _GLIBCXX_NOEXCEPT
2354  { this->_M_impl._M_node._M_reverse(); }
2355 
2356  /**
2357  * @brief Sort the elements.
2358  *
2359  * Sorts the elements of this list in NlogN time. Equivalent
2360  * elements remain in list order.
2361  */
2362  void
2363  sort();
2364 
2365  /**
2366  * @brief Sort the elements according to comparison function.
2367  *
2368  * Sorts the elements of this list in NlogN time. Equivalent
2369  * elements remain in list order.
2370  */
2371  template<typename _StrictWeakOrdering>
2372  void
2373  sort(_StrictWeakOrdering);
2374 
2375  protected:
2376  // Internal constructor functions follow.
2377 
2378  // Called by the range constructor to implement [23.1.1]/9
2379 
2380  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2381  // 438. Ambiguity in the "do the right thing" clause
2382  template<typename _Integer>
2383  void
2384  _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
2385  { _M_fill_initialize(static_cast<size_type>(__n), __x); }
2386 
2387  // Called by the range constructor to implement [23.1.1]/9
2388  template<typename _InputIterator>
2389  void
2390  _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
2391  __false_type)
2392  {
2393  bool __notempty = __first != __last;
2394  for (; __first != __last; ++__first)
2395 #if __cplusplus >= 201103L
2396  emplace_back(*__first);
2397 #else
2398  push_back(*__first);
2399 #endif
2400  if (__notempty)
2401  {
2402  if (begin() == end())
2403  __builtin_unreachable();
2404  }
2405  }
2406 
2407  // Called by list(n,v,a), and the range constructor when it turns out
2408  // to be the same thing.
2409  void
2410  _M_fill_initialize(size_type __n, const value_type& __x)
2411  {
2412  for (; __n; --__n)
2413  push_back(__x);
2414  }
2415 
2416 #if __cplusplus >= 201103L
2417  // Called by list(n).
2418  void
2419  _M_default_initialize(size_type __n)
2420  {
2421  for (; __n; --__n)
2422  emplace_back();
2423  }
2424 
2425  // Called by resize(sz).
2426  void
2427  _M_default_append(size_type __n);
2428 #endif
2429 
2430  // Internal assign functions follow.
2431 
2432  // Called by the range assign to implement [23.1.1]/9
2433 
2434  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2435  // 438. Ambiguity in the "do the right thing" clause
2436  template<typename _Integer>
2437  void
2438  _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
2439  { _M_fill_assign(__n, __val); }
2440 
2441  // Called by the range assign to implement [23.1.1]/9
2442  template<typename _InputIterator>
2443  void
2444  _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
2445  __false_type);
2446 
2447  // Called by assign(n,t), and the range assign when it turns out
2448  // to be the same thing.
2449  void
2450  _M_fill_assign(size_type __n, const value_type& __val);
2451 
2452 
2453  // Moves the elements from [first,last) before position.
2454  void
2455  _M_transfer(iterator __position, iterator __first, iterator __last)
2456  { __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
2457 
2458  // Inserts new element at position given and with value given.
2459 #if __cplusplus < 201103L
2460  void
2461  _M_insert(iterator __position, const value_type& __x)
2462  {
2463  _Node_ptr __tmp = _M_create_node(__x);
2464  __tmp->_M_hook(__position._M_node);
2465  this->_M_inc_size(1);
2466  }
2467 #else
2468  template<typename... _Args>
2469  void
2470  _M_insert(iterator __position, _Args&&... __args)
2471  {
2472  _Node_ptr __tmp = _M_create_node(std::forward<_Args>(__args)...);
2473  __tmp->_M_hook(__position._M_node);
2474  this->_M_inc_size(1);
2475  }
2476 #endif
2477 
2478  // Erases element at position given.
2479  void
2480  _M_erase(iterator __position) _GLIBCXX_NOEXCEPT
2481  {
2482  typedef typename _Node_traits::_Node _Node;
2483  this->_M_dec_size(1);
2484  __position._M_node->_M_unhook();
2485  _Node& __n = static_cast<_Node&>(*__position._M_node);
2486  this->_M_destroy_node(__n._M_node_ptr());
2487  }
2488 
2489  // To implement the splice (and merge) bits of N1599.
2490  void
2491  _M_check_equal_allocators(const list& __x) _GLIBCXX_NOEXCEPT
2492  {
2493  if (_M_get_Node_allocator() != __x._M_get_Node_allocator())
2494  __builtin_abort();
2495  }
2496 
2497  // Used to implement resize.
2498  const_iterator
2499  _M_resize_pos(size_type& __new_size) const;
2500 
2501 #if __cplusplus >= 201103L && ! _GLIBCXX_INLINE_VERSION
2502  // XXX GLIBCXX_ABI Deprecated
2503  // These are unused and only kept so that explicit instantiations will
2504  // continue to define the symbols.
2505  void
2506  _M_move_assign(list&& __x, true_type) noexcept
2507  {
2508  this->clear();
2509  this->_M_move_nodes(std::move(__x));
2510  std::__alloc_on_move(this->_M_get_Node_allocator(),
2511  __x._M_get_Node_allocator());
2512  }
2513 
2514  void
2515  _M_move_assign(list&& __x, false_type)
2516  {
2517  if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator())
2518  _M_move_assign(std::move(__x), true_type{});
2519  else
2520  // The rvalue's allocator cannot be moved, or is not equal,
2521  // so we need to individually move each element.
2522  _M_assign_dispatch(std::make_move_iterator(__x.begin()),
2523  std::make_move_iterator(__x.end()),
2524  __false_type{});
2525  }
2526 #endif
2527 
2528 #if _GLIBCXX_USE_CXX11_ABI
2529  // Update _M_size members after merging (some of) __src into __dest.
2530  struct _Finalize_merge
2531  {
2532  explicit
2533  _Finalize_merge(list& __dest, list& __src, const iterator& __src_next)
2534  : _M_dest(__dest), _M_src(__src), _M_next(__src_next)
2535  { }
2536 
2537  ~_Finalize_merge()
2538  {
2539  // For the common case, _M_next == _M_sec.end() and the std::distance
2540  // call is fast. But if any *iter1 < *iter2 comparison throws then we
2541  // have to count how many elements remain in _M_src.
2542  const size_t __num_unmerged = std::distance(_M_next, _M_src.end());
2543  const size_t __orig_size = _M_src._M_get_size();
2544  _M_dest._M_inc_size(__orig_size - __num_unmerged);
2545  _M_src._M_set_size(__num_unmerged);
2546  }
2547 
2548  list& _M_dest;
2549  list& _M_src;
2550  const iterator& _M_next;
2551 
2552 #if __cplusplus >= 201103L
2553  _Finalize_merge(const _Finalize_merge&) = delete;
2554 #endif
2555  };
2556 #else
2557  struct _Finalize_merge
2558  { explicit _Finalize_merge(list&, list&, const iterator&) { } };
2559 #endif
2560 
2561 #if !_GLIBCXX_INLINE_VERSION
2562  // XXX GLIBCXX_ABI Deprecated
2563  // These members are unused by std::list now, but we keep them here
2564  // so that an explicit instantiation of std::list will define them.
2565  // This ensures that any objects or libraries compiled against old
2566  // versions of GCC will still be able to use the symbols.
2567 
2568 #if _GLIBCXX_USE_CXX11_ABI
2569  static size_t
2570  _S_distance(const_iterator __first, const_iterator __last)
2571  { return std::distance(__first, __last); }
2572 
2573  size_t
2574  _M_node_count() const
2575  { return this->_M_get_size(); }
2576 #else
2577  static size_t
2578  _S_distance(const_iterator, const_iterator)
2579  { return 0; }
2580 
2581  size_t
2582  _M_node_count() const
2583  { return std::distance(begin(), end()); }
2584 #endif
2585 #endif // ! INLINE_VERSION
2586  };
2587 
2588 #if __cpp_deduction_guides >= 201606
2589  template<typename _InputIterator, typename _ValT
2590  = typename iterator_traits<_InputIterator>::value_type,
2591  typename _Allocator = allocator<_ValT>,
2592  typename = _RequireInputIter<_InputIterator>,
2593  typename = _RequireAllocator<_Allocator>>
2594  list(_InputIterator, _InputIterator, _Allocator = _Allocator())
2595  -> list<_ValT, _Allocator>;
2596 
2597 #if __glibcxx_containers_ranges // C++ >= 23
2598  template<ranges::input_range _Rg,
2599  typename _Allocator = allocator<ranges::range_value_t<_Rg>>>
2600  list(from_range_t, _Rg&&, _Allocator = _Allocator())
2601  -> list<ranges::range_value_t<_Rg>, _Allocator>;
2602 #endif
2603 #endif
2604 
2605 _GLIBCXX_END_NAMESPACE_CXX11
2606 
2607  /**
2608  * @brief List equality comparison.
2609  * @param __x A %list.
2610  * @param __y A %list of the same type as @a __x.
2611  * @return True iff the size and elements of the lists are equal.
2612  *
2613  * This is an equivalence relation. It is linear in the size of
2614  * the lists. Lists are considered equivalent if their sizes are
2615  * equal, and if corresponding elements compare equal.
2616  */
2617  template<typename _Tp, typename _Alloc>
2618  _GLIBCXX_NODISCARD
2619  inline bool
2620  operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2621  {
2622 #if _GLIBCXX_USE_CXX11_ABI
2623  if (__x.size() != __y.size())
2624  return false;
2625 #endif
2626 
2627  typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
2628  const_iterator __end1 = __x.end();
2629  const_iterator __end2 = __y.end();
2630 
2631  const_iterator __i1 = __x.begin();
2632  const_iterator __i2 = __y.begin();
2633  while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
2634  {
2635  ++__i1;
2636  ++__i2;
2637  }
2638  return __i1 == __end1 && __i2 == __end2;
2639  }
2640 
2641 #if __cpp_lib_three_way_comparison
2642 /**
2643  * @brief List ordering relation.
2644  * @param __x A `list`.
2645  * @param __y A `list` of the same type as `__x`.
2646  * @return A value indicating whether `__x` is less than, equal to,
2647  * greater than, or incomparable with `__y`.
2648  *
2649  * See `std::lexicographical_compare_three_way()` for how the determination
2650  * is made. This operator is used to synthesize relational operators like
2651  * `<` and `>=` etc.
2652  */
2653  template<typename _Tp, typename _Alloc>
2654  [[nodiscard]]
2655  inline __detail::__synth3way_t<_Tp>
2656  operator<=>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2657  {
2658  return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2659  __y.begin(), __y.end(),
2660  __detail::__synth3way);
2661  }
2662 #else
2663  /**
2664  * @brief List ordering relation.
2665  * @param __x A %list.
2666  * @param __y A %list of the same type as @a __x.
2667  * @return True iff @a __x is lexicographically less than @a __y.
2668  *
2669  * This is a total ordering relation. It is linear in the size of the
2670  * lists. The elements must be comparable with @c <.
2671  *
2672  * See std::lexicographical_compare() for how the determination is made.
2673  */
2674  template<typename _Tp, typename _Alloc>
2675  _GLIBCXX_NODISCARD
2676  inline bool
2677  operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2678  { return std::lexicographical_compare(__x.begin(), __x.end(),
2679  __y.begin(), __y.end()); }
2680 
2681  /// Based on operator==
2682  template<typename _Tp, typename _Alloc>
2683  _GLIBCXX_NODISCARD
2684  inline bool
2685  operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2686  { return !(__x == __y); }
2687 
2688  /// Based on operator<
2689  template<typename _Tp, typename _Alloc>
2690  _GLIBCXX_NODISCARD
2691  inline bool
2692  operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2693  { return __y < __x; }
2694 
2695  /// Based on operator<
2696  template<typename _Tp, typename _Alloc>
2697  _GLIBCXX_NODISCARD
2698  inline bool
2699  operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2700  { return !(__y < __x); }
2701 
2702  /// Based on operator<
2703  template<typename _Tp, typename _Alloc>
2704  _GLIBCXX_NODISCARD
2705  inline bool
2706  operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2707  { return !(__x < __y); }
2708 #endif // three-way comparison
2709 
2710  /// See std::list::swap().
2711  template<typename _Tp, typename _Alloc>
2712  inline void
2714  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2715  { __x.swap(__y); }
2716 
2717 _GLIBCXX_END_NAMESPACE_CONTAINER
2718 
2719 #if _GLIBCXX_USE_CXX11_ABI
2720 
2721  // Detect when distance is used to compute the size of the whole list.
2722  template<typename _Tp>
2723  inline ptrdiff_t
2724  __distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first,
2725  _GLIBCXX_STD_C::_List_iterator<_Tp> __last,
2726  input_iterator_tag __tag)
2727  {
2728  typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _CIter;
2729  return std::__distance(_CIter(__first), _CIter(__last), __tag);
2730  }
2731 
2732  template<typename _Tp>
2733  inline ptrdiff_t
2734  __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp> __first,
2735  _GLIBCXX_STD_C::_List_const_iterator<_Tp> __last,
2736  input_iterator_tag)
2737  {
2738  typedef __detail::_List_node_header _Sentinel;
2739  _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last;
2740  ++__beyond;
2741  const bool __whole = __first == __beyond;
2742  if (__builtin_constant_p (__whole) && __whole)
2743  return static_cast<const _Sentinel*>(__last._M_node)->_M_size;
2744 
2745  ptrdiff_t __n = 0;
2746  while (__first != __last)
2747  {
2748  ++__first;
2749  ++__n;
2750  }
2751  return __n;
2752  }
2753 
2754 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
2755  template<bool _Const, typename _Ptr>
2756  inline ptrdiff_t
2757  __distance(__list::_Iterator<_Const, _Ptr> __first,
2758  __list::_Iterator<_Const, _Ptr> __last,
2759  input_iterator_tag __tag)
2760  {
2761  using _Tp = typename __list::_Iterator<_Const, _Ptr>::value_type;
2762  using _Sentinel = typename __list::_Node_traits<_Tp, _Ptr>::_Node_header;
2763  auto __beyond = __last;
2764  ++__beyond;
2765  const bool __whole = __first == __beyond;
2766  if (__builtin_constant_p (__whole) && __whole)
2767  return static_cast<const _Sentinel&>(*__last._M_node)._M_size;
2768 
2769  ptrdiff_t __n = 0;
2770  while (__first != __last)
2771  {
2772  ++__first;
2773  ++__n;
2774  }
2775  return __n;
2776  }
2777 #endif
2778 #endif
2779 
2780 #if _GLIBCXX_USE_ALLOC_PTR_FOR_LIST
2781 namespace __list
2782 {
2783  template<typename _VoidPtr>
2784  void
2785  _Node_base<_VoidPtr>::swap(_Node_base& __x, _Node_base& __y) noexcept
2786  {
2787  auto __px = __x._M_base();
2788  auto __py = __x._M_base();
2789 
2790  if (__x._M_next != __px)
2791  {
2792  if (__y._M_next != __py)
2793  {
2794  using std::swap;
2795  // Both __x and __y are not empty.
2796  swap(__x._M_next,__y._M_next);
2797  swap(__x._M_prev,__y._M_prev);
2798  __x._M_next->_M_prev = __x._M_prev->_M_next = __px;
2799  __y._M_next->_M_prev = __y._M_prev->_M_next = __py;
2800  }
2801  else
2802  {
2803  // __x is not empty, __y is empty.
2804  __y._M_next = __x._M_next;
2805  __y._M_prev = __x._M_prev;
2806  __y._M_next->_M_prev = __y._M_prev->_M_next = __py;
2807  __x._M_next = __x._M_prev = __px;
2808  }
2809  }
2810  else if (__y._M_next != __py)
2811  {
2812  // __x is empty, __y is not empty.
2813  __x._M_next = __y._M_next;
2814  __x._M_prev = __y._M_prev;
2815  __x._M_next->_M_prev = __x._M_prev->_M_next = __px;
2816  __y._M_next = __y._M_prev = __py;
2817  }
2818  }
2819 
2820  template<typename _VoidPtr>
2821  void
2822  _Node_base<_VoidPtr>::_M_transfer(_Base_ptr const __first,
2823  _Base_ptr const __last) noexcept
2824  {
2825  __glibcxx_assert(__first != __last);
2826 
2827  auto __self = _M_base();
2828  if (__self != __last)
2829  {
2830  // Remove [first, last) from its old position.
2831  __last->_M_prev->_M_next = __self;
2832  __first->_M_prev->_M_next = __last;
2833  this->_M_prev->_M_next = __first;
2834 
2835  // Splice [first, last) into its new position.
2836  auto const __tmp = this->_M_prev;
2837  this->_M_prev = __last->_M_prev;
2838  __last->_M_prev = __first->_M_prev;
2839  __first->_M_prev = __tmp;
2840  }
2841  }
2842 
2843  template<typename _VoidPtr>
2844  void
2845  _Node_header<_VoidPtr>::_M_reverse() noexcept
2846  {
2847  const auto __self = this->_M_base();
2848  auto __tmp = __self;
2849  do
2850  {
2851  using std::swap;
2852  swap(__tmp->_M_next, __tmp->_M_prev);
2853 
2854  // Old next node is now prev.
2855  __tmp = __tmp->_M_prev;
2856  }
2857  while (__tmp != __self);
2858  }
2859 } // namespace __list
2860 #endif
2861 
2862 _GLIBCXX_END_NAMESPACE_VERSION
2863 } // namespace std
2864 
2865 #endif /* _STL_LIST_H */
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:873
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:826
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:866
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:434
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:116
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:119
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:52
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1251
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1229
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void swap(list< _Tp, _Alloc > &__x, list< _Tp, _Alloc > &__y) noexcept(/*conditional */)
See std::list::swap().
Definition: stl_list.h:2713
typename pointer_traits< _Ptr >::template rebind< _Tp > __ptr_rebind
Convenience alias for rebinding pointers.
Definition: ptr_traits.h:201
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:294
initializer_list
is_same
Definition: type_traits:1540
is_nothrow_default_constructible
Definition: type_traits:1245
is_trivially_destructible
Definition: type_traits:1459
Uniform interface to all pointer-like types.
Definition: ptr_traits.h:178
A list::iterator.
Definition: stl_list.h:575
A list::const_iterator.
Definition: stl_list.h:661
Bidirectional iterators support a superset of forward iterator operations.
Common iterator class.
Common part of a node in the list.
Definition: stl_list.h:95
The list node header.
Definition: stl_list.h:131
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: stl_list.h:1026
void splice(const_iterator __position, list &&__x, const_iterator __i) noexcept
Insert element from another list.
Definition: stl_list.h:2138
list(list &&)=default
List move constructor.
void push_back(const value_type &__x)
Add data to the end of the list.
Definition: stl_list.h:1803
iterator begin() noexcept
Definition: stl_list.h:1457
iterator insert(const_iterator __position, value_type &&__x)
Inserts given value into list before specified iterator.
Definition: stl_list.h:1880
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition: stl_list.h:1447
void assign(initializer_list< value_type > __l)
Assigns an initializer_list to a list.
Definition: stl_list.h:1441
const_iterator end() const noexcept
Definition: stl_list.h:1487
const_reverse_iterator rbegin() const noexcept
Definition: stl_list.h:1507
list(size_type __n, const allocator_type &__a=allocator_type())
Creates a list with default constructed elements.
Definition: stl_list.h:1143
reverse_iterator rend() noexcept
Definition: stl_list.h:1517
void pop_back() noexcept
Removes last element.
Definition: stl_list.h:1838
void push_front(const value_type &__x)
Add data to the front of the list.
Definition: stl_list.h:1706
size_type size() const noexcept
Definition: stl_list.h:1586
const_reference front() const noexcept
Definition: stl_list.h:1660
_Node_ptr _M_create_node(_Args &&... __args)
Definition: stl_list.h:1102
void splice(const_iterator __position, list &__x, const_iterator __first, const_iterator __last) noexcept
Insert range from another list.
Definition: stl_list.h:2220
~list()=default
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a list.
Definition: stl_list.h:1419
const_iterator cend() const noexcept
Definition: stl_list.h:1548
list & operator=(initializer_list< value_type > __l)
List initializer list assignment operator.
Definition: stl_list.h:1356
list(const allocator_type &__a) noexcept
Creates a list with no elements.
Definition: stl_list.h:1130
void reverse() noexcept
Reverse the elements in list.
Definition: stl_list.h:2353
reverse_iterator rbegin() noexcept
Definition: stl_list.h:1497
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:1318
iterator erase(const_iterator __first, const_iterator __last) noexcept
Remove a range of elements.
Definition: stl_list.h:2040
reference back() noexcept
Definition: stl_list.h:1672
void assign(size_type __n, const value_type &__val)
Assigns a given value to a list.
Definition: stl_list.h:1400
void splice(const_iterator __position, list &&__x, const_iterator __first, const_iterator __last) noexcept
Insert range from another list.
Definition: stl_list.h:2180
void splice(const_iterator __position, list &__x, const_iterator __i) noexcept
Insert element from another list.
Definition: stl_list.h:2161
const_iterator cbegin() const noexcept
Definition: stl_list.h:1538
const_reverse_iterator crbegin() const noexcept
Definition: stl_list.h:1558
iterator end() noexcept
Definition: stl_list.h:1477
list(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a list from an initializer_list.
Definition: stl_list.h:1205
size_type max_size() const noexcept
Definition: stl_list.h:1598
const_reference back() const noexcept
Definition: stl_list.h:1686
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:1155
const_iterator begin() const noexcept
Definition: stl_list.h:1467
reference front() noexcept
Definition: stl_list.h:1648
void pop_front() noexcept
Removes first element.
Definition: stl_list.h:1786
list(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a list from a range.
Definition: stl_list.h:1250
void splice(const_iterator __position, list &&__x) noexcept
Insert contents of another list.
Definition: stl_list.h:2102
void clear() noexcept
Definition: stl_list.h:2082
list(const list &__x)
List copy constructor.
Definition: stl_list.h:1182
const_reverse_iterator rend() const noexcept
Definition: stl_list.h:1527
bool empty() const noexcept
Definition: stl_list.h:1578
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:1905
const_reverse_iterator crend() const noexcept
Definition: stl_list.h:1568
void swap(list &__x) noexcept
Swaps data with another list.
Definition: stl_list.h:2062
An actual node in the list.
Definition: stl_list.h:552
See bits/stl_deque.h's _Deque_base for an explanation.
Definition: stl_list.h:749
Uniform interface to C++98 and C++11 allocators.