external/bsd/libc++/dist/libcxx/include/list

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