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