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