xref: /llvm-project-15.0.7/libcxx/include/list (revision a462f5cc) 
1// -*- C++ -*-
2//===---------------------------- list ------------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_LIST
12#define _LIBCPP_LIST
13
14/*
15    list synopsis
16
17namespace std
18{
19
20template <class T, class Alloc = allocator<T> >
21class list
22{
23public:
24
25    // types:
26    typedef T value_type;
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;
38
39    list();
40    explicit list(const allocator_type& a);
41    explicit list(size_type n);
42    list(size_type n, const value_type& value);
43    list(size_type n, const value_type& value, const allocator_type& a);
44    template <class Iter>
45        list(Iter first, Iter last);
46    template <class Iter>
47        list(Iter first, Iter last, const allocator_type& a);
48    list(const list& x);
49    list(const list&, const allocator_type& a);
50    list(list&& x);
51    list(list&&, const allocator_type& a);
52    list(initializer_list<value_type>);
53    list(initializer_list<value_type>, const allocator_type& a);
54
55    ~list();
56
57    list& operator=(const list& x);
58    list& operator=(list&& x);
59    list& operator=(initializer_list<value_type>);
60    template <class Iter>
61        void assign(Iter first, Iter last);
62    void assign(size_type n, const value_type& t);
63    void assign(initializer_list<value_type>);
64
65    allocator_type get_allocator() const;
66
67    iterator begin();
68    const_iterator begin() const;
69    iterator end();
70    const_iterator end() const;
71    reverse_iterator rbegin();
72    const_reverse_iterator rbegin() const;
73    reverse_iterator rend();
74    const_reverse_iterator rend() const;
75    const_iterator cbegin() const;
76    const_iterator cend() const;
77    const_reverse_iterator crbegin() const;
78    const_reverse_iterator crend() const;
79
80    reference front();
81    const_reference front() const;
82    reference back();
83    const_reference back() const;
84
85    bool empty() const;
86    size_type size() const;
87    size_type max_size() const;
88
89    template <class... Args>
90        void emplace_front(Args&&... args);
91    void pop_front();
92    template <class... Args>
93        void emplace_back(Args&&... args);
94    void pop_back();
95    void push_front(const value_type& x);
96    void push_front(value_type&& x);
97    void push_back(const value_type& x);
98    void push_back(value_type&& x);
99    template <class... Args>
100        iterator emplace(const_iterator position, Args&&... args);
101    iterator insert(const_iterator position, const value_type& x);
102    iterator insert(const_iterator position, value_type&& x);
103    iterator insert(const_iterator position, size_type n, const value_type& x);
104    template <class Iter>
105        iterator insert(const_iterator position, Iter first, Iter last);
106    iterator insert(const_iterator position, initializer_list<value_type> il);
107
108    iterator erase(const_iterator position);
109    iterator erase(const_iterator position, const_iterator last);
110
111    void resize(size_type sz);
112    void resize(size_type sz, const value_type& c);
113
114    void swap(list<value_type,allocator_type>&);
115    void clear();
116
117    void splice(const_iterator position, list& x);
118    void splice(const_iterator position, list&& x);
119    void splice(const_iterator position, list& x, const_iterator i);
120    void splice(const_iterator position, list&& x, const_iterator i);
121    void splice(const_iterator position, list& x, const_iterator first,
122                                                  const_iterator last);
123    void splice(const_iterator position, list&& x, const_iterator first,
124                                                  const_iterator last);
125
126    void remove(const value_type& value);
127    template <class Pred> void remove_if(Pred pred);
128    void unique();
129    template <class BinaryPredicate>
130        void unique(BinaryPredicate binary_pred);
131    void merge(list& x);
132    void merge(list&& x);
133    template <class Compare>
134        void merge(list& x, Compare comp);
135    template <class Compare>
136        void merge(list&& x, Compare comp);
137    void sort();
138    template <class Compare>
139        void sort(Compare comp);
140    void reverse();
141};
142
143template <class T, class Alloc>
144    bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
145template <class T, class Alloc>
146    bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);
147template <class T, class Alloc>
148    bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);
149template <class T, class Alloc>
150    bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);
151template <class T, class Alloc>
152    bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);
153template <class T, class Alloc>
154    bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);
155
156template <class T, class Alloc>
157    void swap(list<T,Alloc>& x, list<T,Alloc>& y);
158
159}  // std
160
161*/
162
163#include <__config>
164
165#include <memory>
166#include <limits>
167#include <initializer_list>
168#include <iterator>
169#include <algorithm>
170
171#pragma GCC system_header
172
173_LIBCPP_BEGIN_NAMESPACE_STD
174
175template <class, class> struct __list_node;
176
177template <class _Tp, class _VoidPtr>
178struct __list_node_base
179{
180    typedef typename pointer_traits<_VoidPtr>::template
181#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
182        rebind<__list_node<_Tp, _VoidPtr> > pointer;
183#else
184        rebind<__list_node<_Tp, _VoidPtr> >::other pointer;
185#endif
186
187    pointer __prev_;
188    pointer __next_;
189
190    _LIBCPP_INLINE_VISIBILITY
191    __list_node_base()
192        : __prev_(static_cast<pointer>(this)),
193          __next_(static_cast<pointer>(this))
194          {}
195};
196
197template <class _Tp, class _VoidPtr>
198struct __list_node
199    : public __list_node_base<_Tp, _VoidPtr>
200{
201    _Tp __value_;
202};
203
204template <class, class> class list;
205template <class, class> class __list_imp;
206template <class, class> class __list_const_iterator;
207
208template <class _Tp, class _VoidPtr>
209class _LIBCPP_VISIBLE __list_iterator
210{
211    typedef typename pointer_traits<_VoidPtr>::template
212#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
213        rebind<__list_node<_Tp, _VoidPtr> > __node_pointer;
214#else
215        rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer;
216#endif
217
218    __node_pointer __ptr_;
219
220    _LIBCPP_INLINE_VISIBILITY
221    explicit __list_iterator(__node_pointer __p) : __ptr_(__p) {}
222
223    template<class, class> friend class list;
224    template<class, class> friend class __list_imp;
225    template<class, class> friend class __list_const_iterator;
226public:
227    typedef bidirectional_iterator_tag       iterator_category;
228    typedef _Tp                              value_type;
229    typedef value_type&                      reference;
230    typedef typename pointer_traits<_VoidPtr>::template
231#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
232            rebind<value_type>
233#else
234            rebind<value_type>::other
235#endif
236                                             pointer;
237    typedef typename pointer_traits<pointer>::difference_type difference_type;
238
239    _LIBCPP_INLINE_VISIBILITY
240    reference operator*() const {return __ptr_->__value_;}
241    _LIBCPP_INLINE_VISIBILITY
242    pointer operator->() const {return &(operator*());}
243
244    _LIBCPP_INLINE_VISIBILITY
245    __list_iterator& operator++() {__ptr_ = __ptr_->__next_; return *this;}
246    _LIBCPP_INLINE_VISIBILITY
247    __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;}
248
249    _LIBCPP_INLINE_VISIBILITY
250    __list_iterator& operator--() {__ptr_ = __ptr_->__prev_; return *this;}
251    _LIBCPP_INLINE_VISIBILITY
252    __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}
253
254    friend _LIBCPP_INLINE_VISIBILITY
255    bool operator==(const __list_iterator& __x, const __list_iterator& __y)
256        {return __x.__ptr_ == __y.__ptr_;}
257    friend _LIBCPP_INLINE_VISIBILITY
258     bool operator!=(const __list_iterator& __x, const __list_iterator& __y)
259        {return !(__x == __y);}
260};
261
262template <class _Tp, class _VoidPtr>
263class _LIBCPP_VISIBLE __list_const_iterator
264{
265    typedef typename pointer_traits<_VoidPtr>::template
266#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
267        rebind<const __list_node<_Tp, _VoidPtr> > __node_pointer;
268#else
269        rebind<const __list_node<_Tp, _VoidPtr> >::other __node_pointer;
270#endif
271
272    __node_pointer __ptr_;
273
274    _LIBCPP_INLINE_VISIBILITY
275    explicit __list_const_iterator(__node_pointer __p) : __ptr_(__p) {}
276
277    template<class, class> friend class list;
278    template<class, class> friend class __list_imp;
279public:
280    typedef bidirectional_iterator_tag       iterator_category;
281    typedef _Tp                              value_type;
282    typedef const value_type&                reference;
283    typedef typename pointer_traits<_VoidPtr>::template
284#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
285            rebind<const value_type>
286#else
287            rebind<const value_type>::other
288#endif
289                                             pointer;
290    typedef typename pointer_traits<pointer>::difference_type difference_type;
291
292    _LIBCPP_INLINE_VISIBILITY
293    __list_const_iterator(__list_iterator<_Tp, _VoidPtr> __p) : __ptr_(__p.__ptr_) {}
294
295    _LIBCPP_INLINE_VISIBILITY
296    reference operator*() const {return __ptr_->__value_;}
297    _LIBCPP_INLINE_VISIBILITY
298    pointer operator->() const {return &(operator*());}
299
300    _LIBCPP_INLINE_VISIBILITY
301    __list_const_iterator& operator++() {__ptr_ = __ptr_->__next_; return *this;}
302    _LIBCPP_INLINE_VISIBILITY
303    __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;}
304
305    _LIBCPP_INLINE_VISIBILITY
306    __list_const_iterator& operator--() {__ptr_ = __ptr_->__prev_; return *this;}
307    _LIBCPP_INLINE_VISIBILITY
308    __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}
309
310    friend _LIBCPP_INLINE_VISIBILITY
311    bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y)
312        {return __x.__ptr_ == __y.__ptr_;}
313    friend _LIBCPP_INLINE_VISIBILITY
314    bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y)
315        {return !(__x == __y);}
316};
317
318template <class _Tp, class _Alloc>
319class __list_imp
320{
321    __list_imp(const __list_imp&);
322    __list_imp& operator=(const __list_imp&);
323protected:
324    typedef _Tp                                                     value_type;
325    typedef _Alloc                                                  allocator_type;
326    typedef allocator_traits<allocator_type>                        __alloc_traits;
327    typedef typename __alloc_traits::size_type                      size_type;
328    typedef typename __alloc_traits::void_pointer                   __void_pointer;
329    typedef __list_iterator<value_type, __void_pointer>             iterator;
330    typedef __list_const_iterator<value_type, __void_pointer>       const_iterator;
331    typedef __list_node_base<value_type, __void_pointer>            __node_base;
332    typedef __list_node<value_type, __void_pointer>                 __node;
333    typedef typename __alloc_traits::template
334#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
335                rebind_alloc<__node>
336#else
337                rebind_alloc<__node>::other
338#endif
339                                                                     __node_allocator;
340    typedef allocator_traits<__node_allocator>                       __node_alloc_traits;
341    typedef typename __node_alloc_traits::pointer                    __node_pointer;
342    typedef typename __node_alloc_traits::const_pointer              __node_const_pointer;
343    typedef typename __alloc_traits::pointer                         pointer;
344    typedef typename __alloc_traits::const_pointer                   const_pointer;
345    typedef typename __alloc_traits::difference_type                 difference_type;
346
347    __node_base __end_;
348    __compressed_pair<size_type, __node_allocator> __size_alloc_;
349
350    _LIBCPP_INLINE_VISIBILITY
351          size_type& __sz()       {return __size_alloc_.first();}
352    _LIBCPP_INLINE_VISIBILITY
353    const size_type& __sz() const {return __size_alloc_.first();}
354    _LIBCPP_INLINE_VISIBILITY
355          __node_allocator& __node_alloc()       {return __size_alloc_.second();}
356    _LIBCPP_INLINE_VISIBILITY
357    const __node_allocator& __node_alloc() const {return __size_alloc_.second();}
358
359    static void __unlink_nodes(__node_base& __f, __node_base& __l);
360
361    __list_imp();
362    __list_imp(const allocator_type& __a);
363    ~__list_imp();
364    void clear();
365    _LIBCPP_INLINE_VISIBILITY
366    bool empty() const {return __sz() == 0;}
367
368    _LIBCPP_INLINE_VISIBILITY
369          iterator begin()       {return       iterator(__end_.__next_);}
370    _LIBCPP_INLINE_VISIBILITY
371    const_iterator begin() const {return const_iterator(__end_.__next_);}
372    _LIBCPP_INLINE_VISIBILITY
373          iterator end()       {return       iterator(static_cast<__node_pointer>      (&__end_));}
374    _LIBCPP_INLINE_VISIBILITY
375    const_iterator end() const {return const_iterator(static_cast<__node_const_pointer>(&__end_));}
376
377    void swap(__list_imp& __c);
378
379    _LIBCPP_INLINE_VISIBILITY
380    void __copy_assign_alloc(const __list_imp& __c)
381        {__copy_assign_alloc(__c, integral_constant<bool,
382                      __node_alloc_traits::propagate_on_container_copy_assignment::value>());}
383
384    _LIBCPP_INLINE_VISIBILITY
385    void __move_assign_alloc(__list_imp& __c)
386        {__move_assign_alloc(__c, integral_constant<bool,
387                      __node_alloc_traits::propagate_on_container_move_assignment::value>());}
388
389private:
390    _LIBCPP_INLINE_VISIBILITY
391    static void __swap_alloc(__node_allocator& __x, __node_allocator& __y)
392        {__swap_alloc(__x, __y, integral_constant<bool,
393                      __node_alloc_traits::propagate_on_container_swap::value>());}
394    _LIBCPP_INLINE_VISIBILITY
395    static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type)
396        {
397            using _STD::swap;
398            swap(__x, __y);
399        }
400    _LIBCPP_INLINE_VISIBILITY
401    static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type)
402        {}
403
404    _LIBCPP_INLINE_VISIBILITY
405    void __copy_assign_alloc(const __list_imp& __c, true_type)
406        {
407            if (__node_alloc() != __c.__node_alloc())
408                clear();
409            __node_alloc() = __c.__node_alloc();
410        }
411
412    _LIBCPP_INLINE_VISIBILITY
413    void __copy_assign_alloc(const __list_imp& __c, false_type)
414        {}
415
416    _LIBCPP_INLINE_VISIBILITY
417    void __move_assign_alloc(const __list_imp& __c, true_type)
418        {
419            __node_alloc() = _STD::move(__c.__node_alloc());
420        }
421
422    _LIBCPP_INLINE_VISIBILITY
423    void __move_assign_alloc(const __list_imp& __c, false_type)
424        {}
425};
426
427// Unlink nodes [__f, __l]
428template <class _Tp, class _Alloc>
429inline _LIBCPP_INLINE_VISIBILITY
430void
431__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_base& __f, __node_base& __l)
432{
433    __f.__prev_->__next_ = __l.__next_;
434    __l.__next_->__prev_ = __f.__prev_;
435}
436
437template <class _Tp, class _Alloc>
438inline _LIBCPP_INLINE_VISIBILITY
439__list_imp<_Tp, _Alloc>::__list_imp()
440    : __size_alloc_(0)
441{
442}
443
444template <class _Tp, class _Alloc>
445inline _LIBCPP_INLINE_VISIBILITY
446__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a)
447    : __size_alloc_(0, __node_allocator(__a))
448{
449}
450
451template <class _Tp, class _Alloc>
452__list_imp<_Tp, _Alloc>::~__list_imp()
453{
454    clear();
455}
456
457template <class _Tp, class _Alloc>
458void
459__list_imp<_Tp, _Alloc>::clear()
460{
461    if (!empty())
462    {
463        __node_allocator& __na = __node_alloc();
464        iterator __f = begin();
465        iterator __l = end();
466        __unlink_nodes(*__f.__ptr_, *__l.__ptr_->__prev_);
467        __sz() = 0;
468        while (__f != __l)
469        {
470            __node& __n = *__f.__ptr_;
471            ++__f;
472            __node_alloc_traits::destroy(__na, addressof(__n.__value_));
473            __node_alloc_traits::deallocate(__na, addressof(__n), 1);
474        }
475    }
476}
477
478template <class _Tp, class _Alloc>
479void
480__list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
481{
482    using _STD::swap;
483    __swap_alloc(__node_alloc(), __c.__node_alloc());
484    swap(__sz(), __c.__sz());
485    swap(__end_, __c.__end_);
486    if (__sz() == 0)
487        __end_.__next_ = __end_.__prev_ = &static_cast<__node&>(__end_);
488    else
489        __end_.__prev_->__next_ = __end_.__next_->__prev_
490                                = &static_cast<__node&>(__end_);
491    if (__c.__sz() == 0)
492        __c.__end_.__next_ = __c.__end_.__prev_
493                           = &static_cast<__node&>(__c.__end_);
494    else
495        __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_
496                                    = &static_cast<__node&>(__c.__end_);
497}
498
499template <class _Tp, class _Alloc = allocator<_Tp> >
500class _LIBCPP_VISIBLE list
501    : private __list_imp<_Tp, _Alloc>
502{
503    typedef __list_imp<_Tp, _Alloc> base;
504    typedef typename base::__node              __node;
505    typedef typename base::__node_allocator    __node_allocator;
506    typedef typename base::__node_pointer      __node_pointer;
507    typedef typename base::__node_alloc_traits __node_alloc_traits;
508
509public:
510    typedef _Tp                                      value_type;
511    typedef _Alloc                                   allocator_type;
512    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
513                  "Invalid allocator::value_type");
514    typedef value_type&                              reference;
515    typedef const value_type&                        const_reference;
516    typedef typename base::pointer                   pointer;
517    typedef typename base::const_pointer             const_pointer;
518    typedef typename base::size_type                 size_type;
519    typedef typename base::difference_type           difference_type;
520    typedef typename base::iterator                  iterator;
521    typedef typename base::const_iterator            const_iterator;
522    typedef _STD::reverse_iterator<iterator>         reverse_iterator;
523    typedef _STD::reverse_iterator<const_iterator>   const_reverse_iterator;
524
525    _LIBCPP_INLINE_VISIBILITY
526    list() {}
527    _LIBCPP_INLINE_VISIBILITY
528    list(const allocator_type& __a) : base(__a) {}
529    list(size_type __n);
530    list(size_type __n, const value_type& __x);
531    list(size_type __n, const value_type& __x, const allocator_type& __a);
532    template <class _InpIter>
533        list(_InpIter __f, _InpIter __l,
534             typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
535    template <class _InpIter>
536        list(_InpIter __f, _InpIter __l, const allocator_type& __a,
537             typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
538
539    list(const list& __c);
540    list(const list& __c, const allocator_type& __a);
541    list& operator=(const list& __c);
542    list(initializer_list<value_type> __il);
543    list(initializer_list<value_type> __il, const allocator_type& __a);
544#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
545    list(list&& __c);
546    list(list&& __c, const allocator_type& __a);
547    list& operator=(list&& __c);
548#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
549    _LIBCPP_INLINE_VISIBILITY
550    list& operator=(initializer_list<value_type> __il)
551        {assign(__il.begin(), __il.end()); return *this;}
552
553    template <class _InpIter>
554        void assign(_InpIter __f, _InpIter __l,
555             typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
556    void assign(size_type __n, const value_type& __x);
557    _LIBCPP_INLINE_VISIBILITY
558    void assign(initializer_list<value_type> __il)
559        {assign(__il.begin(), __il.end());}
560
561    allocator_type get_allocator() const;
562
563    _LIBCPP_INLINE_VISIBILITY
564    size_type size() const     {return base::__sz();}
565    _LIBCPP_INLINE_VISIBILITY
566    bool empty() const         {return base::empty();}
567    _LIBCPP_INLINE_VISIBILITY
568    size_type max_size() const {return numeric_limits<difference_type>::max();}
569
570    _LIBCPP_INLINE_VISIBILITY
571          iterator begin()        {return base::begin();}
572    _LIBCPP_INLINE_VISIBILITY
573    const_iterator begin()  const {return base::begin();}
574    _LIBCPP_INLINE_VISIBILITY
575          iterator end()          {return base::end();}
576    _LIBCPP_INLINE_VISIBILITY
577    const_iterator end()    const {return base::end();}
578    _LIBCPP_INLINE_VISIBILITY
579    const_iterator cbegin() const {return base::begin();}
580    _LIBCPP_INLINE_VISIBILITY
581    const_iterator cend()   const {return base::end();}
582
583    _LIBCPP_INLINE_VISIBILITY
584          reverse_iterator rbegin()        {return       reverse_iterator(end());}
585    _LIBCPP_INLINE_VISIBILITY
586    const_reverse_iterator rbegin()  const {return const_reverse_iterator(end());}
587    _LIBCPP_INLINE_VISIBILITY
588          reverse_iterator rend()          {return       reverse_iterator(begin());}
589    _LIBCPP_INLINE_VISIBILITY
590    const_reverse_iterator rend()    const {return const_reverse_iterator(begin());}
591    _LIBCPP_INLINE_VISIBILITY
592    const_reverse_iterator crbegin() const {return const_reverse_iterator(end());}
593    _LIBCPP_INLINE_VISIBILITY
594    const_reverse_iterator crend()   const {return const_reverse_iterator(begin());}
595
596    _LIBCPP_INLINE_VISIBILITY
597          reference front()        {return base::__end_.__next_->__value_;}
598    _LIBCPP_INLINE_VISIBILITY
599    const_reference front() const  {return base::__end_.__next_->__value_;}
600    _LIBCPP_INLINE_VISIBILITY
601          reference back()         {return base::__end_.__prev_->__value_;}
602    _LIBCPP_INLINE_VISIBILITY
603    const_reference back()  const  {return base::__end_.__prev_->__value_;}
604
605#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
606    void push_front(value_type&& __x);
607    void push_back(value_type&& __x);
608#ifndef _LIBCPP_HAS_NO_VARIADICS
609    template <class... _Args>
610       void emplace_front(_Args&&... __args);
611    template <class... _Args>
612        void emplace_back(_Args&&... __args);
613    template <class... _Args>
614        iterator emplace(const_iterator __p, _Args&&... __args);
615#endif  // _LIBCPP_HAS_NO_VARIADICS
616    iterator insert(const_iterator __p, value_type&& __x);
617#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
618
619    void push_front(const value_type& __x);
620    void push_back(const value_type& __x);
621
622    iterator insert(const_iterator __p, const value_type& __x);
623    iterator insert(const_iterator __p, size_type __n, const value_type& __x);
624    template <class _InpIter>
625        iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
626             typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
627    _LIBCPP_INLINE_VISIBILITY
628    iterator insert(const_iterator __p, initializer_list<value_type> __il)
629        {return insert(__p, __il.begin(), __il.end());}
630
631    _LIBCPP_INLINE_VISIBILITY
632    void swap(list& __c) {base::swap(__c);}
633    _LIBCPP_INLINE_VISIBILITY
634    void clear() {base::clear();}
635
636    void pop_front();
637    void pop_back();
638
639    iterator erase(const_iterator __p);
640    iterator erase(const_iterator __f, const_iterator __l);
641
642    void resize(size_type __n);
643    void resize(size_type __n, const value_type& __x);
644
645    void splice(const_iterator __p, list& __c);
646#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
647    _LIBCPP_INLINE_VISIBILITY
648    void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
649#endif
650    void splice(const_iterator __p, list& __c, const_iterator __i);
651#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
652    _LIBCPP_INLINE_VISIBILITY
653    void splice(const_iterator __p, list&& __c, const_iterator __i)
654        {splice(__p, __c, __i);}
655#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
656    void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
657#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
658    _LIBCPP_INLINE_VISIBILITY
659    void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
660        {splice(__p, __c, __f, __l);}
661#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
662
663    void remove(const value_type& __x);
664    template <class _Pred> void remove_if(_Pred __pred);
665    void unique();
666    template <class _BinaryPred>
667        void unique(_BinaryPred __binary_pred);
668    void merge(list& __c);
669#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
670    _LIBCPP_INLINE_VISIBILITY
671    void merge(list&& __c) {merge(__c);}
672#endif
673    template <class _Comp>
674        void merge(list& __c, _Comp __comp);
675#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
676    template <class _Comp>
677    _LIBCPP_INLINE_VISIBILITY
678        void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
679#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
680    void sort();
681    template <class _Comp>
682        void sort(_Comp __comp);
683
684    void reverse();
685
686private:
687    static void __link_nodes(__node& __p, __node& __f, __node& __l);
688    iterator __iterator(size_type __n);
689    template <class _Comp>
690        static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
691
692    void __move_assign(list& __c, true_type);
693    void __move_assign(list& __c, false_type);
694};
695
696// Link in nodes [__f, __l] just prior to __p
697template <class _Tp, class _Alloc>
698inline _LIBCPP_INLINE_VISIBILITY
699void
700list<_Tp, _Alloc>::__link_nodes(__node& __p, __node& __f, __node& __l)
701{
702    __p.__prev_->__next_ = &__f;
703    __f.__prev_ = __p.__prev_;
704    __p.__prev_ = &__l;
705    __l.__next_ = &__p;
706}
707
708template <class _Tp, class _Alloc>
709inline _LIBCPP_INLINE_VISIBILITY
710typename list<_Tp, _Alloc>::iterator
711list<_Tp, _Alloc>::__iterator(size_type __n)
712{
713    return __n <= base::__sz() / 2 ? next(begin(), __n)
714                                   : prev(end(), base::__sz() - __n);
715}
716
717template <class _Tp, class _Alloc>
718list<_Tp, _Alloc>::list(size_type __n)
719{
720    for (; __n > 0; --__n)
721#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
722        emplace_back();
723#else
724        push_back(value_type());
725#endif
726}
727
728template <class _Tp, class _Alloc>
729list<_Tp, _Alloc>::list(size_type __n, const value_type& __x)
730{
731    for (; __n > 0; --__n)
732        push_back(__x);
733}
734
735template <class _Tp, class _Alloc>
736list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a)
737    : base(__a)
738{
739    for (; __n > 0; --__n)
740        push_back(__x);
741}
742
743template <class _Tp, class _Alloc>
744template <class _InpIter>
745list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
746                        typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
747{
748    for (; __f != __l; ++__f)
749        push_back(*__f);
750}
751
752template <class _Tp, class _Alloc>
753template <class _InpIter>
754list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
755                        typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
756    : base(__a)
757{
758    for (; __f != __l; ++__f)
759        push_back(*__f);
760}
761
762template <class _Tp, class _Alloc>
763list<_Tp, _Alloc>::list(const list& __c)
764    : base(allocator_type(
765           __node_alloc_traits::select_on_container_copy_construction(
766                __c.__node_alloc())))
767{
768    for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
769        push_back(*__i);
770}
771
772template <class _Tp, class _Alloc>
773list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a)
774    : base(__a)
775{
776    for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
777        push_back(*__i);
778}
779
780template <class _Tp, class _Alloc>
781list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a)
782    : base(__a)
783{
784    for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
785            __e = __il.end(); __i != __e; ++__i)
786        push_back(*__i);
787}
788
789template <class _Tp, class _Alloc>
790list<_Tp, _Alloc>::list(initializer_list<value_type> __il)
791{
792    for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
793            __e = __il.end(); __i != __e; ++__i)
794        push_back(*__i);
795}
796
797template <class _Tp, class _Alloc>
798inline _LIBCPP_INLINE_VISIBILITY
799list<_Tp, _Alloc>&
800list<_Tp, _Alloc>::operator=(const list& __c)
801{
802    if (this != &__c)
803    {
804        base::__copy_assign_alloc(__c);
805        assign(__c.begin(), __c.end());
806    }
807    return *this;
808}
809
810#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
811
812template <class _Tp, class _Alloc>
813inline _LIBCPP_INLINE_VISIBILITY
814list<_Tp, _Alloc>::list(list&& __c)
815    : base(allocator_type(_STD::move(__c.__node_alloc())))
816{
817    splice(end(), __c);
818}
819
820template <class _Tp, class _Alloc>
821inline _LIBCPP_INLINE_VISIBILITY
822list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a)
823    : base(__a)
824{
825    if (__a == __c.get_allocator())
826        splice(end(), __c);
827    else
828    {
829        typedef move_iterator<iterator> _I;
830        assign(_I(__c.begin()), _I(__c.end()));
831    }
832}
833
834template <class _Tp, class _Alloc>
835inline _LIBCPP_INLINE_VISIBILITY
836list<_Tp, _Alloc>&
837list<_Tp, _Alloc>::operator=(list&& __c)
838{
839    __move_assign(__c, integral_constant<bool,
840          __node_alloc_traits::propagate_on_container_move_assignment::value>());
841    return *this;
842}
843
844template <class _Tp, class _Alloc>
845void
846list<_Tp, _Alloc>::__move_assign(list& __c, false_type)
847{
848    if (base::__node_alloc() != __c.__node_alloc())
849    {
850        typedef move_iterator<iterator> _I;
851        assign(_I(__c.begin()), _I(__c.end()));
852    }
853    else
854        __move_assign(__c, true_type());
855}
856
857template <class _Tp, class _Alloc>
858void
859list<_Tp, _Alloc>::__move_assign(list& __c, true_type)
860{
861    clear();
862    base::__move_assign_alloc(__c);
863    splice(end(), __c);
864}
865
866#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
867
868template <class _Tp, class _Alloc>
869template <class _InpIter>
870void
871list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l,
872                          typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
873{
874    iterator __i = begin();
875    iterator __e = end();
876    for (; __f != __l && __i != __e; ++__f, ++__i)
877        *__i = *__f;
878    if (__i == __e)
879        insert(__e, __f, __l);
880    else
881        erase(__i, __e);
882}
883
884template <class _Tp, class _Alloc>
885void
886list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x)
887{
888    iterator __i = begin();
889    iterator __e = end();
890    for (; __n > 0 && __i != __e; --__n, ++__i)
891        *__i = __x;
892    if (__i == __e)
893        insert(__e, __n, __x);
894    else
895        erase(__i, __e);
896}
897
898template <class _Tp, class _Alloc>
899inline _LIBCPP_INLINE_VISIBILITY
900_Alloc
901list<_Tp, _Alloc>::get_allocator() const
902{
903    return allocator_type(base::__node_alloc());
904}
905
906template <class _Tp, class _Alloc>
907typename list<_Tp, _Alloc>::iterator
908list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
909{
910    __node_allocator& __na = base::__node_alloc();
911    typedef __allocator_destructor<__node_allocator> _D;
912    unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
913    __hold->__prev_ = 0;
914    __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x);
915    __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold);
916    ++base::__sz();
917    return iterator(__hold.release());
918}
919
920template <class _Tp, class _Alloc>
921typename list<_Tp, _Alloc>::iterator
922list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
923{
924    iterator __r(const_cast<__node_pointer>(__p.__ptr_));
925    if (__n > 0)
926    {
927        size_type __ds = 0;
928        __node_allocator& __na = base::__node_alloc();
929        typedef __allocator_destructor<__node_allocator> _D;
930        unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
931        __hold->__prev_ = 0;
932        __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x);
933        ++__ds;
934        __r = iterator(__hold.get());
935        __hold.release();
936        iterator __e = __r;
937#ifndef _LIBCPP_NO_EXCEPTIONS
938        try
939        {
940#endif  // _LIBCPP_NO_EXCEPTIONS
941            for (--__n; __n != 0; --__n, ++__e, ++__ds)
942            {
943                __hold.reset(__node_alloc_traits::allocate(__na, 1));
944                __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x);
945                __e.__ptr_->__next_ = __hold.get();
946                __hold->__prev_ = __e.__ptr_;
947                __hold.release();
948            }
949#ifndef _LIBCPP_NO_EXCEPTIONS
950        }
951        catch (...)
952        {
953            while (true)
954            {
955                __node_alloc_traits::destroy(__na, addressof(*__e));
956                __node_pointer __prev = __e.__ptr_->__prev_;
957                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
958                if (__prev == 0)
959                    break;
960                __e = iterator(__prev);
961            }
962            throw;
963        }
964#endif  // _LIBCPP_NO_EXCEPTIONS
965        __link_nodes(const_cast<__node&>(*__p.__ptr_), *__r.__ptr_, *__e.__ptr_);
966        base::__sz() += __ds;
967    }
968    return __r;
969}
970
971template <class _Tp, class _Alloc>
972template <class _InpIter>
973typename list<_Tp, _Alloc>::iterator
974list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
975             typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
976{
977    iterator __r(const_cast<__node_pointer>(__p.__ptr_));
978    if (__f != __l)
979    {
980        size_type __ds = 0;
981        __node_allocator& __na = base::__node_alloc();
982        typedef __allocator_destructor<__node_allocator> _D;
983        unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
984        __hold->__prev_ = 0;
985        __node_alloc_traits::construct(__na, addressof(__hold->__value_), *__f);
986        ++__ds;
987        __r = iterator(__hold.get());
988        __hold.release();
989        iterator __e = __r;
990#ifndef _LIBCPP_NO_EXCEPTIONS
991        try
992        {
993#endif  // _LIBCPP_NO_EXCEPTIONS
994            for (++__f; __f != __l; ++__f, ++__e, ++__ds)
995            {
996                __hold.reset(__node_alloc_traits::allocate(__na, 1));
997                __node_alloc_traits::construct(__na, addressof(__hold->__value_), *__f);
998                __e.__ptr_->__next_ = __hold.get();
999                __hold->__prev_ = __e.__ptr_;
1000                __hold.release();
1001            }
1002#ifndef _LIBCPP_NO_EXCEPTIONS
1003        }
1004        catch (...)
1005        {
1006            while (true)
1007            {
1008                __node_alloc_traits::destroy(__na, addressof(*__e));
1009                __node_pointer __prev = __e.__ptr_->__prev_;
1010                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1011                if (__prev == 0)
1012                    break;
1013                __e = iterator(__prev);
1014            }
1015            throw;
1016        }
1017#endif  // _LIBCPP_NO_EXCEPTIONS
1018        __link_nodes(const_cast<__node&>(*__p.__ptr_), *__r.__ptr_, *__e.__ptr_);
1019        base::__sz() += __ds;
1020    }
1021    return __r;
1022}
1023
1024template <class _Tp, class _Alloc>
1025void
1026list<_Tp, _Alloc>::push_front(const value_type& __x)
1027{
1028    __node_allocator& __na = base::__node_alloc();
1029    typedef __allocator_destructor<__node_allocator> _D;
1030    unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1031    __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x);
1032    __link_nodes(*base::__end_.__next_, *__hold, *__hold);
1033    ++base::__sz();
1034    __hold.release();
1035}
1036
1037template <class _Tp, class _Alloc>
1038void
1039list<_Tp, _Alloc>::push_back(const value_type& __x)
1040{
1041    __node_allocator& __na = base::__node_alloc();
1042    typedef __allocator_destructor<__node_allocator> _D;
1043    unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1044    __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x);
1045    __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold);
1046    ++base::__sz();
1047    __hold.release();
1048}
1049
1050#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1051
1052template <class _Tp, class _Alloc>
1053void
1054list<_Tp, _Alloc>::push_front(value_type&& __x)
1055{
1056    __node_allocator& __na = base::__node_alloc();
1057    typedef __allocator_destructor<__node_allocator> _D;
1058    unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1059    __node_alloc_traits::construct(__na, addressof(__hold->__value_), _STD::move(__x));
1060    __link_nodes(*base::__end_.__next_, *__hold, *__hold);
1061    ++base::__sz();
1062    __hold.release();
1063}
1064
1065template <class _Tp, class _Alloc>
1066void
1067list<_Tp, _Alloc>::push_back(value_type&& __x)
1068{
1069    __node_allocator& __na = base::__node_alloc();
1070    typedef __allocator_destructor<__node_allocator> _D;
1071    unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1072    __node_alloc_traits::construct(__na, addressof(__hold->__value_), _STD::move(__x));
1073    __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold);
1074    ++base::__sz();
1075    __hold.release();
1076}
1077
1078#ifndef _LIBCPP_HAS_NO_VARIADICS
1079
1080template <class _Tp, class _Alloc>
1081template <class... _Args>
1082void
1083list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1084{
1085    __node_allocator& __na = base::__node_alloc();
1086    typedef __allocator_destructor<__node_allocator> _D;
1087    unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1088    __node_alloc_traits::construct(__na, addressof(__hold->__value_), _STD::forward<_Args>(__args)...);
1089    __link_nodes(*base::__end_.__next_, *__hold, *__hold);
1090    ++base::__sz();
1091    __hold.release();
1092}
1093
1094template <class _Tp, class _Alloc>
1095template <class... _Args>
1096void
1097list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1098{
1099    __node_allocator& __na = base::__node_alloc();
1100    typedef __allocator_destructor<__node_allocator> _D;
1101    unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1102    __node_alloc_traits::construct(__na, addressof(__hold->__value_), _STD::forward<_Args>(__args)...);
1103    __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold);
1104    ++base::__sz();
1105    __hold.release();
1106}
1107
1108template <class _Tp, class _Alloc>
1109template <class... _Args>
1110typename list<_Tp, _Alloc>::iterator
1111list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1112{
1113    __node_allocator& __na = base::__node_alloc();
1114    typedef __allocator_destructor<__node_allocator> _D;
1115    unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1116    __hold->__prev_ = 0;
1117    __node_alloc_traits::construct(__na, addressof(__hold->__value_), _STD::forward<_Args>(__args)...);
1118    __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold);
1119    ++base::__sz();
1120    return iterator(__hold.release());
1121}
1122
1123#endif  // _LIBCPP_HAS_NO_VARIADICS
1124
1125template <class _Tp, class _Alloc>
1126typename list<_Tp, _Alloc>::iterator
1127list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1128{
1129    __node_allocator& __na = base::__node_alloc();
1130    typedef __allocator_destructor<__node_allocator> _D;
1131    unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1132    __hold->__prev_ = 0;
1133    __node_alloc_traits::construct(__na, addressof(__hold->__value_), _STD::move(__x));
1134    __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold);
1135    ++base::__sz();
1136    return iterator(__hold.release());
1137}
1138
1139#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1140
1141template <class _Tp, class _Alloc>
1142void
1143list<_Tp, _Alloc>::pop_front()
1144{
1145    __node_allocator& __na = base::__node_alloc();
1146    __node& __n = *base::__end_.__next_;
1147    base::__unlink_nodes(__n, __n);
1148    --base::__sz();
1149    __node_alloc_traits::destroy(__na, addressof(__n.__value_));
1150    __node_alloc_traits::deallocate(__na, addressof(__n), 1);
1151}
1152
1153template <class _Tp, class _Alloc>
1154void
1155list<_Tp, _Alloc>::pop_back()
1156{
1157    __node_allocator& __na = base::__node_alloc();
1158    __node& __n = *base::__end_.__prev_;
1159    base::__unlink_nodes(__n, __n);
1160    --base::__sz();
1161    __node_alloc_traits::destroy(__na, addressof(__n.__value_));
1162    __node_alloc_traits::deallocate(__na, addressof(__n), 1);
1163}
1164
1165template <class _Tp, class _Alloc>
1166typename list<_Tp, _Alloc>::iterator
1167list<_Tp, _Alloc>::erase(const_iterator __p)
1168{
1169    __node_allocator& __na = base::__node_alloc();
1170    __node& __n = const_cast<__node&>(*__p.__ptr_);
1171    __node_pointer __r = __n.__next_;
1172    base::__unlink_nodes(__n, __n);
1173    --base::__sz();
1174    __node_alloc_traits::destroy(__na, addressof(__n.__value_));
1175    __node_alloc_traits::deallocate(__na, addressof(__n), 1);
1176    return iterator(__r);
1177}
1178
1179template <class _Tp, class _Alloc>
1180typename list<_Tp, _Alloc>::iterator
1181list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1182{
1183    if (__f != __l)
1184    {
1185        __node_allocator& __na = base::__node_alloc();
1186        base::__unlink_nodes(const_cast<__node&>(*__f.__ptr_), *__l.__ptr_->__prev_);
1187        while (__f != __l)
1188        {
1189            __node& __n = const_cast<__node&>(*__f.__ptr_);
1190            ++__f;
1191            --base::__sz();
1192            __node_alloc_traits::destroy(__na, addressof(__n.__value_));
1193            __node_alloc_traits::deallocate(__na, addressof(__n), 1);
1194        }
1195    }
1196    return iterator(const_cast<__node_pointer>(__l.__ptr_));
1197}
1198
1199template <class _Tp, class _Alloc>
1200void
1201list<_Tp, _Alloc>::resize(size_type __n)
1202{
1203    if (__n < base::__sz())
1204        erase(__iterator(__n), end());
1205    else if (__n > base::__sz())
1206    {
1207        __n -= base::__sz();
1208        size_type __ds = 0;
1209        __node_allocator& __na = base::__node_alloc();
1210        typedef __allocator_destructor<__node_allocator> _D;
1211        unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1212        __hold->__prev_ = 0;
1213        __node_alloc_traits::construct(__na, addressof(__hold->__value_));
1214        ++__ds;
1215        iterator __r = iterator(__hold.release());
1216        iterator __e = __r;
1217#ifndef _LIBCPP_NO_EXCEPTIONS
1218        try
1219        {
1220#endif  // _LIBCPP_NO_EXCEPTIONS
1221            for (--__n; __n != 0; --__n, ++__e, ++__ds)
1222            {
1223                __hold.reset(__node_alloc_traits::allocate(__na, 1));
1224                __node_alloc_traits::construct(__na, addressof(__hold->__value_));
1225                __e.__ptr_->__next_ = __hold.get();
1226                __hold->__prev_ = __e.__ptr_;
1227                __hold.release();
1228            }
1229#ifndef _LIBCPP_NO_EXCEPTIONS
1230        }
1231        catch (...)
1232        {
1233            while (true)
1234            {
1235                __node_alloc_traits::destroy(__na, addressof(*__e));
1236                __node_pointer __prev = __e.__ptr_->__prev_;
1237                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1238                if (__prev == 0)
1239                    break;
1240                __e = iterator(__prev);
1241            }
1242            throw;
1243        }
1244#endif  // _LIBCPP_NO_EXCEPTIONS
1245        __link_nodes(static_cast<__node&>(base::__end_), *__r.__ptr_, *__e.__ptr_);
1246        base::__sz() += __ds;
1247    }
1248}
1249
1250template <class _Tp, class _Alloc>
1251void
1252list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1253{
1254    if (__n < base::__sz())
1255        erase(__iterator(__n), end());
1256    else if (__n > base::__sz())
1257    {
1258        __n -= base::__sz();
1259        size_type __ds = 0;
1260        __node_allocator& __na = base::__node_alloc();
1261        typedef __allocator_destructor<__node_allocator> _D;
1262        unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1263        __hold->__prev_ = 0;
1264        __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x);
1265        ++__ds;
1266        iterator __r = iterator(__hold.release());
1267        iterator __e = __r;
1268#ifndef _LIBCPP_NO_EXCEPTIONS
1269        try
1270        {
1271#endif  // _LIBCPP_NO_EXCEPTIONS
1272            for (--__n; __n != 0; --__n, ++__e, ++__ds)
1273            {
1274                __hold.reset(__node_alloc_traits::allocate(__na, 1));
1275                __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x);
1276                __e.__ptr_->__next_ = __hold.get();
1277                __hold->__prev_ = __e.__ptr_;
1278                __hold.release();
1279            }
1280#ifndef _LIBCPP_NO_EXCEPTIONS
1281        }
1282        catch (...)
1283        {
1284            while (true)
1285            {
1286                __node_alloc_traits::destroy(__na, addressof(*__e));
1287                __node_pointer __prev = __e.__ptr_->__prev_;
1288                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1289                if (__prev == 0)
1290                    break;
1291                __e = iterator(__prev);
1292            }
1293            throw;
1294        }
1295#endif  // _LIBCPP_NO_EXCEPTIONS
1296        __link_nodes(static_cast<__node&>(base::__end_), *__r.__ptr_, *__e.__ptr_);
1297        base::__sz() += __ds;
1298    }
1299}
1300
1301template <class _Tp, class _Alloc>
1302void
1303list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
1304{
1305    if (!__c.empty())
1306    {
1307        __node& __f = *__c.__end_.__next_;
1308        __node& __l = *__c.__end_.__prev_;
1309        base::__unlink_nodes(__f, __l);
1310        __link_nodes(const_cast<__node&>(*__p.__ptr_), __f, __l);
1311        base::__sz() += __c.__sz();
1312        __c.__sz() = 0;
1313    }
1314}
1315
1316template <class _Tp, class _Alloc>
1317void
1318list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
1319{
1320    if (__p != __i && __p != next(__i))
1321    {
1322        __node& __f = const_cast<__node&>(*__i.__ptr_);
1323        base::__unlink_nodes(__f, __f);
1324        __link_nodes(const_cast<__node&>(*__p.__ptr_), __f, __f);
1325        --__c.__sz();
1326        ++base::__sz();
1327    }
1328}
1329
1330template <class _Tp, class _Alloc>
1331void
1332list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
1333{
1334    if (__f != __l)
1335    {
1336        if (this != &__c)
1337        {
1338            size_type __s = _STD::distance(__f, __l);
1339            __c.__sz() -= __s;
1340            base::__sz() += __s;
1341        }
1342        __node& __first = const_cast<__node&>(*__f.__ptr_);
1343        --__l;
1344        __node& __last = const_cast<__node&>(*__l.__ptr_);
1345        base::__unlink_nodes(__first, __last);
1346        __link_nodes(const_cast<__node&>(*__p.__ptr_), __first, __last);
1347    }
1348}
1349
1350template <class _Tp, class _Alloc>
1351void
1352list<_Tp, _Alloc>::remove(const value_type& __x)
1353{
1354    for (iterator __i = begin(), __e = end(); __i != __e;)
1355    {
1356        if (*__i == __x)
1357        {
1358            iterator __j = next(__i);
1359            for (; __j != __e && *__j == __x; ++__j)
1360                ;
1361            __i = erase(__i, __j);
1362        }
1363        else
1364            ++__i;
1365    }
1366}
1367
1368template <class _Tp, class _Alloc>
1369template <class _Pred>
1370void
1371list<_Tp, _Alloc>::remove_if(_Pred __pred)
1372{
1373    for (iterator __i = begin(), __e = end(); __i != __e;)
1374    {
1375        if (__pred(*__i))
1376        {
1377            iterator __j = next(__i);
1378            for (; __j != __e && __pred(*__j); ++__j)
1379                ;
1380            __i = erase(__i, __j);
1381        }
1382        else
1383            ++__i;
1384    }
1385}
1386
1387template <class _Tp, class _Alloc>
1388inline _LIBCPP_INLINE_VISIBILITY
1389void
1390list<_Tp, _Alloc>::unique()
1391{
1392    unique(__equal_to<value_type>());
1393}
1394
1395template <class _Tp, class _Alloc>
1396template <class _BinaryPred>
1397void
1398list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
1399{
1400    for (iterator __i = begin(), __e = end(); __i != __e;)
1401    {
1402        iterator __j = next(__i);
1403        for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
1404            ;
1405        if (++__i != __j)
1406            __i = erase(__i, __j);
1407    }
1408}
1409
1410template <class _Tp, class _Alloc>
1411inline _LIBCPP_INLINE_VISIBILITY
1412void
1413list<_Tp, _Alloc>::merge(list& __c)
1414{
1415    merge(__c, __less<value_type>());
1416}
1417
1418template <class _Tp, class _Alloc>
1419template <class _Comp>
1420void
1421list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
1422{
1423    if (this != &__c)
1424    {
1425        iterator __f1 = begin();
1426        iterator __e1 = end();
1427        iterator __f2 = __c.begin();
1428        iterator __e2 = __c.end();
1429        while (__f1 != __e1 && __f2 != __e2)
1430        {
1431            if (__comp(*__f2, *__f1))
1432            {
1433                size_type __ds = 1;
1434                iterator __m2 = next(__f2);
1435                for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
1436                    ;
1437                base::__sz() += __ds;
1438                __c.__sz() -= __ds;
1439                __node& __f = *__f2.__ptr_;
1440                __node& __l = *__m2.__ptr_->__prev_;
1441                __f2 = __m2;
1442                base::__unlink_nodes(__f, __l);
1443                __m2 = next(__f1);
1444                __link_nodes(*__f1.__ptr_, __f, __l);
1445                __f1 = __m2;
1446            }
1447            else
1448                ++__f1;
1449        }
1450        splice(__e1, __c);
1451    }
1452}
1453
1454template <class _Tp, class _Alloc>
1455inline _LIBCPP_INLINE_VISIBILITY
1456void
1457list<_Tp, _Alloc>::sort()
1458{
1459    sort(__less<value_type>());
1460}
1461
1462template <class _Tp, class _Alloc>
1463template <class _Comp>
1464inline _LIBCPP_INLINE_VISIBILITY
1465void
1466list<_Tp, _Alloc>::sort(_Comp __comp)
1467{
1468    __sort(begin(), end(), base::__sz(), __comp);
1469}
1470
1471template <class _Tp, class _Alloc>
1472template <class _Comp>
1473typename list<_Tp, _Alloc>::iterator
1474list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
1475{
1476    switch (__n)
1477    {
1478    case 0:
1479    case 1:
1480        return __f1;
1481    case 2:
1482        if (__comp(*--__e2, *__f1))
1483        {
1484            __node& __f = *__e2.__ptr_;
1485            base::__unlink_nodes(__f, __f);
1486            __link_nodes(*__f1.__ptr_, __f, __f);
1487            return __e2;
1488        }
1489        return __f1;
1490    }
1491    size_type __n2 = __n / 2;
1492    iterator __e1 = next(__f1, __n2);
1493    iterator  __r = __f1 = __sort(__f1, __e1, __n2, __comp);
1494    iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
1495    if (__comp(*__f2, *__f1))
1496    {
1497        iterator __m2 = next(__f2);
1498        for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
1499            ;
1500        __node& __f = *__f2.__ptr_;
1501        __node& __l = *__m2.__ptr_->__prev_;
1502        __r = __f2;
1503        __e1 = __f2 = __m2;
1504        base::__unlink_nodes(__f, __l);
1505        __m2 = next(__f1);
1506        __link_nodes(*__f1.__ptr_, __f, __l);
1507        __f1 = __m2;
1508    }
1509    else
1510        ++__f1;
1511    while (__f1 != __e1 && __f2 != __e2)
1512    {
1513        if (__comp(*__f2, *__f1))
1514        {
1515            iterator __m2 = next(__f2);
1516            for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
1517                ;
1518            __node& __f = *__f2.__ptr_;
1519            __node& __l = *__m2.__ptr_->__prev_;
1520            if (__e1 == __f2)
1521                __e1 = __m2;
1522            __f2 = __m2;
1523            base::__unlink_nodes(__f, __l);
1524            __m2 = next(__f1);
1525            __link_nodes(*__f1.__ptr_, __f, __l);
1526            __f1 = __m2;
1527        }
1528        else
1529            ++__f1;
1530    }
1531    return __r;
1532}
1533
1534template <class _Tp, class _Alloc>
1535void
1536list<_Tp, _Alloc>::reverse()
1537{
1538    if (base::__sz() > 1)
1539    {
1540        iterator __e = end();
1541        for (iterator __i = begin(); __i != __e; --__i)
1542            _STD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
1543        _STD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
1544    }
1545}
1546
1547template <class _Tp, class _Alloc>
1548inline _LIBCPP_INLINE_VISIBILITY
1549bool
1550operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1551{
1552    return __x.size() == __y.size() && _STD::equal(__x.begin(), __x.end(), __y.begin());
1553}
1554
1555template <class _Tp, class _Alloc>
1556inline _LIBCPP_INLINE_VISIBILITY
1557bool
1558operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1559{
1560    return _STD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1561}
1562
1563template <class _Tp, class _Alloc>
1564inline _LIBCPP_INLINE_VISIBILITY
1565bool
1566operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1567{
1568    return !(__x == __y);
1569}
1570
1571template <class _Tp, class _Alloc>
1572inline _LIBCPP_INLINE_VISIBILITY
1573bool
1574operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1575{
1576    return __y < __x;
1577}
1578
1579template <class _Tp, class _Alloc>
1580inline _LIBCPP_INLINE_VISIBILITY
1581bool
1582operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1583{
1584    return !(__x < __y);
1585}
1586
1587template <class _Tp, class _Alloc>
1588inline _LIBCPP_INLINE_VISIBILITY
1589bool
1590operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1591{
1592    return !(__y < __x);
1593}
1594
1595template <class _Tp, class _Alloc>
1596inline _LIBCPP_INLINE_VISIBILITY
1597void
1598swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
1599{
1600    __x.swap(__y);
1601}
1602
1603_LIBCPP_END_NAMESPACE_STD
1604
1605#endif  // _LIBCPP_LIST
1606