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