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         }
2050         else
2051             ++__i;
2052     }
2053 }
2054
2055 template <class _Tp, class _Alloc>
2056 template <class _Pred>
2057 void
2058 list<_Tp, _Alloc>::remove_if(_Pred __pred)
2059 {
2060     for (iterator __i = begin(), __e = end(); __i != __e;)
2061     {
2062         if (__pred(*__i))
2063         {
2064             iterator __j = _VSTD::next(__i);
2065             for (; __j != __e && __pred(*__j); ++__j)
2066                 ;
2067             __i = erase(__i, __j);
2068         }
2069         else
2070             ++__i;
2071     }
2072 }
2073
2074 template <class _Tp, class _Alloc>
2075 inline _LIBCPP_INLINE_VISIBILITY
2076 void
2077 list<_Tp, _Alloc>::unique()
2078 {
2079     unique(__equal_to<value_type>());
2080 }
2081
2082 template <class _Tp, class _Alloc>
2083 template <class _BinaryPred>
2084 void
2085 list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
2086 {
2087     for (iterator __i = begin(), __e = end(); __i != __e;)
2088     {
2089         iterator __j = _VSTD::next(__i);
2090         for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
2091             ;
2092         if (++__i != __j)
2093             __i = erase(__i, __j);
2094     }
2095 }
2096
2097 template <class _Tp, class _Alloc>
2098 inline _LIBCPP_INLINE_VISIBILITY
2099 void
2100 list<_Tp, _Alloc>::merge(list& __c)
2101 {
2102     merge(__c, __less<value_type>());
2103 }
2104
2105 template <class _Tp, class _Alloc>
2106 template <class _Comp>
2107 void
2108 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2109 {
2110     if (this != &__c)
2111     {
2112         iterator __f1 = begin();
2113         iterator __e1 = end();
2114         iterator __f2 = __c.begin();
2115         iterator __e2 = __c.end();
2116         while (__f1 != __e1 && __f2 != __e2)
2117         {
2118             if (__comp(*__f2, *__f1))
2119             {
2120                 size_type __ds = 1;
2121                 iterator __m2 = _VSTD::next(__f2);
2122                 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
2123                     ;
2124                 base::__sz() += __ds;
2125                 __c.__sz() -= __ds;
2126                 __node_pointer __f = __f2.__ptr_;
2127                 __node_pointer __l = __m2.__ptr_->__prev_;
2128                 __f2 = __m2;
2129                 base::__unlink_nodes(__f, __l);
2130                 __m2 = _VSTD::next(__f1);
2131                 __link_nodes(__f1.__ptr_, __f, __l);
2132                 __f1 = __m2;
2133             }
2134             else
2135                 ++__f1;
2136         }
2137         splice(__e1, __c);
2138 #if _LIBCPP_DEBUG_LEVEL >= 2
2139         __libcpp_db* __db = __get_db();
2140         __c_node* __cn1 = __db->__find_c_and_lock(this);
2141         __c_node* __cn2 = __db->__find_c(&__c);
2142         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2143         {
2144             --__p;
2145             iterator* __i = static_cast<iterator*>((*__p)->__i_);
2146             if (__i->__ptr_ != static_cast<__node_pointer>(
2147                        pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
2148             {
2149                 __cn1->__add(*__p);
2150                 (*__p)->__c_ = __cn1;
2151                 if (--__cn2->end_ != __p)
2152                     memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2153             }
2154         }
2155         __db->unlock();
2156 #endif
2157     }
2158 }
2159
2160 template <class _Tp, class _Alloc>
2161 inline _LIBCPP_INLINE_VISIBILITY
2162 void
2163 list<_Tp, _Alloc>::sort()
2164 {
2165     sort(__less<value_type>());
2166 }
2167
2168 template <class _Tp, class _Alloc>
2169 template <class _Comp>
2170 inline _LIBCPP_INLINE_VISIBILITY
2171 void
2172 list<_Tp, _Alloc>::sort(_Comp __comp)
2173 {
2174     __sort(begin(), end(), base::__sz(), __comp);
2175 }
2176
2177 template <class _Tp, class _Alloc>
2178 template <class _Comp>
2179 typename list<_Tp, _Alloc>::iterator
2180 list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
2181 {
2182     switch (__n)
2183     {
2184     case 0:
2185     case 1:
2186         return __f1;
2187     case 2:
2188         if (__comp(*--__e2, *__f1))
2189         {
2190             __node_pointer __f = __e2.__ptr_;
2191             base::__unlink_nodes(__f, __f);
2192             __link_nodes(__f1.__ptr_, __f, __f);
2193             return __e2;
2194         }
2195         return __f1;
2196     }
2197     size_type __n2 = __n / 2;
2198     iterator __e1 = _VSTD::next(__f1, __n2);
2199     iterator  __r = __f1 = __sort(__f1, __e1, __n2, __comp);
2200     iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2201     if (__comp(*__f2, *__f1))
2202     {
2203         iterator __m2 = _VSTD::next(__f2);
2204         for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2205             ;
2206         __node_pointer __f = __f2.__ptr_;
2207         __node_pointer __l = __m2.__ptr_->__prev_;
2208         __r = __f2;
2209         __e1 = __f2 = __m2;
2210         base::__unlink_nodes(__f, __l);
2211         __m2 = _VSTD::next(__f1);
2212         __link_nodes(__f1.__ptr_, __f, __l);
2213         __f1 = __m2;
2214     }
2215     else
2216         ++__f1;
2217     while (__f1 != __e1 && __f2 != __e2)
2218     {
2219         if (__comp(*__f2, *__f1))
2220         {
2221             iterator __m2 = _VSTD::next(__f2);
2222             for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2223                 ;
2224             __node_pointer __f = __f2.__ptr_;
2225             __node_pointer __l = __m2.__ptr_->__prev_;
2226             if (__e1 == __f2)
2227                 __e1 = __m2;
2228             __f2 = __m2;
2229             base::__unlink_nodes(__f, __l);
2230             __m2 = _VSTD::next(__f1);
2231             __link_nodes(__f1.__ptr_, __f, __l);
2232             __f1 = __m2;
2233         }
2234         else
2235             ++__f1;
2236     }
2237     return __r;
2238 }
2239
2240 template <class _Tp, class _Alloc>
2241 void
2242 list<_Tp, _Alloc>::reverse() _NOEXCEPT
2243 {
2244     if (base::__sz() > 1)
2245     {
2246         iterator __e = end();
2247         for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
2248         {
2249             _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
2250             __i.__ptr_ = __i.__ptr_->__prev_;
2251         }
2252         _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
2253     }
2254 }
2255
2256 template <class _Tp, class _Alloc>
2257 bool
2258 list<_Tp, _Alloc>::__invariants() const
2259 {
2260     return size() == _VSTD::distance(begin(), end());
2261 }
2262
2263 #if _LIBCPP_DEBUG_LEVEL >= 2
2264
2265 template <class _Tp, class _Alloc>
2266 bool
2267 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
2268 {
2269     return __i->__ptr_ != static_cast<__node_pointer>(
2270                        pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(this->__end_)));
2271 }
2272
2273 template <class _Tp, class _Alloc>
2274 bool
2275 list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
2276 {
2277     return !empty() &&  __i->__ptr_ != base::__end_.__next_;
2278 }
2279
2280 template <class _Tp, class _Alloc>
2281 bool
2282 list<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2283 {
2284     return false;
2285 }
2286
2287 template <class _Tp, class _Alloc>
2288 bool
2289 list<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2290 {
2291     return false;
2292 }
2293
2294 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
2295
2296 template <class _Tp, class _Alloc>
2297 inline _LIBCPP_INLINE_VISIBILITY
2298 bool
2299 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2300 {
2301     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2302 }
2303
2304 template <class _Tp, class _Alloc>
2305 inline _LIBCPP_INLINE_VISIBILITY
2306 bool
2307 operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2308 {
2309     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2310 }
2311
2312 template <class _Tp, class _Alloc>
2313 inline _LIBCPP_INLINE_VISIBILITY
2314 bool
2315 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2316 {
2317     return !(__x == __y);
2318 }
2319
2320 template <class _Tp, class _Alloc>
2321 inline _LIBCPP_INLINE_VISIBILITY
2322 bool
2323 operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2324 {
2325     return __y < __x;
2326 }
2327
2328 template <class _Tp, class _Alloc>
2329 inline _LIBCPP_INLINE_VISIBILITY
2330 bool
2331 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2332 {
2333     return !(__x < __y);
2334 }
2335
2336 template <class _Tp, class _Alloc>
2337 inline _LIBCPP_INLINE_VISIBILITY
2338 bool
2339 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2340 {
2341     return !(__y < __x);
2342 }
2343
2344 template <class _Tp, class _Alloc>
2345 inline _LIBCPP_INLINE_VISIBILITY
2346 void
2347 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2348     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2349 {
2350     __x.swap(__y);
2351 }
2352
2353 _LIBCPP_END_NAMESPACE_STD
2354
2355 #endif  // _LIBCPP_LIST