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 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 void emplace_front(Args&&... args);
97 template <class... Args>
98 void emplace_back(Args&&... args);
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_type::propagate_on_container_swap::value ||
121 __is_nothrow_swappable<allocator_type>::value);
122 void clear() noexcept;
124 void splice(const_iterator position, list& x);
125 void splice(const_iterator position, list&& x);
126 void splice(const_iterator position, list& x, const_iterator i);
127 void splice(const_iterator position, list&& x, const_iterator i);
128 void splice(const_iterator position, list& x, const_iterator first,
129 const_iterator last);
130 void splice(const_iterator position, list&& x, const_iterator first,
131 const_iterator last);
133 void remove(const value_type& value);
134 template <class Pred> void remove_if(Pred pred);
136 template <class BinaryPredicate>
137 void unique(BinaryPredicate binary_pred);
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;
150 template <class T, class Alloc>
151 bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
152 template <class T, class Alloc>
153 bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);
154 template <class T, class Alloc>
155 bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);
156 template <class T, class Alloc>
157 bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);
158 template <class T, class Alloc>
159 bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);
160 template <class T, class Alloc>
161 bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);
163 template <class T, class Alloc>
164 void swap(list<T,Alloc>& x, list<T,Alloc>& y)
165 noexcept(noexcept(x.swap(y)));
175 #include <initializer_list>
179 #include <__undef_min_max>
181 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
182 #pragma GCC system_header
185 _LIBCPP_BEGIN_NAMESPACE_STD
187 template <class _Tp, class _VoidPtr> struct __list_node;
189 template <class _Tp, class _VoidPtr>
190 struct __list_node_base
192 typedef typename pointer_traits<_VoidPtr>::template
193 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
194 rebind<__list_node<_Tp, _VoidPtr> > pointer;
196 rebind<__list_node<_Tp, _VoidPtr> >::other pointer;
199 typedef typename pointer_traits<_VoidPtr>::template
200 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
201 rebind<__list_node_base> __base_pointer;
203 rebind<__list_node_base>::other __base_pointer;
209 _LIBCPP_INLINE_VISIBILITY
211 : __prev_(static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this))),
212 __next_(static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this)))
216 template <class _Tp, class _VoidPtr>
218 : public __list_node_base<_Tp, _VoidPtr>
223 template <class _Tp, class _Alloc> class _LIBCPP_TYPE_VIS list;
224 template <class _Tp, class _Alloc> class __list_imp;
225 template <class _Tp, class _VoidPtr> class _LIBCPP_TYPE_VIS __list_const_iterator;
227 template <class _Tp, class _VoidPtr>
228 class _LIBCPP_TYPE_VIS __list_iterator
230 typedef typename pointer_traits<_VoidPtr>::template
231 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
232 rebind<__list_node<_Tp, _VoidPtr> > __node_pointer;
234 rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer;
237 __node_pointer __ptr_;
239 #if _LIBCPP_DEBUG_LEVEL >= 2
240 _LIBCPP_INLINE_VISIBILITY
241 explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
244 __get_db()->__insert_ic(this, __c);
247 _LIBCPP_INLINE_VISIBILITY
248 explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
253 template<class, class> friend class list;
254 template<class, class> friend class __list_imp;
255 template<class, class> friend class __list_const_iterator;
257 typedef bidirectional_iterator_tag iterator_category;
258 typedef _Tp value_type;
259 typedef value_type& reference;
260 typedef typename pointer_traits<_VoidPtr>::template
261 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
264 rebind<value_type>::other
267 typedef typename pointer_traits<pointer>::difference_type difference_type;
269 _LIBCPP_INLINE_VISIBILITY
270 __list_iterator() _NOEXCEPT
272 #if _LIBCPP_DEBUG_LEVEL >= 2
273 __get_db()->__insert_i(this);
277 #if _LIBCPP_DEBUG_LEVEL >= 2
279 _LIBCPP_INLINE_VISIBILITY
280 __list_iterator(const __list_iterator& __p)
283 __get_db()->__iterator_copy(this, &__p);
286 _LIBCPP_INLINE_VISIBILITY
289 __get_db()->__erase_i(this);
292 _LIBCPP_INLINE_VISIBILITY
293 __list_iterator& operator=(const __list_iterator& __p)
297 __get_db()->__iterator_copy(this, &__p);
303 #endif // _LIBCPP_DEBUG_LEVEL >= 2
305 _LIBCPP_INLINE_VISIBILITY
306 reference operator*() const
308 #if _LIBCPP_DEBUG_LEVEL >= 2
309 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
310 "Attempted to dereference a non-dereferenceable list::iterator");
312 return __ptr_->__value_;
314 _LIBCPP_INLINE_VISIBILITY
315 pointer operator->() const
317 #if _LIBCPP_DEBUG_LEVEL >= 2
318 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
319 "Attempted to dereference a non-dereferenceable list::iterator");
321 return pointer_traits<pointer>::pointer_to(__ptr_->__value_);
324 _LIBCPP_INLINE_VISIBILITY
325 __list_iterator& operator++()
327 #if _LIBCPP_DEBUG_LEVEL >= 2
328 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
329 "Attempted to increment non-incrementable list::iterator");
331 __ptr_ = __ptr_->__next_;
334 _LIBCPP_INLINE_VISIBILITY
335 __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;}
337 _LIBCPP_INLINE_VISIBILITY
338 __list_iterator& operator--()
340 #if _LIBCPP_DEBUG_LEVEL >= 2
341 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
342 "Attempted to decrement non-decrementable list::iterator");
344 __ptr_ = __ptr_->__prev_;
347 _LIBCPP_INLINE_VISIBILITY
348 __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}
350 friend _LIBCPP_INLINE_VISIBILITY
351 bool operator==(const __list_iterator& __x, const __list_iterator& __y)
353 #if _LIBCPP_DEBUG_LEVEL >= 2
354 _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
355 "Attempted to compare non-comparable list::iterator");
357 return __x.__ptr_ == __y.__ptr_;
359 friend _LIBCPP_INLINE_VISIBILITY
360 bool operator!=(const __list_iterator& __x, const __list_iterator& __y)
361 {return !(__x == __y);}
364 template <class _Tp, class _VoidPtr>
365 class _LIBCPP_TYPE_VIS __list_const_iterator
367 typedef typename pointer_traits<_VoidPtr>::template
368 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
369 rebind<__list_node<_Tp, _VoidPtr> > __node_pointer;
371 rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer;
374 __node_pointer __ptr_;
376 #if _LIBCPP_DEBUG_LEVEL >= 2
377 _LIBCPP_INLINE_VISIBILITY
378 explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
381 __get_db()->__insert_ic(this, __c);
384 _LIBCPP_INLINE_VISIBILITY
385 explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
388 template<class, class> friend class list;
389 template<class, class> friend class __list_imp;
391 typedef bidirectional_iterator_tag iterator_category;
392 typedef _Tp value_type;
393 typedef const value_type& reference;
394 typedef typename pointer_traits<_VoidPtr>::template
395 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
396 rebind<const value_type>
398 rebind<const value_type>::other
401 typedef typename pointer_traits<pointer>::difference_type difference_type;
403 _LIBCPP_INLINE_VISIBILITY
404 __list_const_iterator() _NOEXCEPT
406 #if _LIBCPP_DEBUG_LEVEL >= 2
407 __get_db()->__insert_i(this);
410 _LIBCPP_INLINE_VISIBILITY
411 __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT
414 #if _LIBCPP_DEBUG_LEVEL >= 2
415 __get_db()->__iterator_copy(this, &__p);
419 #if _LIBCPP_DEBUG_LEVEL >= 2
421 _LIBCPP_INLINE_VISIBILITY
422 __list_const_iterator(const __list_const_iterator& __p)
425 __get_db()->__iterator_copy(this, &__p);
428 _LIBCPP_INLINE_VISIBILITY
429 ~__list_const_iterator()
431 __get_db()->__erase_i(this);
434 _LIBCPP_INLINE_VISIBILITY
435 __list_const_iterator& operator=(const __list_const_iterator& __p)
439 __get_db()->__iterator_copy(this, &__p);
445 #endif // _LIBCPP_DEBUG_LEVEL >= 2
446 _LIBCPP_INLINE_VISIBILITY
447 reference operator*() const
449 #if _LIBCPP_DEBUG_LEVEL >= 2
450 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
451 "Attempted to dereference a non-dereferenceable list::const_iterator");
453 return __ptr_->__value_;
455 _LIBCPP_INLINE_VISIBILITY
456 pointer operator->() const
458 #if _LIBCPP_DEBUG_LEVEL >= 2
459 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
460 "Attempted to dereference a non-dereferenceable list::iterator");
462 return pointer_traits<pointer>::pointer_to(__ptr_->__value_);
465 _LIBCPP_INLINE_VISIBILITY
466 __list_const_iterator& operator++()
468 #if _LIBCPP_DEBUG_LEVEL >= 2
469 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
470 "Attempted to increment non-incrementable list::const_iterator");
472 __ptr_ = __ptr_->__next_;
475 _LIBCPP_INLINE_VISIBILITY
476 __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;}
478 _LIBCPP_INLINE_VISIBILITY
479 __list_const_iterator& operator--()
481 #if _LIBCPP_DEBUG_LEVEL >= 2
482 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
483 "Attempted to decrement non-decrementable list::const_iterator");
485 __ptr_ = __ptr_->__prev_;
488 _LIBCPP_INLINE_VISIBILITY
489 __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}
491 friend _LIBCPP_INLINE_VISIBILITY
492 bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y)
494 #if _LIBCPP_DEBUG_LEVEL >= 2
495 _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
496 "Attempted to compare non-comparable list::const_iterator");
498 return __x.__ptr_ == __y.__ptr_;
500 friend _LIBCPP_INLINE_VISIBILITY
501 bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y)
502 {return !(__x == __y);}
505 template <class _Tp, class _Alloc>
508 __list_imp(const __list_imp&);
509 __list_imp& operator=(const __list_imp&);
511 typedef _Tp value_type;
512 typedef _Alloc allocator_type;
513 typedef allocator_traits<allocator_type> __alloc_traits;
514 typedef typename __alloc_traits::size_type size_type;
515 typedef typename __alloc_traits::void_pointer __void_pointer;
516 typedef __list_iterator<value_type, __void_pointer> iterator;
517 typedef __list_const_iterator<value_type, __void_pointer> const_iterator;
518 typedef __list_node_base<value_type, __void_pointer> __node_base;
519 typedef __list_node<value_type, __void_pointer> __node;
520 typedef typename __alloc_traits::template
521 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
524 rebind_alloc<__node>::other
527 typedef allocator_traits<__node_allocator> __node_alloc_traits;
528 typedef typename __node_alloc_traits::pointer __node_pointer;
529 typedef typename __node_alloc_traits::pointer __node_const_pointer;
530 typedef typename __alloc_traits::pointer pointer;
531 typedef typename __alloc_traits::const_pointer const_pointer;
532 typedef typename __alloc_traits::difference_type difference_type;
534 typedef typename __alloc_traits::template
535 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
536 rebind_alloc<__node_base>
538 rebind_alloc<__node_base>::other
540 __node_base_allocator;
541 typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;
544 __compressed_pair<size_type, __node_allocator> __size_alloc_;
546 _LIBCPP_INLINE_VISIBILITY
547 size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
548 _LIBCPP_INLINE_VISIBILITY
549 const size_type& __sz() const _NOEXCEPT
550 {return __size_alloc_.first();}
551 _LIBCPP_INLINE_VISIBILITY
552 __node_allocator& __node_alloc() _NOEXCEPT
553 {return __size_alloc_.second();}
554 _LIBCPP_INLINE_VISIBILITY
555 const __node_allocator& __node_alloc() const _NOEXCEPT
556 {return __size_alloc_.second();}
558 static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT;
561 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
562 __list_imp(const allocator_type& __a);
564 void clear() _NOEXCEPT;
565 _LIBCPP_INLINE_VISIBILITY
566 bool empty() const _NOEXCEPT {return __sz() == 0;}
568 _LIBCPP_INLINE_VISIBILITY
569 iterator begin() _NOEXCEPT
571 #if _LIBCPP_DEBUG_LEVEL >= 2
572 return iterator(__end_.__next_, this);
574 return iterator(__end_.__next_);
577 _LIBCPP_INLINE_VISIBILITY
578 const_iterator begin() const _NOEXCEPT
580 #if _LIBCPP_DEBUG_LEVEL >= 2
581 return const_iterator(__end_.__next_, this);
583 return const_iterator(__end_.__next_);
586 _LIBCPP_INLINE_VISIBILITY
587 iterator end() _NOEXCEPT
589 #if _LIBCPP_DEBUG_LEVEL >= 2
590 return iterator(static_cast<__node_pointer>(
591 pointer_traits<__node_base_pointer>::pointer_to(__end_)), this);
593 return iterator(static_cast<__node_pointer>(
594 pointer_traits<__node_base_pointer>::pointer_to(__end_)));
597 _LIBCPP_INLINE_VISIBILITY
598 const_iterator end() const _NOEXCEPT
600 #if _LIBCPP_DEBUG_LEVEL >= 2
601 return const_iterator(static_cast<__node_const_pointer>(
602 pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))), this);
604 return const_iterator(static_cast<__node_const_pointer>(
605 pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))));
609 void swap(__list_imp& __c)
610 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
611 __is_nothrow_swappable<__node_allocator>::value);
613 _LIBCPP_INLINE_VISIBILITY
614 void __copy_assign_alloc(const __list_imp& __c)
615 {__copy_assign_alloc(__c, integral_constant<bool,
616 __node_alloc_traits::propagate_on_container_copy_assignment::value>());}
618 _LIBCPP_INLINE_VISIBILITY
619 void __move_assign_alloc(__list_imp& __c)
621 !__node_alloc_traits::propagate_on_container_move_assignment::value ||
622 is_nothrow_move_assignable<__node_allocator>::value)
623 {__move_assign_alloc(__c, integral_constant<bool,
624 __node_alloc_traits::propagate_on_container_move_assignment::value>());}
627 _LIBCPP_INLINE_VISIBILITY
628 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y)
629 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
630 __is_nothrow_swappable<__node_allocator>::value)
631 {__swap_alloc(__x, __y, integral_constant<bool,
632 __node_alloc_traits::propagate_on_container_swap::value>());}
633 _LIBCPP_INLINE_VISIBILITY
634 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type)
635 _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value)
640 _LIBCPP_INLINE_VISIBILITY
641 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type)
645 _LIBCPP_INLINE_VISIBILITY
646 void __copy_assign_alloc(const __list_imp& __c, true_type)
648 if (__node_alloc() != __c.__node_alloc())
650 __node_alloc() = __c.__node_alloc();
653 _LIBCPP_INLINE_VISIBILITY
654 void __copy_assign_alloc(const __list_imp& __c, false_type)
657 _LIBCPP_INLINE_VISIBILITY
658 void __move_assign_alloc(__list_imp& __c, true_type)
659 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
661 __node_alloc() = _VSTD::move(__c.__node_alloc());
664 _LIBCPP_INLINE_VISIBILITY
665 void __move_assign_alloc(__list_imp& __c, false_type)
670 // Unlink nodes [__f, __l]
671 template <class _Tp, class _Alloc>
672 inline _LIBCPP_INLINE_VISIBILITY
674 __list_imp<_Tp, _Alloc>::__unlink_nodes(__node_pointer __f, __node_pointer __l)
677 __f->__prev_->__next_ = __l->__next_;
678 __l->__next_->__prev_ = __f->__prev_;
681 template <class _Tp, class _Alloc>
682 inline _LIBCPP_INLINE_VISIBILITY
683 __list_imp<_Tp, _Alloc>::__list_imp()
684 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
689 template <class _Tp, class _Alloc>
690 inline _LIBCPP_INLINE_VISIBILITY
691 __list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a)
692 : __size_alloc_(0, __node_allocator(__a))
696 template <class _Tp, class _Alloc>
697 __list_imp<_Tp, _Alloc>::~__list_imp()
700 #if _LIBCPP_DEBUG_LEVEL >= 2
701 __get_db()->__erase_c(this);
705 template <class _Tp, class _Alloc>
707 __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
711 __node_allocator& __na = __node_alloc();
712 __node_pointer __f = __end_.__next_;
713 __node_pointer __l = static_cast<__node_pointer>(
714 pointer_traits<__node_base_pointer>::pointer_to(__end_));
715 __unlink_nodes(__f, __l->__prev_);
719 __node_pointer __n = __f;
721 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
722 __node_alloc_traits::deallocate(__na, __n, 1);
724 #if _LIBCPP_DEBUG_LEVEL >= 2
725 __c_node* __c = __get_db()->__find_c_and_lock(this);
726 for (__i_node** __p = __c->end_; __p != __c->beg_; )
729 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
730 if (__i->__ptr_ != __l)
732 (*__p)->__c_ = nullptr;
733 if (--__c->end_ != __p)
734 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
737 __get_db()->unlock();
742 template <class _Tp, class _Alloc>
744 __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
745 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
746 __is_nothrow_swappable<__node_allocator>::value)
748 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
749 this->__node_alloc() == __c.__node_alloc(),
750 "list::swap: Either propagate_on_container_swap must be true"
751 " or the allocators must compare equal");
753 __swap_alloc(__node_alloc(), __c.__node_alloc());
754 swap(__sz(), __c.__sz());
755 swap(__end_, __c.__end_);
757 __end_.__next_ = __end_.__prev_ = static_cast<__node_pointer>(
758 pointer_traits<__node_base_pointer>::pointer_to(__end_));
760 __end_.__prev_->__next_ = __end_.__next_->__prev_
761 = static_cast<__node_pointer>(
762 pointer_traits<__node_base_pointer>::pointer_to(__end_));
764 __c.__end_.__next_ = __c.__end_.__prev_
765 = static_cast<__node_pointer>(
766 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_));
768 __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_
769 = static_cast<__node_pointer>(
770 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_));
771 #if _LIBCPP_DEBUG_LEVEL >= 2
772 __libcpp_db* __db = __get_db();
773 __c_node* __cn1 = __db->__find_c_and_lock(this);
774 __c_node* __cn2 = __db->__find_c(&__c);
775 std::swap(__cn1->beg_, __cn2->beg_);
776 std::swap(__cn1->end_, __cn2->end_);
777 std::swap(__cn1->cap_, __cn2->cap_);
778 for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;)
781 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
782 if (__i->__ptr_ == static_cast<__node_pointer>(
783 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
786 if (--__cn1->end_ != __p)
787 memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*));
790 (*__p)->__c_ = __cn1;
792 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
795 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
796 if (__i->__ptr_ == static_cast<__node_pointer>(
797 pointer_traits<__node_base_pointer>::pointer_to(__end_)))
800 if (--__cn2->end_ != __p)
801 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
804 (*__p)->__c_ = __cn2;
810 template <class _Tp, class _Alloc = allocator<_Tp> >
811 class _LIBCPP_TYPE_VIS list
812 : private __list_imp<_Tp, _Alloc>
814 typedef __list_imp<_Tp, _Alloc> base;
815 typedef typename base::__node __node;
816 typedef typename base::__node_allocator __node_allocator;
817 typedef typename base::__node_pointer __node_pointer;
818 typedef typename base::__node_alloc_traits __node_alloc_traits;
819 typedef typename base::__node_base __node_base;
820 typedef typename base::__node_base_pointer __node_base_pointer;
823 typedef _Tp value_type;
824 typedef _Alloc allocator_type;
825 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
826 "Invalid allocator::value_type");
827 typedef value_type& reference;
828 typedef const value_type& const_reference;
829 typedef typename base::pointer pointer;
830 typedef typename base::const_pointer const_pointer;
831 typedef typename base::size_type size_type;
832 typedef typename base::difference_type difference_type;
833 typedef typename base::iterator iterator;
834 typedef typename base::const_iterator const_iterator;
835 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
836 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
838 _LIBCPP_INLINE_VISIBILITY
840 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
842 #if _LIBCPP_DEBUG_LEVEL >= 2
843 __get_db()->__insert_c(this);
846 _LIBCPP_INLINE_VISIBILITY
847 list(const allocator_type& __a) : base(__a)
849 #if _LIBCPP_DEBUG_LEVEL >= 2
850 __get_db()->__insert_c(this);
854 list(size_type __n, const value_type& __x);
855 list(size_type __n, const value_type& __x, const allocator_type& __a);
856 template <class _InpIter>
857 list(_InpIter __f, _InpIter __l,
858 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
859 template <class _InpIter>
860 list(_InpIter __f, _InpIter __l, const allocator_type& __a,
861 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
863 list(const list& __c);
864 list(const list& __c, const allocator_type& __a);
865 list& operator=(const list& __c);
866 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
867 list(initializer_list<value_type> __il);
868 list(initializer_list<value_type> __il, const allocator_type& __a);
869 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
870 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
872 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
873 list(list&& __c, const allocator_type& __a);
874 list& operator=(list&& __c)
876 __node_alloc_traits::propagate_on_container_move_assignment::value &&
877 is_nothrow_move_assignable<__node_allocator>::value);
878 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
879 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
880 _LIBCPP_INLINE_VISIBILITY
881 list& operator=(initializer_list<value_type> __il)
882 {assign(__il.begin(), __il.end()); return *this;}
883 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
885 template <class _InpIter>
886 void assign(_InpIter __f, _InpIter __l,
887 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
888 void assign(size_type __n, const value_type& __x);
889 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
890 _LIBCPP_INLINE_VISIBILITY
891 void assign(initializer_list<value_type> __il)
892 {assign(__il.begin(), __il.end());}
893 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
895 allocator_type get_allocator() const _NOEXCEPT;
897 _LIBCPP_INLINE_VISIBILITY
898 size_type size() const _NOEXCEPT {return base::__sz();}
899 _LIBCPP_INLINE_VISIBILITY
900 bool empty() const _NOEXCEPT {return base::empty();}
901 _LIBCPP_INLINE_VISIBILITY
902 size_type max_size() const _NOEXCEPT
903 {return numeric_limits<difference_type>::max();}
905 _LIBCPP_INLINE_VISIBILITY
906 iterator begin() _NOEXCEPT {return base::begin();}
907 _LIBCPP_INLINE_VISIBILITY
908 const_iterator begin() const _NOEXCEPT {return base::begin();}
909 _LIBCPP_INLINE_VISIBILITY
910 iterator end() _NOEXCEPT {return base::end();}
911 _LIBCPP_INLINE_VISIBILITY
912 const_iterator end() const _NOEXCEPT {return base::end();}
913 _LIBCPP_INLINE_VISIBILITY
914 const_iterator cbegin() const _NOEXCEPT {return base::begin();}
915 _LIBCPP_INLINE_VISIBILITY
916 const_iterator cend() const _NOEXCEPT {return base::end();}
918 _LIBCPP_INLINE_VISIBILITY
919 reverse_iterator rbegin() _NOEXCEPT
920 {return reverse_iterator(end());}
921 _LIBCPP_INLINE_VISIBILITY
922 const_reverse_iterator rbegin() const _NOEXCEPT
923 {return const_reverse_iterator(end());}
924 _LIBCPP_INLINE_VISIBILITY
925 reverse_iterator rend() _NOEXCEPT
926 {return reverse_iterator(begin());}
927 _LIBCPP_INLINE_VISIBILITY
928 const_reverse_iterator rend() const _NOEXCEPT
929 {return const_reverse_iterator(begin());}
930 _LIBCPP_INLINE_VISIBILITY
931 const_reverse_iterator crbegin() const _NOEXCEPT
932 {return const_reverse_iterator(end());}
933 _LIBCPP_INLINE_VISIBILITY
934 const_reverse_iterator crend() const _NOEXCEPT
935 {return const_reverse_iterator(begin());}
937 _LIBCPP_INLINE_VISIBILITY
940 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
941 return base::__end_.__next_->__value_;
943 _LIBCPP_INLINE_VISIBILITY
944 const_reference front() const
946 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
947 return base::__end_.__next_->__value_;
949 _LIBCPP_INLINE_VISIBILITY
952 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
953 return base::__end_.__prev_->__value_;
955 _LIBCPP_INLINE_VISIBILITY
956 const_reference back() const
958 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
959 return base::__end_.__prev_->__value_;
962 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
963 void push_front(value_type&& __x);
964 void push_back(value_type&& __x);
965 #ifndef _LIBCPP_HAS_NO_VARIADICS
966 template <class... _Args>
967 void emplace_front(_Args&&... __args);
968 template <class... _Args>
969 void emplace_back(_Args&&... __args);
970 template <class... _Args>
971 iterator emplace(const_iterator __p, _Args&&... __args);
972 #endif // _LIBCPP_HAS_NO_VARIADICS
973 iterator insert(const_iterator __p, value_type&& __x);
974 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
976 void push_front(const value_type& __x);
977 void push_back(const value_type& __x);
979 iterator insert(const_iterator __p, const value_type& __x);
980 iterator insert(const_iterator __p, size_type __n, const value_type& __x);
981 template <class _InpIter>
982 iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
983 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
984 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
985 _LIBCPP_INLINE_VISIBILITY
986 iterator insert(const_iterator __p, initializer_list<value_type> __il)
987 {return insert(__p, __il.begin(), __il.end());}
988 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
990 _LIBCPP_INLINE_VISIBILITY
992 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
993 __is_nothrow_swappable<__node_allocator>::value)
995 _LIBCPP_INLINE_VISIBILITY
996 void clear() _NOEXCEPT {base::clear();}
1001 iterator erase(const_iterator __p);
1002 iterator erase(const_iterator __f, const_iterator __l);
1004 void resize(size_type __n);
1005 void resize(size_type __n, const value_type& __x);
1007 void splice(const_iterator __p, list& __c);
1008 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1009 _LIBCPP_INLINE_VISIBILITY
1010 void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
1012 void splice(const_iterator __p, list& __c, const_iterator __i);
1013 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1014 _LIBCPP_INLINE_VISIBILITY
1015 void splice(const_iterator __p, list&& __c, const_iterator __i)
1016 {splice(__p, __c, __i);}
1017 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1018 void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
1019 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1020 _LIBCPP_INLINE_VISIBILITY
1021 void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
1022 {splice(__p, __c, __f, __l);}
1023 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1025 void remove(const value_type& __x);
1026 template <class _Pred> void remove_if(_Pred __pred);
1028 template <class _BinaryPred>
1029 void unique(_BinaryPred __binary_pred);
1030 void merge(list& __c);
1031 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1032 _LIBCPP_INLINE_VISIBILITY
1033 void merge(list&& __c) {merge(__c);}
1035 template <class _Comp>
1036 void merge(list& __c, _Comp __comp);
1037 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1038 template <class _Comp>
1039 _LIBCPP_INLINE_VISIBILITY
1040 void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
1041 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1043 template <class _Comp>
1044 void sort(_Comp __comp);
1046 void reverse() _NOEXCEPT;
1048 bool __invariants() const;
1050 #if _LIBCPP_DEBUG_LEVEL >= 2
1052 bool __dereferenceable(const const_iterator* __i) const;
1053 bool __decrementable(const const_iterator* __i) const;
1054 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1055 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1057 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1060 static void __link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l);
1061 iterator __iterator(size_type __n);
1062 template <class _Comp>
1063 static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
1065 void __move_assign(list& __c, true_type)
1066 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
1067 void __move_assign(list& __c, false_type);
1070 // Link in nodes [__f, __l] just prior to __p
1071 template <class _Tp, class _Alloc>
1072 inline _LIBCPP_INLINE_VISIBILITY
1074 list<_Tp, _Alloc>::__link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l)
1076 __p->__prev_->__next_ = __f;
1077 __f->__prev_ = __p->__prev_;
1082 template <class _Tp, class _Alloc>
1083 inline _LIBCPP_INLINE_VISIBILITY
1084 typename list<_Tp, _Alloc>::iterator
1085 list<_Tp, _Alloc>::__iterator(size_type __n)
1087 return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n)
1088 : _VSTD::prev(end(), base::__sz() - __n);
1091 template <class _Tp, class _Alloc>
1092 list<_Tp, _Alloc>::list(size_type __n)
1094 #if _LIBCPP_DEBUG_LEVEL >= 2
1095 __get_db()->__insert_c(this);
1097 for (; __n > 0; --__n)
1098 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1101 push_back(value_type());
1105 template <class _Tp, class _Alloc>
1106 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x)
1108 #if _LIBCPP_DEBUG_LEVEL >= 2
1109 __get_db()->__insert_c(this);
1111 for (; __n > 0; --__n)
1115 template <class _Tp, class _Alloc>
1116 list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a)
1119 #if _LIBCPP_DEBUG_LEVEL >= 2
1120 __get_db()->__insert_c(this);
1122 for (; __n > 0; --__n)
1126 template <class _Tp, class _Alloc>
1127 template <class _InpIter>
1128 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
1129 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1131 #if _LIBCPP_DEBUG_LEVEL >= 2
1132 __get_db()->__insert_c(this);
1134 for (; __f != __l; ++__f)
1138 template <class _Tp, class _Alloc>
1139 template <class _InpIter>
1140 list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
1141 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1144 #if _LIBCPP_DEBUG_LEVEL >= 2
1145 __get_db()->__insert_c(this);
1147 for (; __f != __l; ++__f)
1151 template <class _Tp, class _Alloc>
1152 list<_Tp, _Alloc>::list(const list& __c)
1153 : base(allocator_type(
1154 __node_alloc_traits::select_on_container_copy_construction(
1155 __c.__node_alloc())))
1157 #if _LIBCPP_DEBUG_LEVEL >= 2
1158 __get_db()->__insert_c(this);
1160 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1164 template <class _Tp, class _Alloc>
1165 list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a)
1168 #if _LIBCPP_DEBUG_LEVEL >= 2
1169 __get_db()->__insert_c(this);
1171 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1175 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1177 template <class _Tp, class _Alloc>
1178 list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a)
1181 #if _LIBCPP_DEBUG_LEVEL >= 2
1182 __get_db()->__insert_c(this);
1184 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1185 __e = __il.end(); __i != __e; ++__i)
1189 template <class _Tp, class _Alloc>
1190 list<_Tp, _Alloc>::list(initializer_list<value_type> __il)
1192 #if _LIBCPP_DEBUG_LEVEL >= 2
1193 __get_db()->__insert_c(this);
1195 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1196 __e = __il.end(); __i != __e; ++__i)
1200 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1202 template <class _Tp, class _Alloc>
1203 inline _LIBCPP_INLINE_VISIBILITY
1205 list<_Tp, _Alloc>::operator=(const list& __c)
1209 base::__copy_assign_alloc(__c);
1210 assign(__c.begin(), __c.end());
1215 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1217 template <class _Tp, class _Alloc>
1218 inline _LIBCPP_INLINE_VISIBILITY
1219 list<_Tp, _Alloc>::list(list&& __c)
1220 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
1221 : base(allocator_type(_VSTD::move(__c.__node_alloc())))
1223 #if _LIBCPP_DEBUG_LEVEL >= 2
1224 __get_db()->__insert_c(this);
1229 template <class _Tp, class _Alloc>
1230 inline _LIBCPP_INLINE_VISIBILITY
1231 list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a)
1234 #if _LIBCPP_DEBUG_LEVEL >= 2
1235 __get_db()->__insert_c(this);
1237 if (__a == __c.get_allocator())
1241 typedef move_iterator<iterator> _Ip;
1242 assign(_Ip(__c.begin()), _Ip(__c.end()));
1246 template <class _Tp, class _Alloc>
1247 inline _LIBCPP_INLINE_VISIBILITY
1249 list<_Tp, _Alloc>::operator=(list&& __c)
1251 __node_alloc_traits::propagate_on_container_move_assignment::value &&
1252 is_nothrow_move_assignable<__node_allocator>::value)
1254 __move_assign(__c, integral_constant<bool,
1255 __node_alloc_traits::propagate_on_container_move_assignment::value>());
1259 template <class _Tp, class _Alloc>
1261 list<_Tp, _Alloc>::__move_assign(list& __c, false_type)
1263 if (base::__node_alloc() != __c.__node_alloc())
1265 typedef move_iterator<iterator> _Ip;
1266 assign(_Ip(__c.begin()), _Ip(__c.end()));
1269 __move_assign(__c, true_type());
1272 template <class _Tp, class _Alloc>
1274 list<_Tp, _Alloc>::__move_assign(list& __c, true_type)
1275 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
1278 base::__move_assign_alloc(__c);
1282 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1284 template <class _Tp, class _Alloc>
1285 template <class _InpIter>
1287 list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l,
1288 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1290 iterator __i = begin();
1291 iterator __e = end();
1292 for (; __f != __l && __i != __e; ++__f, ++__i)
1295 insert(__e, __f, __l);
1300 template <class _Tp, class _Alloc>
1302 list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x)
1304 iterator __i = begin();
1305 iterator __e = end();
1306 for (; __n > 0 && __i != __e; --__n, ++__i)
1309 insert(__e, __n, __x);
1314 template <class _Tp, class _Alloc>
1315 inline _LIBCPP_INLINE_VISIBILITY
1317 list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT
1319 return allocator_type(base::__node_alloc());
1322 template <class _Tp, class _Alloc>
1323 typename list<_Tp, _Alloc>::iterator
1324 list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
1326 #if _LIBCPP_DEBUG_LEVEL >= 2
1327 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1328 "list::insert(iterator, x) called with an iterator not"
1329 " referring to this list");
1331 __node_allocator& __na = base::__node_alloc();
1332 typedef __allocator_destructor<__node_allocator> _Dp;
1333 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1334 __hold->__prev_ = 0;
1335 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1336 __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
1338 #if _LIBCPP_DEBUG_LEVEL >= 2
1339 return iterator(__hold.release(), this);
1341 return iterator(__hold.release());
1345 template <class _Tp, class _Alloc>
1346 typename list<_Tp, _Alloc>::iterator
1347 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
1349 #if _LIBCPP_DEBUG_LEVEL >= 2
1350 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1351 "list::insert(iterator, n, x) called with an iterator not"
1352 " referring to this list");
1353 iterator __r(__p.__ptr_, this);
1355 iterator __r(__p.__ptr_);
1360 __node_allocator& __na = base::__node_alloc();
1361 typedef __allocator_destructor<__node_allocator> _Dp;
1362 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1363 __hold->__prev_ = 0;
1364 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1366 #if _LIBCPP_DEBUG_LEVEL >= 2
1367 __r = iterator(__hold.get(), this);
1369 __r = iterator(__hold.get());
1373 #ifndef _LIBCPP_NO_EXCEPTIONS
1376 #endif // _LIBCPP_NO_EXCEPTIONS
1377 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1379 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1380 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1381 __e.__ptr_->__next_ = __hold.get();
1382 __hold->__prev_ = __e.__ptr_;
1385 #ifndef _LIBCPP_NO_EXCEPTIONS
1391 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1392 __node_pointer __prev = __e.__ptr_->__prev_;
1393 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1396 #if _LIBCPP_DEBUG_LEVEL >= 2
1397 __e = iterator(__prev, this);
1399 __e = iterator(__prev);
1404 #endif // _LIBCPP_NO_EXCEPTIONS
1405 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1406 base::__sz() += __ds;
1411 template <class _Tp, class _Alloc>
1412 template <class _InpIter>
1413 typename list<_Tp, _Alloc>::iterator
1414 list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
1415 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1417 #if _LIBCPP_DEBUG_LEVEL >= 2
1418 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1419 "list::insert(iterator, range) called with an iterator not"
1420 " referring to this list");
1421 iterator __r(__p.__ptr_, this);
1423 iterator __r(__p.__ptr_);
1428 __node_allocator& __na = base::__node_alloc();
1429 typedef __allocator_destructor<__node_allocator> _Dp;
1430 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1431 __hold->__prev_ = 0;
1432 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1434 #if _LIBCPP_DEBUG_LEVEL >= 2
1435 __r = iterator(__hold.get(), this);
1437 __r = iterator(__hold.get());
1441 #ifndef _LIBCPP_NO_EXCEPTIONS
1444 #endif // _LIBCPP_NO_EXCEPTIONS
1445 for (++__f; __f != __l; ++__f, ++__e, ++__ds)
1447 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1448 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1449 __e.__ptr_->__next_ = __hold.get();
1450 __hold->__prev_ = __e.__ptr_;
1453 #ifndef _LIBCPP_NO_EXCEPTIONS
1459 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1460 __node_pointer __prev = __e.__ptr_->__prev_;
1461 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1464 #if _LIBCPP_DEBUG_LEVEL >= 2
1465 __e = iterator(__prev, this);
1467 __e = iterator(__prev);
1472 #endif // _LIBCPP_NO_EXCEPTIONS
1473 __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_);
1474 base::__sz() += __ds;
1479 template <class _Tp, class _Alloc>
1481 list<_Tp, _Alloc>::push_front(const value_type& __x)
1483 __node_allocator& __na = base::__node_alloc();
1484 typedef __allocator_destructor<__node_allocator> _Dp;
1485 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1486 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1487 __link_nodes(base::__end_.__next_, __hold.get(), __hold.get());
1492 template <class _Tp, class _Alloc>
1494 list<_Tp, _Alloc>::push_back(const value_type& __x)
1496 __node_allocator& __na = base::__node_alloc();
1497 typedef __allocator_destructor<__node_allocator> _Dp;
1498 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1499 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1500 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1501 pointer_to(base::__end_)), __hold.get(), __hold.get());
1506 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1508 template <class _Tp, class _Alloc>
1510 list<_Tp, _Alloc>::push_front(value_type&& __x)
1512 __node_allocator& __na = base::__node_alloc();
1513 typedef __allocator_destructor<__node_allocator> _Dp;
1514 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1515 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1516 __link_nodes(base::__end_.__next_, __hold.get(), __hold.get());
1521 template <class _Tp, class _Alloc>
1523 list<_Tp, _Alloc>::push_back(value_type&& __x)
1525 __node_allocator& __na = base::__node_alloc();
1526 typedef __allocator_destructor<__node_allocator> _Dp;
1527 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1528 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1529 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1530 pointer_to(base::__end_)), __hold.get(), __hold.get());
1535 #ifndef _LIBCPP_HAS_NO_VARIADICS
1537 template <class _Tp, class _Alloc>
1538 template <class... _Args>
1540 list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1542 __node_allocator& __na = base::__node_alloc();
1543 typedef __allocator_destructor<__node_allocator> _Dp;
1544 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1545 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1546 __link_nodes(base::__end_.__next_, __hold.get(), __hold.get());
1551 template <class _Tp, class _Alloc>
1552 template <class... _Args>
1554 list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1556 __node_allocator& __na = base::__node_alloc();
1557 typedef __allocator_destructor<__node_allocator> _Dp;
1558 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1559 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1560 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1561 pointer_to(base::__end_)), __hold.get(), __hold.get());
1566 template <class _Tp, class _Alloc>
1567 template <class... _Args>
1568 typename list<_Tp, _Alloc>::iterator
1569 list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1571 #if _LIBCPP_DEBUG_LEVEL >= 2
1572 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1573 "list::emplace(iterator, args...) called with an iterator not"
1574 " referring to this list");
1576 __node_allocator& __na = base::__node_alloc();
1577 typedef __allocator_destructor<__node_allocator> _Dp;
1578 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1579 __hold->__prev_ = 0;
1580 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1581 __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
1583 #if _LIBCPP_DEBUG_LEVEL >= 2
1584 return iterator(__hold.release(), this);
1586 return iterator(__hold.release());
1590 #endif // _LIBCPP_HAS_NO_VARIADICS
1592 template <class _Tp, class _Alloc>
1593 typename list<_Tp, _Alloc>::iterator
1594 list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1596 #if _LIBCPP_DEBUG_LEVEL >= 2
1597 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1598 "list::insert(iterator, x) called with an iterator not"
1599 " referring to this list");
1601 __node_allocator& __na = base::__node_alloc();
1602 typedef __allocator_destructor<__node_allocator> _Dp;
1603 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1604 __hold->__prev_ = 0;
1605 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1606 __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
1608 #if _LIBCPP_DEBUG_LEVEL >= 2
1609 return iterator(__hold.release(), this);
1611 return iterator(__hold.release());
1615 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1617 template <class _Tp, class _Alloc>
1619 list<_Tp, _Alloc>::pop_front()
1621 _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
1622 __node_allocator& __na = base::__node_alloc();
1623 __node_pointer __n = base::__end_.__next_;
1624 base::__unlink_nodes(__n, __n);
1626 #if _LIBCPP_DEBUG_LEVEL >= 2
1627 __c_node* __c = __get_db()->__find_c_and_lock(this);
1628 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1631 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1632 if (__i->__ptr_ == __n)
1634 (*__p)->__c_ = nullptr;
1635 if (--__c->end_ != __p)
1636 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1639 __get_db()->unlock();
1641 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
1642 __node_alloc_traits::deallocate(__na, __n, 1);
1645 template <class _Tp, class _Alloc>
1647 list<_Tp, _Alloc>::pop_back()
1649 _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list");
1650 __node_allocator& __na = base::__node_alloc();
1651 __node_pointer __n = base::__end_.__prev_;
1652 base::__unlink_nodes(__n, __n);
1654 #if _LIBCPP_DEBUG_LEVEL >= 2
1655 __c_node* __c = __get_db()->__find_c_and_lock(this);
1656 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1659 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1660 if (__i->__ptr_ == __n)
1662 (*__p)->__c_ = nullptr;
1663 if (--__c->end_ != __p)
1664 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1667 __get_db()->unlock();
1669 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
1670 __node_alloc_traits::deallocate(__na, __n, 1);
1673 template <class _Tp, class _Alloc>
1674 typename list<_Tp, _Alloc>::iterator
1675 list<_Tp, _Alloc>::erase(const_iterator __p)
1677 #if _LIBCPP_DEBUG_LEVEL >= 2
1678 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1679 "list::erase(iterator) called with an iterator not"
1680 " referring to this list");
1682 _LIBCPP_ASSERT(__p != end(),
1683 "list::erase(iterator) called with a non-dereferenceable iterator");
1684 __node_allocator& __na = base::__node_alloc();
1685 __node_pointer __n = __p.__ptr_;
1686 __node_pointer __r = __n->__next_;
1687 base::__unlink_nodes(__n, __n);
1689 #if _LIBCPP_DEBUG_LEVEL >= 2
1690 __c_node* __c = __get_db()->__find_c_and_lock(this);
1691 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1694 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1695 if (__i->__ptr_ == __n)
1697 (*__p)->__c_ = nullptr;
1698 if (--__c->end_ != __p)
1699 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1702 __get_db()->unlock();
1704 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
1705 __node_alloc_traits::deallocate(__na, __n, 1);
1706 #if _LIBCPP_DEBUG_LEVEL >= 2
1707 return iterator(__r, this);
1709 return iterator(__r);
1713 template <class _Tp, class _Alloc>
1714 typename list<_Tp, _Alloc>::iterator
1715 list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1717 #if _LIBCPP_DEBUG_LEVEL >= 2
1718 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this,
1719 "list::erase(iterator, iterator) called with an iterator not"
1720 " referring to this list");
1724 __node_allocator& __na = base::__node_alloc();
1725 base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
1728 __node_pointer __n = __f.__ptr_;
1731 #if _LIBCPP_DEBUG_LEVEL >= 2
1732 __c_node* __c = __get_db()->__find_c_and_lock(this);
1733 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1736 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1737 if (__i->__ptr_ == __n)
1739 (*__p)->__c_ = nullptr;
1740 if (--__c->end_ != __p)
1741 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1744 __get_db()->unlock();
1746 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
1747 __node_alloc_traits::deallocate(__na, __n, 1);
1750 #if _LIBCPP_DEBUG_LEVEL >= 2
1751 return iterator(__l.__ptr_, this);
1753 return iterator(__l.__ptr_);
1757 template <class _Tp, class _Alloc>
1759 list<_Tp, _Alloc>::resize(size_type __n)
1761 if (__n < base::__sz())
1762 erase(__iterator(__n), end());
1763 else if (__n > base::__sz())
1765 __n -= base::__sz();
1767 __node_allocator& __na = base::__node_alloc();
1768 typedef __allocator_destructor<__node_allocator> _Dp;
1769 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1770 __hold->__prev_ = 0;
1771 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1773 #if _LIBCPP_DEBUG_LEVEL >= 2
1774 iterator __r = iterator(__hold.release(), this);
1776 iterator __r = iterator(__hold.release());
1779 #ifndef _LIBCPP_NO_EXCEPTIONS
1782 #endif // _LIBCPP_NO_EXCEPTIONS
1783 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1785 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1786 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1787 __e.__ptr_->__next_ = __hold.get();
1788 __hold->__prev_ = __e.__ptr_;
1791 #ifndef _LIBCPP_NO_EXCEPTIONS
1797 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1798 __node_pointer __prev = __e.__ptr_->__prev_;
1799 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1802 #if _LIBCPP_DEBUG_LEVEL >= 2
1803 __e = iterator(__prev, this);
1805 __e = iterator(__prev);
1810 #endif // _LIBCPP_NO_EXCEPTIONS
1811 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1812 pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_);
1813 base::__sz() += __ds;
1817 template <class _Tp, class _Alloc>
1819 list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1821 if (__n < base::__sz())
1822 erase(__iterator(__n), end());
1823 else if (__n > base::__sz())
1825 __n -= base::__sz();
1827 __node_allocator& __na = base::__node_alloc();
1828 typedef __allocator_destructor<__node_allocator> _Dp;
1829 unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1830 __hold->__prev_ = 0;
1831 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1833 #if _LIBCPP_DEBUG_LEVEL >= 2
1834 iterator __r = iterator(__hold.release(), this);
1836 iterator __r = iterator(__hold.release());
1839 #ifndef _LIBCPP_NO_EXCEPTIONS
1842 #endif // _LIBCPP_NO_EXCEPTIONS
1843 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1845 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1846 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1847 __e.__ptr_->__next_ = __hold.get();
1848 __hold->__prev_ = __e.__ptr_;
1851 #ifndef _LIBCPP_NO_EXCEPTIONS
1857 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1858 __node_pointer __prev = __e.__ptr_->__prev_;
1859 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1862 #if _LIBCPP_DEBUG_LEVEL >= 2
1863 __e = iterator(__prev, this);
1865 __e = iterator(__prev);
1870 #endif // _LIBCPP_NO_EXCEPTIONS
1871 __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
1872 pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_);
1873 base::__sz() += __ds;
1877 template <class _Tp, class _Alloc>
1879 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
1881 _LIBCPP_ASSERT(this != &__c,
1882 "list::splice(iterator, list) called with this == &list");
1883 #if _LIBCPP_DEBUG_LEVEL >= 2
1884 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1885 "list::splice(iterator, list) called with an iterator not"
1886 " referring to this list");
1890 __node_pointer __f = __c.__end_.__next_;
1891 __node_pointer __l = __c.__end_.__prev_;
1892 base::__unlink_nodes(__f, __l);
1893 __link_nodes(__p.__ptr_, __f, __l);
1894 base::__sz() += __c.__sz();
1896 #if _LIBCPP_DEBUG_LEVEL >= 2
1897 __libcpp_db* __db = __get_db();
1898 __c_node* __cn1 = __db->__find_c_and_lock(this);
1899 __c_node* __cn2 = __db->__find_c(&__c);
1900 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1903 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1904 if (__i->__ptr_ != static_cast<__node_pointer>(
1905 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
1908 (*__p)->__c_ = __cn1;
1909 if (--__cn2->end_ != __p)
1910 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1918 template <class _Tp, class _Alloc>
1920 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
1922 #if _LIBCPP_DEBUG_LEVEL >= 2
1923 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1924 "list::splice(iterator, list, iterator) called with first iterator not"
1925 " referring to this list");
1926 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c,
1927 "list::splice(iterator, list, iterator) called with second iterator not"
1928 " referring to list argument");
1929 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i),
1930 "list::splice(iterator, list, iterator) called with second iterator not"
1933 if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
1935 __node_pointer __f = __i.__ptr_;
1936 base::__unlink_nodes(__f, __f);
1937 __link_nodes(__p.__ptr_, __f, __f);
1940 #if _LIBCPP_DEBUG_LEVEL >= 2
1941 __libcpp_db* __db = __get_db();
1942 __c_node* __cn1 = __db->__find_c_and_lock(this);
1943 __c_node* __cn2 = __db->__find_c(&__c);
1944 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1947 iterator* __j = static_cast<iterator*>((*__p)->__i_);
1948 if (__j->__ptr_ == __f)
1951 (*__p)->__c_ = __cn1;
1952 if (--__cn2->end_ != __p)
1953 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1961 template <class _Tp, class _Alloc>
1963 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
1965 #if _LIBCPP_DEBUG_LEVEL >= 2
1966 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1967 "list::splice(iterator, list, iterator, iterator) called with first iterator not"
1968 " referring to this list");
1969 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c,
1970 "list::splice(iterator, list, iterator, iterator) called with second iterator not"
1971 " referring to list argument");
1974 for (const_iterator __i = __f; __i != __l; ++__i)
1975 _LIBCPP_ASSERT(__i != __p,
1976 "list::splice(iterator, list, iterator, iterator)"
1977 " called with the first iterator within the range"
1978 " of the second and third iterators");
1985 size_type __s = _VSTD::distance(__f, __l);
1987 base::__sz() += __s;
1989 __node_pointer __first = __f.__ptr_;
1991 __node_pointer __last = __l.__ptr_;
1992 base::__unlink_nodes(__first, __last);
1993 __link_nodes(__p.__ptr_, __first, __last);
1994 #if _LIBCPP_DEBUG_LEVEL >= 2
1995 __libcpp_db* __db = __get_db();
1996 __c_node* __cn1 = __db->__find_c_and_lock(this);
1997 __c_node* __cn2 = __db->__find_c(&__c);
1998 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2001 iterator* __j = static_cast<iterator*>((*__p)->__i_);
2002 for (__node_pointer __k = __f.__ptr_;
2003 __k != __l.__ptr_; __k = __k->__next_)
2005 if (__j->__ptr_ == __k)
2008 (*__p)->__c_ = __cn1;
2009 if (--__cn2->end_ != __p)
2010 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2019 template <class _Tp, class _Alloc>
2021 list<_Tp, _Alloc>::remove(const value_type& __x)
2023 for (iterator __i = begin(), __e = end(); __i != __e;)
2027 iterator __j = _VSTD::next(__i);
2028 for (; __j != __e && *__j == __x; ++__j)
2030 __i = erase(__i, __j);
2037 template <class _Tp, class _Alloc>
2038 template <class _Pred>
2040 list<_Tp, _Alloc>::remove_if(_Pred __pred)
2042 for (iterator __i = begin(), __e = end(); __i != __e;)
2046 iterator __j = _VSTD::next(__i);
2047 for (; __j != __e && __pred(*__j); ++__j)
2049 __i = erase(__i, __j);
2056 template <class _Tp, class _Alloc>
2057 inline _LIBCPP_INLINE_VISIBILITY
2059 list<_Tp, _Alloc>::unique()
2061 unique(__equal_to<value_type>());
2064 template <class _Tp, class _Alloc>
2065 template <class _BinaryPred>
2067 list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
2069 for (iterator __i = begin(), __e = end(); __i != __e;)
2071 iterator __j = _VSTD::next(__i);
2072 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
2075 __i = erase(__i, __j);
2079 template <class _Tp, class _Alloc>
2080 inline _LIBCPP_INLINE_VISIBILITY
2082 list<_Tp, _Alloc>::merge(list& __c)
2084 merge(__c, __less<value_type>());
2087 template <class _Tp, class _Alloc>
2088 template <class _Comp>
2090 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2094 iterator __f1 = begin();
2095 iterator __e1 = end();
2096 iterator __f2 = __c.begin();
2097 iterator __e2 = __c.end();
2098 while (__f1 != __e1 && __f2 != __e2)
2100 if (__comp(*__f2, *__f1))
2103 iterator __m2 = _VSTD::next(__f2);
2104 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
2106 base::__sz() += __ds;
2108 __node_pointer __f = __f2.__ptr_;
2109 __node_pointer __l = __m2.__ptr_->__prev_;
2111 base::__unlink_nodes(__f, __l);
2112 __m2 = _VSTD::next(__f1);
2113 __link_nodes(__f1.__ptr_, __f, __l);
2120 #if _LIBCPP_DEBUG_LEVEL >= 2
2121 __libcpp_db* __db = __get_db();
2122 __c_node* __cn1 = __db->__find_c_and_lock(this);
2123 __c_node* __cn2 = __db->__find_c(&__c);
2124 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2127 iterator* __i = static_cast<iterator*>((*__p)->__i_);
2128 if (__i->__ptr_ != static_cast<__node_pointer>(
2129 pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
2132 (*__p)->__c_ = __cn1;
2133 if (--__cn2->end_ != __p)
2134 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2142 template <class _Tp, class _Alloc>
2143 inline _LIBCPP_INLINE_VISIBILITY
2145 list<_Tp, _Alloc>::sort()
2147 sort(__less<value_type>());
2150 template <class _Tp, class _Alloc>
2151 template <class _Comp>
2152 inline _LIBCPP_INLINE_VISIBILITY
2154 list<_Tp, _Alloc>::sort(_Comp __comp)
2156 __sort(begin(), end(), base::__sz(), __comp);
2159 template <class _Tp, class _Alloc>
2160 template <class _Comp>
2161 typename list<_Tp, _Alloc>::iterator
2162 list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
2170 if (__comp(*--__e2, *__f1))
2172 __node_pointer __f = __e2.__ptr_;
2173 base::__unlink_nodes(__f, __f);
2174 __link_nodes(__f1.__ptr_, __f, __f);
2179 size_type __n2 = __n / 2;
2180 iterator __e1 = _VSTD::next(__f1, __n2);
2181 iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp);
2182 iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2183 if (__comp(*__f2, *__f1))
2185 iterator __m2 = _VSTD::next(__f2);
2186 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2188 __node_pointer __f = __f2.__ptr_;
2189 __node_pointer __l = __m2.__ptr_->__prev_;
2192 base::__unlink_nodes(__f, __l);
2193 __m2 = _VSTD::next(__f1);
2194 __link_nodes(__f1.__ptr_, __f, __l);
2199 while (__f1 != __e1 && __f2 != __e2)
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_;
2211 base::__unlink_nodes(__f, __l);
2212 __m2 = _VSTD::next(__f1);
2213 __link_nodes(__f1.__ptr_, __f, __l);
2222 template <class _Tp, class _Alloc>
2224 list<_Tp, _Alloc>::reverse() _NOEXCEPT
2226 if (base::__sz() > 1)
2228 iterator __e = end();
2229 for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
2231 _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
2232 __i.__ptr_ = __i.__ptr_->__prev_;
2234 _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
2238 template <class _Tp, class _Alloc>
2240 list<_Tp, _Alloc>::__invariants() const
2242 return size() == _VSTD::distance(begin(), end());
2245 #if _LIBCPP_DEBUG_LEVEL >= 2
2247 template <class _Tp, class _Alloc>
2249 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
2251 return __i->__ptr_ != static_cast<__node_pointer>(
2252 pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(this->__end_)));
2255 template <class _Tp, class _Alloc>
2257 list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
2259 return !empty() && __i->__ptr_ != base::__end_.__next_;
2262 template <class _Tp, class _Alloc>
2264 list<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2269 template <class _Tp, class _Alloc>
2271 list<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2276 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2278 template <class _Tp, class _Alloc>
2279 inline _LIBCPP_INLINE_VISIBILITY
2281 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2283 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2286 template <class _Tp, class _Alloc>
2287 inline _LIBCPP_INLINE_VISIBILITY
2289 operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2291 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2294 template <class _Tp, class _Alloc>
2295 inline _LIBCPP_INLINE_VISIBILITY
2297 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2299 return !(__x == __y);
2302 template <class _Tp, class _Alloc>
2303 inline _LIBCPP_INLINE_VISIBILITY
2305 operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2310 template <class _Tp, class _Alloc>
2311 inline _LIBCPP_INLINE_VISIBILITY
2313 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2315 return !(__x < __y);
2318 template <class _Tp, class _Alloc>
2319 inline _LIBCPP_INLINE_VISIBILITY
2321 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2323 return !(__y < __x);
2326 template <class _Tp, class _Alloc>
2327 inline _LIBCPP_INLINE_VISIBILITY
2329 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2330 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2335 _LIBCPP_END_NAMESPACE_STD
2337 #endif // _LIBCPP_LIST