2 //===---------------------------- list ------------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
20 template <class T, class Alloc = allocator<T> >
27 typedef Alloc allocator_type;
28 typedef typename allocator_type::reference reference;
29 typedef typename allocator_type::const_reference const_reference;
30 typedef typename allocator_type::pointer pointer;
31 typedef typename allocator_type::const_pointer const_pointer;
32 typedef implementation-defined iterator;
33 typedef implementation-defined const_iterator;
34 typedef implementation-defined size_type;
35 typedef implementation-defined difference_type;
36 typedef reverse_iterator<iterator> reverse_iterator;
37 typedef reverse_iterator<const_iterator> const_reverse_iterator;
40 noexcept(is_nothrow_default_constructible<allocator_type>::value);
41 explicit list(const allocator_type& a);
42 explicit list(size_type n);
43 explicit list(size_type n, const allocator_type& a); // C++14
44 list(size_type n, const value_type& value);
45 list(size_type n, const value_type& value, const allocator_type& a);
47 list(Iter first, Iter last);
49 list(Iter first, Iter last, const allocator_type& a);
51 list(const list&, const allocator_type& a);
53 noexcept(is_nothrow_move_constructible<allocator_type>::value);
54 list(list&&, const allocator_type& a);
55 list(initializer_list<value_type>);
56 list(initializer_list<value_type>, const allocator_type& a);
60 list& operator=(const list& x);
61 list& operator=(list&& x)
63 allocator_type::propagate_on_container_move_assignment::value &&
64 is_nothrow_move_assignable<allocator_type>::value);
65 list& operator=(initializer_list<value_type>);
67 void assign(Iter first, Iter last);
68 void assign(size_type n, const value_type& t);
69 void assign(initializer_list<value_type>);
71 allocator_type get_allocator() const noexcept;
73 iterator begin() noexcept;
74 const_iterator begin() const noexcept;
75 iterator end() noexcept;
76 const_iterator end() const noexcept;
77 reverse_iterator rbegin() noexcept;
78 const_reverse_iterator rbegin() const noexcept;
79 reverse_iterator rend() noexcept;
80 const_reverse_iterator rend() const noexcept;
81 const_iterator cbegin() const noexcept;
82 const_iterator cend() const noexcept;
83 const_reverse_iterator crbegin() const noexcept;
84 const_reverse_iterator crend() const noexcept;
87 const_reference front() const;
89 const_reference back() const;
91 bool empty() const noexcept;
92 size_type size() const noexcept;
93 size_type max_size() const noexcept;
95 template <class... Args>
96 void emplace_front(Args&&... args);
98 template <class... Args>
99 void emplace_back(Args&&... args);
101 void push_front(const value_type& x);
102 void push_front(value_type&& x);
103 void push_back(const value_type& x);
104 void push_back(value_type&& x);
105 template <class... Args>
106 iterator emplace(const_iterator position, Args&&... args);
107 iterator insert(const_iterator position, const value_type& x);
108 iterator insert(const_iterator position, value_type&& x);
109 iterator insert(const_iterator position, size_type n, const value_type& x);
110 template <class Iter>
111 iterator insert(const_iterator position, Iter first, Iter last);
112 iterator insert(const_iterator position, initializer_list<value_type> il);
114 iterator erase(const_iterator position);
115 iterator erase(const_iterator position, const_iterator last);
117 void resize(size_type sz);
118 void resize(size_type sz, const value_type& c);
121 noexcept(!allocator_type::propagate_on_container_swap::value ||
122 __is_nothrow_swappable<allocator_type>::value);
123 void clear() noexcept;
125 void splice(const_iterator position, list& x);
126 void splice(const_iterator position, list&& x);
127 void splice(const_iterator position, list& x, const_iterator i);
128 void splice(const_iterator position, list&& x, const_iterator i);
129 void splice(const_iterator position, list& x, const_iterator first,
130 const_iterator last);
131 void splice(const_iterator position, list&& x, const_iterator first,
132 const_iterator last);
134 void remove(const value_type& value);
135 template <class Pred> void remove_if(Pred pred);
137 template <class BinaryPredicate>
138 void unique(BinaryPredicate binary_pred);
140 void merge(list&& x);
141 template <class Compare>
142 void merge(list& x, Compare comp);
143 template <class Compare>
144 void merge(list&& x, Compare comp);
146 template <class Compare>
147 void sort(Compare comp);
148 void reverse() noexcept;
151 template <class T, class Alloc>
152 bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
153 template <class T, class Alloc>
154 bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);
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);
164 template <class T, class Alloc>
165 void swap(list<T,Alloc>& x, list<T,Alloc>& y)
166 noexcept(noexcept(x.swap(y)));
176 #include <initializer_list>
180 #include <__undef_min_max>
185 # define _LIBCPP_ASSERT(x, m) ((void)0)
188 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
189 #pragma GCC system_header
192 _LIBCPP_BEGIN_NAMESPACE_STD
194 template <class _Tp, class _VoidPtr> struct __list_node;
196 template <class _Tp, class _VoidPtr>
197 struct __list_node_base
199 typedef typename pointer_traits<_VoidPtr>::template
200 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
201 rebind<__list_node<_Tp, _VoidPtr> > pointer;
203 rebind<__list_node<_Tp, _VoidPtr> >::other pointer;
206 typedef typename pointer_traits<_VoidPtr>::template
207 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
208 rebind<__list_node_base> __base_pointer;
210 rebind<__list_node_base>::other __base_pointer;
216 _LIBCPP_INLINE_VISIBILITY
218 : __prev_(static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this))),
219 __next_(static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this)))
223 template <class _Tp, class _VoidPtr>
225 : public __list_node_base<_Tp, _VoidPtr>
230 template <class _Tp, class _Alloc> class _LIBCPP_TYPE_VIS_ONLY list;
231 template <class _Tp, class _Alloc> class __list_imp;
232 template <class _Tp, class _VoidPtr> class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator;
234 template <class _Tp, class _VoidPtr>
235 class _LIBCPP_TYPE_VIS_ONLY __list_iterator
237 typedef typename pointer_traits<_VoidPtr>::template
238 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
239 rebind<__list_node<_Tp, _VoidPtr> > __node_pointer;
241 rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer;
244 __node_pointer __ptr_;
246 #if _LIBCPP_DEBUG_LEVEL >= 2
247 _LIBCPP_INLINE_VISIBILITY
248 explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
251 __get_db()->__insert_ic(this, __c);
254 _LIBCPP_INLINE_VISIBILITY
255 explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
260 template<class, class> friend class list;
261 template<class, class> friend class __list_imp;
262 template<class, class> friend class __list_const_iterator;
264 typedef bidirectional_iterator_tag iterator_category;
265 typedef _Tp value_type;
266 typedef value_type& reference;
267 typedef typename pointer_traits<_VoidPtr>::template
268 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
271 rebind<value_type>::other
274 typedef typename pointer_traits<pointer>::difference_type difference_type;
276 _LIBCPP_INLINE_VISIBILITY
277 __list_iterator() _NOEXCEPT : __ptr_(nullptr)
279 #if _LIBCPP_DEBUG_LEVEL >= 2
280 __get_db()->__insert_i(this);
284 #if _LIBCPP_DEBUG_LEVEL >= 2
286 _LIBCPP_INLINE_VISIBILITY
287 __list_iterator(const __list_iterator& __p)
290 __get_db()->__iterator_copy(this, &__p);
293 _LIBCPP_INLINE_VISIBILITY
296 __get_db()->__erase_i(this);
299 _LIBCPP_INLINE_VISIBILITY
300 __list_iterator& operator=(const __list_iterator& __p)
304 __get_db()->__iterator_copy(this, &__p);
310 #endif // _LIBCPP_DEBUG_LEVEL >= 2
312 _LIBCPP_INLINE_VISIBILITY
313 reference operator*() const
315 #if _LIBCPP_DEBUG_LEVEL >= 2
316 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
317 "Attempted to dereference a non-dereferenceable list::iterator");
319 return __ptr_->__value_;
321 _LIBCPP_INLINE_VISIBILITY
322 pointer operator->() const
324 #if _LIBCPP_DEBUG_LEVEL >= 2
325 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
326 "Attempted to dereference a non-dereferenceable list::iterator");
328 return pointer_traits<pointer>::pointer_to(__ptr_->__value_);
331 _LIBCPP_INLINE_VISIBILITY
332 __list_iterator& operator++()
334 #if _LIBCPP_DEBUG_LEVEL >= 2
335 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
336 "Attempted to increment non-incrementable list::iterator");
338 __ptr_ = __ptr_->__next_;
341 _LIBCPP_INLINE_VISIBILITY
342 __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;}
344 _LIBCPP_INLINE_VISIBILITY
345 __list_iterator& operator--()
347 #if _LIBCPP_DEBUG_LEVEL >= 2
348 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
349 "Attempted to decrement non-decrementable list::iterator");
351 __ptr_ = __ptr_->__prev_;
354 _LIBCPP_INLINE_VISIBILITY
355 __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}
357 friend _LIBCPP_INLINE_VISIBILITY
358 bool operator==(const __list_iterator& __x, const __list_iterator& __y)
360 return __x.__ptr_ == __y.__ptr_;
362 friend _LIBCPP_INLINE_VISIBILITY
363 bool operator!=(const __list_iterator& __x, const __list_iterator& __y)
364 {return !(__x == __y);}
367 template <class _Tp, class _VoidPtr>
368 class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator
370 typedef typename pointer_traits<_VoidPtr>::template
371 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
372 rebind<__list_node<_Tp, _VoidPtr> > __node_pointer;
374 rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer;
377 __node_pointer __ptr_;
379 #if _LIBCPP_DEBUG_LEVEL >= 2
380 _LIBCPP_INLINE_VISIBILITY
381 explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
384 __get_db()->__insert_ic(this, __c);
387 _LIBCPP_INLINE_VISIBILITY
388 explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
391 template<class, class> friend class list;
392 template<class, class> friend class __list_imp;
394 typedef bidirectional_iterator_tag iterator_category;
395 typedef _Tp value_type;
396 typedef const value_type& reference;
397 typedef typename pointer_traits<_VoidPtr>::template
398 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
399 rebind<const value_type>
401 rebind<const value_type>::other
404 typedef typename pointer_traits<pointer>::difference_type difference_type;
406 _LIBCPP_INLINE_VISIBILITY
407 __list_const_iterator() _NOEXCEPT : __ptr_(nullptr)
409 #if _LIBCPP_DEBUG_LEVEL >= 2
410 __get_db()->__insert_i(this);
413 _LIBCPP_INLINE_VISIBILITY
414 __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT
417 #if _LIBCPP_DEBUG_LEVEL >= 2
418 __get_db()->__iterator_copy(this, &__p);
422 #if _LIBCPP_DEBUG_LEVEL >= 2
424 _LIBCPP_INLINE_VISIBILITY
425 __list_const_iterator(const __list_const_iterator& __p)
428 __get_db()->__iterator_copy(this, &__p);
431 _LIBCPP_INLINE_VISIBILITY
432 ~__list_const_iterator()
434 __get_db()->__erase_i(this);
437 _LIBCPP_INLINE_VISIBILITY
438 __list_const_iterator& operator=(const __list_const_iterator& __p)
442 __get_db()->__iterator_copy(this, &__p);
448 #endif // _LIBCPP_DEBUG_LEVEL >= 2
449 _LIBCPP_INLINE_VISIBILITY
450 reference operator*() const
452 #if _LIBCPP_DEBUG_LEVEL >= 2
453 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
454 "Attempted to dereference a non-dereferenceable list::const_iterator");
456 return __ptr_->__value_;
458 _LIBCPP_INLINE_VISIBILITY
459 pointer operator->() const
461 #if _LIBCPP_DEBUG_LEVEL >= 2
462 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
463 "Attempted to dereference a non-dereferenceable list::iterator");
465 return pointer_traits<pointer>::pointer_to(__ptr_->__value_);
468 _LIBCPP_INLINE_VISIBILITY
469 __list_const_iterator& operator++()
471 #if _LIBCPP_DEBUG_LEVEL >= 2
472 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
473 "Attempted to increment non-incrementable list::const_iterator");
475 __ptr_ = __ptr_->__next_;
478 _LIBCPP_INLINE_VISIBILITY
479 __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;}
481 _LIBCPP_INLINE_VISIBILITY
482 __list_const_iterator& operator--()
484 #if _LIBCPP_DEBUG_LEVEL >= 2
485 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
486 "Attempted to decrement non-decrementable list::const_iterator");
488 __ptr_ = __ptr_->__prev_;
491 _LIBCPP_INLINE_VISIBILITY
492 __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}
494 friend _LIBCPP_INLINE_VISIBILITY
495 bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y)
497 return __x.__ptr_ == __y.__ptr_;
499 friend _LIBCPP_INLINE_VISIBILITY
500 bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y)
501 {return !(__x == __y);}
504 template <class _Tp, class _Alloc>
507 __list_imp(const __list_imp&);
508 __list_imp& operator=(const __list_imp&);
510 typedef _Tp value_type;
511 typedef _Alloc allocator_type;
512 typedef allocator_traits<allocator_type> __alloc_traits;
513 typedef typename __alloc_traits::size_type size_type;
514 typedef typename __alloc_traits::void_pointer __void_pointer;
515 typedef __list_iterator<value_type, __void_pointer> iterator;
516 typedef __list_const_iterator<value_type, __void_pointer> const_iterator;
517 typedef __list_node_base<value_type, __void_pointer> __node_base;
518 typedef __list_node<value_type, __void_pointer> __node;
519 typedef typename __alloc_traits::template
520 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
523 rebind_alloc<__node>::other
526 typedef allocator_traits<__node_allocator> __node_alloc_traits;
527 typedef typename __node_alloc_traits::pointer __node_pointer;
528 typedef typename __node_alloc_traits::pointer __node_const_pointer;
529 typedef typename __alloc_traits::pointer pointer;
530 typedef typename __alloc_traits::const_pointer const_pointer;
531 typedef typename __alloc_traits::difference_type difference_type;
533 typedef typename __alloc_traits::template
534 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
535 rebind_alloc<__node_base>
537 rebind_alloc<__node_base>::other
539 __node_base_allocator;
540 typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
543 __compressed_pair<size_type, __node_allocator> __size_alloc_;
545 _LIBCPP_INLINE_VISIBILITY
546 size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
547 _LIBCPP_INLINE_VISIBILITY
548 const size_type& __sz() const _NOEXCEPT
549 {return __size_alloc_.first();}
550 _LIBCPP_INLINE_VISIBILITY
551 __node_allocator& __node_alloc() _NOEXCEPT
552 {return __size_alloc_.second();}
553 _LIBCPP_INLINE_VISIBILITY
554 const __node_allocator& __node_alloc() const _NOEXCEPT
555 {return __size_alloc_.second();}
557 static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT;
560 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
561 __list_imp(const allocator_type& __a);
563 void clear() _NOEXCEPT;
564 _LIBCPP_INLINE_VISIBILITY
565 bool empty() const _NOEXCEPT {return __sz() == 0;}
567 _LIBCPP_INLINE_VISIBILITY
568 iterator begin() _NOEXCEPT
570 #if _LIBCPP_DEBUG_LEVEL >= 2
571 return iterator(__end_.__next_, this);
573 return iterator(__end_.__next_);
576 _LIBCPP_INLINE_VISIBILITY
577 const_iterator begin() const _NOEXCEPT
579 #if _LIBCPP_DEBUG_LEVEL >= 2
580 return const_iterator(__end_.__next_, this);
582 return const_iterator(__end_.__next_);
585 _LIBCPP_INLINE_VISIBILITY
586 iterator end() _NOEXCEPT
588 #if _LIBCPP_DEBUG_LEVEL >= 2
589 return iterator(static_cast<__node_pointer>(
590 pointer_traits<__node_base_pointer>::pointer_to(__end_)), this);
592 return iterator(static_cast<__node_pointer>(
593 pointer_traits<__node_base_pointer>::pointer_to(__end_)));
596 _LIBCPP_INLINE_VISIBILITY
597 const_iterator end() const _NOEXCEPT
599 #if _LIBCPP_DEBUG_LEVEL >= 2
600 return const_iterator(static_cast<__node_const_pointer>(
601 pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))), this);
603 return const_iterator(static_cast<__node_const_pointer>(
604 pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))));
608 void swap(__list_imp& __c)
609 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
610 __is_nothrow_swappable<__node_allocator>::value);
612 _LIBCPP_INLINE_VISIBILITY
613 void __copy_assign_alloc(const __list_imp& __c)
614 {__copy_assign_alloc(__c, integral_constant<bool,
615 __node_alloc_traits::propagate_on_container_copy_assignment::value>());}
617 _LIBCPP_INLINE_VISIBILITY
618 void __move_assign_alloc(__list_imp& __c)
620 !__node_alloc_traits::propagate_on_container_move_assignment::value ||
621 is_nothrow_move_assignable<__node_allocator>::value)
622 {__move_assign_alloc(__c, integral_constant<bool,
623 __node_alloc_traits::propagate_on_container_move_assignment::value>());}
626 _LIBCPP_INLINE_VISIBILITY
627 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y)
628 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
629 __is_nothrow_swappable<__node_allocator>::value)
630 {__swap_alloc(__x, __y, integral_constant<bool,
631 __node_alloc_traits::propagate_on_container_swap::value>());}
632 _LIBCPP_INLINE_VISIBILITY
633 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type)
634 _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value)
639 _LIBCPP_INLINE_VISIBILITY
640 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type)
644 _LIBCPP_INLINE_VISIBILITY
645 void __copy_assign_alloc(const __list_imp& __c, true_type)
647 if (__node_alloc() != __c.__node_alloc())
649 __node_alloc() = __c.__node_alloc();
652 _LIBCPP_INLINE_VISIBILITY
653 void __copy_assign_alloc(const __list_imp& __c, false_type)
656 _LIBCPP_INLINE_VISIBILITY
657 void __move_assign_alloc(__list_imp& __c, true_type)
658 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
660 __node_alloc() = _VSTD::move(__c.__node_alloc());
663 _LIBCPP_INLINE_VISIBILITY
664 void __move_assign_alloc(__list_imp& __c, false_type)
669 // Unlink nodes [__f, __l]
670 template <class _Tp, class _Alloc>
671 inline _LIBCPP_INLINE_VISIBILITY
673 __list_imp<_Tp, _Alloc>::__unlink_nodes(__node_pointer __f, __node_pointer __l)
676 __f->__prev_->__next_ = __l->__next_;
677 __l->__next_->__prev_ = __f->__prev_;
680 template <class _Tp, class _Alloc>
681 inline _LIBCPP_INLINE_VISIBILITY
682 __list_imp<_Tp, _Alloc>::__list_imp()
683 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
688 template <class _Tp, class _Alloc>
689 inline _LIBCPP_INLINE_VISIBILITY
690 __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a)
691 : __size_alloc_(0, __node_allocator(__a))
695 template <class _Tp, class _Alloc>
696 __list_imp<_Tp, _Alloc>::~__list_imp()
699 #if _LIBCPP_DEBUG_LEVEL >= 2
700 __get_db()->__erase_c(this);
704 template <class _Tp, class _Alloc>
706 __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
710 __node_allocator& __na = __node_alloc();
711 __node_pointer __f = __end_.__next_;
712 __node_pointer __l = static_cast<__node_pointer>(
713 pointer_traits<__node_base_pointer>::pointer_to(__end_));
714 __unlink_nodes(__f, __l->__prev_);
718 __node_pointer __n = __f;
720 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
721 __node_alloc_traits::deallocate(__na, __n, 1);
723 #if _LIBCPP_DEBUG_LEVEL >= 2
724 __c_node* __c = __get_db()->__find_c_and_lock(this);
725 for (__i_node** __p = __c->end_; __p != __c->beg_; )
728 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
729 if (__i->__ptr_ != __l)
731 (*__p)->__c_ = nullptr;
732 if (--__c->end_ != __p)
733 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
736 __get_db()->unlock();
741 template <class _Tp, class _Alloc>
743 __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
744 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
745 __is_nothrow_swappable<__node_allocator>::value)
747 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
748 this->__node_alloc() == __c.__node_alloc(),
749 "list::swap: Either propagate_on_container_swap must be true"
750 " or the allocators must compare equal");
752 __swap_alloc(__node_alloc(), __c.__node_alloc());
753 swap(__sz(), __c.__sz());
754 swap(__end_, __c.__end_);
756 __end_.__next_ = __end_.__prev_ = static_cast<__node_pointer>(
757 pointer_traits<__node_base_pointer>::pointer_to(__end_));
759 __end_.__prev_->__next_ = __end_.__next_->__prev_
760 = static_cast<__node_pointer>(
761 pointer_traits<__node_base_pointer>::pointer_to(__end_));
763 __c.__end_.__next_ = __c.__end_.__prev_
764 = static_cast<__node_pointer>(
765 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_));
767 __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_
768 = static_cast<__node_pointer>(
769 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_));
770 #if _LIBCPP_DEBUG_LEVEL >= 2
771 __libcpp_db* __db = __get_db();
772 __c_node* __cn1 = __db->__find_c_and_lock(this);
773 __c_node* __cn2 = __db->__find_c(&__c);
774 std::swap(__cn1->beg_, __cn2->beg_);
775 std::swap(__cn1->end_, __cn2->end_);
776 std::swap(__cn1->cap_, __cn2->cap_);
777 for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;)
780 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
781 if (__i->__ptr_ == static_cast<__node_pointer>(
782 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
785 if (--__cn1->end_ != __p)
786 memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*));
789 (*__p)->__c_ = __cn1;
791 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
794 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
795 if (__i->__ptr_ == static_cast<__node_pointer>(
796 pointer_traits<__node_base_pointer>::pointer_to(__end_)))
799 if (--__cn2->end_ != __p)
800 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
803 (*__p)->__c_ = __cn2;
809 template <class _Tp, class _Alloc = allocator<_Tp> >
810 class _LIBCPP_TYPE_VIS_ONLY list
811 : private __list_imp<_Tp, _Alloc>
813 typedef __list_imp<_Tp, _Alloc> base;
814 typedef typename base::__node __node;
815 typedef typename base::__node_allocator __node_allocator;
816 typedef typename base::__node_pointer __node_pointer;
817 typedef typename base::__node_alloc_traits __node_alloc_traits;
818 typedef typename base::__node_base __node_base;
819 typedef typename base::__node_base_pointer __node_base_pointer;
822 typedef _Tp value_type;
823 typedef _Alloc allocator_type;
824 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
825 "Invalid allocator::value_type");
826 typedef value_type& reference;
827 typedef const value_type& const_reference;
828 typedef typename base::pointer pointer;
829 typedef typename base::const_pointer const_pointer;
830 typedef typename base::size_type size_type;
831 typedef typename base::difference_type difference_type;
832 typedef typename base::iterator iterator;
833 typedef typename base::const_iterator const_iterator;
834 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
835 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
837 _LIBCPP_INLINE_VISIBILITY
839 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
841 #if _LIBCPP_DEBUG_LEVEL >= 2
842 __get_db()->__insert_c(this);
845 _LIBCPP_INLINE_VISIBILITY
846 explicit list(const allocator_type& __a) : base(__a)
848 #if _LIBCPP_DEBUG_LEVEL >= 2
849 __get_db()->__insert_c(this);
852 explicit list(size_type __n);
853 #if _LIBCPP_STD_VER > 11
854 explicit list(size_type __n, const allocator_type& __a);
856 list(size_type __n, const value_type& __x);
857 list(size_type __n, const value_type& __x, const allocator_type& __a);
858 template <class _InpIter>
859 list(_InpIter __f, _InpIter __l,
860 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
861 template <class _InpIter>
862 list(_InpIter __f, _InpIter __l, const allocator_type& __a,
863 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
865 list(const list& __c);
866 list(const list& __c, const allocator_type& __a);
867 list& operator=(const list& __c);
868 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
869 list(initializer_list<value_type> __il);
870 list(initializer_list<value_type> __il, const allocator_type& __a);
871 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
872 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
874 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
875 list(list&& __c, const allocator_type& __a);
876 list& operator=(list&& __c)
878 __node_alloc_traits::propagate_on_container_move_assignment::value &&
879 is_nothrow_move_assignable<__node_allocator>::value);
880 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
881 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
882 _LIBCPP_INLINE_VISIBILITY
883 list& operator=(initializer_list<value_type> __il)
884 {assign(__il.begin(), __il.end()); return *this;}
885 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
887 template <class _InpIter>
888 void assign(_InpIter __f, _InpIter __l,
889 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
890 void assign(size_type __n, const value_type& __x);
891 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
892 _LIBCPP_INLINE_VISIBILITY
893 void assign(initializer_list<value_type> __il)
894 {assign(__il.begin(), __il.end());}
895 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
897 allocator_type get_allocator() const _NOEXCEPT;
899 _LIBCPP_INLINE_VISIBILITY
900 size_type size() const _NOEXCEPT {return base::__sz();}
901 _LIBCPP_INLINE_VISIBILITY
902 bool empty() const _NOEXCEPT {return base::empty();}
903 _LIBCPP_INLINE_VISIBILITY
904 size_type max_size() const _NOEXCEPT
905 {return numeric_limits<difference_type>::max();}
907 _LIBCPP_INLINE_VISIBILITY
908 iterator begin() _NOEXCEPT {return base::begin();}
909 _LIBCPP_INLINE_VISIBILITY
910 const_iterator begin() const _NOEXCEPT {return base::begin();}
911 _LIBCPP_INLINE_VISIBILITY
912 iterator end() _NOEXCEPT {return base::end();}
913 _LIBCPP_INLINE_VISIBILITY
914 const_iterator end() const _NOEXCEPT {return base::end();}
915 _LIBCPP_INLINE_VISIBILITY
916 const_iterator cbegin() const _NOEXCEPT {return base::begin();}
917 _LIBCPP_INLINE_VISIBILITY
918 const_iterator cend() const _NOEXCEPT {return base::end();}
920 _LIBCPP_INLINE_VISIBILITY
921 reverse_iterator rbegin() _NOEXCEPT
922 {return reverse_iterator(end());}
923 _LIBCPP_INLINE_VISIBILITY
924 const_reverse_iterator rbegin() const _NOEXCEPT
925 {return const_reverse_iterator(end());}
926 _LIBCPP_INLINE_VISIBILITY
927 reverse_iterator rend() _NOEXCEPT
928 {return reverse_iterator(begin());}
929 _LIBCPP_INLINE_VISIBILITY
930 const_reverse_iterator rend() const _NOEXCEPT
931 {return const_reverse_iterator(begin());}
932 _LIBCPP_INLINE_VISIBILITY
933 const_reverse_iterator crbegin() const _NOEXCEPT
934 {return const_reverse_iterator(end());}
935 _LIBCPP_INLINE_VISIBILITY
936 const_reverse_iterator crend() const _NOEXCEPT
937 {return const_reverse_iterator(begin());}
939 _LIBCPP_INLINE_VISIBILITY
942 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
943 return base::__end_.__next_->__value_;
945 _LIBCPP_INLINE_VISIBILITY
946 const_reference front() const
948 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
949 return base::__end_.__next_->__value_;
951 _LIBCPP_INLINE_VISIBILITY
954 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
955 return base::__end_.__prev_->__value_;
957 _LIBCPP_INLINE_VISIBILITY
958 const_reference back() const
960 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
961 return base::__end_.__prev_->__value_;
964 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
965 void push_front(value_type&& __x);
966 void push_back(value_type&& __x);
967 #ifndef _LIBCPP_HAS_NO_VARIADICS
968 template <class... _Args>
969 void emplace_front(_Args&&... __args);
970 template <class... _Args>
971 void emplace_back(_Args&&... __args);
972 template <class... _Args>
973 iterator emplace(const_iterator __p, _Args&&... __args);
974 #endif // _LIBCPP_HAS_NO_VARIADICS
975 iterator insert(const_iterator __p, value_type&& __x);
976 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
978 void push_front(const value_type& __x);
979 void push_back(const value_type& __x);
981 iterator insert(const_iterator __p, const value_type& __x);
982 iterator insert(const_iterator __p, size_type __n, const value_type& __x);
983 template <class _InpIter>
984 iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
985 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
986 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
987 _LIBCPP_INLINE_VISIBILITY
988 iterator insert(const_iterator __p, initializer_list<value_type> __il)
989 {return insert(__p, __il.begin(), __il.end());}
990 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
992 _LIBCPP_INLINE_VISIBILITY
994 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
995 __is_nothrow_swappable<__node_allocator>::value)
997 _LIBCPP_INLINE_VISIBILITY
998 void clear() _NOEXCEPT {base::clear();}
1003 iterator erase(const_iterator __p);
1004 iterator erase(const_iterator __f, const_iterator __l);
1006 void resize(size_type __n);
1007 void resize(size_type __n, const value_type& __x);
1009 void splice(const_iterator __p, list& __c);
1010 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1011 _LIBCPP_INLINE_VISIBILITY
1012 void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
1014 void splice(const_iterator __p, list& __c, const_iterator __i);
1015 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1016 _LIBCPP_INLINE_VISIBILITY
1017 void splice(const_iterator __p, list&& __c, const_iterator __i)
1018 {splice(__p, __c, __i);}
1019 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1020 void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
1021 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1022 _LIBCPP_INLINE_VISIBILITY
1023 void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
1024 {splice(__p, __c, __f, __l);}
1025 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1027 void remove(const value_type& __x);
1028 template <class _Pred> void remove_if(_Pred __pred);
1030 template <class _BinaryPred>
1031 void unique(_BinaryPred __binary_pred);
1032 void merge(list& __c);
1033 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1034 _LIBCPP_INLINE_VISIBILITY
1035 void merge(list&& __c) {merge(__c);}
1037 template <class _Comp>
1038 void merge(list& __c, _Comp __comp);
1039 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1040 template <class _Comp>
1041 _LIBCPP_INLINE_VISIBILITY
1042 void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
1043 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1045 template <class _Comp>
1046 void sort(_Comp __comp);
1048 void reverse() _NOEXCEPT;
1050 bool __invariants() const;
1052 #if _LIBCPP_DEBUG_LEVEL >= 2
1054 bool __dereferenceable(const const_iterator* __i) const;
1055 bool __decrementable(const const_iterator* __i) const;
1056 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1057 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1059 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1062 static void __link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l);
1063 iterator __iterator(size_type __n);
1064 template <class _Comp>
1065 static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
1067 void __move_assign(list& __c, true_type)
1068 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
1069 void __move_assign(list& __c, false_type);
1072 // Link in nodes [__f, __l] just prior to __p
1073 template <class _Tp, class _Alloc>
1074 inline _LIBCPP_INLINE_VISIBILITY
1076 list<_Tp, _Alloc>::__link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l)
1078 __p->__prev_->__next_ = __f;
1079 __f->__prev_ = __p->__prev_;
1084 template <class _Tp, class _Alloc>
1085 inline _LIBCPP_INLINE_VISIBILITY
1086 typename list<_Tp, _Alloc>::iterator
1087 list<_Tp, _Alloc>::__iterator(size_type __n)
1089 return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n)
1090 : _VSTD::prev(end(), base::__sz() - __n);
1093 template <class _Tp, class _Alloc>
1094 list<_Tp, _Alloc>::list(size_type __n)
1096 #if _LIBCPP_DEBUG_LEVEL >= 2
1097 __get_db()->__insert_c(this);
1099 for (; __n > 0; --__n)
1100 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1103 push_back(value_type());
1107 #if _LIBCPP_STD_VER > 11
1108 template <class _Tp, class _Alloc>
1109 list<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a)
1111 #if _LIBCPP_DEBUG_LEVEL >= 2
1112 __get_db()->__insert_c(this);
1114 for (; __n > 0; --__n)
1115 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1118 push_back(value_type());
1123 template <class _Tp, class _Alloc>
1124 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x)
1126 #if _LIBCPP_DEBUG_LEVEL >= 2
1127 __get_db()->__insert_c(this);
1129 for (; __n > 0; --__n)
1133 template <class _Tp, class _Alloc>
1134 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a)
1137 #if _LIBCPP_DEBUG_LEVEL >= 2
1138 __get_db()->__insert_c(this);
1140 for (; __n > 0; --__n)
1144 template <class _Tp, class _Alloc>
1145 template <class _InpIter>
1146 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
1147 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1149 #if _LIBCPP_DEBUG_LEVEL >= 2
1150 __get_db()->__insert_c(this);
1152 for (; __f != __l; ++__f)
1156 template <class _Tp, class _Alloc>
1157 template <class _InpIter>
1158 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
1159 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1162 #if _LIBCPP_DEBUG_LEVEL >= 2
1163 __get_db()->__insert_c(this);
1165 for (; __f != __l; ++__f)
1169 template <class _Tp, class _Alloc>
1170 list<_Tp, _Alloc>::list(const list& __c)
1171 : base(allocator_type(
1172 __node_alloc_traits::select_on_container_copy_construction(
1173 __c.__node_alloc())))
1175 #if _LIBCPP_DEBUG_LEVEL >= 2
1176 __get_db()->__insert_c(this);
1178 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1182 template <class _Tp, class _Alloc>
1183 list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a)
1186 #if _LIBCPP_DEBUG_LEVEL >= 2
1187 __get_db()->__insert_c(this);
1189 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1193 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1195 template <class _Tp, class _Alloc>
1196 list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a)
1199 #if _LIBCPP_DEBUG_LEVEL >= 2
1200 __get_db()->__insert_c(this);
1202 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1203 __e = __il.end(); __i != __e; ++__i)
1207 template <class _Tp, class _Alloc>
1208 list<_Tp, _Alloc>::list(initializer_list<value_type> __il)
1210 #if _LIBCPP_DEBUG_LEVEL >= 2
1211 __get_db()->__insert_c(this);
1213 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1214 __e = __il.end(); __i != __e; ++__i)
1218 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1220 template <class _Tp, class _Alloc>
1221 inline _LIBCPP_INLINE_VISIBILITY
1223 list<_Tp, _Alloc>::operator=(const list& __c)
1227 base::__copy_assign_alloc(__c);
1228 assign(__c.begin(), __c.end());
1233 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1235 template <class _Tp, class _Alloc>
1236 inline _LIBCPP_INLINE_VISIBILITY
1237 list<_Tp, _Alloc>::list(list&& __c)
1238 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
1239 : base(allocator_type(_VSTD::move(__c.__node_alloc())))
1241 #if _LIBCPP_DEBUG_LEVEL >= 2
1242 __get_db()->__insert_c(this);
1247 template <class _Tp, class _Alloc>
1248 inline _LIBCPP_INLINE_VISIBILITY
1249 list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a)
1252 #if _LIBCPP_DEBUG_LEVEL >= 2
1253 __get_db()->__insert_c(this);
1255 if (__a == __c.get_allocator())
1259 typedef move_iterator<iterator> _Ip;
1260 assign(_Ip(__c.begin()), _Ip(__c.end()));
1264 template <class _Tp, class _Alloc>
1265 inline _LIBCPP_INLINE_VISIBILITY
1267 list<_Tp, _Alloc>::operator=(list&& __c)
1269 __node_alloc_traits::propagate_on_container_move_assignment::value &&
1270 is_nothrow_move_assignable<__node_allocator>::value)
1272 __move_assign(__c, integral_constant<bool,
1273 __node_alloc_traits::propagate_on_container_move_assignment::value>());
1277 template <class _Tp, class _Alloc>
1279 list<_Tp, _Alloc>::__move_assign(list& __c, false_type)
1281 if (base::__node_alloc() != __c.__node_alloc())
1283 typedef move_iterator<iterator> _Ip;
1284 assign(_Ip(__c.begin()), _Ip(__c.end()));
1287 __move_assign(__c, true_type());
1290 template <class _Tp, class _Alloc>
1292 list<_Tp, _Alloc>::__move_assign(list& __c, true_type)
1293 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1296 base::__move_assign_alloc(__c);
1300 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1302 template <class _Tp, class _Alloc>
1303 template <class _InpIter>
1305 list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l,
1306 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1308 iterator __i = begin();
1309 iterator __e = end();
1310 for (; __f != __l && __i != __e; ++__f, ++__i)
1313 insert(__e, __f, __l);
1318 template <class _Tp, class _Alloc>
1320 list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x)
1322 iterator __i = begin();
1323 iterator __e = end();
1324 for (; __n > 0 && __i != __e; --__n, ++__i)
1327 insert(__e, __n, __x);
1332 template <class _Tp, class _Alloc>
1333 inline _LIBCPP_INLINE_VISIBILITY
1335 list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT
1337 return allocator_type(base::__node_alloc());
1340 template <class _Tp, class _Alloc>
1341 typename list<_Tp, _Alloc>::iterator
1342 list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
1344 #if _LIBCPP_DEBUG_LEVEL >= 2
1345 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1346 "list::insert(iterator, x) called with an iterator not"
1347 " referring to this list");
1349 __node_allocator& __na = base::__node_alloc();
1350 typedef __allocator_destructor<__node_allocator> _Dp;
1351 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1352 __hold->__prev_ = 0;
1353 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1354 __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
1356 #if _LIBCPP_DEBUG_LEVEL >= 2
1357 return iterator(__hold.release(), this);
1359 return iterator(__hold.release());
1363 template <class _Tp, class _Alloc>
1364 typename list<_Tp, _Alloc>::iterator
1365 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
1367 #if _LIBCPP_DEBUG_LEVEL >= 2
1368 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1369 "list::insert(iterator, n, x) called with an iterator not"
1370 " referring to this list");
1371 iterator __r(__p.__ptr_, this);
1373 iterator __r(__p.__ptr_);
1378 __node_allocator& __na = base::__node_alloc();
1379 typedef __allocator_destructor<__node_allocator> _Dp;
1380 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1381 __hold->__prev_ = 0;
1382 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1384 #if _LIBCPP_DEBUG_LEVEL >= 2
1385 __r = iterator(__hold.get(), this);
1387 __r = iterator(__hold.get());
1391 #ifndef _LIBCPP_NO_EXCEPTIONS
1394 #endif // _LIBCPP_NO_EXCEPTIONS
1395 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1397 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1398 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1399 __e.__ptr_->__next_ = __hold.get();
1400 __hold->__prev_ = __e.__ptr_;
1403 #ifndef _LIBCPP_NO_EXCEPTIONS
1409 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1410 __node_pointer __prev = __e.__ptr_->__prev_;
1411 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1414 #if _LIBCPP_DEBUG_LEVEL >= 2
1415 __e = iterator(__prev, this);
1417 __e = iterator(__prev);
1422 #endif // _LIBCPP_NO_EXCEPTIONS
1423 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1424 base::__sz() += __ds;
1429 template <class _Tp, class _Alloc>
1430 template <class _InpIter>
1431 typename list<_Tp, _Alloc>::iterator
1432 list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
1433 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1435 #if _LIBCPP_DEBUG_LEVEL >= 2
1436 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1437 "list::insert(iterator, range) called with an iterator not"
1438 " referring to this list");
1439 iterator __r(__p.__ptr_, this);
1441 iterator __r(__p.__ptr_);
1446 __node_allocator& __na = base::__node_alloc();
1447 typedef __allocator_destructor<__node_allocator> _Dp;
1448 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1449 __hold->__prev_ = 0;
1450 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1452 #if _LIBCPP_DEBUG_LEVEL >= 2
1453 __r = iterator(__hold.get(), this);
1455 __r = iterator(__hold.get());
1459 #ifndef _LIBCPP_NO_EXCEPTIONS
1462 #endif // _LIBCPP_NO_EXCEPTIONS
1463 for (++__f; __f != __l; ++__f, ++__e, ++__ds)
1465 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1466 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1467 __e.__ptr_->__next_ = __hold.get();
1468 __hold->__prev_ = __e.__ptr_;
1471 #ifndef _LIBCPP_NO_EXCEPTIONS
1477 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1478 __node_pointer __prev = __e.__ptr_->__prev_;
1479 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1482 #if _LIBCPP_DEBUG_LEVEL >= 2
1483 __e = iterator(__prev, this);
1485 __e = iterator(__prev);
1490 #endif // _LIBCPP_NO_EXCEPTIONS
1491 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1492 base::__sz() += __ds;
1497 template <class _Tp, class _Alloc>
1499 list<_Tp, _Alloc>::push_front(const value_type& __x)
1501 __node_allocator& __na = base::__node_alloc();
1502 typedef __allocator_destructor<__node_allocator> _Dp;
1503 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1504 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1505 __link_nodes(base::__end_.__next_, __hold.get(), __hold.get());
1510 template <class _Tp, class _Alloc>
1512 list<_Tp, _Alloc>::push_back(const value_type& __x)
1514 __node_allocator& __na = base::__node_alloc();
1515 typedef __allocator_destructor<__node_allocator> _Dp;
1516 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1517 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1518 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1519 pointer_to(base::__end_)), __hold.get(), __hold.get());
1524 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1526 template <class _Tp, class _Alloc>
1528 list<_Tp, _Alloc>::push_front(value_type&& __x)
1530 __node_allocator& __na = base::__node_alloc();
1531 typedef __allocator_destructor<__node_allocator> _Dp;
1532 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1533 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1534 __link_nodes(base::__end_.__next_, __hold.get(), __hold.get());
1539 template <class _Tp, class _Alloc>
1541 list<_Tp, _Alloc>::push_back(value_type&& __x)
1543 __node_allocator& __na = base::__node_alloc();
1544 typedef __allocator_destructor<__node_allocator> _Dp;
1545 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1546 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1547 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1548 pointer_to(base::__end_)), __hold.get(), __hold.get());
1553 #ifndef _LIBCPP_HAS_NO_VARIADICS
1555 template <class _Tp, class _Alloc>
1556 template <class... _Args>
1558 list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1560 __node_allocator& __na = base::__node_alloc();
1561 typedef __allocator_destructor<__node_allocator> _Dp;
1562 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1563 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1564 __link_nodes(base::__end_.__next_, __hold.get(), __hold.get());
1569 template <class _Tp, class _Alloc>
1570 template <class... _Args>
1572 list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1574 __node_allocator& __na = base::__node_alloc();
1575 typedef __allocator_destructor<__node_allocator> _Dp;
1576 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1577 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1578 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1579 pointer_to(base::__end_)), __hold.get(), __hold.get());
1584 template <class _Tp, class _Alloc>
1585 template <class... _Args>
1586 typename list<_Tp, _Alloc>::iterator
1587 list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1589 #if _LIBCPP_DEBUG_LEVEL >= 2
1590 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1591 "list::emplace(iterator, args...) called with an iterator not"
1592 " referring to this list");
1594 __node_allocator& __na = base::__node_alloc();
1595 typedef __allocator_destructor<__node_allocator> _Dp;
1596 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1597 __hold->__prev_ = 0;
1598 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1599 __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
1601 #if _LIBCPP_DEBUG_LEVEL >= 2
1602 return iterator(__hold.release(), this);
1604 return iterator(__hold.release());
1608 #endif // _LIBCPP_HAS_NO_VARIADICS
1610 template <class _Tp, class _Alloc>
1611 typename list<_Tp, _Alloc>::iterator
1612 list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1614 #if _LIBCPP_DEBUG_LEVEL >= 2
1615 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1616 "list::insert(iterator, x) called with an iterator not"
1617 " referring to this list");
1619 __node_allocator& __na = base::__node_alloc();
1620 typedef __allocator_destructor<__node_allocator> _Dp;
1621 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1622 __hold->__prev_ = 0;
1623 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1624 __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
1626 #if _LIBCPP_DEBUG_LEVEL >= 2
1627 return iterator(__hold.release(), this);
1629 return iterator(__hold.release());
1633 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1635 template <class _Tp, class _Alloc>
1637 list<_Tp, _Alloc>::pop_front()
1639 _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
1640 __node_allocator& __na = base::__node_alloc();
1641 __node_pointer __n = base::__end_.__next_;
1642 base::__unlink_nodes(__n, __n);
1644 #if _LIBCPP_DEBUG_LEVEL >= 2
1645 __c_node* __c = __get_db()->__find_c_and_lock(this);
1646 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1649 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1650 if (__i->__ptr_ == __n)
1652 (*__p)->__c_ = nullptr;
1653 if (--__c->end_ != __p)
1654 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1657 __get_db()->unlock();
1659 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
1660 __node_alloc_traits::deallocate(__na, __n, 1);
1663 template <class _Tp, class _Alloc>
1665 list<_Tp, _Alloc>::pop_back()
1667 _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list");
1668 __node_allocator& __na = base::__node_alloc();
1669 __node_pointer __n = base::__end_.__prev_;
1670 base::__unlink_nodes(__n, __n);
1672 #if _LIBCPP_DEBUG_LEVEL >= 2
1673 __c_node* __c = __get_db()->__find_c_and_lock(this);
1674 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1677 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1678 if (__i->__ptr_ == __n)
1680 (*__p)->__c_ = nullptr;
1681 if (--__c->end_ != __p)
1682 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1685 __get_db()->unlock();
1687 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
1688 __node_alloc_traits::deallocate(__na, __n, 1);
1691 template <class _Tp, class _Alloc>
1692 typename list<_Tp, _Alloc>::iterator
1693 list<_Tp, _Alloc>::erase(const_iterator __p)
1695 #if _LIBCPP_DEBUG_LEVEL >= 2
1696 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1697 "list::erase(iterator) called with an iterator not"
1698 " referring to this list");
1700 _LIBCPP_ASSERT(__p != end(),
1701 "list::erase(iterator) called with a non-dereferenceable iterator");
1702 __node_allocator& __na = base::__node_alloc();
1703 __node_pointer __n = __p.__ptr_;
1704 __node_pointer __r = __n->__next_;
1705 base::__unlink_nodes(__n, __n);
1707 #if _LIBCPP_DEBUG_LEVEL >= 2
1708 __c_node* __c = __get_db()->__find_c_and_lock(this);
1709 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1712 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1713 if (__i->__ptr_ == __n)
1715 (*__p)->__c_ = nullptr;
1716 if (--__c->end_ != __p)
1717 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1720 __get_db()->unlock();
1722 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
1723 __node_alloc_traits::deallocate(__na, __n, 1);
1724 #if _LIBCPP_DEBUG_LEVEL >= 2
1725 return iterator(__r, this);
1727 return iterator(__r);
1731 template <class _Tp, class _Alloc>
1732 typename list<_Tp, _Alloc>::iterator
1733 list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1735 #if _LIBCPP_DEBUG_LEVEL >= 2
1736 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this,
1737 "list::erase(iterator, iterator) called with an iterator not"
1738 " referring to this list");
1742 __node_allocator& __na = base::__node_alloc();
1743 base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
1746 __node_pointer __n = __f.__ptr_;
1749 #if _LIBCPP_DEBUG_LEVEL >= 2
1750 __c_node* __c = __get_db()->__find_c_and_lock(this);
1751 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1754 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1755 if (__i->__ptr_ == __n)
1757 (*__p)->__c_ = nullptr;
1758 if (--__c->end_ != __p)
1759 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1762 __get_db()->unlock();
1764 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
1765 __node_alloc_traits::deallocate(__na, __n, 1);
1768 #if _LIBCPP_DEBUG_LEVEL >= 2
1769 return iterator(__l.__ptr_, this);
1771 return iterator(__l.__ptr_);
1775 template <class _Tp, class _Alloc>
1777 list<_Tp, _Alloc>::resize(size_type __n)
1779 if (__n < base::__sz())
1780 erase(__iterator(__n), end());
1781 else if (__n > base::__sz())
1783 __n -= base::__sz();
1785 __node_allocator& __na = base::__node_alloc();
1786 typedef __allocator_destructor<__node_allocator> _Dp;
1787 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1788 __hold->__prev_ = 0;
1789 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1791 #if _LIBCPP_DEBUG_LEVEL >= 2
1792 iterator __r = iterator(__hold.release(), this);
1794 iterator __r = iterator(__hold.release());
1797 #ifndef _LIBCPP_NO_EXCEPTIONS
1800 #endif // _LIBCPP_NO_EXCEPTIONS
1801 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1803 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1804 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1805 __e.__ptr_->__next_ = __hold.get();
1806 __hold->__prev_ = __e.__ptr_;
1809 #ifndef _LIBCPP_NO_EXCEPTIONS
1815 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1816 __node_pointer __prev = __e.__ptr_->__prev_;
1817 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1820 #if _LIBCPP_DEBUG_LEVEL >= 2
1821 __e = iterator(__prev, this);
1823 __e = iterator(__prev);
1828 #endif // _LIBCPP_NO_EXCEPTIONS
1829 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1830 pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_);
1831 base::__sz() += __ds;
1835 template <class _Tp, class _Alloc>
1837 list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1839 if (__n < base::__sz())
1840 erase(__iterator(__n), end());
1841 else if (__n > base::__sz())
1843 __n -= base::__sz();
1845 __node_allocator& __na = base::__node_alloc();
1846 typedef __allocator_destructor<__node_allocator> _Dp;
1847 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1848 __hold->__prev_ = 0;
1849 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1851 #if _LIBCPP_DEBUG_LEVEL >= 2
1852 iterator __r = iterator(__hold.release(), this);
1854 iterator __r = iterator(__hold.release());
1857 #ifndef _LIBCPP_NO_EXCEPTIONS
1860 #endif // _LIBCPP_NO_EXCEPTIONS
1861 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1863 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1864 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1865 __e.__ptr_->__next_ = __hold.get();
1866 __hold->__prev_ = __e.__ptr_;
1869 #ifndef _LIBCPP_NO_EXCEPTIONS
1875 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1876 __node_pointer __prev = __e.__ptr_->__prev_;
1877 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1880 #if _LIBCPP_DEBUG_LEVEL >= 2
1881 __e = iterator(__prev, this);
1883 __e = iterator(__prev);
1888 #endif // _LIBCPP_NO_EXCEPTIONS
1889 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1890 pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_);
1891 base::__sz() += __ds;
1895 template <class _Tp, class _Alloc>
1897 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
1899 _LIBCPP_ASSERT(this != &__c,
1900 "list::splice(iterator, list) called with this == &list");
1901 #if _LIBCPP_DEBUG_LEVEL >= 2
1902 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1903 "list::splice(iterator, list) called with an iterator not"
1904 " referring to this list");
1908 __node_pointer __f = __c.__end_.__next_;
1909 __node_pointer __l = __c.__end_.__prev_;
1910 base::__unlink_nodes(__f, __l);
1911 __link_nodes(__p.__ptr_, __f, __l);
1912 base::__sz() += __c.__sz();
1914 #if _LIBCPP_DEBUG_LEVEL >= 2
1915 __libcpp_db* __db = __get_db();
1916 __c_node* __cn1 = __db->__find_c_and_lock(this);
1917 __c_node* __cn2 = __db->__find_c(&__c);
1918 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1921 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1922 if (__i->__ptr_ != static_cast<__node_pointer>(
1923 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
1926 (*__p)->__c_ = __cn1;
1927 if (--__cn2->end_ != __p)
1928 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1936 template <class _Tp, class _Alloc>
1938 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
1940 #if _LIBCPP_DEBUG_LEVEL >= 2
1941 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1942 "list::splice(iterator, list, iterator) called with first iterator not"
1943 " referring to this list");
1944 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c,
1945 "list::splice(iterator, list, iterator) called with second iterator not"
1946 " referring to list argument");
1947 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i),
1948 "list::splice(iterator, list, iterator) called with second iterator not"
1951 if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
1953 __node_pointer __f = __i.__ptr_;
1954 base::__unlink_nodes(__f, __f);
1955 __link_nodes(__p.__ptr_, __f, __f);
1958 #if _LIBCPP_DEBUG_LEVEL >= 2
1959 __libcpp_db* __db = __get_db();
1960 __c_node* __cn1 = __db->__find_c_and_lock(this);
1961 __c_node* __cn2 = __db->__find_c(&__c);
1962 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1965 iterator* __j = static_cast<iterator*>((*__p)->__i_);
1966 if (__j->__ptr_ == __f)
1969 (*__p)->__c_ = __cn1;
1970 if (--__cn2->end_ != __p)
1971 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1979 template <class _Tp, class _Alloc>
1981 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
1983 #if _LIBCPP_DEBUG_LEVEL >= 2
1984 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1985 "list::splice(iterator, list, iterator, iterator) called with first iterator not"
1986 " referring to this list");
1987 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c,
1988 "list::splice(iterator, list, iterator, iterator) called with second iterator not"
1989 " referring to list argument");
1992 for (const_iterator __i = __f; __i != __l; ++__i)
1993 _LIBCPP_ASSERT(__i != __p,
1994 "list::splice(iterator, list, iterator, iterator)"
1995 " called with the first iterator within the range"
1996 " of the second and third iterators");
2003 size_type __s = _VSTD::distance(__f, __l);
2005 base::__sz() += __s;
2007 __node_pointer __first = __f.__ptr_;
2009 __node_pointer __last = __l.__ptr_;
2010 base::__unlink_nodes(__first, __last);
2011 __link_nodes(__p.__ptr_, __first, __last);
2012 #if _LIBCPP_DEBUG_LEVEL >= 2
2013 __libcpp_db* __db = __get_db();
2014 __c_node* __cn1 = __db->__find_c_and_lock(this);
2015 __c_node* __cn2 = __db->__find_c(&__c);
2016 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2019 iterator* __j = static_cast<iterator*>((*__p)->__i_);
2020 for (__node_pointer __k = __f.__ptr_;
2021 __k != __l.__ptr_; __k = __k->__next_)
2023 if (__j->__ptr_ == __k)
2026 (*__p)->__c_ = __cn1;
2027 if (--__cn2->end_ != __p)
2028 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2037 template <class _Tp, class _Alloc>
2039 list<_Tp, _Alloc>::remove(const value_type& __x)
2041 for (iterator __i = begin(), __e = end(); __i != __e;)
2045 iterator __j = _VSTD::next(__i);
2046 for (; __j != __e && *__j == __x; ++__j)
2048 __i = erase(__i, __j);
2055 template <class _Tp, class _Alloc>
2056 template <class _Pred>
2058 list<_Tp, _Alloc>::remove_if(_Pred __pred)
2060 for (iterator __i = begin(), __e = end(); __i != __e;)
2064 iterator __j = _VSTD::next(__i);
2065 for (; __j != __e && __pred(*__j); ++__j)
2067 __i = erase(__i, __j);
2074 template <class _Tp, class _Alloc>
2075 inline _LIBCPP_INLINE_VISIBILITY
2077 list<_Tp, _Alloc>::unique()
2079 unique(__equal_to<value_type>());
2082 template <class _Tp, class _Alloc>
2083 template <class _BinaryPred>
2085 list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
2087 for (iterator __i = begin(), __e = end(); __i != __e;)
2089 iterator __j = _VSTD::next(__i);
2090 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
2093 __i = erase(__i, __j);
2097 template <class _Tp, class _Alloc>
2098 inline _LIBCPP_INLINE_VISIBILITY
2100 list<_Tp, _Alloc>::merge(list& __c)
2102 merge(__c, __less<value_type>());
2105 template <class _Tp, class _Alloc>
2106 template <class _Comp>
2108 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2112 iterator __f1 = begin();
2113 iterator __e1 = end();
2114 iterator __f2 = __c.begin();
2115 iterator __e2 = __c.end();
2116 while (__f1 != __e1 && __f2 != __e2)
2118 if (__comp(*__f2, *__f1))
2121 iterator __m2 = _VSTD::next(__f2);
2122 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
2124 base::__sz() += __ds;
2126 __node_pointer __f = __f2.__ptr_;
2127 __node_pointer __l = __m2.__ptr_->__prev_;
2129 base::__unlink_nodes(__f, __l);
2130 __m2 = _VSTD::next(__f1);
2131 __link_nodes(__f1.__ptr_, __f, __l);
2138 #if _LIBCPP_DEBUG_LEVEL >= 2
2139 __libcpp_db* __db = __get_db();
2140 __c_node* __cn1 = __db->__find_c_and_lock(this);
2141 __c_node* __cn2 = __db->__find_c(&__c);
2142 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2145 iterator* __i = static_cast<iterator*>((*__p)->__i_);
2146 if (__i->__ptr_ != static_cast<__node_pointer>(
2147 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
2150 (*__p)->__c_ = __cn1;
2151 if (--__cn2->end_ != __p)
2152 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2160 template <class _Tp, class _Alloc>
2161 inline _LIBCPP_INLINE_VISIBILITY
2163 list<_Tp, _Alloc>::sort()
2165 sort(__less<value_type>());
2168 template <class _Tp, class _Alloc>
2169 template <class _Comp>
2170 inline _LIBCPP_INLINE_VISIBILITY
2172 list<_Tp, _Alloc>::sort(_Comp __comp)
2174 __sort(begin(), end(), base::__sz(), __comp);
2177 template <class _Tp, class _Alloc>
2178 template <class _Comp>
2179 typename list<_Tp, _Alloc>::iterator
2180 list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
2188 if (__comp(*--__e2, *__f1))
2190 __node_pointer __f = __e2.__ptr_;
2191 base::__unlink_nodes(__f, __f);
2192 __link_nodes(__f1.__ptr_, __f, __f);
2197 size_type __n2 = __n / 2;
2198 iterator __e1 = _VSTD::next(__f1, __n2);
2199 iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp);
2200 iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2201 if (__comp(*__f2, *__f1))
2203 iterator __m2 = _VSTD::next(__f2);
2204 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2206 __node_pointer __f = __f2.__ptr_;
2207 __node_pointer __l = __m2.__ptr_->__prev_;
2210 base::__unlink_nodes(__f, __l);
2211 __m2 = _VSTD::next(__f1);
2212 __link_nodes(__f1.__ptr_, __f, __l);
2217 while (__f1 != __e1 && __f2 != __e2)
2219 if (__comp(*__f2, *__f1))
2221 iterator __m2 = _VSTD::next(__f2);
2222 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2224 __node_pointer __f = __f2.__ptr_;
2225 __node_pointer __l = __m2.__ptr_->__prev_;
2229 base::__unlink_nodes(__f, __l);
2230 __m2 = _VSTD::next(__f1);
2231 __link_nodes(__f1.__ptr_, __f, __l);
2240 template <class _Tp, class _Alloc>
2242 list<_Tp, _Alloc>::reverse() _NOEXCEPT
2244 if (base::__sz() > 1)
2246 iterator __e = end();
2247 for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
2249 _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
2250 __i.__ptr_ = __i.__ptr_->__prev_;
2252 _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
2256 template <class _Tp, class _Alloc>
2258 list<_Tp, _Alloc>::__invariants() const
2260 return size() == _VSTD::distance(begin(), end());
2263 #if _LIBCPP_DEBUG_LEVEL >= 2
2265 template <class _Tp, class _Alloc>
2267 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
2269 return __i->__ptr_ != static_cast<__node_pointer>(
2270 pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(this->__end_)));
2273 template <class _Tp, class _Alloc>
2275 list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
2277 return !empty() && __i->__ptr_ != base::__end_.__next_;
2280 template <class _Tp, class _Alloc>
2282 list<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2287 template <class _Tp, class _Alloc>
2289 list<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2294 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2296 template <class _Tp, class _Alloc>
2297 inline _LIBCPP_INLINE_VISIBILITY
2299 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2301 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2304 template <class _Tp, class _Alloc>
2305 inline _LIBCPP_INLINE_VISIBILITY
2307 operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2309 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2312 template <class _Tp, class _Alloc>
2313 inline _LIBCPP_INLINE_VISIBILITY
2315 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2317 return !(__x == __y);
2320 template <class _Tp, class _Alloc>
2321 inline _LIBCPP_INLINE_VISIBILITY
2323 operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2328 template <class _Tp, class _Alloc>
2329 inline _LIBCPP_INLINE_VISIBILITY
2331 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2333 return !(__x < __y);
2336 template <class _Tp, class _Alloc>
2337 inline _LIBCPP_INLINE_VISIBILITY
2339 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2341 return !(__y < __x);
2344 template <class _Tp, class _Alloc>
2345 inline _LIBCPP_INLINE_VISIBILITY
2347 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2348 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2353 _LIBCPP_END_NAMESPACE_STD
2355 #endif // _LIBCPP_LIST