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