1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_LIST
11#define _LIBCPP_LIST
12
13/*
14 list synopsis
15
16namespace std
17{
18
19template <class T, class Alloc = allocator<T> >
20class list
21{
22public:
23
24 // types:
25 typedef T value_type;
26 typedef Alloc allocator_type;
27 typedef typename allocator_type::reference reference;
28 typedef typename allocator_type::const_reference const_reference;
29 typedef typename allocator_type::pointer pointer;
30 typedef typename allocator_type::const_pointer const_pointer;
31 typedef implementation-defined iterator;
32 typedef implementation-defined const_iterator;
33 typedef implementation-defined size_type;
34 typedef implementation-defined difference_type;
35 typedef reverse_iterator<iterator> reverse_iterator;
36 typedef reverse_iterator<const_iterator> const_reverse_iterator;
37
38 list()
39 noexcept(is_nothrow_default_constructible<allocator_type>::value);
40 explicit list(const allocator_type& a);
41 explicit list(size_type n);
42 explicit list(size_type n, const allocator_type& a); // C++14
43 list(size_type n, const value_type& value);
44 list(size_type n, const value_type& value, const allocator_type& a);
45 template <class Iter>
46 list(Iter first, Iter last);
47 template <class Iter>
48 list(Iter first, Iter last, const allocator_type& a);
49 list(const list& x);
50 list(const list&, const allocator_type& a);
51 list(list&& x)
52 noexcept(is_nothrow_move_constructible<allocator_type>::value);
53 list(list&&, const allocator_type& a);
54 list(initializer_list<value_type>);
55 list(initializer_list<value_type>, const allocator_type& a);
56
57 ~list();
58
59 list& operator=(const list& x);
60 list& operator=(list&& x)
61 noexcept(
62 allocator_type::propagate_on_container_move_assignment::value &&
63 is_nothrow_move_assignable<allocator_type>::value);
64 list& operator=(initializer_list<value_type>);
65 template <class Iter>
66 void assign(Iter first, Iter last);
67 void assign(size_type n, const value_type& t);
68 void assign(initializer_list<value_type>);
69
70 allocator_type get_allocator() const noexcept;
71
72 iterator begin() noexcept;
73 const_iterator begin() const noexcept;
74 iterator end() noexcept;
75 const_iterator end() const noexcept;
76 reverse_iterator rbegin() noexcept;
77 const_reverse_iterator rbegin() const noexcept;
78 reverse_iterator rend() noexcept;
79 const_reverse_iterator rend() const noexcept;
80 const_iterator cbegin() const noexcept;
81 const_iterator cend() const noexcept;
82 const_reverse_iterator crbegin() const noexcept;
83 const_reverse_iterator crend() const noexcept;
84
85 reference front();
86 const_reference front() const;
87 reference back();
88 const_reference back() const;
89
90 bool empty() const noexcept;
91 size_type size() const noexcept;
92 size_type max_size() const noexcept;
93
94 template <class... Args>
95 reference emplace_front(Args&&... args); // reference in C++17
96 void pop_front();
97 template <class... Args>
98 reference emplace_back(Args&&... args); // reference in C++17
99 void pop_back();
100 void push_front(const value_type& x);
101 void push_front(value_type&& x);
102 void push_back(const value_type& x);
103 void push_back(value_type&& x);
104 template <class... Args>
105 iterator emplace(const_iterator position, Args&&... args);
106 iterator insert(const_iterator position, const value_type& x);
107 iterator insert(const_iterator position, value_type&& x);
108 iterator insert(const_iterator position, size_type n, const value_type& x);
109 template <class Iter>
110 iterator insert(const_iterator position, Iter first, Iter last);
111 iterator insert(const_iterator position, initializer_list<value_type> il);
112
113 iterator erase(const_iterator position);
114 iterator erase(const_iterator position, const_iterator last);
115
116 void resize(size_type sz);
117 void resize(size_type sz, const value_type& c);
118
119 void swap(list&)
120 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
121 void clear() noexcept;
122
123 void splice(const_iterator position, list& x);
124 void splice(const_iterator position, list&& x);
125 void splice(const_iterator position, list& x, const_iterator i);
126 void splice(const_iterator position, list&& x, const_iterator i);
127 void splice(const_iterator position, list& x, const_iterator first,
128 const_iterator last);
129 void splice(const_iterator position, list&& x, const_iterator first,
130 const_iterator last);
131
132 size_type remove(const value_type& value); // void before C++20
133 template <class Pred>
134 size_type remove_if(Pred pred); // void before C++20
135 size_type unique(); // void before C++20
136 template <class BinaryPredicate>
137 size_type unique(BinaryPredicate binary_pred); // void before C++20
138 void merge(list& x);
139 void merge(list&& x);
140 template <class Compare>
141 void merge(list& x, Compare comp);
142 template <class Compare>
143 void merge(list&& x, Compare comp);
144 void sort();
145 template <class Compare>
146 void sort(Compare comp);
147 void reverse() noexcept;
148};
149
150
151template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
152 list(InputIterator, InputIterator, Allocator = Allocator())
153 -> list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
154
155template <class T, class Alloc>
156 bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
157template <class T, class Alloc>
158 bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);
159template <class T, class Alloc>
160 bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);
161template <class T, class Alloc>
162 bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);
163template <class T, class Alloc>
164 bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);
165template <class T, class Alloc>
166 bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);
167
168template <class T, class Alloc>
169 void swap(list<T,Alloc>& x, list<T,Alloc>& y)
170 noexcept(noexcept(x.swap(y)));
171
172template <class T, class Allocator, class U>
173 typename list<T, Allocator>::size_type
174 erase(list<T, Allocator>& c, const U& value); // C++20
175template <class T, class Allocator, class Predicate>
176 typename list<T, Allocator>::size_type
177 erase_if(list<T, Allocator>& c, Predicate pred); // C++20
178
179} // std
180
181*/
182
183#include <__algorithm/comp.h>
184#include <__algorithm/equal.h>
185#include <__algorithm/lexicographical_compare.h>
186#include <__algorithm/min.h>
187#include <__assert> // all public C++ headers provide the assertion handler
188#include <__config>
189#include <__debug>
190#include <__format/enable_insertable.h>
191#include <__iterator/distance.h>
192#include <__iterator/iterator_traits.h>
193#include <__iterator/move_iterator.h>
194#include <__iterator/next.h>
195#include <__iterator/prev.h>
196#include <__iterator/reverse_iterator.h>
197#include <__utility/forward.h>
198#include <__utility/move.h>
199#include <__utility/swap.h>
200#include <limits>
201#include <memory>
202#include <type_traits>
203#include <version>
204
205#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES
206# include <algorithm>
207# include <functional>
208# include <iterator>
209#endif
210
211// standard-mandated includes
212
213// [iterator.range]
214#include <__iterator/access.h>
215#include <__iterator/data.h>
216#include <__iterator/empty.h>
217#include <__iterator/reverse_access.h>
218#include <__iterator/size.h>
219
220// [list.syn]
221#include <compare>
222#include <initializer_list>
223
224#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
225# pragma GCC system_header
226#endif
227
228_LIBCPP_PUSH_MACROS
229#include <__undef_macros>
230
231
232_LIBCPP_BEGIN_NAMESPACE_STD
233
234template <class _Tp, class _VoidPtr> struct __list_node;
235template <class _Tp, class _VoidPtr> struct __list_node_base;
236
237template <class _Tp, class _VoidPtr>
238struct __list_node_pointer_traits {
239 typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
240 __node_pointer;
241 typedef typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type
242 __base_pointer;
243
244#if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)
245 typedef __base_pointer __link_pointer;
246#else
247 typedef typename conditional<
248 is_pointer<_VoidPtr>::value,
249 __base_pointer,
250 __node_pointer
251 >::type __link_pointer;
252#endif
253
254 typedef typename conditional<
255 is_same<__link_pointer, __node_pointer>::value,
256 __base_pointer,
257 __node_pointer
258 >::type __non_link_pointer;
259
260 static _LIBCPP_INLINE_VISIBILITY
261 __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) {
262 return __p;
263 }
264
265 static _LIBCPP_INLINE_VISIBILITY
266 __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {
267 return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));
268 }
269
270};
271
272template <class _Tp, class _VoidPtr>
273struct __list_node_base
274{
275 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
276 typedef typename _NodeTraits::__node_pointer __node_pointer;
277 typedef typename _NodeTraits::__base_pointer __base_pointer;
278 typedef typename _NodeTraits::__link_pointer __link_pointer;
279
280 __link_pointer __prev_;
281 __link_pointer __next_;
282
283 _LIBCPP_INLINE_VISIBILITY
284 __list_node_base() : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),
285 __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}
286
287 _LIBCPP_INLINE_VISIBILITY
288 __base_pointer __self() {
289 return pointer_traits<__base_pointer>::pointer_to(*this);
290 }
291
292 _LIBCPP_INLINE_VISIBILITY
293 __node_pointer __as_node() {
294 return static_cast<__node_pointer>(__self());
295 }
296};
297
298template <class _Tp, class _VoidPtr>
299struct _LIBCPP_STANDALONE_DEBUG __list_node
300 : public __list_node_base<_Tp, _VoidPtr>
301{
302 _Tp __value_;
303
304 typedef __list_node_base<_Tp, _VoidPtr> __base;
305 typedef typename __base::__link_pointer __link_pointer;
306
307 _LIBCPP_INLINE_VISIBILITY
308 __link_pointer __as_link() {
309 return static_cast<__link_pointer>(__base::__self());
310 }
311};
312
313template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS list;
314template <class _Tp, class _Alloc> class __list_imp;
315template <class _Tp, class _VoidPtr> class _LIBCPP_TEMPLATE_VIS __list_const_iterator;
316
317template <class _Tp, class _VoidPtr>
318class _LIBCPP_TEMPLATE_VIS __list_iterator
319{
320 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
321 typedef typename _NodeTraits::__link_pointer __link_pointer;
322
323 __link_pointer __ptr_;
324
325 _LIBCPP_INLINE_VISIBILITY
326 explicit __list_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
327 : __ptr_(__p)
328 {
329 (void)__c;
330#ifdef _LIBCPP_ENABLE_DEBUG_MODE
331 __get_db()->__insert_ic(this, __c);
332#endif
333 }
334
335 template<class, class> friend class list;
336 template<class, class> friend class __list_imp;
337 template<class, class> friend class __list_const_iterator;
338public:
339 typedef bidirectional_iterator_tag iterator_category;
340 typedef _Tp value_type;
341 typedef value_type& reference;
342 typedef typename __rebind_pointer<_VoidPtr, value_type>::type pointer;
343 typedef typename pointer_traits<pointer>::difference_type difference_type;
344
345 _LIBCPP_INLINE_VISIBILITY
346 __list_iterator() _NOEXCEPT : __ptr_(nullptr)
347 {
348 _VSTD::__debug_db_insert_i(this);
349 }
350
351#ifdef _LIBCPP_ENABLE_DEBUG_MODE
352
353 _LIBCPP_INLINE_VISIBILITY
354 __list_iterator(const __list_iterator& __p)
355 : __ptr_(__p.__ptr_)
356 {
357 __get_db()->__iterator_copy(this, _VSTD::addressof(__p));
358 }
359
360 _LIBCPP_INLINE_VISIBILITY
361 ~__list_iterator()
362 {
363 __get_db()->__erase_i(this);
364 }
365
366 _LIBCPP_INLINE_VISIBILITY
367 __list_iterator& operator=(const __list_iterator& __p)
368 {
369 if (this != _VSTD::addressof(__p))
370 {
371 __get_db()->__iterator_copy(this, _VSTD::addressof(__p));
372 __ptr_ = __p.__ptr_;
373 }
374 return *this;
375 }
376
377#endif // _LIBCPP_ENABLE_DEBUG_MODE
378
379 _LIBCPP_INLINE_VISIBILITY
380 reference operator*() const
381 {
382 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
383 "Attempted to dereference a non-dereferenceable list::iterator");
384 return __ptr_->__as_node()->__value_;
385 }
386 _LIBCPP_INLINE_VISIBILITY
387 pointer operator->() const
388 {
389 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
390 "Attempted to dereference a non-dereferenceable list::iterator");
391 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
392 }
393
394 _LIBCPP_INLINE_VISIBILITY
395 __list_iterator& operator++()
396 {
397 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
398 "Attempted to increment a non-incrementable list::iterator");
399 __ptr_ = __ptr_->__next_;
400 return *this;
401 }
402 _LIBCPP_INLINE_VISIBILITY
403 __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;}
404
405 _LIBCPP_INLINE_VISIBILITY
406 __list_iterator& operator--()
407 {
408 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__decrementable(this),
409 "Attempted to decrement a non-decrementable list::iterator");
410 __ptr_ = __ptr_->__prev_;
411 return *this;
412 }
413 _LIBCPP_INLINE_VISIBILITY
414 __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}
415
416 friend _LIBCPP_INLINE_VISIBILITY
417 bool operator==(const __list_iterator& __x, const __list_iterator& __y)
418 {
419 return __x.__ptr_ == __y.__ptr_;
420 }
421 friend _LIBCPP_INLINE_VISIBILITY
422 bool operator!=(const __list_iterator& __x, const __list_iterator& __y)
423 {return !(__x == __y);}
424};
425
426template <class _Tp, class _VoidPtr>
427class _LIBCPP_TEMPLATE_VIS __list_const_iterator
428{
429 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
430 typedef typename _NodeTraits::__link_pointer __link_pointer;
431
432 __link_pointer __ptr_;
433
434 _LIBCPP_INLINE_VISIBILITY
435 explicit __list_const_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
436 : __ptr_(__p)
437 {
438 (void)__c;
439#ifdef _LIBCPP_ENABLE_DEBUG_MODE
440 __get_db()->__insert_ic(this, __c);
441#endif
442 }
443
444 template<class, class> friend class list;
445 template<class, class> friend class __list_imp;
446public:
447 typedef bidirectional_iterator_tag iterator_category;
448 typedef _Tp value_type;
449 typedef const value_type& reference;
450 typedef typename __rebind_pointer<_VoidPtr, const value_type>::type pointer;
451 typedef typename pointer_traits<pointer>::difference_type difference_type;
452
453 _LIBCPP_INLINE_VISIBILITY
454 __list_const_iterator() _NOEXCEPT : __ptr_(nullptr)
455 {
456 _VSTD::__debug_db_insert_i(this);
457 }
458 _LIBCPP_INLINE_VISIBILITY
459 __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT
460 : __ptr_(__p.__ptr_)
461 {
462#ifdef _LIBCPP_ENABLE_DEBUG_MODE
463 __get_db()->__iterator_copy(this, _VSTD::addressof(__p));
464#endif
465 }
466
467#ifdef _LIBCPP_ENABLE_DEBUG_MODE
468
469 _LIBCPP_INLINE_VISIBILITY
470 __list_const_iterator(const __list_const_iterator& __p)
471 : __ptr_(__p.__ptr_)
472 {
473 __get_db()->__iterator_copy(this, _VSTD::addressof(__p));
474 }
475
476 _LIBCPP_INLINE_VISIBILITY
477 ~__list_const_iterator()
478 {
479 __get_db()->__erase_i(this);
480 }
481
482 _LIBCPP_INLINE_VISIBILITY
483 __list_const_iterator& operator=(const __list_const_iterator& __p)
484 {
485 if (this != _VSTD::addressof(__p))
486 {
487 __get_db()->__iterator_copy(this, _VSTD::addressof(__p));
488 __ptr_ = __p.__ptr_;
489 }
490 return *this;
491 }
492
493#endif // _LIBCPP_ENABLE_DEBUG_MODE
494 _LIBCPP_INLINE_VISIBILITY
495 reference operator*() const
496 {
497 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
498 "Attempted to dereference a non-dereferenceable list::const_iterator");
499 return __ptr_->__as_node()->__value_;
500 }
501 _LIBCPP_INLINE_VISIBILITY
502 pointer operator->() const
503 {
504 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
505 "Attempted to dereference a non-dereferenceable list::const_iterator");
506 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
507 }
508
509 _LIBCPP_INLINE_VISIBILITY
510 __list_const_iterator& operator++()
511 {
512 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
513 "Attempted to increment a non-incrementable list::const_iterator");
514 __ptr_ = __ptr_->__next_;
515 return *this;
516 }
517 _LIBCPP_INLINE_VISIBILITY
518 __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;}
519
520 _LIBCPP_INLINE_VISIBILITY
521 __list_const_iterator& operator--()
522 {
523 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__decrementable(this),
524 "Attempted to decrement a non-decrementable list::const_iterator");
525 __ptr_ = __ptr_->__prev_;
526 return *this;
527 }
528 _LIBCPP_INLINE_VISIBILITY
529 __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}
530
531 friend _LIBCPP_INLINE_VISIBILITY
532 bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y)
533 {
534 return __x.__ptr_ == __y.__ptr_;
535 }
536 friend _LIBCPP_INLINE_VISIBILITY
537 bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y)
538 {return !(__x == __y);}
539};
540
541template <class _Tp, class _Alloc>
542class __list_imp
543{
544 __list_imp(const __list_imp&);
545 __list_imp& operator=(const __list_imp&);
546public:
547 typedef _Alloc allocator_type;
548 typedef allocator_traits<allocator_type> __alloc_traits;
549 typedef typename __alloc_traits::size_type size_type;
550protected:
551 typedef _Tp value_type;
552 typedef typename __alloc_traits::void_pointer __void_pointer;
553 typedef __list_iterator<value_type, __void_pointer> iterator;
554 typedef __list_const_iterator<value_type, __void_pointer> const_iterator;
555 typedef __list_node_base<value_type, __void_pointer> __node_base;
556 typedef __list_node<value_type, __void_pointer> __node;
557 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
558 typedef allocator_traits<__node_allocator> __node_alloc_traits;
559 typedef typename __node_alloc_traits::pointer __node_pointer;
560 typedef typename __node_alloc_traits::pointer __node_const_pointer;
561 typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;
562 typedef typename __node_pointer_traits::__link_pointer __link_pointer;
563 typedef __link_pointer __link_const_pointer;
564 typedef typename __alloc_traits::pointer pointer;
565 typedef typename __alloc_traits::const_pointer const_pointer;
566 typedef typename __alloc_traits::difference_type difference_type;
567
568 typedef typename __rebind_alloc_helper<__alloc_traits, __node_base>::type __node_base_allocator;
569 typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
570 static_assert((!is_same<allocator_type, __node_allocator>::value),
571 "internal allocator type must differ from user-specified "
572 "type; otherwise overload resolution breaks");
573
574 __node_base __end_;
575 __compressed_pair<size_type, __node_allocator> __size_alloc_;
576
577 _LIBCPP_INLINE_VISIBILITY
578 __link_pointer __end_as_link() const _NOEXCEPT {
579 return __node_pointer_traits::__unsafe_link_pointer_cast(
580 const_cast<__node_base&>(__end_).__self());
581 }
582
583 _LIBCPP_INLINE_VISIBILITY
584 size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
585 _LIBCPP_INLINE_VISIBILITY
586 const size_type& __sz() const _NOEXCEPT
587 {return __size_alloc_.first();}
588 _LIBCPP_INLINE_VISIBILITY
589 __node_allocator& __node_alloc() _NOEXCEPT
590 {return __size_alloc_.second();}
591 _LIBCPP_INLINE_VISIBILITY
592 const __node_allocator& __node_alloc() const _NOEXCEPT
593 {return __size_alloc_.second();}
594
595 _LIBCPP_INLINE_VISIBILITY
596 size_type __node_alloc_max_size() const _NOEXCEPT {
597 return __node_alloc_traits::max_size(__node_alloc());
598 }
599 _LIBCPP_INLINE_VISIBILITY
600 static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;
601
602 _LIBCPP_INLINE_VISIBILITY
603 __list_imp()
604 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
605 _LIBCPP_INLINE_VISIBILITY
606 __list_imp(const allocator_type& __a);
607 _LIBCPP_INLINE_VISIBILITY
608 __list_imp(const __node_allocator& __a);
609#ifndef _LIBCPP_CXX03_LANG
610 __list_imp(__node_allocator&& __a) _NOEXCEPT;
611#endif
612 ~__list_imp();
613 void clear() _NOEXCEPT;
614 _LIBCPP_INLINE_VISIBILITY
615 bool empty() const _NOEXCEPT {return __sz() == 0;}
616
617 _LIBCPP_INLINE_VISIBILITY
618 iterator begin() _NOEXCEPT
619 {
620 return iterator(__end_.__next_, this);
621 }
622 _LIBCPP_INLINE_VISIBILITY
623 const_iterator begin() const _NOEXCEPT
624 {
625 return const_iterator(__end_.__next_, this);
626 }
627 _LIBCPP_INLINE_VISIBILITY
628 iterator end() _NOEXCEPT
629 {
630 return iterator(__end_as_link(), this);
631 }
632 _LIBCPP_INLINE_VISIBILITY
633 const_iterator end() const _NOEXCEPT
634 {
635 return const_iterator(__end_as_link(), this);
636 }
637
638 void swap(__list_imp& __c)
639#if _LIBCPP_STD_VER >= 14
640 _NOEXCEPT;
641#else
642 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
643 __is_nothrow_swappable<allocator_type>::value);
644#endif
645
646 _LIBCPP_INLINE_VISIBILITY
647 void __copy_assign_alloc(const __list_imp& __c)
648 {__copy_assign_alloc(__c, integral_constant<bool,
649 __node_alloc_traits::propagate_on_container_copy_assignment::value>());}
650
651 _LIBCPP_INLINE_VISIBILITY
652 void __move_assign_alloc(__list_imp& __c)
653 _NOEXCEPT_(
654 !__node_alloc_traits::propagate_on_container_move_assignment::value ||
655 is_nothrow_move_assignable<__node_allocator>::value)
656 {__move_assign_alloc(__c, integral_constant<bool,
657 __node_alloc_traits::propagate_on_container_move_assignment::value>());}
658
659private:
660 _LIBCPP_INLINE_VISIBILITY
661 void __copy_assign_alloc(const __list_imp& __c, true_type)
662 {
663 if (__node_alloc() != __c.__node_alloc())
664 clear();
665 __node_alloc() = __c.__node_alloc();
666 }
667
668 _LIBCPP_INLINE_VISIBILITY
669 void __copy_assign_alloc(const __list_imp&, false_type)
670 {}
671
672 _LIBCPP_INLINE_VISIBILITY
673 void __move_assign_alloc(__list_imp& __c, true_type)
674 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
675 {
676 __node_alloc() = _VSTD::move(__c.__node_alloc());
677 }
678
679 _LIBCPP_INLINE_VISIBILITY
680 void __move_assign_alloc(__list_imp&, false_type)
681 _NOEXCEPT
682 {}
683};
684
685// Unlink nodes [__f, __l]
686template <class _Tp, class _Alloc>
687inline
688void
689__list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l)
690 _NOEXCEPT
691{
692 __f->__prev_->__next_ = __l->__next_;
693 __l->__next_->__prev_ = __f->__prev_;
694}
695
696template <class _Tp, class _Alloc>
697inline
698__list_imp<_Tp, _Alloc>::__list_imp()
699 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
700 : __size_alloc_(0, __default_init_tag())
701{
702}
703
704template <class _Tp, class _Alloc>
705inline
706__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a)
707 : __size_alloc_(0, __node_allocator(__a))
708{
709}
710
711template <class _Tp, class _Alloc>
712inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a)
713 : __size_alloc_(0, __a) {}
714
715#ifndef _LIBCPP_CXX03_LANG
716template <class _Tp, class _Alloc>
717inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT
718 : __size_alloc_(0, _VSTD::move(__a)) {}
719#endif
720
721template <class _Tp, class _Alloc>
722__list_imp<_Tp, _Alloc>::~__list_imp() {
723 clear();
724 std::__debug_db_erase_c(this);
725}
726
727template <class _Tp, class _Alloc>
728void
729__list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
730{
731 if (!empty())
732 {
733 __node_allocator& __na = __node_alloc();
734 __link_pointer __f = __end_.__next_;
735 __link_pointer __l = __end_as_link();
736 __unlink_nodes(__f, l: __l->__prev_);
737 __sz() = 0;
738 while (__f != __l)
739 {
740 __node_pointer __np = __f->__as_node();
741 __f = __f->__next_;
742 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
743 __node_alloc_traits::deallocate(__na, __np, 1);
744 }
745 std::__debug_db_invalidate_all(this);
746 }
747}
748
749template <class _Tp, class _Alloc>
750void
751__list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
752#if _LIBCPP_STD_VER >= 14
753 _NOEXCEPT
754#else
755 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
756 __is_nothrow_swappable<allocator_type>::value)
757#endif
758{
759 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
760 this->__node_alloc() == __c.__node_alloc(),
761 "list::swap: Either propagate_on_container_swap must be true"
762 " or the allocators must compare equal");
763 using _VSTD::swap;
764 _VSTD::__swap_allocator(__node_alloc(), __c.__node_alloc());
765 swap(__sz(), __c.__sz());
766 swap(__end_, __c.__end_);
767 if (__sz() == 0)
768 __end_.__next_ = __end_.__prev_ = __end_as_link();
769 else
770 __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
771 if (__c.__sz() == 0)
772 __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();
773 else
774 __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();
775
776#ifdef _LIBCPP_ENABLE_DEBUG_MODE
777 __libcpp_db* __db = __get_db();
778 __c_node* __cn1 = __db->__find_c_and_lock(this);
779 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c));
780 _VSTD::swap(__cn1->beg_, __cn2->beg_);
781 _VSTD::swap(__cn1->end_, __cn2->end_);
782 _VSTD::swap(__cn1->cap_, __cn2->cap_);
783 for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;)
784 {
785 --__p;
786 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
787 if (__i->__ptr_ == __c.__end_as_link())
788 {
789 __cn2->__add(*__p);
790 if (--__cn1->end_ != __p)
791 _VSTD::memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*));
792 }
793 else
794 (*__p)->__c_ = __cn1;
795 }
796 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
797 {
798 --__p;
799 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
800 if (__i->__ptr_ == __end_as_link())
801 {
802 __cn1->__add(*__p);
803 if (--__cn2->end_ != __p)
804 _VSTD::memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
805 }
806 else
807 (*__p)->__c_ = __cn2;
808 }
809 __db->unlock();
810#endif
811}
812
813template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
814class _LIBCPP_TEMPLATE_VIS list
815 : private __list_imp<_Tp, _Alloc>
816{
817 typedef __list_imp<_Tp, _Alloc> base;
818 typedef typename base::__node __node;
819 typedef typename base::__node_allocator __node_allocator;
820 typedef typename base::__node_pointer __node_pointer;
821 typedef typename base::__node_alloc_traits __node_alloc_traits;
822 typedef typename base::__node_base __node_base;
823 typedef typename base::__node_base_pointer __node_base_pointer;
824 typedef typename base::__link_pointer __link_pointer;
825
826public:
827 typedef _Tp value_type;
828 typedef _Alloc allocator_type;
829 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
830 "Invalid allocator::value_type");
831 typedef value_type& reference;
832 typedef const value_type& const_reference;
833 typedef typename base::pointer pointer;
834 typedef typename base::const_pointer const_pointer;
835 typedef typename base::size_type size_type;
836 typedef typename base::difference_type difference_type;
837 typedef typename base::iterator iterator;
838 typedef typename base::const_iterator const_iterator;
839 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
840 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
841#if _LIBCPP_STD_VER > 17
842 typedef size_type __remove_return_type;
843#else
844 typedef void __remove_return_type;
845#endif
846
847 _LIBCPP_INLINE_VISIBILITY
848 list()
849 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
850 {
851 _VSTD::__debug_db_insert_c(this);
852 }
853 _LIBCPP_INLINE_VISIBILITY
854 explicit list(const allocator_type& __a) : base(__a)
855 {
856 _VSTD::__debug_db_insert_c(this);
857 }
858 explicit list(size_type __n);
859#if _LIBCPP_STD_VER > 11
860 explicit list(size_type __n, const allocator_type& __a);
861#endif
862 list(size_type __n, const value_type& __x);
863 template <class = __enable_if_t<__is_allocator<_Alloc>::value> >
864 list(size_type __n, const value_type& __x, const allocator_type& __a) : base(__a)
865 {
866 _VSTD::__debug_db_insert_c(this);
867 for (; __n > 0; --__n)
868 push_back(__x);
869 }
870
871 template <class _InpIter>
872 list(_InpIter __f, _InpIter __l,
873 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0);
874 template <class _InpIter>
875 list(_InpIter __f, _InpIter __l, const allocator_type& __a,
876 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0);
877
878 list(const list& __c);
879 list(const list& __c, const __type_identity_t<allocator_type>& __a);
880 _LIBCPP_INLINE_VISIBILITY
881 list& operator=(const list& __c);
882#ifndef _LIBCPP_CXX03_LANG
883 list(initializer_list<value_type> __il);
884 list(initializer_list<value_type> __il, const allocator_type& __a);
885
886 _LIBCPP_INLINE_VISIBILITY
887 list(list&& __c)
888 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
889 _LIBCPP_INLINE_VISIBILITY
890 list(list&& __c, const __type_identity_t<allocator_type>& __a);
891 _LIBCPP_INLINE_VISIBILITY
892 list& operator=(list&& __c)
893 _NOEXCEPT_(
894 __node_alloc_traits::propagate_on_container_move_assignment::value &&
895 is_nothrow_move_assignable<__node_allocator>::value);
896
897 _LIBCPP_INLINE_VISIBILITY
898 list& operator=(initializer_list<value_type> __il)
899 {assign(__il.begin(), __il.end()); return *this;}
900
901 _LIBCPP_INLINE_VISIBILITY
902 void assign(initializer_list<value_type> __il)
903 {assign(__il.begin(), __il.end());}
904#endif // _LIBCPP_CXX03_LANG
905
906 template <class _InpIter>
907 void assign(_InpIter __f, _InpIter __l,
908 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0);
909 void assign(size_type __n, const value_type& __x);
910
911 _LIBCPP_INLINE_VISIBILITY
912 allocator_type get_allocator() const _NOEXCEPT;
913
914 _LIBCPP_INLINE_VISIBILITY
915 size_type size() const _NOEXCEPT {return base::__sz();}
916 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
917 bool empty() const _NOEXCEPT {return base::empty();}
918 _LIBCPP_INLINE_VISIBILITY
919 size_type max_size() const _NOEXCEPT
920 {
921 return _VSTD::min<size_type>(
922 base::__node_alloc_max_size(),
923 numeric_limits<difference_type >::max());
924 }
925
926 _LIBCPP_INLINE_VISIBILITY
927 iterator begin() _NOEXCEPT {return base::begin();}
928 _LIBCPP_INLINE_VISIBILITY
929 const_iterator begin() const _NOEXCEPT {return base::begin();}
930 _LIBCPP_INLINE_VISIBILITY
931 iterator end() _NOEXCEPT {return base::end();}
932 _LIBCPP_INLINE_VISIBILITY
933 const_iterator end() const _NOEXCEPT {return base::end();}
934 _LIBCPP_INLINE_VISIBILITY
935 const_iterator cbegin() const _NOEXCEPT {return base::begin();}
936 _LIBCPP_INLINE_VISIBILITY
937 const_iterator cend() const _NOEXCEPT {return base::end();}
938
939 _LIBCPP_INLINE_VISIBILITY
940 reverse_iterator rbegin() _NOEXCEPT
941 {return reverse_iterator(end());}
942 _LIBCPP_INLINE_VISIBILITY
943 const_reverse_iterator rbegin() const _NOEXCEPT
944 {return const_reverse_iterator(end());}
945 _LIBCPP_INLINE_VISIBILITY
946 reverse_iterator rend() _NOEXCEPT
947 {return reverse_iterator(begin());}
948 _LIBCPP_INLINE_VISIBILITY
949 const_reverse_iterator rend() const _NOEXCEPT
950 {return const_reverse_iterator(begin());}
951 _LIBCPP_INLINE_VISIBILITY
952 const_reverse_iterator crbegin() const _NOEXCEPT
953 {return const_reverse_iterator(end());}
954 _LIBCPP_INLINE_VISIBILITY
955 const_reverse_iterator crend() const _NOEXCEPT
956 {return const_reverse_iterator(begin());}
957
958 _LIBCPP_INLINE_VISIBILITY
959 reference front()
960 {
961 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
962 return base::__end_.__next_->__as_node()->__value_;
963 }
964 _LIBCPP_INLINE_VISIBILITY
965 const_reference front() const
966 {
967 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
968 return base::__end_.__next_->__as_node()->__value_;
969 }
970 _LIBCPP_INLINE_VISIBILITY
971 reference back()
972 {
973 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
974 return base::__end_.__prev_->__as_node()->__value_;
975 }
976 _LIBCPP_INLINE_VISIBILITY
977 const_reference back() const
978 {
979 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
980 return base::__end_.__prev_->__as_node()->__value_;
981 }
982
983#ifndef _LIBCPP_CXX03_LANG
984 void push_front(value_type&& __x);
985 void push_back(value_type&& __x);
986
987 template <class... _Args>
988#if _LIBCPP_STD_VER > 14
989 reference emplace_front(_Args&&... __args);
990#else
991 void emplace_front(_Args&&... __args);
992#endif
993 template <class... _Args>
994#if _LIBCPP_STD_VER > 14
995 reference emplace_back(_Args&&... __args);
996#else
997 void emplace_back(_Args&&... __args);
998#endif
999 template <class... _Args>
1000 iterator emplace(const_iterator __p, _Args&&... __args);
1001
1002 iterator insert(const_iterator __p, value_type&& __x);
1003
1004 _LIBCPP_INLINE_VISIBILITY
1005 iterator insert(const_iterator __p, initializer_list<value_type> __il)
1006 {return insert(__p, __il.begin(), __il.end());}
1007#endif // _LIBCPP_CXX03_LANG
1008
1009 void push_front(const value_type& __x);
1010 void push_back(const value_type& __x);
1011
1012#ifndef _LIBCPP_CXX03_LANG
1013 template <class _Arg>
1014 _LIBCPP_INLINE_VISIBILITY
1015 void __emplace_back(_Arg&& __arg) { emplace_back(_VSTD::forward<_Arg>(__arg)); }
1016#else
1017 _LIBCPP_INLINE_VISIBILITY
1018 void __emplace_back(value_type const& __arg) { push_back(__arg); }
1019#endif
1020
1021 iterator insert(const_iterator __p, const value_type& __x);
1022 iterator insert(const_iterator __p, size_type __n, const value_type& __x);
1023 template <class _InpIter>
1024 iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
1025 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0);
1026
1027 _LIBCPP_INLINE_VISIBILITY
1028 void swap(list& __c)
1029#if _LIBCPP_STD_VER >= 14
1030 _NOEXCEPT
1031#else
1032 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
1033 __is_nothrow_swappable<__node_allocator>::value)
1034#endif
1035 {base::swap(__c);}
1036 _LIBCPP_INLINE_VISIBILITY
1037 void clear() _NOEXCEPT {base::clear();}
1038
1039 void pop_front();
1040 void pop_back();
1041
1042 iterator erase(const_iterator __p);
1043 iterator erase(const_iterator __f, const_iterator __l);
1044
1045 void resize(size_type __n);
1046 void resize(size_type __n, const value_type& __x);
1047
1048 void splice(const_iterator __p, list& __c);
1049#ifndef _LIBCPP_CXX03_LANG
1050 _LIBCPP_INLINE_VISIBILITY
1051 void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
1052 _LIBCPP_INLINE_VISIBILITY
1053 void splice(const_iterator __p, list&& __c, const_iterator __i)
1054 {splice(__p, __c, __i);}
1055 _LIBCPP_INLINE_VISIBILITY
1056 void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
1057 {splice(__p, __c, __f, __l);}
1058#endif
1059 void splice(const_iterator __p, list& __c, const_iterator __i);
1060 void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
1061
1062 __remove_return_type remove(const value_type& __x);
1063 template <class _Pred> __remove_return_type remove_if(_Pred __pred);
1064 _LIBCPP_INLINE_VISIBILITY
1065 __remove_return_type unique() { return unique(__equal_to<value_type>()); }
1066 template <class _BinaryPred>
1067 __remove_return_type unique(_BinaryPred __binary_pred);
1068 _LIBCPP_INLINE_VISIBILITY
1069 void merge(list& __c);
1070#ifndef _LIBCPP_CXX03_LANG
1071 _LIBCPP_INLINE_VISIBILITY
1072 void merge(list&& __c) {merge(__c);}
1073
1074 template <class _Comp>
1075 _LIBCPP_INLINE_VISIBILITY
1076 void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
1077#endif
1078 template <class _Comp>
1079 void merge(list& __c, _Comp __comp);
1080
1081 _LIBCPP_INLINE_VISIBILITY
1082 void sort();
1083 template <class _Comp>
1084 _LIBCPP_INLINE_VISIBILITY
1085 void sort(_Comp __comp);
1086
1087 void reverse() _NOEXCEPT;
1088
1089 bool __invariants() const;
1090
1091 typedef __allocator_destructor<__node_allocator> __node_destructor;
1092 typedef unique_ptr<__node, __node_destructor> __hold_pointer;
1093
1094 _LIBCPP_INLINE_VISIBILITY
1095 __hold_pointer __allocate_node(__node_allocator& __na) {
1096 __node_pointer __p = __node_alloc_traits::allocate(__na, 1);
1097 __p->__prev_ = nullptr;
1098 return __hold_pointer(__p, __node_destructor(__na, 1));
1099 }
1100
1101#ifdef _LIBCPP_ENABLE_DEBUG_MODE
1102
1103 bool __dereferenceable(const const_iterator* __i) const;
1104 bool __decrementable(const const_iterator* __i) const;
1105 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1106 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1107
1108#endif // _LIBCPP_ENABLE_DEBUG_MODE
1109
1110private:
1111 _LIBCPP_INLINE_VISIBILITY
1112 static void __link_nodes (__link_pointer __p, __link_pointer __f, __link_pointer __l);
1113 _LIBCPP_INLINE_VISIBILITY
1114 void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);
1115 _LIBCPP_INLINE_VISIBILITY
1116 void __link_nodes_at_back (__link_pointer __f, __link_pointer __l);
1117 iterator __iterator(size_type __n);
1118 template <class _Comp>
1119 static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
1120
1121 void __move_assign(list& __c, true_type)
1122 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
1123 void __move_assign(list& __c, false_type);
1124};
1125
1126#if _LIBCPP_STD_VER >= 17
1127template<class _InputIterator,
1128 class _Alloc = allocator<__iter_value_type<_InputIterator>>,
1129 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
1130 class = enable_if_t<__is_allocator<_Alloc>::value>
1131 >
1132list(_InputIterator, _InputIterator)
1133 -> list<__iter_value_type<_InputIterator>, _Alloc>;
1134
1135template<class _InputIterator,
1136 class _Alloc,
1137 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
1138 class = enable_if_t<__is_allocator<_Alloc>::value>
1139 >
1140list(_InputIterator, _InputIterator, _Alloc)
1141 -> list<__iter_value_type<_InputIterator>, _Alloc>;
1142#endif
1143
1144// Link in nodes [__f, __l] just prior to __p
1145template <class _Tp, class _Alloc>
1146inline
1147void
1148list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l)
1149{
1150 __p->__prev_->__next_ = __f;
1151 __f->__prev_ = __p->__prev_;
1152 __p->__prev_ = __l;
1153 __l->__next_ = __p;
1154}
1155
1156// Link in nodes [__f, __l] at the front of the list
1157template <class _Tp, class _Alloc>
1158inline
1159void
1160list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l)
1161{
1162 __f->__prev_ = base::__end_as_link();
1163 __l->__next_ = base::__end_.__next_;
1164 __l->__next_->__prev_ = __l;
1165 base::__end_.__next_ = __f;
1166}
1167
1168// Link in nodes [__f, __l] at the back of the list
1169template <class _Tp, class _Alloc>
1170inline
1171void
1172list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l)
1173{
1174 __l->__next_ = base::__end_as_link();
1175 __f->__prev_ = base::__end_.__prev_;
1176 __f->__prev_->__next_ = __f;
1177 base::__end_.__prev_ = __l;
1178}
1179
1180
1181template <class _Tp, class _Alloc>
1182inline
1183typename list<_Tp, _Alloc>::iterator
1184list<_Tp, _Alloc>::__iterator(size_type __n)
1185{
1186 return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n)
1187 : _VSTD::prev(end(), base::__sz() - __n);
1188}
1189
1190template <class _Tp, class _Alloc>
1191list<_Tp, _Alloc>::list(size_type __n)
1192{
1193 _VSTD::__debug_db_insert_c(this);
1194 for (; __n > 0; --__n)
1195#ifndef _LIBCPP_CXX03_LANG
1196 emplace_back();
1197#else
1198 push_back(value_type());
1199#endif
1200}
1201
1202#if _LIBCPP_STD_VER > 11
1203template <class _Tp, class _Alloc>
1204list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a)
1205{
1206 _VSTD::__debug_db_insert_c(this);
1207 for (; __n > 0; --__n)
1208 emplace_back();
1209}
1210#endif
1211
1212template <class _Tp, class _Alloc>
1213list<_Tp, _Alloc>::list(size_type __n, const value_type& __x)
1214{
1215 _VSTD::__debug_db_insert_c(this);
1216 for (; __n > 0; --__n)
1217 push_back(__x);
1218}
1219
1220template <class _Tp, class _Alloc>
1221template <class _InpIter>
1222list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
1223 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>*)
1224{
1225 _VSTD::__debug_db_insert_c(this);
1226 for (; __f != __l; ++__f)
1227 __emplace_back(*__f);
1228}
1229
1230template <class _Tp, class _Alloc>
1231template <class _InpIter>
1232list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
1233 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>*)
1234 : base(__a)
1235{
1236 _VSTD::__debug_db_insert_c(this);
1237 for (; __f != __l; ++__f)
1238 __emplace_back(*__f);
1239}
1240
1241template <class _Tp, class _Alloc>
1242list<_Tp, _Alloc>::list(const list& __c)
1243 : base(__node_alloc_traits::select_on_container_copy_construction(
1244 __c.__node_alloc())) {
1245 _VSTD::__debug_db_insert_c(this);
1246 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1247 push_back(*__i);
1248}
1249
1250template <class _Tp, class _Alloc>
1251list<_Tp, _Alloc>::list(const list& __c, const __type_identity_t<allocator_type>& __a)
1252 : base(__a)
1253{
1254 _VSTD::__debug_db_insert_c(this);
1255 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1256 push_back(*__i);
1257}
1258
1259#ifndef _LIBCPP_CXX03_LANG
1260
1261template <class _Tp, class _Alloc>
1262list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a)
1263 : base(__a)
1264{
1265 _VSTD::__debug_db_insert_c(this);
1266 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1267 __e = __il.end(); __i != __e; ++__i)
1268 push_back(*__i);
1269}
1270
1271template <class _Tp, class _Alloc>
1272list<_Tp, _Alloc>::list(initializer_list<value_type> __il)
1273{
1274 _VSTD::__debug_db_insert_c(this);
1275 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1276 __e = __il.end(); __i != __e; ++__i)
1277 push_back(*__i);
1278}
1279
1280template <class _Tp, class _Alloc>
1281inline list<_Tp, _Alloc>::list(list&& __c)
1282 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
1283 : base(_VSTD::move(__c.__node_alloc())) {
1284 _VSTD::__debug_db_insert_c(this);
1285 splice(end(), __c);
1286}
1287
1288template <class _Tp, class _Alloc>
1289inline
1290list<_Tp, _Alloc>::list(list&& __c, const __type_identity_t<allocator_type>& __a)
1291 : base(__a)
1292{
1293 _VSTD::__debug_db_insert_c(this);
1294 if (__a == __c.get_allocator())
1295 splice(end(), __c);
1296 else
1297 {
1298 typedef move_iterator<iterator> _Ip;
1299 assign(_Ip(__c.begin()), _Ip(__c.end()));
1300 }
1301}
1302
1303template <class _Tp, class _Alloc>
1304inline
1305list<_Tp, _Alloc>&
1306list<_Tp, _Alloc>::operator=(list&& __c)
1307 _NOEXCEPT_(
1308 __node_alloc_traits::propagate_on_container_move_assignment::value &&
1309 is_nothrow_move_assignable<__node_allocator>::value)
1310{
1311 __move_assign(__c, integral_constant<bool,
1312 __node_alloc_traits::propagate_on_container_move_assignment::value>());
1313 return *this;
1314}
1315
1316template <class _Tp, class _Alloc>
1317void
1318list<_Tp, _Alloc>::__move_assign(list& __c, false_type)
1319{
1320 if (base::__node_alloc() != __c.__node_alloc())
1321 {
1322 typedef move_iterator<iterator> _Ip;
1323 assign(_Ip(__c.begin()), _Ip(__c.end()));
1324 }
1325 else
1326 __move_assign(__c, true_type());
1327}
1328
1329template <class _Tp, class _Alloc>
1330void
1331list<_Tp, _Alloc>::__move_assign(list& __c, true_type)
1332 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1333{
1334 clear();
1335 base::__move_assign_alloc(__c);
1336 splice(end(), __c);
1337}
1338
1339#endif // _LIBCPP_CXX03_LANG
1340
1341template <class _Tp, class _Alloc>
1342inline
1343list<_Tp, _Alloc>&
1344list<_Tp, _Alloc>::operator=(const list& __c)
1345{
1346 if (this != _VSTD::addressof(__c))
1347 {
1348 base::__copy_assign_alloc(__c);
1349 assign(__c.begin(), __c.end());
1350 }
1351 return *this;
1352}
1353
1354template <class _Tp, class _Alloc>
1355template <class _InpIter>
1356void
1357list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l,
1358 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>*)
1359{
1360 iterator __i = begin();
1361 iterator __e = end();
1362 for (; __f != __l && __i != __e; ++__f, (void) ++__i)
1363 *__i = *__f;
1364 if (__i == __e)
1365 insert(__e, __f, __l);
1366 else
1367 erase(__i, __e);
1368 std::__debug_db_invalidate_all(this);
1369}
1370
1371template <class _Tp, class _Alloc>
1372void
1373list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x)
1374{
1375 iterator __i = begin();
1376 iterator __e = end();
1377 for (; __n > 0 && __i != __e; --__n, (void) ++__i)
1378 *__i = __x;
1379 if (__i == __e)
1380 insert(__e, __n, __x);
1381 else
1382 erase(__i, __e);
1383 std::__debug_db_invalidate_all(this);
1384}
1385
1386template <class _Tp, class _Alloc>
1387inline
1388_Alloc
1389list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT
1390{
1391 return allocator_type(base::__node_alloc());
1392}
1393
1394template <class _Tp, class _Alloc>
1395typename list<_Tp, _Alloc>::iterator
1396list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
1397{
1398 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1399 "list::insert(iterator, x) called with an iterator not referring to this list");
1400 __node_allocator& __na = base::__node_alloc();
1401 __hold_pointer __hold = __allocate_node(__na);
1402 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1403 __link_nodes(p: __p.__ptr_, f: __hold->__as_link(), l: __hold->__as_link());
1404 ++base::__sz();
1405 return iterator(__hold.release()->__as_link(), this);
1406}
1407
1408template <class _Tp, class _Alloc>
1409typename list<_Tp, _Alloc>::iterator
1410list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
1411{
1412 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1413 "list::insert(iterator, n, x) called with an iterator not referring to this list");
1414 iterator __r(__p.__ptr_, this);
1415 if (__n > 0)
1416 {
1417 size_type __ds = 0;
1418 __node_allocator& __na = base::__node_alloc();
1419 __hold_pointer __hold = __allocate_node(__na);
1420 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1421 ++__ds;
1422 __r = iterator(__hold->__as_link(), this);
1423 __hold.release();
1424 iterator __e = __r;
1425#ifndef _LIBCPP_NO_EXCEPTIONS
1426 try
1427 {
1428#endif // _LIBCPP_NO_EXCEPTIONS
1429 for (--__n; __n != 0; --__n, (void) ++__e, ++__ds)
1430 {
1431 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1432 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1433 __e.__ptr_->__next_ = __hold->__as_link();
1434 __hold->__prev_ = __e.__ptr_;
1435 __hold.release();
1436 }
1437#ifndef _LIBCPP_NO_EXCEPTIONS
1438 }
1439 catch (...)
1440 {
1441 while (true)
1442 {
1443 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1444 __link_pointer __prev = __e.__ptr_->__prev_;
1445 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1446 if (__prev == 0)
1447 break;
1448 __e = iterator(__prev, this);
1449 }
1450 throw;
1451 }
1452#endif // _LIBCPP_NO_EXCEPTIONS
1453 __link_nodes(p: __p.__ptr_, f: __r.__ptr_, l: __e.__ptr_);
1454 base::__sz() += __ds;
1455 }
1456 return __r;
1457}
1458
1459template <class _Tp, class _Alloc>
1460template <class _InpIter>
1461typename list<_Tp, _Alloc>::iterator
1462list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
1463 __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>*)
1464{
1465 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1466 "list::insert(iterator, range) called with an iterator not referring to this list");
1467 iterator __r(__p.__ptr_, this);
1468 if (__f != __l)
1469 {
1470 size_type __ds = 0;
1471 __node_allocator& __na = base::__node_alloc();
1472 __hold_pointer __hold = __allocate_node(__na);
1473 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1474 ++__ds;
1475 __r = iterator(__hold.get()->__as_link(), this);
1476 __hold.release();
1477 iterator __e = __r;
1478#ifndef _LIBCPP_NO_EXCEPTIONS
1479 try
1480 {
1481#endif // _LIBCPP_NO_EXCEPTIONS
1482 for (++__f; __f != __l; ++__f, (void) ++__e, ++__ds)
1483 {
1484 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1485 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1486 __e.__ptr_->__next_ = __hold.get()->__as_link();
1487 __hold->__prev_ = __e.__ptr_;
1488 __hold.release();
1489 }
1490#ifndef _LIBCPP_NO_EXCEPTIONS
1491 }
1492 catch (...)
1493 {
1494 while (true)
1495 {
1496 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1497 __link_pointer __prev = __e.__ptr_->__prev_;
1498 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1499 if (__prev == 0)
1500 break;
1501 __e = iterator(__prev, this);
1502 }
1503 throw;
1504 }
1505#endif // _LIBCPP_NO_EXCEPTIONS
1506 __link_nodes(p: __p.__ptr_, f: __r.__ptr_, l: __e.__ptr_);
1507 base::__sz() += __ds;
1508 }
1509 return __r;
1510}
1511
1512template <class _Tp, class _Alloc>
1513void
1514list<_Tp, _Alloc>::push_front(const value_type& __x)
1515{
1516 __node_allocator& __na = base::__node_alloc();
1517 __hold_pointer __hold = __allocate_node(__na);
1518 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1519 __link_pointer __nl = __hold->__as_link();
1520 __link_nodes_at_front(f: __nl, l: __nl);
1521 ++base::__sz();
1522 __hold.release();
1523}
1524
1525template <class _Tp, class _Alloc>
1526void
1527list<_Tp, _Alloc>::push_back(const value_type& __x)
1528{
1529 __node_allocator& __na = base::__node_alloc();
1530 __hold_pointer __hold = __allocate_node(__na);
1531 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1532 __link_nodes_at_back(f: __hold.get()->__as_link(), l: __hold.get()->__as_link());
1533 ++base::__sz();
1534 __hold.release();
1535}
1536
1537#ifndef _LIBCPP_CXX03_LANG
1538
1539template <class _Tp, class _Alloc>
1540void
1541list<_Tp, _Alloc>::push_front(value_type&& __x)
1542{
1543 __node_allocator& __na = base::__node_alloc();
1544 __hold_pointer __hold = __allocate_node(__na);
1545 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1546 __link_nodes_at_front(f: __hold.get()->__as_link(), l: __hold.get()->__as_link());
1547 ++base::__sz();
1548 __hold.release();
1549}
1550
1551template <class _Tp, class _Alloc>
1552void
1553list<_Tp, _Alloc>::push_back(value_type&& __x)
1554{
1555 __node_allocator& __na = base::__node_alloc();
1556 __hold_pointer __hold = __allocate_node(__na);
1557 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1558 __link_nodes_at_back(f: __hold.get()->__as_link(), l: __hold.get()->__as_link());
1559 ++base::__sz();
1560 __hold.release();
1561}
1562
1563template <class _Tp, class _Alloc>
1564template <class... _Args>
1565#if _LIBCPP_STD_VER > 14
1566typename list<_Tp, _Alloc>::reference
1567#else
1568void
1569#endif
1570list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1571{
1572 __node_allocator& __na = base::__node_alloc();
1573 __hold_pointer __hold = __allocate_node(__na);
1574 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1575 __link_nodes_at_front(f: __hold.get()->__as_link(), l: __hold.get()->__as_link());
1576 ++base::__sz();
1577#if _LIBCPP_STD_VER > 14
1578 return __hold.release()->__value_;
1579#else
1580 __hold.release();
1581#endif
1582}
1583
1584template <class _Tp, class _Alloc>
1585template <class... _Args>
1586#if _LIBCPP_STD_VER > 14
1587typename list<_Tp, _Alloc>::reference
1588#else
1589void
1590#endif
1591list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1592{
1593 __node_allocator& __na = base::__node_alloc();
1594 __hold_pointer __hold = __allocate_node(__na);
1595 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1596 __link_pointer __nl = __hold->__as_link();
1597 __link_nodes_at_back(f: __nl, l: __nl);
1598 ++base::__sz();
1599#if _LIBCPP_STD_VER > 14
1600 return __hold.release()->__value_;
1601#else
1602 __hold.release();
1603#endif
1604}
1605
1606template <class _Tp, class _Alloc>
1607template <class... _Args>
1608typename list<_Tp, _Alloc>::iterator
1609list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1610{
1611 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1612 "list::emplace(iterator, args...) called with an iterator not referring to this list");
1613 __node_allocator& __na = base::__node_alloc();
1614 __hold_pointer __hold = __allocate_node(__na);
1615 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1616 __link_pointer __nl = __hold.get()->__as_link();
1617 __link_nodes(p: __p.__ptr_, f: __nl, l: __nl);
1618 ++base::__sz();
1619 __hold.release();
1620 return iterator(__nl, this);
1621}
1622
1623template <class _Tp, class _Alloc>
1624typename list<_Tp, _Alloc>::iterator
1625list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1626{
1627 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1628 "list::insert(iterator, x) called with an iterator not referring to this list");
1629 __node_allocator& __na = base::__node_alloc();
1630 __hold_pointer __hold = __allocate_node(__na);
1631 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1632 __link_pointer __nl = __hold->__as_link();
1633 __link_nodes(p: __p.__ptr_, f: __nl, l: __nl);
1634 ++base::__sz();
1635 __hold.release();
1636 return iterator(__nl, this);
1637}
1638
1639#endif // _LIBCPP_CXX03_LANG
1640
1641template <class _Tp, class _Alloc>
1642void
1643list<_Tp, _Alloc>::pop_front()
1644{
1645 _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
1646 __node_allocator& __na = base::__node_alloc();
1647 __link_pointer __n = base::__end_.__next_;
1648 base::__unlink_nodes(__n, __n);
1649 --base::__sz();
1650#ifdef _LIBCPP_ENABLE_DEBUG_MODE
1651 __c_node* __c = __get_db()->__find_c_and_lock(this);
1652 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1653 {
1654 --__p;
1655 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1656 if (__i->__ptr_ == __n)
1657 {
1658 (*__p)->__c_ = nullptr;
1659 if (--__c->end_ != __p)
1660 _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1661 }
1662 }
1663 __get_db()->unlock();
1664#endif
1665 __node_pointer __np = __n->__as_node();
1666 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1667 __node_alloc_traits::deallocate(__na, __np, 1);
1668}
1669
1670template <class _Tp, class _Alloc>
1671void
1672list<_Tp, _Alloc>::pop_back()
1673{
1674 _LIBCPP_ASSERT(!empty(), "list::pop_back() called on an empty list");
1675 __node_allocator& __na = base::__node_alloc();
1676 __link_pointer __n = base::__end_.__prev_;
1677 base::__unlink_nodes(__n, __n);
1678 --base::__sz();
1679#ifdef _LIBCPP_ENABLE_DEBUG_MODE
1680 __c_node* __c = __get_db()->__find_c_and_lock(this);
1681 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1682 {
1683 --__p;
1684 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1685 if (__i->__ptr_ == __n)
1686 {
1687 (*__p)->__c_ = nullptr;
1688 if (--__c->end_ != __p)
1689 _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1690 }
1691 }
1692 __get_db()->unlock();
1693#endif
1694 __node_pointer __np = __n->__as_node();
1695 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1696 __node_alloc_traits::deallocate(__na, __np, 1);
1697}
1698
1699template <class _Tp, class _Alloc>
1700typename list<_Tp, _Alloc>::iterator
1701list<_Tp, _Alloc>::erase(const_iterator __p)
1702{
1703 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1704 "list::erase(iterator) called with an iterator not referring to this list");
1705 _LIBCPP_ASSERT(__p != end(),
1706 "list::erase(iterator) called with a non-dereferenceable iterator");
1707 __node_allocator& __na = base::__node_alloc();
1708 __link_pointer __n = __p.__ptr_;
1709 __link_pointer __r = __n->__next_;
1710 base::__unlink_nodes(__n, __n);
1711 --base::__sz();
1712#ifdef _LIBCPP_ENABLE_DEBUG_MODE
1713 __c_node* __c = __get_db()->__find_c_and_lock(this);
1714 for (__i_node** __ip = __c->end_; __ip != __c->beg_; )
1715 {
1716 --__ip;
1717 iterator* __i = static_cast<iterator*>((*__ip)->__i_);
1718 if (__i->__ptr_ == __n)
1719 {
1720 (*__ip)->__c_ = nullptr;
1721 if (--__c->end_ != __ip)
1722 _VSTD::memmove(__ip, __ip+1, (__c->end_ - __ip)*sizeof(__i_node*));
1723 }
1724 }
1725 __get_db()->unlock();
1726#endif
1727 __node_pointer __np = __n->__as_node();
1728 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1729 __node_alloc_traits::deallocate(__na, __np, 1);
1730 return iterator(__r, this);
1731}
1732
1733template <class _Tp, class _Alloc>
1734typename list<_Tp, _Alloc>::iterator
1735list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1736{
1737 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__f)) == this,
1738 "list::erase(iterator, iterator) called with an iterator not referring to this list");
1739 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__l)) == this,
1740 "list::erase(iterator, iterator) called with an iterator not referring to this list");
1741 if (__f != __l)
1742 {
1743 __node_allocator& __na = base::__node_alloc();
1744 base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
1745 while (__f != __l)
1746 {
1747 __link_pointer __n = __f.__ptr_;
1748 ++__f;
1749 --base::__sz();
1750#ifdef _LIBCPP_ENABLE_DEBUG_MODE
1751 __c_node* __c = __get_db()->__find_c_and_lock(this);
1752 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1753 {
1754 --__p;
1755 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1756 if (__i->__ptr_ == __n)
1757 {
1758 (*__p)->__c_ = nullptr;
1759 if (--__c->end_ != __p)
1760 _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1761 }
1762 }
1763 __get_db()->unlock();
1764#endif
1765 __node_pointer __np = __n->__as_node();
1766 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1767 __node_alloc_traits::deallocate(__na, __np, 1);
1768 }
1769 }
1770 return iterator(__l.__ptr_, this);
1771}
1772
1773template <class _Tp, class _Alloc>
1774void
1775list<_Tp, _Alloc>::resize(size_type __n)
1776{
1777 if (__n < base::__sz())
1778 erase(__iterator(__n), end());
1779 else if (__n > base::__sz())
1780 {
1781 __n -= base::__sz();
1782 size_type __ds = 0;
1783 __node_allocator& __na = base::__node_alloc();
1784 __hold_pointer __hold = __allocate_node(__na);
1785 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1786 ++__ds;
1787 iterator __r = iterator(__hold.release()->__as_link(), this);
1788 iterator __e = __r;
1789#ifndef _LIBCPP_NO_EXCEPTIONS
1790 try
1791 {
1792#endif // _LIBCPP_NO_EXCEPTIONS
1793 for (--__n; __n != 0; --__n, (void) ++__e, ++__ds)
1794 {
1795 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1796 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1797 __e.__ptr_->__next_ = __hold.get()->__as_link();
1798 __hold->__prev_ = __e.__ptr_;
1799 __hold.release();
1800 }
1801#ifndef _LIBCPP_NO_EXCEPTIONS
1802 }
1803 catch (...)
1804 {
1805 while (true)
1806 {
1807 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1808 __link_pointer __prev = __e.__ptr_->__prev_;
1809 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1810 if (__prev == 0)
1811 break;
1812 __e = iterator(__prev, this);
1813 }
1814 throw;
1815 }
1816#endif // _LIBCPP_NO_EXCEPTIONS
1817 __link_nodes_at_back(f: __r.__ptr_, l: __e.__ptr_);
1818 base::__sz() += __ds;
1819 }
1820}
1821
1822template <class _Tp, class _Alloc>
1823void
1824list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1825{
1826 if (__n < base::__sz())
1827 erase(__iterator(__n), end());
1828 else if (__n > base::__sz())
1829 {
1830 __n -= base::__sz();
1831 size_type __ds = 0;
1832 __node_allocator& __na = base::__node_alloc();
1833 __hold_pointer __hold = __allocate_node(__na);
1834 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1835 ++__ds;
1836 __link_pointer __nl = __hold.release()->__as_link();
1837 iterator __r = iterator(__nl, this);
1838 iterator __e = __r;
1839#ifndef _LIBCPP_NO_EXCEPTIONS
1840 try
1841 {
1842#endif // _LIBCPP_NO_EXCEPTIONS
1843 for (--__n; __n != 0; --__n, (void) ++__e, ++__ds)
1844 {
1845 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1846 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1847 __e.__ptr_->__next_ = __hold.get()->__as_link();
1848 __hold->__prev_ = __e.__ptr_;
1849 __hold.release();
1850 }
1851#ifndef _LIBCPP_NO_EXCEPTIONS
1852 }
1853 catch (...)
1854 {
1855 while (true)
1856 {
1857 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1858 __link_pointer __prev = __e.__ptr_->__prev_;
1859 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1860 if (__prev == 0)
1861 break;
1862 __e = iterator(__prev, this);
1863 }
1864 throw;
1865 }
1866#endif // _LIBCPP_NO_EXCEPTIONS
1867 __link_nodes(p: base::__end_as_link(), f: __r.__ptr_, l: __e.__ptr_);
1868 base::__sz() += __ds;
1869 }
1870}
1871
1872template <class _Tp, class _Alloc>
1873void
1874list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
1875{
1876 _LIBCPP_ASSERT(this != _VSTD::addressof(__c),
1877 "list::splice(iterator, list) called with this == &list");
1878 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1879 "list::splice(iterator, list) called with an iterator not referring to this list");
1880 if (!__c.empty())
1881 {
1882 __link_pointer __f = __c.__end_.__next_;
1883 __link_pointer __l = __c.__end_.__prev_;
1884 base::__unlink_nodes(__f, __l);
1885 __link_nodes(p: __p.__ptr_, __f, __l);
1886 base::__sz() += __c.__sz();
1887 __c.__sz() = 0;
1888#ifdef _LIBCPP_ENABLE_DEBUG_MODE
1889 if (_VSTD::addressof(__c) != this) {
1890 __libcpp_db* __db = __get_db();
1891 __c_node* __cn1 = __db->__find_c_and_lock(this);
1892 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c));
1893 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
1894 {
1895 --__ip;
1896 iterator* __i = static_cast<iterator*>((*__ip)->__i_);
1897 if (__i->__ptr_ != __c.__end_as_link())
1898 {
1899 __cn1->__add(*__ip);
1900 (*__ip)->__c_ = __cn1;
1901 if (--__cn2->end_ != __ip)
1902 _VSTD::memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
1903 }
1904 }
1905 __db->unlock();
1906 }
1907#endif
1908 }
1909}
1910
1911template <class _Tp, class _Alloc>
1912void
1913list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
1914{
1915 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1916 "list::splice(iterator, list, iterator) called with the first iterator not referring to this list");
1917 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__i)) == _VSTD::addressof(__c),
1918 "list::splice(iterator, list, iterator) called with the second iterator not referring to the list argument");
1919 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(_VSTD::addressof(__i)),
1920 "list::splice(iterator, list, iterator) called with the second iterator not dereferenceable");
1921
1922 if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
1923 {
1924 __link_pointer __f = __i.__ptr_;
1925 base::__unlink_nodes(__f, __f);
1926 __link_nodes(p: __p.__ptr_, __f, l: __f);
1927 --__c.__sz();
1928 ++base::__sz();
1929#ifdef _LIBCPP_ENABLE_DEBUG_MODE
1930 if (_VSTD::addressof(__c) != this) {
1931 __libcpp_db* __db = __get_db();
1932 __c_node* __cn1 = __db->__find_c_and_lock(this);
1933 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c));
1934 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
1935 {
1936 --__ip;
1937 iterator* __j = static_cast<iterator*>((*__ip)->__i_);
1938 if (__j->__ptr_ == __f)
1939 {
1940 __cn1->__add(*__ip);
1941 (*__ip)->__c_ = __cn1;
1942 if (--__cn2->end_ != __ip)
1943 _VSTD::memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
1944 }
1945 }
1946 __db->unlock();
1947 }
1948#endif
1949 }
1950}
1951
1952template <class _Iterator>
1953_LIBCPP_HIDE_FROM_ABI
1954bool __iterator_in_range(_Iterator __first, _Iterator __last, _Iterator __it) {
1955 for (_Iterator __p = __first; __p != __last; ++__p) {
1956 if (__p == __it) {
1957 return true;
1958 }
1959 }
1960 return false;
1961}
1962
1963template <class _Tp, class _Alloc>
1964void
1965list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
1966{
1967 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1968 "list::splice(iterator, list, iterator, iterator) called with first iterator not referring to this list");
1969 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__f)) == _VSTD::addressof(__c),
1970 "list::splice(iterator, list, iterator, iterator) called with second iterator not referring to the list argument");
1971 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__l)) == _VSTD::addressof(__c),
1972 "list::splice(iterator, list, iterator, iterator) called with third iterator not referring to the list argument");
1973 _LIBCPP_DEBUG_ASSERT(this != std::addressof(__c) || !std::__iterator_in_range(__f, __l, __p),
1974 "list::splice(iterator, list, iterator, iterator)"
1975 " called with the first iterator within the range of the second and third iterators");
1976
1977 if (__f != __l)
1978 {
1979 __link_pointer __first = __f.__ptr_;
1980 --__l;
1981 __link_pointer __last = __l.__ptr_;
1982 if (this != _VSTD::addressof(__c))
1983 {
1984 size_type __s = _VSTD::distance(__f, __l) + 1;
1985 __c.__sz() -= __s;
1986 base::__sz() += __s;
1987 }
1988 base::__unlink_nodes(__first, __last);
1989 __link_nodes(p: __p.__ptr_, f: __first, l: __last);
1990#ifdef _LIBCPP_ENABLE_DEBUG_MODE
1991 if (_VSTD::addressof(__c) != this) {
1992 __libcpp_db* __db = __get_db();
1993 __c_node* __cn1 = __db->__find_c_and_lock(this);
1994 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c));
1995 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
1996 {
1997 --__ip;
1998 iterator* __j = static_cast<iterator*>((*__ip)->__i_);
1999 for (__link_pointer __k = __f.__ptr_;
2000 __k != __l.__ptr_; __k = __k->__next_)
2001 {
2002 if (__j->__ptr_ == __k)
2003 {
2004 __cn1->__add(*__ip);
2005 (*__ip)->__c_ = __cn1;
2006 if (--__cn2->end_ != __ip)
2007 _VSTD::memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2008 }
2009 }
2010 }
2011 __db->unlock();
2012 }
2013#endif
2014 }
2015}
2016
2017template <class _Tp, class _Alloc>
2018typename list<_Tp, _Alloc>::__remove_return_type
2019list<_Tp, _Alloc>::remove(const value_type& __x)
2020{
2021 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
2022 for (const_iterator __i = begin(), __e = end(); __i != __e;)
2023 {
2024 if (*__i == __x)
2025 {
2026 const_iterator __j = _VSTD::next(__i);
2027 for (; __j != __e && *__j == __x; ++__j)
2028 ;
2029 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
2030 __i = __j;
2031 if (__i != __e)
2032 ++__i;
2033 }
2034 else
2035 ++__i;
2036 }
2037
2038 return (__remove_return_type) __deleted_nodes.size();
2039}
2040
2041template <class _Tp, class _Alloc>
2042template <class _Pred>
2043typename list<_Tp, _Alloc>::__remove_return_type
2044list<_Tp, _Alloc>::remove_if(_Pred __pred)
2045{
2046 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
2047 for (iterator __i = begin(), __e = end(); __i != __e;)
2048 {
2049 if (__pred(*__i))
2050 {
2051 iterator __j = _VSTD::next(__i);
2052 for (; __j != __e && __pred(*__j); ++__j)
2053 ;
2054 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
2055 __i = __j;
2056 if (__i != __e)
2057 ++__i;
2058 }
2059 else
2060 ++__i;
2061 }
2062
2063 return (__remove_return_type) __deleted_nodes.size();
2064}
2065
2066template <class _Tp, class _Alloc>
2067template <class _BinaryPred>
2068typename list<_Tp, _Alloc>::__remove_return_type
2069list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
2070{
2071 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
2072 for (iterator __i = begin(), __e = end(); __i != __e;)
2073 {
2074 iterator __j = _VSTD::next(__i);
2075 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
2076 ;
2077 if (++__i != __j) {
2078 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
2079 __i = __j;
2080 }
2081 }
2082
2083 return (__remove_return_type) __deleted_nodes.size();
2084}
2085
2086template <class _Tp, class _Alloc>
2087inline
2088void
2089list<_Tp, _Alloc>::merge(list& __c)
2090{
2091 merge(__c, __less<value_type>());
2092}
2093
2094template <class _Tp, class _Alloc>
2095template <class _Comp>
2096void
2097list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2098{
2099 if (this != _VSTD::addressof(__c))
2100 {
2101 iterator __f1 = begin();
2102 iterator __e1 = end();
2103 iterator __f2 = __c.begin();
2104 iterator __e2 = __c.end();
2105 while (__f1 != __e1 && __f2 != __e2)
2106 {
2107 if (__comp(*__f2, *__f1))
2108 {
2109 size_type __ds = 1;
2110 iterator __m2 = _VSTD::next(__f2);
2111 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, (void) ++__ds)
2112 ;
2113 base::__sz() += __ds;
2114 __c.__sz() -= __ds;
2115 __link_pointer __f = __f2.__ptr_;
2116 __link_pointer __l = __m2.__ptr_->__prev_;
2117 __f2 = __m2;
2118 base::__unlink_nodes(__f, __l);
2119 __m2 = _VSTD::next(__f1);
2120 __link_nodes(p: __f1.__ptr_, __f, __l);
2121 __f1 = __m2;
2122 }
2123 else
2124 ++__f1;
2125 }
2126 splice(__e1, __c);
2127#ifdef _LIBCPP_ENABLE_DEBUG_MODE
2128 __libcpp_db* __db = __get_db();
2129 __c_node* __cn1 = __db->__find_c_and_lock(this);
2130 __c_node* __cn2 = __db->__find_c(_VSTD::addressof(__c));
2131 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2132 {
2133 --__p;
2134 iterator* __i = static_cast<iterator*>((*__p)->__i_);
2135 if (__i->__ptr_ != __c.__end_as_link())
2136 {
2137 __cn1->__add(*__p);
2138 (*__p)->__c_ = __cn1;
2139 if (--__cn2->end_ != __p)
2140 _VSTD::memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2141 }
2142 }
2143 __db->unlock();
2144#endif
2145 }
2146}
2147
2148template <class _Tp, class _Alloc>
2149inline
2150void
2151list<_Tp, _Alloc>::sort()
2152{
2153 sort(__less<value_type>());
2154}
2155
2156template <class _Tp, class _Alloc>
2157template <class _Comp>
2158inline
2159void
2160list<_Tp, _Alloc>::sort(_Comp __comp)
2161{
2162 __sort(begin(), end(), base::__sz(), __comp);
2163}
2164
2165template <class _Tp, class _Alloc>
2166template <class _Comp>
2167typename list<_Tp, _Alloc>::iterator
2168list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
2169{
2170 switch (__n)
2171 {
2172 case 0:
2173 case 1:
2174 return __f1;
2175 case 2:
2176 if (__comp(*--__e2, *__f1))
2177 {
2178 __link_pointer __f = __e2.__ptr_;
2179 base::__unlink_nodes(__f, __f);
2180 __link_nodes(p: __f1.__ptr_, __f, l: __f);
2181 return __e2;
2182 }
2183 return __f1;
2184 }
2185 size_type __n2 = __n / 2;
2186 iterator __e1 = _VSTD::next(__f1, __n2);
2187 iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp);
2188 iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2189 if (__comp(*__f2, *__f1))
2190 {
2191 iterator __m2 = _VSTD::next(__f2);
2192 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2193 ;
2194 __link_pointer __f = __f2.__ptr_;
2195 __link_pointer __l = __m2.__ptr_->__prev_;
2196 __r = __f2;
2197 __e1 = __f2 = __m2;
2198 base::__unlink_nodes(__f, __l);
2199 __m2 = _VSTD::next(__f1);
2200 __link_nodes(p: __f1.__ptr_, __f, __l);
2201 __f1 = __m2;
2202 }
2203 else
2204 ++__f1;
2205 while (__f1 != __e1 && __f2 != __e2)
2206 {
2207 if (__comp(*__f2, *__f1))
2208 {
2209 iterator __m2 = _VSTD::next(__f2);
2210 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2211 ;
2212 __link_pointer __f = __f2.__ptr_;
2213 __link_pointer __l = __m2.__ptr_->__prev_;
2214 if (__e1 == __f2)
2215 __e1 = __m2;
2216 __f2 = __m2;
2217 base::__unlink_nodes(__f, __l);
2218 __m2 = _VSTD::next(__f1);
2219 __link_nodes(p: __f1.__ptr_, __f, __l);
2220 __f1 = __m2;
2221 }
2222 else
2223 ++__f1;
2224 }
2225 return __r;
2226}
2227
2228template <class _Tp, class _Alloc>
2229void
2230list<_Tp, _Alloc>::reverse() _NOEXCEPT
2231{
2232 if (base::__sz() > 1)
2233 {
2234 iterator __e = end();
2235 for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
2236 {
2237 _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
2238 __i.__ptr_ = __i.__ptr_->__prev_;
2239 }
2240 _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
2241 }
2242}
2243
2244template <class _Tp, class _Alloc>
2245bool
2246list<_Tp, _Alloc>::__invariants() const
2247{
2248 return size() == _VSTD::distance(begin(), end());
2249}
2250
2251#ifdef _LIBCPP_ENABLE_DEBUG_MODE
2252
2253template <class _Tp, class _Alloc>
2254bool
2255list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
2256{
2257 return __i->__ptr_ != this->__end_as_link();
2258}
2259
2260template <class _Tp, class _Alloc>
2261bool
2262list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
2263{
2264 return !empty() && __i->__ptr_ != base::__end_.__next_;
2265}
2266
2267template <class _Tp, class _Alloc>
2268bool
2269list<_Tp, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2270{
2271 return false;
2272}
2273
2274template <class _Tp, class _Alloc>
2275bool
2276list<_Tp, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2277{
2278 return false;
2279}
2280
2281#endif // _LIBCPP_ENABLE_DEBUG_MODE
2282
2283template <class _Tp, class _Alloc>
2284inline _LIBCPP_INLINE_VISIBILITY
2285bool
2286operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2287{
2288 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2289}
2290
2291template <class _Tp, class _Alloc>
2292inline _LIBCPP_INLINE_VISIBILITY
2293bool
2294operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2295{
2296 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2297}
2298
2299template <class _Tp, class _Alloc>
2300inline _LIBCPP_INLINE_VISIBILITY
2301bool
2302operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2303{
2304 return !(__x == __y);
2305}
2306
2307template <class _Tp, class _Alloc>
2308inline _LIBCPP_INLINE_VISIBILITY
2309bool
2310operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2311{
2312 return __y < __x;
2313}
2314
2315template <class _Tp, class _Alloc>
2316inline _LIBCPP_INLINE_VISIBILITY
2317bool
2318operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2319{
2320 return !(__x < __y);
2321}
2322
2323template <class _Tp, class _Alloc>
2324inline _LIBCPP_INLINE_VISIBILITY
2325bool
2326operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2327{
2328 return !(__y < __x);
2329}
2330
2331template <class _Tp, class _Alloc>
2332inline _LIBCPP_INLINE_VISIBILITY
2333void
2334swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2335 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2336{
2337 __x.swap(__y);
2338}
2339
2340#if _LIBCPP_STD_VER > 17
2341template <class _Tp, class _Allocator, class _Predicate>
2342inline _LIBCPP_INLINE_VISIBILITY typename list<_Tp, _Allocator>::size_type
2343erase_if(list<_Tp, _Allocator>& __c, _Predicate __pred) {
2344 return __c.remove_if(__pred);
2345}
2346
2347template <class _Tp, class _Allocator, class _Up>
2348inline _LIBCPP_INLINE_VISIBILITY typename list<_Tp, _Allocator>::size_type
2349erase(list<_Tp, _Allocator>& __c, const _Up& __v) {
2350 return _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
2351}
2352
2353template <>
2354inline constexpr bool __format::__enable_insertable<std::list<char>> = true;
2355#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
2356template <>
2357inline constexpr bool __format::__enable_insertable<std::list<wchar_t>> = true;
2358#endif
2359
2360#endif // _LIBCPP_STD_VER > 17
2361
2362_LIBCPP_END_NAMESPACE_STD
2363
2364_LIBCPP_POP_MACROS
2365
2366#endif // _LIBCPP_LIST
2367

source code of flutter_engine/third_party/libcxx/include/list