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
81namespace 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.
94 struct _List_node_base
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
188namespace __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
432namespace __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>
551 struct _List_node : public __detail::_List_node_base
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>
574 struct _List_iterator
575 {
576 typedef _List_node<_Tp> _Node;
577
578 typedef ptrdiff_t difference_type;
579 typedef std::bidirectional_iterator_tag iterator_category;
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
591 _List_iterator
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
606 _List_iterator&
607 operator++() _GLIBCXX_NOEXCEPT
608 {
609 _M_node = _M_node->_M_next;
610 return *this;
611 }
612
613 _List_iterator
614 operator++(int) _GLIBCXX_NOEXCEPT
615 {
616 _List_iterator __tmp = *this;
617 _M_node = _M_node->_M_next;
618 return __tmp;
619 }
620
621 _List_iterator&
622 operator--() _GLIBCXX_NOEXCEPT
623 {
624 _M_node = _M_node->_M_prev;
625 return *this;
626 }
627
628 _List_iterator
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>
660 struct _List_const_iterator
661 {
662 typedef const _List_node<_Tp> _Node;
663 typedef _List_iterator<_Tp> iterator;
664
665 typedef ptrdiff_t difference_type;
666 typedef std::bidirectional_iterator_tag iterator_category;
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
675 _List_const_iterator(const __detail::_List_node_base* __x)
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
697 _List_const_iterator&
698 operator++() _GLIBCXX_NOEXCEPT
699 {
700 _M_node = _M_node->_M_next;
701 return *this;
702 }
703
704 _List_const_iterator
705 operator++(int) _GLIBCXX_NOEXCEPT
706 {
707 _List_const_iterator __tmp = *this;
708 _M_node = _M_node->_M_next;
709 return __tmp;
710 }
711
712 _List_const_iterator&
713 operator--() _GLIBCXX_NOEXCEPT
714 {
715 _M_node = _M_node->_M_prev;
716 return *this;
717 }
718
719 _List_const_iterator
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>
748 class _List_base
749 {
750 protected:
751 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
752 rebind<_Tp>::other _Tp_alloc_type;
753 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tp_alloc_traits;
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;
759 typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
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(
773 is_nothrow_default_constructible<_Node_alloc_type>::value)
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;
825 if constexpr (is_same<_Node_ptr, __alloc_pointer>::value)
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.
831 auto __ap = pointer_traits<__alloc_pointer>::pointer_to(*__p);
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
851 if constexpr (!is_trivially_destructible<_Base_ptr>::value)
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
929 if constexpr (is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value)
930#endif
931 if (__x._M_get_Node_allocator() == _M_get_Node_allocator())
932 _M_move_nodes(x: 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
942 if constexpr (!is_same<typename _Tp_alloc_traits::pointer, _Tp*>::value)
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__
1040 static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
1041 "std::list must have the same value_type as its allocator");
1042# endif
1043#endif
1044
1045 typedef _List_base<_Tp, _Alloc> _Base;
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;
1049 typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
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;
1060 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1061 typedef std::reverse_iterator<iterator> reverse_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, x: __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)
1183 : _Base(_Node_alloc_traits::
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 */
1205 list(initializer_list<value_type> __l,
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&
1318 operator=(list&& __x)
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&
1356 operator=(initializer_list<value_type> __l)
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
1441 assign(initializer_list<value_type> __l)
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
1496 reverse_iterator
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
1516 reverse_iterator
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(position: 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(position: 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: __position._M_const_cast(),
2112 first: __x.begin(), last: __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: __position._M_const_cast(),
2153 first: __i._M_const_cast(), last: __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: __position._M_const_cast(),
2200 first: __first._M_const_cast(),
2201 last: __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(n: 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
2713 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
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
2781namespace __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 */
2866