2 //===---------------------------- list ------------------------------------===//
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
8 //===----------------------------------------------------------------------===//
19 template <class T, class Alloc = allocator<T> >
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;
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);
46 list(Iter first, Iter last);
48 list(Iter first, Iter last, const allocator_type& a);
50 list(const list&, const allocator_type& a);
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);
59 list& operator=(const list& x);
60 list& operator=(list&& x)
62 allocator_type::propagate_on_container_move_assignment::value &&
63 is_nothrow_move_assignable<allocator_type>::value);
64 list& operator=(initializer_list<value_type>);
66 void assign(Iter first, Iter last);
67 void assign(size_type n, const value_type& t);
68 void assign(initializer_list<value_type>);
70 allocator_type get_allocator() const noexcept;
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;
86 const_reference front() const;
88 const_reference back() const;
90 bool empty() const noexcept;
91 size_type size() const noexcept;
92 size_type max_size() const noexcept;
94 template <class... Args>
95 reference emplace_front(Args&&... args); // reference in C++17
97 template <class... Args>
98 reference emplace_back(Args&&... args); // reference in C++17
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);
113 iterator erase(const_iterator position);
114 iterator erase(const_iterator position, const_iterator last);
116 void resize(size_type sz);
117 void resize(size_type sz, const value_type& c);
120 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17
121 void clear() noexcept;
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);
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
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);
145 template <class Compare>
146 void sort(Compare comp);
147 void reverse() noexcept;
151 template <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
155 template <class T, class Alloc>
156 bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
157 template <class T, class Alloc>
158 bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);
159 template <class T, class Alloc>
160 bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);
161 template <class T, class Alloc>
162 bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);
163 template <class T, class Alloc>
164 bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);
165 template <class T, class Alloc>
166 bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);
168 template <class T, class Alloc>
169 void swap(list<T,Alloc>& x, list<T,Alloc>& y)
170 noexcept(noexcept(x.swap(y)));
172 template <class T, class Allocator, class U>
173 typename list<T, Allocator>::size_type
174 erase(list<T, Allocator>& c, const U& value); // C++20
175 template <class T, class Allocator, class Predicate>
176 typename list<T, Allocator>::size_type
177 erase_if(list<T, Allocator>& c, Predicate pred); // C++20
187 #include <initializer_list>
190 #include <type_traits>
195 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
196 #pragma GCC system_header
200 #include <__undef_macros>
203 _LIBCPP_BEGIN_NAMESPACE_STD
205 template <class _Tp, class _VoidPtr> struct __list_node;
206 template <class _Tp, class _VoidPtr> struct __list_node_base;
208 template <class _Tp, class _VoidPtr>
209 struct __list_node_pointer_traits {
210 typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
212 typedef typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type
215 #if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)
216 typedef __base_pointer __link_pointer;
218 typedef typename conditional<
219 is_pointer<_VoidPtr>::value,
222 >::type __link_pointer;
225 typedef typename conditional<
226 is_same<__link_pointer, __node_pointer>::value,
229 >::type __non_link_pointer;
231 static _LIBCPP_INLINE_VISIBILITY
232 __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) {
236 static _LIBCPP_INLINE_VISIBILITY
237 __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {
238 return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));
243 template <class _Tp, class _VoidPtr>
244 struct __list_node_base
246 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
247 typedef typename _NodeTraits::__node_pointer __node_pointer;
248 typedef typename _NodeTraits::__base_pointer __base_pointer;
249 typedef typename _NodeTraits::__link_pointer __link_pointer;
251 __link_pointer __prev_;
252 __link_pointer __next_;
254 _LIBCPP_INLINE_VISIBILITY
255 __list_node_base() : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),
256 __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}
258 _LIBCPP_INLINE_VISIBILITY
259 __base_pointer __self() {
260 return pointer_traits<__base_pointer>::pointer_to(*this);
263 _LIBCPP_INLINE_VISIBILITY
264 __node_pointer __as_node() {
265 return static_cast<__node_pointer>(__self());
269 template <class _Tp, class _VoidPtr>
271 : public __list_node_base<_Tp, _VoidPtr>
275 typedef __list_node_base<_Tp, _VoidPtr> __base;
276 typedef typename __base::__link_pointer __link_pointer;
278 _LIBCPP_INLINE_VISIBILITY
279 __link_pointer __as_link() {
280 return static_cast<__link_pointer>(__base::__self());
284 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS list;
285 template <class _Tp, class _Alloc> class __list_imp;
286 template <class _Tp, class _VoidPtr> class _LIBCPP_TEMPLATE_VIS __list_const_iterator;
288 template <class _Tp, class _VoidPtr>
289 class _LIBCPP_TEMPLATE_VIS __list_iterator
291 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
292 typedef typename _NodeTraits::__link_pointer __link_pointer;
294 __link_pointer __ptr_;
296 #if _LIBCPP_DEBUG_LEVEL >= 2
297 _LIBCPP_INLINE_VISIBILITY
298 explicit __list_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
301 __get_db()->__insert_ic(this, __c);
304 _LIBCPP_INLINE_VISIBILITY
305 explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
310 template<class, class> friend class list;
311 template<class, class> friend class __list_imp;
312 template<class, class> friend class __list_const_iterator;
314 typedef bidirectional_iterator_tag iterator_category;
315 typedef _Tp value_type;
316 typedef value_type& reference;
317 typedef typename __rebind_pointer<_VoidPtr, value_type>::type pointer;
318 typedef typename pointer_traits<pointer>::difference_type difference_type;
320 _LIBCPP_INLINE_VISIBILITY
321 __list_iterator() _NOEXCEPT : __ptr_(nullptr)
323 #if _LIBCPP_DEBUG_LEVEL >= 2
324 __get_db()->__insert_i(this);
328 #if _LIBCPP_DEBUG_LEVEL >= 2
330 _LIBCPP_INLINE_VISIBILITY
331 __list_iterator(const __list_iterator& __p)
334 __get_db()->__iterator_copy(this, &__p);
337 _LIBCPP_INLINE_VISIBILITY
340 __get_db()->__erase_i(this);
343 _LIBCPP_INLINE_VISIBILITY
344 __list_iterator& operator=(const __list_iterator& __p)
348 __get_db()->__iterator_copy(this, &__p);
354 #endif // _LIBCPP_DEBUG_LEVEL >= 2
356 _LIBCPP_INLINE_VISIBILITY
357 reference operator*() const
359 #if _LIBCPP_DEBUG_LEVEL >= 2
360 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
361 "Attempted to dereference a non-dereferenceable list::iterator");
363 return __ptr_->__as_node()->__value_;
365 _LIBCPP_INLINE_VISIBILITY
366 pointer operator->() const
368 #if _LIBCPP_DEBUG_LEVEL >= 2
369 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
370 "Attempted to dereference a non-dereferenceable list::iterator");
372 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
375 _LIBCPP_INLINE_VISIBILITY
376 __list_iterator& operator++()
378 #if _LIBCPP_DEBUG_LEVEL >= 2
379 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
380 "Attempted to increment non-incrementable list::iterator");
382 __ptr_ = __ptr_->__next_;
385 _LIBCPP_INLINE_VISIBILITY
386 __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;}
388 _LIBCPP_INLINE_VISIBILITY
389 __list_iterator& operator--()
391 #if _LIBCPP_DEBUG_LEVEL >= 2
392 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
393 "Attempted to decrement non-decrementable list::iterator");
395 __ptr_ = __ptr_->__prev_;
398 _LIBCPP_INLINE_VISIBILITY
399 __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}
401 friend _LIBCPP_INLINE_VISIBILITY
402 bool operator==(const __list_iterator& __x, const __list_iterator& __y)
404 return __x.__ptr_ == __y.__ptr_;
406 friend _LIBCPP_INLINE_VISIBILITY
407 bool operator!=(const __list_iterator& __x, const __list_iterator& __y)
408 {return !(__x == __y);}
411 template <class _Tp, class _VoidPtr>
412 class _LIBCPP_TEMPLATE_VIS __list_const_iterator
414 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
415 typedef typename _NodeTraits::__link_pointer __link_pointer;
417 __link_pointer __ptr_;
419 #if _LIBCPP_DEBUG_LEVEL >= 2
420 _LIBCPP_INLINE_VISIBILITY
421 explicit __list_const_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
424 __get_db()->__insert_ic(this, __c);
427 _LIBCPP_INLINE_VISIBILITY
428 explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
431 template<class, class> friend class list;
432 template<class, class> friend class __list_imp;
434 typedef bidirectional_iterator_tag iterator_category;
435 typedef _Tp value_type;
436 typedef const value_type& reference;
437 typedef typename __rebind_pointer<_VoidPtr, const value_type>::type pointer;
438 typedef typename pointer_traits<pointer>::difference_type difference_type;
440 _LIBCPP_INLINE_VISIBILITY
441 __list_const_iterator() _NOEXCEPT : __ptr_(nullptr)
443 #if _LIBCPP_DEBUG_LEVEL >= 2
444 __get_db()->__insert_i(this);
447 _LIBCPP_INLINE_VISIBILITY
448 __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT
451 #if _LIBCPP_DEBUG_LEVEL >= 2
452 __get_db()->__iterator_copy(this, &__p);
456 #if _LIBCPP_DEBUG_LEVEL >= 2
458 _LIBCPP_INLINE_VISIBILITY
459 __list_const_iterator(const __list_const_iterator& __p)
462 __get_db()->__iterator_copy(this, &__p);
465 _LIBCPP_INLINE_VISIBILITY
466 ~__list_const_iterator()
468 __get_db()->__erase_i(this);
471 _LIBCPP_INLINE_VISIBILITY
472 __list_const_iterator& operator=(const __list_const_iterator& __p)
476 __get_db()->__iterator_copy(this, &__p);
482 #endif // _LIBCPP_DEBUG_LEVEL >= 2
483 _LIBCPP_INLINE_VISIBILITY
484 reference operator*() const
486 #if _LIBCPP_DEBUG_LEVEL >= 2
487 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
488 "Attempted to dereference a non-dereferenceable list::const_iterator");
490 return __ptr_->__as_node()->__value_;
492 _LIBCPP_INLINE_VISIBILITY
493 pointer operator->() const
495 #if _LIBCPP_DEBUG_LEVEL >= 2
496 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
497 "Attempted to dereference a non-dereferenceable list::const_iterator");
499 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
502 _LIBCPP_INLINE_VISIBILITY
503 __list_const_iterator& operator++()
505 #if _LIBCPP_DEBUG_LEVEL >= 2
506 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
507 "Attempted to increment non-incrementable list::const_iterator");
509 __ptr_ = __ptr_->__next_;
512 _LIBCPP_INLINE_VISIBILITY
513 __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;}
515 _LIBCPP_INLINE_VISIBILITY
516 __list_const_iterator& operator--()
518 #if _LIBCPP_DEBUG_LEVEL >= 2
519 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
520 "Attempted to decrement non-decrementable list::const_iterator");
522 __ptr_ = __ptr_->__prev_;
525 _LIBCPP_INLINE_VISIBILITY
526 __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}
528 friend _LIBCPP_INLINE_VISIBILITY
529 bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y)
531 return __x.__ptr_ == __y.__ptr_;
533 friend _LIBCPP_INLINE_VISIBILITY
534 bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y)
535 {return !(__x == __y);}
538 template <class _Tp, class _Alloc>
541 __list_imp(const __list_imp&);
542 __list_imp& operator=(const __list_imp&);
544 typedef _Alloc allocator_type;
545 typedef allocator_traits<allocator_type> __alloc_traits;
546 typedef typename __alloc_traits::size_type size_type;
548 typedef _Tp value_type;
549 typedef typename __alloc_traits::void_pointer __void_pointer;
550 typedef __list_iterator<value_type, __void_pointer> iterator;
551 typedef __list_const_iterator<value_type, __void_pointer> const_iterator;
552 typedef __list_node_base<value_type, __void_pointer> __node_base;
553 typedef __list_node<value_type, __void_pointer> __node;
554 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
555 typedef allocator_traits<__node_allocator> __node_alloc_traits;
556 typedef typename __node_alloc_traits::pointer __node_pointer;
557 typedef typename __node_alloc_traits::pointer __node_const_pointer;
558 typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;
559 typedef typename __node_pointer_traits::__link_pointer __link_pointer;
560 typedef __link_pointer __link_const_pointer;
561 typedef typename __alloc_traits::pointer pointer;
562 typedef typename __alloc_traits::const_pointer const_pointer;
563 typedef typename __alloc_traits::difference_type difference_type;
565 typedef typename __rebind_alloc_helper<__alloc_traits, __node_base>::type __node_base_allocator;
566 typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
567 static_assert((!is_same<allocator_type, __node_allocator>::value),
568 "internal allocator type must differ from user-specified "
569 "type; otherwise overload resolution breaks");
572 __compressed_pair<size_type, __node_allocator> __size_alloc_;
574 _LIBCPP_INLINE_VISIBILITY
575 __link_pointer __end_as_link() const _NOEXCEPT {
576 return __node_pointer_traits::__unsafe_link_pointer_cast(
577 const_cast<__node_base&>(__end_).__self());
580 _LIBCPP_INLINE_VISIBILITY
581 size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
582 _LIBCPP_INLINE_VISIBILITY
583 const size_type& __sz() const _NOEXCEPT
584 {return __size_alloc_.first();}
585 _LIBCPP_INLINE_VISIBILITY
586 __node_allocator& __node_alloc() _NOEXCEPT
587 {return __size_alloc_.second();}
588 _LIBCPP_INLINE_VISIBILITY
589 const __node_allocator& __node_alloc() const _NOEXCEPT
590 {return __size_alloc_.second();}
592 _LIBCPP_INLINE_VISIBILITY
593 size_type __node_alloc_max_size() const _NOEXCEPT {
594 return __node_alloc_traits::max_size(__node_alloc());
596 _LIBCPP_INLINE_VISIBILITY
597 static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;
599 _LIBCPP_INLINE_VISIBILITY
601 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
602 _LIBCPP_INLINE_VISIBILITY
603 __list_imp(const allocator_type& __a);
604 _LIBCPP_INLINE_VISIBILITY
605 __list_imp(const __node_allocator& __a);
606 #ifndef _LIBCPP_CXX03_LANG
607 __list_imp(__node_allocator&& __a) _NOEXCEPT;
610 void clear() _NOEXCEPT;
611 _LIBCPP_INLINE_VISIBILITY
612 bool empty() const _NOEXCEPT {return __sz() == 0;}
614 _LIBCPP_INLINE_VISIBILITY
615 iterator begin() _NOEXCEPT
617 #if _LIBCPP_DEBUG_LEVEL >= 2
618 return iterator(__end_.__next_, this);
620 return iterator(__end_.__next_);
623 _LIBCPP_INLINE_VISIBILITY
624 const_iterator begin() const _NOEXCEPT
626 #if _LIBCPP_DEBUG_LEVEL >= 2
627 return const_iterator(__end_.__next_, this);
629 return const_iterator(__end_.__next_);
632 _LIBCPP_INLINE_VISIBILITY
633 iterator end() _NOEXCEPT
635 #if _LIBCPP_DEBUG_LEVEL >= 2
636 return iterator(__end_as_link(), this);
638 return iterator(__end_as_link());
641 _LIBCPP_INLINE_VISIBILITY
642 const_iterator end() const _NOEXCEPT
644 #if _LIBCPP_DEBUG_LEVEL >= 2
645 return const_iterator(__end_as_link(), this);
647 return const_iterator(__end_as_link());
651 void swap(__list_imp& __c)
652 #if _LIBCPP_STD_VER >= 14
655 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
656 __is_nothrow_swappable<allocator_type>::value);
659 _LIBCPP_INLINE_VISIBILITY
660 void __copy_assign_alloc(const __list_imp& __c)
661 {__copy_assign_alloc(__c, integral_constant<bool,
662 __node_alloc_traits::propagate_on_container_copy_assignment::value>());}
664 _LIBCPP_INLINE_VISIBILITY
665 void __move_assign_alloc(__list_imp& __c)
667 !__node_alloc_traits::propagate_on_container_move_assignment::value ||
668 is_nothrow_move_assignable<__node_allocator>::value)
669 {__move_assign_alloc(__c, integral_constant<bool,
670 __node_alloc_traits::propagate_on_container_move_assignment::value>());}
673 _LIBCPP_INLINE_VISIBILITY
674 void __copy_assign_alloc(const __list_imp& __c, true_type)
676 if (__node_alloc() != __c.__node_alloc())
678 __node_alloc() = __c.__node_alloc();
681 _LIBCPP_INLINE_VISIBILITY
682 void __copy_assign_alloc(const __list_imp&, false_type)
685 _LIBCPP_INLINE_VISIBILITY
686 void __move_assign_alloc(__list_imp& __c, true_type)
687 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
689 __node_alloc() = _VSTD::move(__c.__node_alloc());
692 _LIBCPP_INLINE_VISIBILITY
693 void __move_assign_alloc(__list_imp&, false_type)
697 _LIBCPP_INLINE_VISIBILITY
698 void __invalidate_all_iterators() {
699 #if _LIBCPP_DEBUG_LEVEL >= 2
700 __get_db()->__invalidate_all(this);
705 // Unlink nodes [__f, __l]
706 template <class _Tp, class _Alloc>
709 __list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l)
712 __f->__prev_->__next_ = __l->__next_;
713 __l->__next_->__prev_ = __f->__prev_;
716 template <class _Tp, class _Alloc>
718 __list_imp<_Tp, _Alloc>::__list_imp()
719 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
720 : __size_alloc_(0, __default_init_tag())
724 template <class _Tp, class _Alloc>
726 __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a)
727 : __size_alloc_(0, __node_allocator(__a))
731 template <class _Tp, class _Alloc>
732 inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a)
733 : __size_alloc_(0, __a) {}
735 #ifndef _LIBCPP_CXX03_LANG
736 template <class _Tp, class _Alloc>
737 inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) _NOEXCEPT
738 : __size_alloc_(0, std::move(__a)) {}
741 template <class _Tp, class _Alloc>
742 __list_imp<_Tp, _Alloc>::~__list_imp() {
744 #if _LIBCPP_DEBUG_LEVEL >= 2
745 __get_db()->__erase_c(this);
749 template <class _Tp, class _Alloc>
751 __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
755 __node_allocator& __na = __node_alloc();
756 __link_pointer __f = __end_.__next_;
757 __link_pointer __l = __end_as_link();
758 __unlink_nodes(__f, __l->__prev_);
762 __node_pointer __np = __f->__as_node();
764 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
765 __node_alloc_traits::deallocate(__na, __np, 1);
767 __invalidate_all_iterators();
771 template <class _Tp, class _Alloc>
773 __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
774 #if _LIBCPP_STD_VER >= 14
777 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
778 __is_nothrow_swappable<allocator_type>::value)
781 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
782 this->__node_alloc() == __c.__node_alloc(),
783 "list::swap: Either propagate_on_container_swap must be true"
784 " or the allocators must compare equal");
786 __swap_allocator(__node_alloc(), __c.__node_alloc());
787 swap(__sz(), __c.__sz());
788 swap(__end_, __c.__end_);
790 __end_.__next_ = __end_.__prev_ = __end_as_link();
792 __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
794 __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();
796 __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();
798 #if _LIBCPP_DEBUG_LEVEL >= 2
799 __libcpp_db* __db = __get_db();
800 __c_node* __cn1 = __db->__find_c_and_lock(this);
801 __c_node* __cn2 = __db->__find_c(&__c);
802 std::swap(__cn1->beg_, __cn2->beg_);
803 std::swap(__cn1->end_, __cn2->end_);
804 std::swap(__cn1->cap_, __cn2->cap_);
805 for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;)
808 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
809 if (__i->__ptr_ == __c.__end_as_link())
812 if (--__cn1->end_ != __p)
813 memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*));
816 (*__p)->__c_ = __cn1;
818 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
821 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
822 if (__i->__ptr_ == __end_as_link())
825 if (--__cn2->end_ != __p)
826 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
829 (*__p)->__c_ = __cn2;
835 template <class _Tp, class _Alloc /*= allocator<_Tp>*/>
836 class _LIBCPP_TEMPLATE_VIS list
837 : private __list_imp<_Tp, _Alloc>
839 typedef __list_imp<_Tp, _Alloc> base;
840 typedef typename base::__node __node;
841 typedef typename base::__node_allocator __node_allocator;
842 typedef typename base::__node_pointer __node_pointer;
843 typedef typename base::__node_alloc_traits __node_alloc_traits;
844 typedef typename base::__node_base __node_base;
845 typedef typename base::__node_base_pointer __node_base_pointer;
846 typedef typename base::__link_pointer __link_pointer;
849 typedef _Tp value_type;
850 typedef _Alloc allocator_type;
851 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
852 "Invalid allocator::value_type");
853 typedef value_type& reference;
854 typedef const value_type& const_reference;
855 typedef typename base::pointer pointer;
856 typedef typename base::const_pointer const_pointer;
857 typedef typename base::size_type size_type;
858 typedef typename base::difference_type difference_type;
859 typedef typename base::iterator iterator;
860 typedef typename base::const_iterator const_iterator;
861 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
862 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
863 #if _LIBCPP_STD_VER > 17
864 typedef size_type __remove_return_type;
866 typedef void __remove_return_type;
869 _LIBCPP_INLINE_VISIBILITY
871 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
873 #if _LIBCPP_DEBUG_LEVEL >= 2
874 __get_db()->__insert_c(this);
877 _LIBCPP_INLINE_VISIBILITY
878 explicit list(const allocator_type& __a) : base(__a)
880 #if _LIBCPP_DEBUG_LEVEL >= 2
881 __get_db()->__insert_c(this);
884 explicit list(size_type __n);
885 #if _LIBCPP_STD_VER > 11
886 explicit list(size_type __n, const allocator_type& __a);
888 list(size_type __n, const value_type& __x);
889 list(size_type __n, const value_type& __x, const allocator_type& __a);
890 template <class _InpIter>
891 list(_InpIter __f, _InpIter __l,
892 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);
893 template <class _InpIter>
894 list(_InpIter __f, _InpIter __l, const allocator_type& __a,
895 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);
897 list(const list& __c);
898 list(const list& __c, const allocator_type& __a);
899 _LIBCPP_INLINE_VISIBILITY
900 list& operator=(const list& __c);
901 #ifndef _LIBCPP_CXX03_LANG
902 list(initializer_list<value_type> __il);
903 list(initializer_list<value_type> __il, const allocator_type& __a);
905 _LIBCPP_INLINE_VISIBILITY
907 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
908 _LIBCPP_INLINE_VISIBILITY
909 list(list&& __c, const allocator_type& __a);
910 _LIBCPP_INLINE_VISIBILITY
911 list& operator=(list&& __c)
913 __node_alloc_traits::propagate_on_container_move_assignment::value &&
914 is_nothrow_move_assignable<__node_allocator>::value);
916 _LIBCPP_INLINE_VISIBILITY
917 list& operator=(initializer_list<value_type> __il)
918 {assign(__il.begin(), __il.end()); return *this;}
920 _LIBCPP_INLINE_VISIBILITY
921 void assign(initializer_list<value_type> __il)
922 {assign(__il.begin(), __il.end());}
923 #endif // _LIBCPP_CXX03_LANG
925 template <class _InpIter>
926 void assign(_InpIter __f, _InpIter __l,
927 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);
928 void assign(size_type __n, const value_type& __x);
930 _LIBCPP_INLINE_VISIBILITY
931 allocator_type get_allocator() const _NOEXCEPT;
933 _LIBCPP_INLINE_VISIBILITY
934 size_type size() const _NOEXCEPT {return base::__sz();}
935 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
936 bool empty() const _NOEXCEPT {return base::empty();}
937 _LIBCPP_INLINE_VISIBILITY
938 size_type max_size() const _NOEXCEPT
940 return std::min<size_type>(
941 base::__node_alloc_max_size(),
942 numeric_limits<difference_type >::max());
945 _LIBCPP_INLINE_VISIBILITY
946 iterator begin() _NOEXCEPT {return base::begin();}
947 _LIBCPP_INLINE_VISIBILITY
948 const_iterator begin() const _NOEXCEPT {return base::begin();}
949 _LIBCPP_INLINE_VISIBILITY
950 iterator end() _NOEXCEPT {return base::end();}
951 _LIBCPP_INLINE_VISIBILITY
952 const_iterator end() const _NOEXCEPT {return base::end();}
953 _LIBCPP_INLINE_VISIBILITY
954 const_iterator cbegin() const _NOEXCEPT {return base::begin();}
955 _LIBCPP_INLINE_VISIBILITY
956 const_iterator cend() const _NOEXCEPT {return base::end();}
958 _LIBCPP_INLINE_VISIBILITY
959 reverse_iterator rbegin() _NOEXCEPT
960 {return reverse_iterator(end());}
961 _LIBCPP_INLINE_VISIBILITY
962 const_reverse_iterator rbegin() const _NOEXCEPT
963 {return const_reverse_iterator(end());}
964 _LIBCPP_INLINE_VISIBILITY
965 reverse_iterator rend() _NOEXCEPT
966 {return reverse_iterator(begin());}
967 _LIBCPP_INLINE_VISIBILITY
968 const_reverse_iterator rend() const _NOEXCEPT
969 {return const_reverse_iterator(begin());}
970 _LIBCPP_INLINE_VISIBILITY
971 const_reverse_iterator crbegin() const _NOEXCEPT
972 {return const_reverse_iterator(end());}
973 _LIBCPP_INLINE_VISIBILITY
974 const_reverse_iterator crend() const _NOEXCEPT
975 {return const_reverse_iterator(begin());}
977 _LIBCPP_INLINE_VISIBILITY
980 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
981 return base::__end_.__next_->__as_node()->__value_;
983 _LIBCPP_INLINE_VISIBILITY
984 const_reference front() const
986 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
987 return base::__end_.__next_->__as_node()->__value_;
989 _LIBCPP_INLINE_VISIBILITY
992 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
993 return base::__end_.__prev_->__as_node()->__value_;
995 _LIBCPP_INLINE_VISIBILITY
996 const_reference back() const
998 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
999 return base::__end_.__prev_->__as_node()->__value_;
1002 #ifndef _LIBCPP_CXX03_LANG
1003 void push_front(value_type&& __x);
1004 void push_back(value_type&& __x);
1006 template <class... _Args>
1007 #if _LIBCPP_STD_VER > 14
1008 reference emplace_front(_Args&&... __args);
1010 void emplace_front(_Args&&... __args);
1012 template <class... _Args>
1013 #if _LIBCPP_STD_VER > 14
1014 reference emplace_back(_Args&&... __args);
1016 void emplace_back(_Args&&... __args);
1018 template <class... _Args>
1019 iterator emplace(const_iterator __p, _Args&&... __args);
1021 iterator insert(const_iterator __p, value_type&& __x);
1023 _LIBCPP_INLINE_VISIBILITY
1024 iterator insert(const_iterator __p, initializer_list<value_type> __il)
1025 {return insert(__p, __il.begin(), __il.end());}
1026 #endif // _LIBCPP_CXX03_LANG
1028 void push_front(const value_type& __x);
1029 void push_back(const value_type& __x);
1031 #ifndef _LIBCPP_CXX03_LANG
1032 template <class _Arg>
1033 _LIBCPP_INLINE_VISIBILITY
1034 void __emplace_back(_Arg&& __arg) { emplace_back(_VSTD::forward<_Arg>(__arg)); }
1036 _LIBCPP_INLINE_VISIBILITY
1037 void __emplace_back(value_type const& __arg) { push_back(__arg); }
1040 iterator insert(const_iterator __p, const value_type& __x);
1041 iterator insert(const_iterator __p, size_type __n, const value_type& __x);
1042 template <class _InpIter>
1043 iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
1044 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);
1046 _LIBCPP_INLINE_VISIBILITY
1047 void swap(list& __c)
1048 #if _LIBCPP_STD_VER >= 14
1051 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
1052 __is_nothrow_swappable<__node_allocator>::value)
1055 _LIBCPP_INLINE_VISIBILITY
1056 void clear() _NOEXCEPT {base::clear();}
1061 iterator erase(const_iterator __p);
1062 iterator erase(const_iterator __f, const_iterator __l);
1064 void resize(size_type __n);
1065 void resize(size_type __n, const value_type& __x);
1067 void splice(const_iterator __p, list& __c);
1068 #ifndef _LIBCPP_CXX03_LANG
1069 _LIBCPP_INLINE_VISIBILITY
1070 void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
1071 _LIBCPP_INLINE_VISIBILITY
1072 void splice(const_iterator __p, list&& __c, const_iterator __i)
1073 {splice(__p, __c, __i);}
1074 _LIBCPP_INLINE_VISIBILITY
1075 void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
1076 {splice(__p, __c, __f, __l);}
1078 void splice(const_iterator __p, list& __c, const_iterator __i);
1079 void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
1081 __remove_return_type remove(const value_type& __x);
1082 template <class _Pred> __remove_return_type remove_if(_Pred __pred);
1083 _LIBCPP_INLINE_VISIBILITY
1084 __remove_return_type unique() { return unique(__equal_to<value_type>()); }
1085 template <class _BinaryPred>
1086 __remove_return_type unique(_BinaryPred __binary_pred);
1087 _LIBCPP_INLINE_VISIBILITY
1088 void merge(list& __c);
1089 #ifndef _LIBCPP_CXX03_LANG
1090 _LIBCPP_INLINE_VISIBILITY
1091 void merge(list&& __c) {merge(__c);}
1093 template <class _Comp>
1094 _LIBCPP_INLINE_VISIBILITY
1095 void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
1097 template <class _Comp>
1098 void merge(list& __c, _Comp __comp);
1100 _LIBCPP_INLINE_VISIBILITY
1102 template <class _Comp>
1103 _LIBCPP_INLINE_VISIBILITY
1104 void sort(_Comp __comp);
1106 void reverse() _NOEXCEPT;
1108 bool __invariants() const;
1110 typedef __allocator_destructor<__node_allocator> __node_destructor;
1111 typedef unique_ptr<__node, __node_destructor> __hold_pointer;
1113 _LIBCPP_INLINE_VISIBILITY
1114 __hold_pointer __allocate_node(__node_allocator& __na) {
1115 __node_pointer __p = __node_alloc_traits::allocate(__na, 1);
1116 __p->__prev_ = nullptr;
1117 return __hold_pointer(__p, __node_destructor(__na, 1));
1120 #if _LIBCPP_DEBUG_LEVEL >= 2
1122 bool __dereferenceable(const const_iterator* __i) const;
1123 bool __decrementable(const const_iterator* __i) const;
1124 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1125 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1127 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1130 _LIBCPP_INLINE_VISIBILITY
1131 static void __link_nodes (__link_pointer __p, __link_pointer __f, __link_pointer __l);
1132 _LIBCPP_INLINE_VISIBILITY
1133 void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);
1134 _LIBCPP_INLINE_VISIBILITY
1135 void __link_nodes_at_back (__link_pointer __f, __link_pointer __l);
1136 iterator __iterator(size_type __n);
1137 template <class _Comp>
1138 static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
1140 void __move_assign(list& __c, true_type)
1141 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
1142 void __move_assign(list& __c, false_type);
1145 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1146 template<class _InputIterator,
1147 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,
1148 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
1150 list(_InputIterator, _InputIterator)
1151 -> list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
1153 template<class _InputIterator,
1155 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
1157 list(_InputIterator, _InputIterator, _Alloc)
1158 -> list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
1161 // Link in nodes [__f, __l] just prior to __p
1162 template <class _Tp, class _Alloc>
1165 list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l)
1167 __p->__prev_->__next_ = __f;
1168 __f->__prev_ = __p->__prev_;
1173 // Link in nodes [__f, __l] at the front of the list
1174 template <class _Tp, class _Alloc>
1177 list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l)
1179 __f->__prev_ = base::__end_as_link();
1180 __l->__next_ = base::__end_.__next_;
1181 __l->__next_->__prev_ = __l;
1182 base::__end_.__next_ = __f;
1185 // Link in nodes [__f, __l] at the back of the list
1186 template <class _Tp, class _Alloc>
1189 list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l)
1191 __l->__next_ = base::__end_as_link();
1192 __f->__prev_ = base::__end_.__prev_;
1193 __f->__prev_->__next_ = __f;
1194 base::__end_.__prev_ = __l;
1198 template <class _Tp, class _Alloc>
1200 typename list<_Tp, _Alloc>::iterator
1201 list<_Tp, _Alloc>::__iterator(size_type __n)
1203 return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n)
1204 : _VSTD::prev(end(), base::__sz() - __n);
1207 template <class _Tp, class _Alloc>
1208 list<_Tp, _Alloc>::list(size_type __n)
1210 #if _LIBCPP_DEBUG_LEVEL >= 2
1211 __get_db()->__insert_c(this);
1213 for (; __n > 0; --__n)
1214 #ifndef _LIBCPP_CXX03_LANG
1217 push_back(value_type());
1221 #if _LIBCPP_STD_VER > 11
1222 template <class _Tp, class _Alloc>
1223 list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a)
1225 #if _LIBCPP_DEBUG_LEVEL >= 2
1226 __get_db()->__insert_c(this);
1228 for (; __n > 0; --__n)
1233 template <class _Tp, class _Alloc>
1234 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x)
1236 #if _LIBCPP_DEBUG_LEVEL >= 2
1237 __get_db()->__insert_c(this);
1239 for (; __n > 0; --__n)
1243 template <class _Tp, class _Alloc>
1244 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a)
1247 #if _LIBCPP_DEBUG_LEVEL >= 2
1248 __get_db()->__insert_c(this);
1250 for (; __n > 0; --__n)
1254 template <class _Tp, class _Alloc>
1255 template <class _InpIter>
1256 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
1257 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type*)
1259 #if _LIBCPP_DEBUG_LEVEL >= 2
1260 __get_db()->__insert_c(this);
1262 for (; __f != __l; ++__f)
1263 __emplace_back(*__f);
1266 template <class _Tp, class _Alloc>
1267 template <class _InpIter>
1268 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
1269 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type*)
1272 #if _LIBCPP_DEBUG_LEVEL >= 2
1273 __get_db()->__insert_c(this);
1275 for (; __f != __l; ++__f)
1276 __emplace_back(*__f);
1279 template <class _Tp, class _Alloc>
1280 list<_Tp, _Alloc>::list(const list& __c)
1281 : base(__node_alloc_traits::select_on_container_copy_construction(
1282 __c.__node_alloc())) {
1283 #if _LIBCPP_DEBUG_LEVEL >= 2
1284 __get_db()->__insert_c(this);
1286 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1290 template <class _Tp, class _Alloc>
1291 list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a)
1294 #if _LIBCPP_DEBUG_LEVEL >= 2
1295 __get_db()->__insert_c(this);
1297 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1301 #ifndef _LIBCPP_CXX03_LANG
1303 template <class _Tp, class _Alloc>
1304 list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a)
1307 #if _LIBCPP_DEBUG_LEVEL >= 2
1308 __get_db()->__insert_c(this);
1310 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1311 __e = __il.end(); __i != __e; ++__i)
1315 template <class _Tp, class _Alloc>
1316 list<_Tp, _Alloc>::list(initializer_list<value_type> __il)
1318 #if _LIBCPP_DEBUG_LEVEL >= 2
1319 __get_db()->__insert_c(this);
1321 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1322 __e = __il.end(); __i != __e; ++__i)
1326 template <class _Tp, class _Alloc>
1327 inline list<_Tp, _Alloc>::list(list&& __c)
1328 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
1329 : base(_VSTD::move(__c.__node_alloc())) {
1330 #if _LIBCPP_DEBUG_LEVEL >= 2
1331 __get_db()->__insert_c(this);
1336 template <class _Tp, class _Alloc>
1338 list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a)
1341 #if _LIBCPP_DEBUG_LEVEL >= 2
1342 __get_db()->__insert_c(this);
1344 if (__a == __c.get_allocator())
1348 typedef move_iterator<iterator> _Ip;
1349 assign(_Ip(__c.begin()), _Ip(__c.end()));
1353 template <class _Tp, class _Alloc>
1356 list<_Tp, _Alloc>::operator=(list&& __c)
1358 __node_alloc_traits::propagate_on_container_move_assignment::value &&
1359 is_nothrow_move_assignable<__node_allocator>::value)
1361 __move_assign(__c, integral_constant<bool,
1362 __node_alloc_traits::propagate_on_container_move_assignment::value>());
1366 template <class _Tp, class _Alloc>
1368 list<_Tp, _Alloc>::__move_assign(list& __c, false_type)
1370 if (base::__node_alloc() != __c.__node_alloc())
1372 typedef move_iterator<iterator> _Ip;
1373 assign(_Ip(__c.begin()), _Ip(__c.end()));
1376 __move_assign(__c, true_type());
1379 template <class _Tp, class _Alloc>
1381 list<_Tp, _Alloc>::__move_assign(list& __c, true_type)
1382 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1385 base::__move_assign_alloc(__c);
1389 #endif // _LIBCPP_CXX03_LANG
1391 template <class _Tp, class _Alloc>
1394 list<_Tp, _Alloc>::operator=(const list& __c)
1398 base::__copy_assign_alloc(__c);
1399 assign(__c.begin(), __c.end());
1404 template <class _Tp, class _Alloc>
1405 template <class _InpIter>
1407 list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l,
1408 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type*)
1410 iterator __i = begin();
1411 iterator __e = end();
1412 for (; __f != __l && __i != __e; ++__f, ++__i)
1415 insert(__e, __f, __l);
1418 #if _LIBCPP_DEBUG_LEVEL >= 2
1419 __get_db()->__invalidate_all(this);
1423 template <class _Tp, class _Alloc>
1425 list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x)
1427 iterator __i = begin();
1428 iterator __e = end();
1429 for (; __n > 0 && __i != __e; --__n, ++__i)
1432 insert(__e, __n, __x);
1435 #if _LIBCPP_DEBUG_LEVEL >= 2
1436 __get_db()->__invalidate_all(this);
1440 template <class _Tp, class _Alloc>
1443 list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT
1445 return allocator_type(base::__node_alloc());
1448 template <class _Tp, class _Alloc>
1449 typename list<_Tp, _Alloc>::iterator
1450 list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
1452 #if _LIBCPP_DEBUG_LEVEL >= 2
1453 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1454 "list::insert(iterator, x) called with an iterator not"
1455 " referring to this list");
1457 __node_allocator& __na = base::__node_alloc();
1458 __hold_pointer __hold = __allocate_node(__na);
1459 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1460 __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link());
1462 #if _LIBCPP_DEBUG_LEVEL >= 2
1463 return iterator(__hold.release()->__as_link(), this);
1465 return iterator(__hold.release()->__as_link());
1469 template <class _Tp, class _Alloc>
1470 typename list<_Tp, _Alloc>::iterator
1471 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
1473 #if _LIBCPP_DEBUG_LEVEL >= 2
1474 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1475 "list::insert(iterator, n, x) called with an iterator not"
1476 " referring to this list");
1477 iterator __r(__p.__ptr_, this);
1479 iterator __r(__p.__ptr_);
1484 __node_allocator& __na = base::__node_alloc();
1485 __hold_pointer __hold = __allocate_node(__na);
1486 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1488 #if _LIBCPP_DEBUG_LEVEL >= 2
1489 __r = iterator(__hold->__as_link(), this);
1491 __r = iterator(__hold->__as_link());
1495 #ifndef _LIBCPP_NO_EXCEPTIONS
1498 #endif // _LIBCPP_NO_EXCEPTIONS
1499 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1501 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1502 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1503 __e.__ptr_->__next_ = __hold->__as_link();
1504 __hold->__prev_ = __e.__ptr_;
1507 #ifndef _LIBCPP_NO_EXCEPTIONS
1513 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1514 __link_pointer __prev = __e.__ptr_->__prev_;
1515 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1518 #if _LIBCPP_DEBUG_LEVEL >= 2
1519 __e = iterator(__prev, this);
1521 __e = iterator(__prev);
1526 #endif // _LIBCPP_NO_EXCEPTIONS
1527 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1528 base::__sz() += __ds;
1533 template <class _Tp, class _Alloc>
1534 template <class _InpIter>
1535 typename list<_Tp, _Alloc>::iterator
1536 list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
1537 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type*)
1539 #if _LIBCPP_DEBUG_LEVEL >= 2
1540 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1541 "list::insert(iterator, range) called with an iterator not"
1542 " referring to this list");
1543 iterator __r(__p.__ptr_, this);
1545 iterator __r(__p.__ptr_);
1550 __node_allocator& __na = base::__node_alloc();
1551 __hold_pointer __hold = __allocate_node(__na);
1552 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1554 #if _LIBCPP_DEBUG_LEVEL >= 2
1555 __r = iterator(__hold.get()->__as_link(), this);
1557 __r = iterator(__hold.get()->__as_link());
1561 #ifndef _LIBCPP_NO_EXCEPTIONS
1564 #endif // _LIBCPP_NO_EXCEPTIONS
1565 for (++__f; __f != __l; ++__f, (void) ++__e, (void) ++__ds)
1567 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1568 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1569 __e.__ptr_->__next_ = __hold.get()->__as_link();
1570 __hold->__prev_ = __e.__ptr_;
1573 #ifndef _LIBCPP_NO_EXCEPTIONS
1579 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1580 __link_pointer __prev = __e.__ptr_->__prev_;
1581 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1584 #if _LIBCPP_DEBUG_LEVEL >= 2
1585 __e = iterator(__prev, this);
1587 __e = iterator(__prev);
1592 #endif // _LIBCPP_NO_EXCEPTIONS
1593 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1594 base::__sz() += __ds;
1599 template <class _Tp, class _Alloc>
1601 list<_Tp, _Alloc>::push_front(const value_type& __x)
1603 __node_allocator& __na = base::__node_alloc();
1604 __hold_pointer __hold = __allocate_node(__na);
1605 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1606 __link_pointer __nl = __hold->__as_link();
1607 __link_nodes_at_front(__nl, __nl);
1612 template <class _Tp, class _Alloc>
1614 list<_Tp, _Alloc>::push_back(const value_type& __x)
1616 __node_allocator& __na = base::__node_alloc();
1617 __hold_pointer __hold = __allocate_node(__na);
1618 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1619 __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
1624 #ifndef _LIBCPP_CXX03_LANG
1626 template <class _Tp, class _Alloc>
1628 list<_Tp, _Alloc>::push_front(value_type&& __x)
1630 __node_allocator& __na = base::__node_alloc();
1631 __hold_pointer __hold = __allocate_node(__na);
1632 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1633 __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
1638 template <class _Tp, class _Alloc>
1640 list<_Tp, _Alloc>::push_back(value_type&& __x)
1642 __node_allocator& __na = base::__node_alloc();
1643 __hold_pointer __hold = __allocate_node(__na);
1644 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1645 __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
1650 template <class _Tp, class _Alloc>
1651 template <class... _Args>
1652 #if _LIBCPP_STD_VER > 14
1653 typename list<_Tp, _Alloc>::reference
1657 list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1659 __node_allocator& __na = base::__node_alloc();
1660 __hold_pointer __hold = __allocate_node(__na);
1661 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1662 __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
1664 #if _LIBCPP_STD_VER > 14
1665 return __hold.release()->__value_;
1671 template <class _Tp, class _Alloc>
1672 template <class... _Args>
1673 #if _LIBCPP_STD_VER > 14
1674 typename list<_Tp, _Alloc>::reference
1678 list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1680 __node_allocator& __na = base::__node_alloc();
1681 __hold_pointer __hold = __allocate_node(__na);
1682 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1683 __link_pointer __nl = __hold->__as_link();
1684 __link_nodes_at_back(__nl, __nl);
1686 #if _LIBCPP_STD_VER > 14
1687 return __hold.release()->__value_;
1693 template <class _Tp, class _Alloc>
1694 template <class... _Args>
1695 typename list<_Tp, _Alloc>::iterator
1696 list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1698 #if _LIBCPP_DEBUG_LEVEL >= 2
1699 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1700 "list::emplace(iterator, args...) called with an iterator not"
1701 " referring to this list");
1703 __node_allocator& __na = base::__node_alloc();
1704 __hold_pointer __hold = __allocate_node(__na);
1705 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1706 __link_pointer __nl = __hold.get()->__as_link();
1707 __link_nodes(__p.__ptr_, __nl, __nl);
1710 #if _LIBCPP_DEBUG_LEVEL >= 2
1711 return iterator(__nl, this);
1713 return iterator(__nl);
1717 template <class _Tp, class _Alloc>
1718 typename list<_Tp, _Alloc>::iterator
1719 list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1721 #if _LIBCPP_DEBUG_LEVEL >= 2
1722 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1723 "list::insert(iterator, x) called with an iterator not"
1724 " referring to this list");
1726 __node_allocator& __na = base::__node_alloc();
1727 __hold_pointer __hold = __allocate_node(__na);
1728 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1729 __link_pointer __nl = __hold->__as_link();
1730 __link_nodes(__p.__ptr_, __nl, __nl);
1733 #if _LIBCPP_DEBUG_LEVEL >= 2
1734 return iterator(__nl, this);
1736 return iterator(__nl);
1740 #endif // _LIBCPP_CXX03_LANG
1742 template <class _Tp, class _Alloc>
1744 list<_Tp, _Alloc>::pop_front()
1746 _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
1747 __node_allocator& __na = base::__node_alloc();
1748 __link_pointer __n = base::__end_.__next_;
1749 base::__unlink_nodes(__n, __n);
1751 #if _LIBCPP_DEBUG_LEVEL >= 2
1752 __c_node* __c = __get_db()->__find_c_and_lock(this);
1753 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1756 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1757 if (__i->__ptr_ == __n)
1759 (*__p)->__c_ = nullptr;
1760 if (--__c->end_ != __p)
1761 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1764 __get_db()->unlock();
1766 __node_pointer __np = __n->__as_node();
1767 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1768 __node_alloc_traits::deallocate(__na, __np, 1);
1771 template <class _Tp, class _Alloc>
1773 list<_Tp, _Alloc>::pop_back()
1775 _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list");
1776 __node_allocator& __na = base::__node_alloc();
1777 __link_pointer __n = base::__end_.__prev_;
1778 base::__unlink_nodes(__n, __n);
1780 #if _LIBCPP_DEBUG_LEVEL >= 2
1781 __c_node* __c = __get_db()->__find_c_and_lock(this);
1782 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1785 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1786 if (__i->__ptr_ == __n)
1788 (*__p)->__c_ = nullptr;
1789 if (--__c->end_ != __p)
1790 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1793 __get_db()->unlock();
1795 __node_pointer __np = __n->__as_node();
1796 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1797 __node_alloc_traits::deallocate(__na, __np, 1);
1800 template <class _Tp, class _Alloc>
1801 typename list<_Tp, _Alloc>::iterator
1802 list<_Tp, _Alloc>::erase(const_iterator __p)
1804 #if _LIBCPP_DEBUG_LEVEL >= 2
1805 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1806 "list::erase(iterator) called with an iterator not"
1807 " referring to this list");
1809 _LIBCPP_ASSERT(__p != end(),
1810 "list::erase(iterator) called with a non-dereferenceable iterator");
1811 __node_allocator& __na = base::__node_alloc();
1812 __link_pointer __n = __p.__ptr_;
1813 __link_pointer __r = __n->__next_;
1814 base::__unlink_nodes(__n, __n);
1816 #if _LIBCPP_DEBUG_LEVEL >= 2
1817 __c_node* __c = __get_db()->__find_c_and_lock(this);
1818 for (__i_node** __ip = __c->end_; __ip != __c->beg_; )
1821 iterator* __i = static_cast<iterator*>((*__ip)->__i_);
1822 if (__i->__ptr_ == __n)
1824 (*__ip)->__c_ = nullptr;
1825 if (--__c->end_ != __ip)
1826 memmove(__ip, __ip+1, (__c->end_ - __ip)*sizeof(__i_node*));
1829 __get_db()->unlock();
1831 __node_pointer __np = __n->__as_node();
1832 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1833 __node_alloc_traits::deallocate(__na, __np, 1);
1834 #if _LIBCPP_DEBUG_LEVEL >= 2
1835 return iterator(__r, this);
1837 return iterator(__r);
1841 template <class _Tp, class _Alloc>
1842 typename list<_Tp, _Alloc>::iterator
1843 list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1845 #if _LIBCPP_DEBUG_LEVEL >= 2
1846 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this,
1847 "list::erase(iterator, iterator) called with an iterator not"
1848 " referring to this list");
1849 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__l) == this,
1850 "list::erase(iterator, iterator) called with an iterator not"
1851 " referring to this list");
1855 __node_allocator& __na = base::__node_alloc();
1856 base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
1859 __link_pointer __n = __f.__ptr_;
1862 #if _LIBCPP_DEBUG_LEVEL >= 2
1863 __c_node* __c = __get_db()->__find_c_and_lock(this);
1864 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1867 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1868 if (__i->__ptr_ == __n)
1870 (*__p)->__c_ = nullptr;
1871 if (--__c->end_ != __p)
1872 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1875 __get_db()->unlock();
1877 __node_pointer __np = __n->__as_node();
1878 __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1879 __node_alloc_traits::deallocate(__na, __np, 1);
1882 #if _LIBCPP_DEBUG_LEVEL >= 2
1883 return iterator(__l.__ptr_, this);
1885 return iterator(__l.__ptr_);
1889 template <class _Tp, class _Alloc>
1891 list<_Tp, _Alloc>::resize(size_type __n)
1893 if (__n < base::__sz())
1894 erase(__iterator(__n), end());
1895 else if (__n > base::__sz())
1897 __n -= base::__sz();
1899 __node_allocator& __na = base::__node_alloc();
1900 __hold_pointer __hold = __allocate_node(__na);
1901 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1903 #if _LIBCPP_DEBUG_LEVEL >= 2
1904 iterator __r = iterator(__hold.release()->__as_link(), this);
1906 iterator __r = iterator(__hold.release()->__as_link());
1909 #ifndef _LIBCPP_NO_EXCEPTIONS
1912 #endif // _LIBCPP_NO_EXCEPTIONS
1913 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1915 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1916 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1917 __e.__ptr_->__next_ = __hold.get()->__as_link();
1918 __hold->__prev_ = __e.__ptr_;
1921 #ifndef _LIBCPP_NO_EXCEPTIONS
1927 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1928 __link_pointer __prev = __e.__ptr_->__prev_;
1929 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1932 #if _LIBCPP_DEBUG_LEVEL >= 2
1933 __e = iterator(__prev, this);
1935 __e = iterator(__prev);
1940 #endif // _LIBCPP_NO_EXCEPTIONS
1941 __link_nodes_at_back(__r.__ptr_, __e.__ptr_);
1942 base::__sz() += __ds;
1946 template <class _Tp, class _Alloc>
1948 list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1950 if (__n < base::__sz())
1951 erase(__iterator(__n), end());
1952 else if (__n > base::__sz())
1954 __n -= base::__sz();
1956 __node_allocator& __na = base::__node_alloc();
1957 __hold_pointer __hold = __allocate_node(__na);
1958 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1960 __link_pointer __nl = __hold.release()->__as_link();
1961 #if _LIBCPP_DEBUG_LEVEL >= 2
1962 iterator __r = iterator(__nl, this);
1964 iterator __r = iterator(__nl);
1967 #ifndef _LIBCPP_NO_EXCEPTIONS
1970 #endif // _LIBCPP_NO_EXCEPTIONS
1971 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1973 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1974 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1975 __e.__ptr_->__next_ = __hold.get()->__as_link();
1976 __hold->__prev_ = __e.__ptr_;
1979 #ifndef _LIBCPP_NO_EXCEPTIONS
1985 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1986 __link_pointer __prev = __e.__ptr_->__prev_;
1987 __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
1990 #if _LIBCPP_DEBUG_LEVEL >= 2
1991 __e = iterator(__prev, this);
1993 __e = iterator(__prev);
1998 #endif // _LIBCPP_NO_EXCEPTIONS
1999 __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_);
2000 base::__sz() += __ds;
2004 template <class _Tp, class _Alloc>
2006 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
2008 _LIBCPP_ASSERT(this != &__c,
2009 "list::splice(iterator, list) called with this == &list");
2010 #if _LIBCPP_DEBUG_LEVEL >= 2
2011 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2012 "list::splice(iterator, list) called with an iterator not"
2013 " referring to this list");
2017 __link_pointer __f = __c.__end_.__next_;
2018 __link_pointer __l = __c.__end_.__prev_;
2019 base::__unlink_nodes(__f, __l);
2020 __link_nodes(__p.__ptr_, __f, __l);
2021 base::__sz() += __c.__sz();
2023 #if _LIBCPP_DEBUG_LEVEL >= 2
2025 __libcpp_db* __db = __get_db();
2026 __c_node* __cn1 = __db->__find_c_and_lock(this);
2027 __c_node* __cn2 = __db->__find_c(&__c);
2028 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2031 iterator* __i = static_cast<iterator*>((*__ip)->__i_);
2032 if (__i->__ptr_ != __c.__end_as_link())
2034 __cn1->__add(*__ip);
2035 (*__ip)->__c_ = __cn1;
2036 if (--__cn2->end_ != __ip)
2037 memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2046 template <class _Tp, class _Alloc>
2048 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
2050 #if _LIBCPP_DEBUG_LEVEL >= 2
2051 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2052 "list::splice(iterator, list, iterator) called with first iterator not"
2053 " referring to this list");
2054 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c,
2055 "list::splice(iterator, list, iterator) called with second iterator not"
2056 " referring to list argument");
2057 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i),
2058 "list::splice(iterator, list, iterator) called with second iterator not"
2061 if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
2063 __link_pointer __f = __i.__ptr_;
2064 base::__unlink_nodes(__f, __f);
2065 __link_nodes(__p.__ptr_, __f, __f);
2068 #if _LIBCPP_DEBUG_LEVEL >= 2
2070 __libcpp_db* __db = __get_db();
2071 __c_node* __cn1 = __db->__find_c_and_lock(this);
2072 __c_node* __cn2 = __db->__find_c(&__c);
2073 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2076 iterator* __j = static_cast<iterator*>((*__ip)->__i_);
2077 if (__j->__ptr_ == __f)
2079 __cn1->__add(*__ip);
2080 (*__ip)->__c_ = __cn1;
2081 if (--__cn2->end_ != __ip)
2082 memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2091 template <class _Tp, class _Alloc>
2093 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
2095 #if _LIBCPP_DEBUG_LEVEL >= 2
2096 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2097 "list::splice(iterator, list, iterator, iterator) called with first iterator not"
2098 " referring to this list");
2099 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c,
2100 "list::splice(iterator, list, iterator, iterator) called with second iterator not"
2101 " referring to list argument");
2104 for (const_iterator __i = __f; __i != __l; ++__i)
2105 _LIBCPP_ASSERT(__i != __p,
2106 "list::splice(iterator, list, iterator, iterator)"
2107 " called with the first iterator within the range"
2108 " of the second and third iterators");
2113 __link_pointer __first = __f.__ptr_;
2115 __link_pointer __last = __l.__ptr_;
2118 size_type __s = _VSTD::distance(__f, __l) + 1;
2120 base::__sz() += __s;
2122 base::__unlink_nodes(__first, __last);
2123 __link_nodes(__p.__ptr_, __first, __last);
2124 #if _LIBCPP_DEBUG_LEVEL >= 2
2126 __libcpp_db* __db = __get_db();
2127 __c_node* __cn1 = __db->__find_c_and_lock(this);
2128 __c_node* __cn2 = __db->__find_c(&__c);
2129 for (__i_node** __ip = __cn2->end_; __ip != __cn2->beg_;)
2132 iterator* __j = static_cast<iterator*>((*__ip)->__i_);
2133 for (__link_pointer __k = __f.__ptr_;
2134 __k != __l.__ptr_; __k = __k->__next_)
2136 if (__j->__ptr_ == __k)
2138 __cn1->__add(*__ip);
2139 (*__ip)->__c_ = __cn1;
2140 if (--__cn2->end_ != __ip)
2141 memmove(__ip, __ip+1, (__cn2->end_ - __ip)*sizeof(__i_node*));
2151 template <class _Tp, class _Alloc>
2152 typename list<_Tp, _Alloc>::__remove_return_type
2153 list<_Tp, _Alloc>::remove(const value_type& __x)
2155 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
2156 for (const_iterator __i = begin(), __e = end(); __i != __e;)
2160 const_iterator __j = _VSTD::next(__i);
2161 for (; __j != __e && *__j == __x; ++__j)
2163 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
2172 return (__remove_return_type) __deleted_nodes.size();
2175 template <class _Tp, class _Alloc>
2176 template <class _Pred>
2177 typename list<_Tp, _Alloc>::__remove_return_type
2178 list<_Tp, _Alloc>::remove_if(_Pred __pred)
2180 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
2181 for (iterator __i = begin(), __e = end(); __i != __e;)
2185 iterator __j = _VSTD::next(__i);
2186 for (; __j != __e && __pred(*__j); ++__j)
2188 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
2197 return (__remove_return_type) __deleted_nodes.size();
2200 template <class _Tp, class _Alloc>
2201 template <class _BinaryPred>
2202 typename list<_Tp, _Alloc>::__remove_return_type
2203 list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
2205 list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing
2206 for (iterator __i = begin(), __e = end(); __i != __e;)
2208 iterator __j = _VSTD::next(__i);
2209 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
2212 __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j);
2217 return (__remove_return_type) __deleted_nodes.size();
2220 template <class _Tp, class _Alloc>
2223 list<_Tp, _Alloc>::merge(list& __c)
2225 merge(__c, __less<value_type>());
2228 template <class _Tp, class _Alloc>
2229 template <class _Comp>
2231 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2233 if (this != _VSTD::addressof(__c))
2235 iterator __f1 = begin();
2236 iterator __e1 = end();
2237 iterator __f2 = __c.begin();
2238 iterator __e2 = __c.end();
2239 while (__f1 != __e1 && __f2 != __e2)
2241 if (__comp(*__f2, *__f1))
2244 iterator __m2 = _VSTD::next(__f2);
2245 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
2247 base::__sz() += __ds;
2249 __link_pointer __f = __f2.__ptr_;
2250 __link_pointer __l = __m2.__ptr_->__prev_;
2252 base::__unlink_nodes(__f, __l);
2253 __m2 = _VSTD::next(__f1);
2254 __link_nodes(__f1.__ptr_, __f, __l);
2261 #if _LIBCPP_DEBUG_LEVEL >= 2
2262 __libcpp_db* __db = __get_db();
2263 __c_node* __cn1 = __db->__find_c_and_lock(this);
2264 __c_node* __cn2 = __db->__find_c(&__c);
2265 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2268 iterator* __i = static_cast<iterator*>((*__p)->__i_);
2269 if (__i->__ptr_ != __c.__end_as_link())
2272 (*__p)->__c_ = __cn1;
2273 if (--__cn2->end_ != __p)
2274 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2282 template <class _Tp, class _Alloc>
2285 list<_Tp, _Alloc>::sort()
2287 sort(__less<value_type>());
2290 template <class _Tp, class _Alloc>
2291 template <class _Comp>
2294 list<_Tp, _Alloc>::sort(_Comp __comp)
2296 __sort(begin(), end(), base::__sz(), __comp);
2299 template <class _Tp, class _Alloc>
2300 template <class _Comp>
2301 typename list<_Tp, _Alloc>::iterator
2302 list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
2310 if (__comp(*--__e2, *__f1))
2312 __link_pointer __f = __e2.__ptr_;
2313 base::__unlink_nodes(__f, __f);
2314 __link_nodes(__f1.__ptr_, __f, __f);
2319 size_type __n2 = __n / 2;
2320 iterator __e1 = _VSTD::next(__f1, __n2);
2321 iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp);
2322 iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2323 if (__comp(*__f2, *__f1))
2325 iterator __m2 = _VSTD::next(__f2);
2326 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2328 __link_pointer __f = __f2.__ptr_;
2329 __link_pointer __l = __m2.__ptr_->__prev_;
2332 base::__unlink_nodes(__f, __l);
2333 __m2 = _VSTD::next(__f1);
2334 __link_nodes(__f1.__ptr_, __f, __l);
2339 while (__f1 != __e1 && __f2 != __e2)
2341 if (__comp(*__f2, *__f1))
2343 iterator __m2 = _VSTD::next(__f2);
2344 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2346 __link_pointer __f = __f2.__ptr_;
2347 __link_pointer __l = __m2.__ptr_->__prev_;
2351 base::__unlink_nodes(__f, __l);
2352 __m2 = _VSTD::next(__f1);
2353 __link_nodes(__f1.__ptr_, __f, __l);
2362 template <class _Tp, class _Alloc>
2364 list<_Tp, _Alloc>::reverse() _NOEXCEPT
2366 if (base::__sz() > 1)
2368 iterator __e = end();
2369 for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
2371 _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
2372 __i.__ptr_ = __i.__ptr_->__prev_;
2374 _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
2378 template <class _Tp, class _Alloc>
2380 list<_Tp, _Alloc>::__invariants() const
2382 return size() == _VSTD::distance(begin(), end());
2385 #if _LIBCPP_DEBUG_LEVEL >= 2
2387 template <class _Tp, class _Alloc>
2389 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
2391 return __i->__ptr_ != this->__end_as_link();
2394 template <class _Tp, class _Alloc>
2396 list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
2398 return !empty() && __i->__ptr_ != base::__end_.__next_;
2401 template <class _Tp, class _Alloc>
2403 list<_Tp, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2408 template <class _Tp, class _Alloc>
2410 list<_Tp, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2415 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2417 template <class _Tp, class _Alloc>
2418 inline _LIBCPP_INLINE_VISIBILITY
2420 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2422 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2425 template <class _Tp, class _Alloc>
2426 inline _LIBCPP_INLINE_VISIBILITY
2428 operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2430 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2433 template <class _Tp, class _Alloc>
2434 inline _LIBCPP_INLINE_VISIBILITY
2436 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2438 return !(__x == __y);
2441 template <class _Tp, class _Alloc>
2442 inline _LIBCPP_INLINE_VISIBILITY
2444 operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2449 template <class _Tp, class _Alloc>
2450 inline _LIBCPP_INLINE_VISIBILITY
2452 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2454 return !(__x < __y);
2457 template <class _Tp, class _Alloc>
2458 inline _LIBCPP_INLINE_VISIBILITY
2460 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2462 return !(__y < __x);
2465 template <class _Tp, class _Alloc>
2466 inline _LIBCPP_INLINE_VISIBILITY
2468 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2469 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2474 #if _LIBCPP_STD_VER > 17
2475 template <class _Tp, class _Allocator, class _Predicate>
2476 inline _LIBCPP_INLINE_VISIBILITY typename list<_Tp, _Allocator>::size_type
2477 erase_if(list<_Tp, _Allocator>& __c, _Predicate __pred) {
2478 return __c.remove_if(__pred);
2481 template <class _Tp, class _Allocator, class _Up>
2482 inline _LIBCPP_INLINE_VISIBILITY typename list<_Tp, _Allocator>::size_type
2483 erase(list<_Tp, _Allocator>& __c, const _Up& __v) {
2484 return _VSTD::erase_if(__c, [&](auto& __elem) { return __elem == __v; });
2488 _LIBCPP_END_NAMESPACE_STD
2492 #endif // _LIBCPP_LIST