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