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 {
260 typedef _List_iterator<_Tp> _Self;
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 {
345 typedef _List_const_iterator<_Tp> _Self;
346 typedef const _List_node<_Tp> _Node;
347 typedef _List_iterator<_Tp> iterator;
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
366 iterator
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;
669 typedef _List_iterator<_Tp> iterator;
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
1481 /**
1482 * @brief Inserts given value into %list before specified iterator.
1483 * @param __position A const_iterator into the %list.
1484 * @param __x Data to be inserted.
1485 * @return An iterator that points to the inserted data.
1486 *
1487 * This function will insert a copy of the given value before
1488 * the specified location. Due to the nature of a %list this
1489 * operation can be done in constant time, and does not
1490 * invalidate iterators and references.
1491 */
1492 iterator
1493 insert(const_iterator __position, const value_type& __x);
1494#else
1495 /**
1496 * @brief Inserts given value into %list before specified iterator.
1497 * @param __position An iterator into the %list.
1498 * @param __x Data to be inserted.
1499 * @return An iterator that points to the inserted data.
1500 *
1501 * This function will insert a copy of the given value before
1502 * the specified location. Due to the nature of a %list this
1503 * operation can be done in constant time, and does not
1504 * invalidate iterators and references.
1505 */
1506 iterator
1507 insert(iterator __position, const value_type& __x);
1508#endif
1509
1510#if __cplusplus >= 201103L
1511 /**
1512 * @brief Inserts given rvalue into %list before specified iterator.
1513 * @param __position A const_iterator into the %list.
1514 * @param __x Data to be inserted.
1515 * @return An iterator that points to the inserted data.
1516 *
1517 * This function will insert a copy of the given rvalue before
1518 * the specified location. Due to the nature of a %list this
1519 * operation can be done in constant time, and does not
1520 * invalidate iterators and references.
1521 */
1522 iterator
1523 insert(const_iterator __position, value_type&& __x)
1524 { return emplace(__position, std::move(__x)); }
1525
1526 /**
1527 * @brief Inserts the contents of an initializer_list into %list
1528 * before specified const_iterator.
1529 * @param __p A const_iterator into the %list.
1530 * @param __l An initializer_list of value_type.
1531 * @return An iterator pointing to the first element inserted
1532 * (or __position).
1533 *
1534 * This function will insert copies of the data in the
1535 * initializer_list @a l into the %list before the location
1536 * specified by @a p.
1537 *
1538 * This operation is linear in the number of elements inserted and
1539 * does not invalidate iterators and references.
1540 */
1541 iterator
1543 { return this->insert(__p, __l.begin(), __l.end()); }
1544#endif
1545
1546#if __cplusplus >= 201103L
1547 /**
1548 * @brief Inserts a number of copies of given data into the %list.
1549 * @param __position A const_iterator into the %list.
1550 * @param __n Number of elements to be inserted.
1551 * @param __x Data to be inserted.
1552 * @return An iterator pointing to the first element inserted
1553 * (or __position).
1554 *
1555 * This function will insert a specified number of copies of the
1556 * given data before the location specified by @a position.
1557 *
1558 * This operation is linear in the number of elements inserted and
1559 * does not invalidate iterators and references.
1560 */
1561 iterator
1562 insert(const_iterator __position, size_type __n, const value_type& __x);
1563#else
1564 /**
1565 * @brief Inserts a number of copies of given data into the %list.
1566 * @param __position An iterator into the %list.
1567 * @param __n Number of elements to be inserted.
1568 * @param __x Data to be inserted.
1569 *
1570 * This function will insert a specified number of copies of the
1571 * given data before the location specified by @a position.
1572 *
1573 * This operation is linear in the number of elements inserted and
1574 * does not invalidate iterators and references.
1575 */
1576 void
1577 insert(iterator __position, size_type __n, const value_type& __x)
1578 {
1579 list __tmp(__n, __x, get_allocator());
1580 splice(__position, __tmp);
1581 }
1582#endif
1583
1584#if __cplusplus >= 201103L
1585 /**
1586 * @brief Inserts a range into the %list.
1587 * @param __position A const_iterator into the %list.
1588 * @param __first An input iterator.
1589 * @param __last An input iterator.
1590 * @return An iterator pointing to the first element inserted
1591 * (or __position).
1592 *
1593 * This function will insert copies of the data in the range [@a
1594 * first,@a last) into the %list before the location specified by
1595 * @a position.
1596 *
1597 * This operation is linear in the number of elements inserted and
1598 * does not invalidate iterators and references.
1599 */
1600 template<typename _InputIterator,
1601 typename = std::_RequireInputIter<_InputIterator>>
1602 iterator
1603 insert(const_iterator __position, _InputIterator __first,
1604 _InputIterator __last);
1605#else
1606 /**
1607 * @brief Inserts a range into the %list.
1608 * @param __position An iterator into the %list.
1609 * @param __first An input iterator.
1610 * @param __last An input iterator.
1611 *
1612 * This function will insert copies of the data in the range [@a
1613 * first,@a last) into the %list before the location specified by
1614 * @a position.
1615 *
1616 * This operation is linear in the number of elements inserted and
1617 * does not invalidate iterators and references.
1618 */
1619 template<typename _InputIterator>
1620 void
1621 insert(iterator __position, _InputIterator __first,
1622 _InputIterator __last)
1623 {
1624 list __tmp(__first, __last, get_allocator());
1625 splice(__position, __tmp);
1626 }
1627#endif
1628
1629#if __glibcxx_ranges_to_container // C++ >= 23
1630 /**
1631 * @brief Insert a range into a list.
1632 * @param __position An iterator.
1633 * @param __rg An input range of elements that can be converted to
1634 * the list's value type.
1635 * @return An iterator pointing to the first element inserted,
1636 * or `__position` if the range is empty.
1637 *
1638 * Inserts the elements of `__rg` before `__position`.
1639 * No iterators to existing elements are invalidated by this function.
1640 * If the insertion fails due to an exception, no elements will be added
1641 * and so the list will be unchanged.
1642 *
1643 * @since C++23
1644 */
1645 template<__detail::__container_compatible_range<_Tp> _Rg>
1646 iterator
1647 insert_range(const_iterator __position, _Rg&& __rg)
1648 {
1649 list __tmp(from_range, std::forward<_Rg>(__rg), get_allocator());
1650 if (!__tmp.empty())
1651 {
1652 auto __it = __tmp.begin();
1653 splice(__position, __tmp);
1654 return __it;
1655 }
1656 return __position._M_const_cast();
1657 }
1658#endif
1659
1660 /**
1661 * @brief Remove element at given position.
1662 * @param __position Iterator pointing to element to be erased.
1663 * @return An iterator pointing to the next element (or end()).
1664 *
1665 * This function will erase the element at the given position and thus
1666 * shorten the %list by one.
1667 *
1668 * Due to the nature of a %list this operation can be done in
1669 * constant time, and only invalidates iterators/references to
1670 * the element being removed. The user is also cautioned that
1671 * this function only erases the element, and that if the element
1672 * is itself a pointer, the pointed-to memory is not touched in
1673 * any way. Managing the pointer is the user's responsibility.
1674 */
1675 iterator
1676#if __cplusplus >= 201103L
1677 erase(const_iterator __position) noexcept;
1678#else
1679 erase(iterator __position);
1680#endif
1681
1682 /**
1683 * @brief Remove a range of elements.
1684 * @param __first Iterator pointing to the first element to be erased.
1685 * @param __last Iterator pointing to one past the last element to be
1686 * erased.
1687 * @return An iterator pointing to the element pointed to by @a last
1688 * prior to erasing (or end()).
1689 *
1690 * This function will erase the elements in the range @a
1691 * [first,last) and shorten the %list accordingly.
1692 *
1693 * This operation is linear time in the size of the range and only
1694 * invalidates iterators/references to the element being removed.
1695 * The user is also cautioned that this function only erases the
1696 * elements, and that if the elements themselves are pointers, the
1697 * pointed-to memory is not touched in any way. Managing the pointer
1698 * is the user's responsibility.
1699 */
1700 iterator
1701#if __cplusplus >= 201103L
1702 erase(const_iterator __first, const_iterator __last) noexcept
1703#else
1704 erase(iterator __first, iterator __last)
1705#endif
1706 {
1707 while (__first != __last)
1708 __first = erase(__first);
1709 return __last._M_const_cast();
1710 }
1711
1712 /**
1713 * @brief Swaps data with another %list.
1714 * @param __x A %list of the same element and allocator types.
1715 *
1716 * This exchanges the elements between two lists in constant
1717 * time. Note that the global std::swap() function is
1718 * specialized such that std::swap(l1,l2) will feed to this
1719 * function.
1720 *
1721 * Whether the allocators are swapped depends on the allocator traits.
1722 */
1723 void
1724 swap(list& __x) _GLIBCXX_NOEXCEPT
1725 {
1726 __detail::_List_node_base::swap(this->_M_impl._M_node,
1727 __x._M_impl._M_node);
1728
1729 size_t __xsize = __x._M_get_size();
1730 __x._M_set_size(this->_M_get_size());
1731 this->_M_set_size(__xsize);
1732
1733 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1734 __x._M_get_Node_allocator());
1735 }
1736
1737 /**
1738 * Erases all the elements. Note that this function only erases
1739 * the elements, and that if the elements themselves are
1740 * pointers, the pointed-to memory is not touched in any way.
1741 * Managing the pointer is the user's responsibility.
1742 */
1743 void
1744 clear() _GLIBCXX_NOEXCEPT
1745 {
1746 _Base::_M_clear();
1747 _Base::_M_init();
1748 }
1749
1750 // [23.2.2.4] list operations
1751 /**
1752 * @brief Insert contents of another %list.
1753 * @param __position Iterator referencing the element to insert before.
1754 * @param __x Source list.
1755 *
1756 * The elements of @a __x are inserted in constant time in front of
1757 * the element referenced by @a __position. @a __x becomes an empty
1758 * list.
1759 *
1760 * Requires this != @a __x.
1761 */
1762 void
1763#if __cplusplus >= 201103L
1764 splice(const_iterator __position, list&& __x) noexcept
1765#else
1766 splice(iterator __position, list& __x)
1767#endif
1768 {
1769 if (!__x.empty())
1770 {
1771 _M_check_equal_allocators(__x);
1772
1773 this->_M_transfer(__position._M_const_cast(),
1774 __x.begin(), __x.end());
1775
1776 this->_M_inc_size(__x._M_get_size());
1777 __x._M_set_size(0);
1778 }
1779 }
1780
1781#if __cplusplus >= 201103L
1782 void
1783 splice(const_iterator __position, list& __x) noexcept
1784 { splice(__position, std::move(__x)); }
1785#endif
1786
1787#if __cplusplus >= 201103L
1788 /**
1789 * @brief Insert element from another %list.
1790 * @param __position Const_iterator referencing the element to
1791 * insert before.
1792 * @param __x Source list.
1793 * @param __i Const_iterator referencing the element to move.
1794 *
1795 * Removes the element in list @a __x referenced by @a __i and
1796 * inserts it into the current list before @a __position.
1797 */
1798 void
1799 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
1800#else
1801 /**
1802 * @brief Insert element from another %list.
1803 * @param __position Iterator referencing the element to insert before.
1804 * @param __x Source list.
1805 * @param __i Iterator referencing the element to move.
1806 *
1807 * Removes the element in list @a __x referenced by @a __i and
1808 * inserts it into the current list before @a __position.
1809 */
1810 void
1811 splice(iterator __position, list& __x, iterator __i)
1812#endif
1813 {
1814 iterator __j = __i._M_const_cast();
1815 ++__j;
1816 if (__position == __i || __position == __j)
1817 return;
1818
1819 if (this != std::__addressof(__x))
1820 _M_check_equal_allocators(__x);
1821
1822 this->_M_transfer(__position._M_const_cast(),
1823 __i._M_const_cast(), __j);
1824
1825 this->_M_inc_size(1);
1826 __x._M_dec_size(1);
1827 }
1828
1829#if __cplusplus >= 201103L
1830 /**
1831 * @brief Insert element from another %list.
1832 * @param __position Const_iterator referencing the element to
1833 * insert before.
1834 * @param __x Source list.
1835 * @param __i Const_iterator referencing the element to move.
1836 *
1837 * Removes the element in list @a __x referenced by @a __i and
1838 * inserts it into the current list before @a __position.
1839 */
1840 void
1841 splice(const_iterator __position, list& __x, const_iterator __i) noexcept
1842 { splice(__position, std::move(__x), __i); }
1843#endif
1844
1845#if __cplusplus >= 201103L
1846 /**
1847 * @brief Insert range from another %list.
1848 * @param __position Const_iterator referencing the element to
1849 * insert before.
1850 * @param __x Source list.
1851 * @param __first Const_iterator referencing the start of range in x.
1852 * @param __last Const_iterator referencing the end of range in x.
1853 *
1854 * Removes elements in the range [__first,__last) and inserts them
1855 * before @a __position in constant time.
1856 *
1857 * Undefined if @a __position is in [__first,__last).
1858 */
1859 void
1860 splice(const_iterator __position, list&& __x, const_iterator __first,
1861 const_iterator __last) noexcept
1862#else
1863 /**
1864 * @brief Insert range from another %list.
1865 * @param __position Iterator referencing the element to insert before.
1866 * @param __x Source list.
1867 * @param __first Iterator referencing the start of range in x.
1868 * @param __last Iterator referencing the end of range in x.
1869 *
1870 * Removes elements in the range [__first,__last) and inserts them
1871 * before @a __position in constant time.
1872 *
1873 * Undefined if @a __position is in [__first,__last).
1874 */
1875 void
1876 splice(iterator __position, list& __x, iterator __first,
1877 iterator __last)
1878#endif
1879 {
1880 if (__first != __last)
1881 {
1882 if (this != std::__addressof(__x))
1883 _M_check_equal_allocators(__x);
1884
1885 size_t __n = _S_distance(__first, __last);
1886 this->_M_inc_size(__n);
1887 __x._M_dec_size(__n);
1888
1889 this->_M_transfer(__position._M_const_cast(),
1890 __first._M_const_cast(),
1891 __last._M_const_cast());
1892 }
1893 }
1894
1895#if __cplusplus >= 201103L
1896 /**
1897 * @brief Insert range from another %list.
1898 * @param __position Const_iterator referencing the element to
1899 * insert before.
1900 * @param __x Source list.
1901 * @param __first Const_iterator referencing the start of range in x.
1902 * @param __last Const_iterator referencing the end of range in x.
1903 *
1904 * Removes elements in the range [__first,__last) and inserts them
1905 * before @a __position in constant time.
1906 *
1907 * Undefined if @a __position is in [__first,__last).
1908 */
1909 void
1910 splice(const_iterator __position, list& __x, const_iterator __first,
1911 const_iterator __last) noexcept
1912 { splice(__position, std::move(__x), __first, __last); }
1913#endif
1914
1915 private:
1916#ifdef __glibcxx_list_remove_return_type // C++ >= 20 && HOSTED
1917 typedef size_type __remove_return_type;
1918# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
1919 __attribute__((__abi_tag__("__cxx20")))
1920#else
1921 typedef void __remove_return_type;
1922# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
1923#endif
1924 public:
1925
1926 /**
1927 * @brief Remove all elements equal to value.
1928 * @param __value The value to remove.
1929 *
1930 * Removes every element in the list equal to @a value.
1931 * Remaining elements stay in list order. Note that this
1932 * function only erases the elements, and that if the elements
1933 * themselves are pointers, the pointed-to memory is not
1934 * touched in any way. Managing the pointer is the user's
1935 * responsibility.
1936 */
1937 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
1938 __remove_return_type
1939 remove(const _Tp& __value);
1940
1941 /**
1942 * @brief Remove all elements satisfying a predicate.
1943 * @tparam _Predicate Unary predicate function or object.
1944 *
1945 * Removes every element in the list for which the predicate
1946 * returns true. Remaining elements stay in list order. Note
1947 * that this function only erases the elements, and that if the
1948 * elements themselves are pointers, the pointed-to memory is
1949 * not touched in any way. Managing the pointer is the user's
1950 * responsibility.
1951 */
1952 template<typename _Predicate>
1953 __remove_return_type
1954 remove_if(_Predicate);
1955
1956 /**
1957 * @brief Remove consecutive duplicate elements.
1958 *
1959 * For each consecutive set of elements with the same value,
1960 * remove all but the first one. Remaining elements stay in
1961 * list order. Note that this function only erases the
1962 * elements, and that if the elements themselves are pointers,
1963 * the pointed-to memory is not touched in any way. Managing
1964 * the pointer is the user's responsibility.
1965 */
1966 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
1967 __remove_return_type
1968 unique();
1969
1970 /**
1971 * @brief Remove consecutive elements satisfying a predicate.
1972 * @tparam _BinaryPredicate Binary predicate function or object.
1973 *
1974 * For each consecutive set of elements [first,last) that
1975 * satisfy predicate(first,i) where i is an iterator in
1976 * [first,last), remove all but the first one. Remaining
1977 * elements stay in list order. Note that this function only
1978 * erases the elements, and that if the elements themselves are
1979 * pointers, the pointed-to memory is not touched in any way.
1980 * Managing the pointer is the user's responsibility.
1981 */
1982 template<typename _BinaryPredicate>
1983 __remove_return_type
1984 unique(_BinaryPredicate);
1985
1986#undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
1987
1988 /**
1989 * @brief Merge sorted lists.
1990 * @param __x Sorted list to merge.
1991 *
1992 * Assumes that both @a __x and this list are sorted according to
1993 * operator<(). Merges elements of @a __x into this list in
1994 * sorted order, leaving @a __x empty when complete. Elements in
1995 * this list precede elements in @a __x that are equal.
1996 */
1997#if __cplusplus >= 201103L
1998 void
1999 merge(list&& __x);
2000
2001 void
2002 merge(list& __x)
2003 { merge(std::move(__x)); }
2004#else
2005 void
2006 merge(list& __x);
2007#endif
2008
2009 /**
2010 * @brief Merge sorted lists according to comparison function.
2011 * @tparam _StrictWeakOrdering Comparison function defining
2012 * sort order.
2013 * @param __x Sorted list to merge.
2014 * @param __comp Comparison functor.
2015 *
2016 * Assumes that both @a __x and this list are sorted according to
2017 * StrictWeakOrdering. Merges elements of @a __x into this list
2018 * in sorted order, leaving @a __x empty when complete. Elements
2019 * in this list precede elements in @a __x that are equivalent
2020 * according to StrictWeakOrdering().
2021 */
2022#if __cplusplus >= 201103L
2023 template<typename _StrictWeakOrdering>
2024 void
2025 merge(list&& __x, _StrictWeakOrdering __comp);
2026
2027 template<typename _StrictWeakOrdering>
2028 void
2029 merge(list& __x, _StrictWeakOrdering __comp)
2030 { merge(std::move(__x), __comp); }
2031#else
2032 template<typename _StrictWeakOrdering>
2033 void
2034 merge(list& __x, _StrictWeakOrdering __comp);
2035#endif
2036
2037 /**
2038 * @brief Reverse the elements in list.
2039 *
2040 * Reverse the order of elements in the list in linear time.
2041 */
2042 void
2043 reverse() _GLIBCXX_NOEXCEPT
2044 { this->_M_impl._M_node._M_reverse(); }
2045
2046 /**
2047 * @brief Sort the elements.
2048 *
2049 * Sorts the elements of this list in NlogN time. Equivalent
2050 * elements remain in list order.
2051 */
2052 void
2053 sort();
2054
2055 /**
2056 * @brief Sort the elements according to comparison function.
2057 *
2058 * Sorts the elements of this list in NlogN time. Equivalent
2059 * elements remain in list order.
2060 */
2061 template<typename _StrictWeakOrdering>
2062 void
2063 sort(_StrictWeakOrdering);
2064
2065 protected:
2066 // Internal constructor functions follow.
2067
2068 // Called by the range constructor to implement [23.1.1]/9
2069
2070 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2071 // 438. Ambiguity in the "do the right thing" clause
2072 template<typename _Integer>
2073 void
2074 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
2075 { _M_fill_initialize(static_cast<size_type>(__n), __x); }
2076
2077 // Called by the range constructor to implement [23.1.1]/9
2078 template<typename _InputIterator>
2079 void
2080 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
2081 __false_type)
2082 {
2083 for (; __first != __last; ++__first)
2084#if __cplusplus >= 201103L
2085 emplace_back(*__first);
2086#else
2087 push_back(*__first);
2088#endif
2089 }
2090
2091 // Called by list(n,v,a), and the range constructor when it turns out
2092 // to be the same thing.
2093 void
2094 _M_fill_initialize(size_type __n, const value_type& __x)
2095 {
2096 for (; __n; --__n)
2097 push_back(__x);
2098 }
2099
2100#if __cplusplus >= 201103L
2101 // Called by list(n).
2102 void
2103 _M_default_initialize(size_type __n)
2104 {
2105 for (; __n; --__n)
2106 emplace_back();
2107 }
2108
2109 // Called by resize(sz).
2110 void
2111 _M_default_append(size_type __n);
2112#endif
2113
2114 // Internal assign functions follow.
2115
2116 // Called by the range assign to implement [23.1.1]/9
2117
2118 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2119 // 438. Ambiguity in the "do the right thing" clause
2120 template<typename _Integer>
2121 void
2122 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
2123 { _M_fill_assign(__n, __val); }
2124
2125 // Called by the range assign to implement [23.1.1]/9
2126 template<typename _InputIterator>
2127 void
2128 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
2129 __false_type);
2130
2131 // Called by assign(n,t), and the range assign when it turns out
2132 // to be the same thing.
2133 void
2134 _M_fill_assign(size_type __n, const value_type& __val);
2135
2136
2137 // Moves the elements from [first,last) before position.
2138 void
2139 _M_transfer(iterator __position, iterator __first, iterator __last)
2140 { __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
2141
2142 // Inserts new element at position given and with value given.
2143#if __cplusplus < 201103L
2144 void
2145 _M_insert(iterator __position, const value_type& __x)
2146 {
2147 _Node* __tmp = _M_create_node(__x);
2148 __tmp->_M_hook(__position._M_node);
2149 this->_M_inc_size(1);
2150 }
2151#else
2152 template<typename... _Args>
2153 void
2154 _M_insert(iterator __position, _Args&&... __args)
2155 {
2156 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
2157 __tmp->_M_hook(__position._M_node);
2158 this->_M_inc_size(1);
2159 }
2160#endif
2161
2162 // Erases element at position given.
2163 void
2164 _M_erase(iterator __position) _GLIBCXX_NOEXCEPT
2165 {
2166 this->_M_dec_size(1);
2167 __position._M_node->_M_unhook();
2168 _Node* __n = static_cast<_Node*>(__position._M_node);
2169#if __cplusplus >= 201103L
2170 _Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr());
2171#else
2172 _Tp_alloc_type(_M_get_Node_allocator()).destroy(__n->_M_valptr());
2173#endif
2174
2175 _M_put_node(__n);
2176 }
2177
2178 // To implement the splice (and merge) bits of N1599.
2179 void
2180 _M_check_equal_allocators(const list& __x) _GLIBCXX_NOEXCEPT
2181 {
2182 if (_M_get_Node_allocator() != __x._M_get_Node_allocator())
2183 __builtin_abort();
2184 }
2185
2186 // Used to implement resize.
2187 const_iterator
2188 _M_resize_pos(size_type& __new_size) const;
2189
2190#if __cplusplus >= 201103L && ! _GLIBCXX_INLINE_VERSION
2191 // XXX GLIBCXX_ABI Deprecated
2192 // These are unused and only kept so that explicit instantiations will
2193 // continue to define the symbols.
2194 void
2195 _M_move_assign(list&& __x, true_type) noexcept
2196 {
2197 this->clear();
2198 this->_M_move_nodes(std::move(__x));
2199 std::__alloc_on_move(this->_M_get_Node_allocator(),
2200 __x._M_get_Node_allocator());
2201 }
2202
2203 void
2204 _M_move_assign(list&& __x, false_type)
2205 {
2206 if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator())
2207 _M_move_assign(std::move(__x), true_type{});
2208 else
2209 // The rvalue's allocator cannot be moved, or is not equal,
2210 // so we need to individually move each element.
2211 _M_assign_dispatch(std::make_move_iterator(__x.begin()),
2212 std::make_move_iterator(__x.end()),
2213 __false_type{});
2214 }
2215#endif
2216
2217#if _GLIBCXX_USE_CXX11_ABI
2218 // Update _M_size members after merging (some of) __src into __dest.
2219 struct _Finalize_merge
2220 {
2221 explicit
2222 _Finalize_merge(list& __dest, list& __src, const iterator& __src_next)
2223 : _M_dest(__dest), _M_src(__src), _M_next(__src_next)
2224 { }
2225
2226 ~_Finalize_merge()
2227 {
2228 // For the common case, _M_next == _M_sec.end() and the std::distance
2229 // call is fast. But if any *iter1 < *iter2 comparison throws then we
2230 // have to count how many elements remain in _M_src.
2231 const size_t __num_unmerged = std::distance(_M_next, _M_src.end());
2232 const size_t __orig_size = _M_src._M_get_size();
2233 _M_dest._M_inc_size(__orig_size - __num_unmerged);
2234 _M_src._M_set_size(__num_unmerged);
2235 }
2236
2237 list& _M_dest;
2238 list& _M_src;
2239 const iterator& _M_next;
2240
2241#if __cplusplus >= 201103L
2242 _Finalize_merge(const _Finalize_merge&) = delete;
2243#endif
2244 };
2245#else
2246 struct _Finalize_merge
2247 { explicit _Finalize_merge(list&, list&, const iterator&) { } };
2248#endif
2249
2250 };
2251
2252#if __cpp_deduction_guides >= 201606
2253 template<typename _InputIterator, typename _ValT
2254 = typename iterator_traits<_InputIterator>::value_type,
2255 typename _Allocator = allocator<_ValT>,
2256 typename = _RequireInputIter<_InputIterator>,
2257 typename = _RequireAllocator<_Allocator>>
2258 list(_InputIterator, _InputIterator, _Allocator = _Allocator())
2259 -> list<_ValT, _Allocator>;
2260
2261#if __glibcxx_ranges_to_container // C++ >= 23
2262 template<ranges::input_range _Rg,
2263 typename _Allocator = allocator<ranges::range_value_t<_Rg>>>
2264 list(from_range_t, _Rg&&, _Allocator = _Allocator())
2265 -> list<ranges::range_value_t<_Rg>, _Allocator>;
2266#endif
2267#endif
2268
2269_GLIBCXX_END_NAMESPACE_CXX11
2270
2271 /**
2272 * @brief List equality comparison.
2273 * @param __x A %list.
2274 * @param __y A %list of the same type as @a __x.
2275 * @return True iff the size and elements of the lists are equal.
2276 *
2277 * This is an equivalence relation. It is linear in the size of
2278 * the lists. Lists are considered equivalent if their sizes are
2279 * equal, and if corresponding elements compare equal.
2280 */
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 {
2286#if _GLIBCXX_USE_CXX11_ABI
2287 if (__x.size() != __y.size())
2288 return false;
2289#endif
2290
2291 typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
2292 const_iterator __end1 = __x.end();
2293 const_iterator __end2 = __y.end();
2294
2295 const_iterator __i1 = __x.begin();
2296 const_iterator __i2 = __y.begin();
2297 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
2298 {
2299 ++__i1;
2300 ++__i2;
2301 }
2302 return __i1 == __end1 && __i2 == __end2;
2303 }
2304
2305#if __cpp_lib_three_way_comparison
2306/**
2307 * @brief List ordering relation.
2308 * @param __x A `list`.
2309 * @param __y A `list` of the same type as `__x`.
2310 * @return A value indicating whether `__x` is less than, equal to,
2311 * greater than, or incomparable with `__y`.
2312 *
2313 * See `std::lexicographical_compare_three_way()` for how the determination
2314 * is made. This operator is used to synthesize relational operators like
2315 * `<` and `>=` etc.
2316 */
2317 template<typename _Tp, typename _Alloc>
2318 [[nodiscard]]
2319 inline __detail::__synth3way_t<_Tp>
2320 operator<=>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2321 {
2322 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2323 __y.begin(), __y.end(),
2324 __detail::__synth3way);
2325 }
2326#else
2327 /**
2328 * @brief List ordering relation.
2329 * @param __x A %list.
2330 * @param __y A %list of the same type as @a __x.
2331 * @return True iff @a __x is lexicographically less than @a __y.
2332 *
2333 * This is a total ordering relation. It is linear in the size of the
2334 * lists. The elements must be comparable with @c <.
2335 *
2336 * See std::lexicographical_compare() for how the determination is made.
2337 */
2338 template<typename _Tp, typename _Alloc>
2339 _GLIBCXX_NODISCARD
2340 inline bool
2341 operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2342 { return std::lexicographical_compare(__x.begin(), __x.end(),
2343 __y.begin(), __y.end()); }
2344
2345 /// Based on operator==
2346 template<typename _Tp, typename _Alloc>
2347 _GLIBCXX_NODISCARD
2348 inline bool
2349 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2350 { return !(__x == __y); }
2351
2352 /// Based on operator<
2353 template<typename _Tp, typename _Alloc>
2354 _GLIBCXX_NODISCARD
2355 inline bool
2356 operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2357 { return __y < __x; }
2358
2359 /// Based on operator<
2360 template<typename _Tp, typename _Alloc>
2361 _GLIBCXX_NODISCARD
2362 inline bool
2363 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2364 { return !(__y < __x); }
2365
2366 /// Based on operator<
2367 template<typename _Tp, typename _Alloc>
2368 _GLIBCXX_NODISCARD
2369 inline bool
2370 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2371 { return !(__x < __y); }
2372#endif // three-way comparison
2373
2374 /// See std::list::swap().
2375 template<typename _Tp, typename _Alloc>
2376 inline void
2378 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2379 { __x.swap(__y); }
2380
2381_GLIBCXX_END_NAMESPACE_CONTAINER
2382
2383#if _GLIBCXX_USE_CXX11_ABI
2384
2385 // Detect when distance is used to compute the size of the whole list.
2386 template<typename _Tp>
2387 inline ptrdiff_t
2388 __distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first,
2389 _GLIBCXX_STD_C::_List_iterator<_Tp> __last,
2390 input_iterator_tag __tag)
2391 {
2392 typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _CIter;
2393 return std::__distance(_CIter(__first), _CIter(__last), __tag);
2394 }
2395
2396 template<typename _Tp>
2397 inline ptrdiff_t
2398 __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp> __first,
2399 _GLIBCXX_STD_C::_List_const_iterator<_Tp> __last,
2400 input_iterator_tag)
2401 {
2402 typedef __detail::_List_node_header _Sentinel;
2403 _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last;
2404 ++__beyond;
2405 const bool __whole = __first == __beyond;
2406 if (__builtin_constant_p (__whole) && __whole)
2407 return static_cast<const _Sentinel*>(__last._M_node)->_M_size;
2408
2409 ptrdiff_t __n = 0;
2410 while (__first != __last)
2411 {
2412 ++__first;
2413 ++__n;
2414 }
2415 return __n;
2416 }
2417#endif
2418
2419_GLIBCXX_END_NAMESPACE_VERSION
2420} // namespace std
2421
2422#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
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Definition type_traits:116
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition type_traits:119
constexpr 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 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.
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:1237
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:1799
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 rvalue into list before specified iterator.
Definition stl_list.h:1523
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:1910
~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:2043
__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:1702
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:1860
void splice(const_iterator __position, list &__x, const_iterator __i) noexcept
Insert element from another list.
Definition stl_list.h:1841
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:1764
void clear() noexcept
Definition stl_list.h:1744
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:1542
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:1724
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr size_type max_size(const _Alloc &__a) noexcept
The maximum supported allocation size.