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