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