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     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 list;
 217 template <class _Tp, class _Alloc> class __list_imp;
 218 template <class _Tp, class _VoidPtr> class __list_const_iterator;
 219
 220 template <class _Tp, class _VoidPtr>
 221 class _LIBCPP_VISIBLE __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_VISIBLE __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(__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_VISIBLE 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     return iterator(__hold.release());
1296 }
1297
1298 template <class _Tp, class _Alloc>
1299 typename list<_Tp, _Alloc>::iterator
1300 list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
1301 {
1302 #if _LIBCPP_DEBUG_LEVEL >= 2
1303     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1304         "list::insert(iterator, n, x) called with an iterator not"
1305         " referring to this list");
1306     iterator __r(const_cast<__node_pointer>(__p.__ptr_), this);
1307 #else
1308     iterator __r(const_cast<__node_pointer>(__p.__ptr_));
1309 #endif
1310     if (__n > 0)
1311     {
1312         size_type __ds = 0;
1313         __node_allocator& __na = base::__node_alloc();
1314         typedef __allocator_destructor<__node_allocator> _Dp;
1315         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1316         __hold->__prev_ = 0;
1317         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1318         ++__ds;
1319 #if _LIBCPP_DEBUG_LEVEL >= 2
1320         __r = iterator(__hold.get(), this);
1321 #else
1322         __r = iterator(__hold.get());
1323 #endif
1324         __hold.release();
1325         iterator __e = __r;
1326 #ifndef _LIBCPP_NO_EXCEPTIONS
1327         try
1328         {
1329 #endif  // _LIBCPP_NO_EXCEPTIONS
1330             for (--__n; __n != 0; --__n, ++__e, ++__ds)
1331             {
1332                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1333                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1334                 __e.__ptr_->__next_ = __hold.get();
1335                 __hold->__prev_ = __e.__ptr_;
1336                 __hold.release();
1337             }
1338 #ifndef _LIBCPP_NO_EXCEPTIONS
1339         }
1340         catch (...)
1341         {
1342             while (true)
1343             {
1344                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1345                 __node_pointer __prev = __e.__ptr_->__prev_;
1346                 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1347                 if (__prev == 0)
1348                     break;
1349 #if _LIBCPP_DEBUG_LEVEL >= 2
1350                 __e = iterator(__prev, this);
1351 #else
1352                 __e = iterator(__prev);
1353 #endif
1354             }
1355             throw;
1356         }
1357 #endif  // _LIBCPP_NO_EXCEPTIONS
1358         __link_nodes(const_cast<__node&>(*__p.__ptr_), *__r.__ptr_, *__e.__ptr_);
1359         base::__sz() += __ds;
1360     }
1361     return __r;
1362 }
1363
1364 template <class _Tp, class _Alloc>
1365 template <class _InpIter>
1366 typename list<_Tp, _Alloc>::iterator
1367 list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
1368              typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1369 {
1370 #if _LIBCPP_DEBUG_LEVEL >= 2
1371     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1372         "list::insert(iterator, range) called with an iterator not"
1373         " referring to this list");
1374     iterator __r(const_cast<__node_pointer>(__p.__ptr_), this);
1375 #else
1376     iterator __r(const_cast<__node_pointer>(__p.__ptr_));
1377 #endif
1378     if (__f != __l)
1379     {
1380         size_type __ds = 0;
1381         __node_allocator& __na = base::__node_alloc();
1382         typedef __allocator_destructor<__node_allocator> _Dp;
1383         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1384         __hold->__prev_ = 0;
1385         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1386         ++__ds;
1387 #if _LIBCPP_DEBUG_LEVEL >= 2
1388         __r = iterator(__hold.get(), this);
1389 #else
1390         __r = iterator(__hold.get());
1391 #endif
1392         __hold.release();
1393         iterator __e = __r;
1394 #ifndef _LIBCPP_NO_EXCEPTIONS
1395         try
1396         {
1397 #endif  // _LIBCPP_NO_EXCEPTIONS
1398             for (++__f; __f != __l; ++__f, ++__e, ++__ds)
1399             {
1400                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1401                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
1402                 __e.__ptr_->__next_ = __hold.get();
1403                 __hold->__prev_ = __e.__ptr_;
1404                 __hold.release();
1405             }
1406 #ifndef _LIBCPP_NO_EXCEPTIONS
1407         }
1408         catch (...)
1409         {
1410             while (true)
1411             {
1412                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1413                 __node_pointer __prev = __e.__ptr_->__prev_;
1414                 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1415                 if (__prev == 0)
1416                     break;
1417 #if _LIBCPP_DEBUG_LEVEL >= 2
1418                 __e = iterator(__prev, this);
1419 #else
1420                 __e = iterator(__prev);
1421 #endif
1422             }
1423             throw;
1424         }
1425 #endif  // _LIBCPP_NO_EXCEPTIONS
1426         __link_nodes(const_cast<__node&>(*__p.__ptr_), *__r.__ptr_, *__e.__ptr_);
1427         base::__sz() += __ds;
1428     }
1429     return __r;
1430 }
1431
1432 template <class _Tp, class _Alloc>
1433 void
1434 list<_Tp, _Alloc>::push_front(const value_type& __x)
1435 {
1436     __node_allocator& __na = base::__node_alloc();
1437     typedef __allocator_destructor<__node_allocator> _Dp;
1438     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1439     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1440     __link_nodes(*base::__end_.__next_, *__hold, *__hold);
1441     ++base::__sz();
1442     __hold.release();
1443 }
1444
1445 template <class _Tp, class _Alloc>
1446 void
1447 list<_Tp, _Alloc>::push_back(const value_type& __x)
1448 {
1449     __node_allocator& __na = base::__node_alloc();
1450     typedef __allocator_destructor<__node_allocator> _Dp;
1451     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1452     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1453     __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold);
1454     ++base::__sz();
1455     __hold.release();
1456 }
1457
1458 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1459
1460 template <class _Tp, class _Alloc>
1461 void
1462 list<_Tp, _Alloc>::push_front(value_type&& __x)
1463 {
1464     __node_allocator& __na = base::__node_alloc();
1465     typedef __allocator_destructor<__node_allocator> _Dp;
1466     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1467     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1468     __link_nodes(*base::__end_.__next_, *__hold, *__hold);
1469     ++base::__sz();
1470     __hold.release();
1471 }
1472
1473 template <class _Tp, class _Alloc>
1474 void
1475 list<_Tp, _Alloc>::push_back(value_type&& __x)
1476 {
1477     __node_allocator& __na = base::__node_alloc();
1478     typedef __allocator_destructor<__node_allocator> _Dp;
1479     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1480     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1481     __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold);
1482     ++base::__sz();
1483     __hold.release();
1484 }
1485
1486 #ifndef _LIBCPP_HAS_NO_VARIADICS
1487
1488 template <class _Tp, class _Alloc>
1489 template <class... _Args>
1490 void
1491 list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1492 {
1493     __node_allocator& __na = base::__node_alloc();
1494     typedef __allocator_destructor<__node_allocator> _Dp;
1495     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1496     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1497     __link_nodes(*base::__end_.__next_, *__hold, *__hold);
1498     ++base::__sz();
1499     __hold.release();
1500 }
1501
1502 template <class _Tp, class _Alloc>
1503 template <class... _Args>
1504 void
1505 list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1506 {
1507     __node_allocator& __na = base::__node_alloc();
1508     typedef __allocator_destructor<__node_allocator> _Dp;
1509     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1510     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1511     __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold);
1512     ++base::__sz();
1513     __hold.release();
1514 }
1515
1516 template <class _Tp, class _Alloc>
1517 template <class... _Args>
1518 typename list<_Tp, _Alloc>::iterator
1519 list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1520 {
1521     __node_allocator& __na = base::__node_alloc();
1522     typedef __allocator_destructor<__node_allocator> _Dp;
1523     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1524     __hold->__prev_ = 0;
1525     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
1526     __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold);
1527     ++base::__sz();
1528 #if _LIBCPP_DEBUG_LEVEL >= 2
1529     return iterator(__hold.release(), this);
1530 #else
1531     return iterator(__hold.release());
1532 #endif
1533 }
1534
1535 #endif  // _LIBCPP_HAS_NO_VARIADICS
1536
1537 template <class _Tp, class _Alloc>
1538 typename list<_Tp, _Alloc>::iterator
1539 list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1540 {
1541 #if _LIBCPP_DEBUG_LEVEL >= 2
1542     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1543         "list::insert(iterator, x) called with an iterator not"
1544         " referring to this list");
1545 #endif
1546     __node_allocator& __na = base::__node_alloc();
1547     typedef __allocator_destructor<__node_allocator> _Dp;
1548     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1549     __hold->__prev_ = 0;
1550     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
1551     __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold);
1552     ++base::__sz();
1553 #if _LIBCPP_DEBUG_LEVEL >= 2
1554     return iterator(__hold.release(), this);
1555 #else
1556     return iterator(__hold.release());
1557 #endif
1558 }
1559
1560 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1561
1562 template <class _Tp, class _Alloc>
1563 void
1564 list<_Tp, _Alloc>::pop_front()
1565 {
1566     _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
1567     __node_allocator& __na = base::__node_alloc();
1568     __node& __n = *base::__end_.__next_;
1569     base::__unlink_nodes(__n, __n);
1570     --base::__sz();
1571 #if _LIBCPP_DEBUG_LEVEL >= 2
1572     __c_node* __c = __get_db()->__find_c_and_lock(this);
1573     for (__i_node** __p = __c->end_; __p != __c->beg_; )
1574     {
1575         --__p;
1576         iterator* __i = static_cast<iterator*>((*__p)->__i_);
1577         if (__i->__ptr_ == &__n)
1578         {
1579             (*__p)->__c_ = nullptr;
1580             if (--__c->end_ != __p)
1581                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1582         }
1583     }
1584     __get_db()->unlock();
1585 #endif
1586     __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_));
1587     __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1);
1588 }
1589
1590 template <class _Tp, class _Alloc>
1591 void
1592 list<_Tp, _Alloc>::pop_back()
1593 {
1594     _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
1595     __node_allocator& __na = base::__node_alloc();
1596     __node& __n = *base::__end_.__prev_;
1597     base::__unlink_nodes(__n, __n);
1598     --base::__sz();
1599 #if _LIBCPP_DEBUG_LEVEL >= 2
1600     __c_node* __c = __get_db()->__find_c_and_lock(this);
1601     for (__i_node** __p = __c->end_; __p != __c->beg_; )
1602     {
1603         --__p;
1604         iterator* __i = static_cast<iterator*>((*__p)->__i_);
1605         if (__i->__ptr_ == &__n)
1606         {
1607             (*__p)->__c_ = nullptr;
1608             if (--__c->end_ != __p)
1609                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1610         }
1611     }
1612     __get_db()->unlock();
1613 #endif
1614     __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_));
1615     __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1);
1616 }
1617
1618 template <class _Tp, class _Alloc>
1619 typename list<_Tp, _Alloc>::iterator
1620 list<_Tp, _Alloc>::erase(const_iterator __p)
1621 {
1622 #if _LIBCPP_DEBUG_LEVEL >= 2
1623     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1624         "list::erase(iterator) called with an iterator not"
1625         " referring to this list");
1626 #endif
1627     __node_allocator& __na = base::__node_alloc();
1628     __node& __n = const_cast<__node&>(*__p.__ptr_);
1629     __node_pointer __r = __n.__next_;
1630     base::__unlink_nodes(__n, __n);
1631     --base::__sz();
1632 #if _LIBCPP_DEBUG_LEVEL >= 2
1633     __c_node* __c = __get_db()->__find_c_and_lock(this);
1634     for (__i_node** __p = __c->end_; __p != __c->beg_; )
1635     {
1636         --__p;
1637         iterator* __i = static_cast<iterator*>((*__p)->__i_);
1638         if (__i->__ptr_ == &__n)
1639         {
1640             (*__p)->__c_ = nullptr;
1641             if (--__c->end_ != __p)
1642                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1643         }
1644     }
1645     __get_db()->unlock();
1646 #endif
1647     __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_));
1648     __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1);
1649 #if _LIBCPP_DEBUG_LEVEL >= 2
1650     return iterator(__r, this);
1651 #else
1652     return iterator(__r);
1653 #endif
1654 }
1655
1656 template <class _Tp, class _Alloc>
1657 typename list<_Tp, _Alloc>::iterator
1658 list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1659 {
1660 #if _LIBCPP_DEBUG_LEVEL >= 2
1661     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this,
1662         "list::erase(iterator, iterator) called with an iterator not"
1663         " referring to this list");
1664 #endif
1665     if (__f != __l)
1666     {
1667         __node_allocator& __na = base::__node_alloc();
1668         base::__unlink_nodes(const_cast<__node&>(*__f.__ptr_), *__l.__ptr_->__prev_);
1669         while (__f != __l)
1670         {
1671             __node& __n = const_cast<__node&>(*__f.__ptr_);
1672             ++__f;
1673             --base::__sz();
1674 #if _LIBCPP_DEBUG_LEVEL >= 2
1675             __c_node* __c = __get_db()->__find_c_and_lock(this);
1676             for (__i_node** __p = __c->end_; __p != __c->beg_; )
1677             {
1678                 --__p;
1679                 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1680                 if (__i->__ptr_ == &__n)
1681                 {
1682                     (*__p)->__c_ = nullptr;
1683                     if (--__c->end_ != __p)
1684                         memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1685                 }
1686             }
1687             __get_db()->unlock();
1688 #endif
1689             __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_));
1690             __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1);
1691         }
1692     }
1693 #if _LIBCPP_DEBUG_LEVEL >= 2
1694     return iterator(const_cast<__node_pointer>(__l.__ptr_), this);
1695 #else
1696     return iterator(const_cast<__node_pointer>(__l.__ptr_));
1697 #endif
1698 }
1699
1700 template <class _Tp, class _Alloc>
1701 void
1702 list<_Tp, _Alloc>::resize(size_type __n)
1703 {
1704     if (__n < base::__sz())
1705         erase(__iterator(__n), end());
1706     else if (__n > base::__sz())
1707     {
1708         __n -= base::__sz();
1709         size_type __ds = 0;
1710         __node_allocator& __na = base::__node_alloc();
1711         typedef __allocator_destructor<__node_allocator> _Dp;
1712         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1713         __hold->__prev_ = 0;
1714         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1715         ++__ds;
1716 #if _LIBCPP_DEBUG_LEVEL >= 2
1717         iterator __r = iterator(__hold.release(), this);
1718 #else
1719         iterator __r = iterator(__hold.release());
1720 #endif
1721         iterator __e = __r;
1722 #ifndef _LIBCPP_NO_EXCEPTIONS
1723         try
1724         {
1725 #endif  // _LIBCPP_NO_EXCEPTIONS
1726             for (--__n; __n != 0; --__n, ++__e, ++__ds)
1727             {
1728                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1729                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
1730                 __e.__ptr_->__next_ = __hold.get();
1731                 __hold->__prev_ = __e.__ptr_;
1732                 __hold.release();
1733             }
1734 #ifndef _LIBCPP_NO_EXCEPTIONS
1735         }
1736         catch (...)
1737         {
1738             while (true)
1739             {
1740                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1741                 __node_pointer __prev = __e.__ptr_->__prev_;
1742                 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1743                 if (__prev == 0)
1744                     break;
1745 #if _LIBCPP_DEBUG_LEVEL >= 2
1746                 __e = iterator(__prev, this);
1747 #else
1748                 __e = iterator(__prev);
1749 #endif
1750             }
1751             throw;
1752         }
1753 #endif  // _LIBCPP_NO_EXCEPTIONS
1754         __link_nodes(static_cast<__node&>(base::__end_), *__r.__ptr_, *__e.__ptr_);
1755         base::__sz() += __ds;
1756     }
1757 }
1758
1759 template <class _Tp, class _Alloc>
1760 void
1761 list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1762 {
1763     if (__n < base::__sz())
1764         erase(__iterator(__n), end());
1765     else if (__n > base::__sz())
1766     {
1767         __n -= base::__sz();
1768         size_type __ds = 0;
1769         __node_allocator& __na = base::__node_alloc();
1770         typedef __allocator_destructor<__node_allocator> _Dp;
1771         unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
1772         __hold->__prev_ = 0;
1773         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1774         ++__ds;
1775 #if _LIBCPP_DEBUG_LEVEL >= 2
1776         iterator __r = iterator(__hold.release(), this);
1777 #else
1778         iterator __r = iterator(__hold.release());
1779 #endif
1780         iterator __e = __r;
1781 #ifndef _LIBCPP_NO_EXCEPTIONS
1782         try
1783         {
1784 #endif  // _LIBCPP_NO_EXCEPTIONS
1785             for (--__n; __n != 0; --__n, ++__e, ++__ds)
1786             {
1787                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
1788                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
1789                 __e.__ptr_->__next_ = __hold.get();
1790                 __hold->__prev_ = __e.__ptr_;
1791                 __hold.release();
1792             }
1793 #ifndef _LIBCPP_NO_EXCEPTIONS
1794         }
1795         catch (...)
1796         {
1797             while (true)
1798             {
1799                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
1800                 __node_pointer __prev = __e.__ptr_->__prev_;
1801                 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1802                 if (__prev == 0)
1803                     break;
1804 #if _LIBCPP_DEBUG_LEVEL >= 2
1805                 __e = iterator(__prev, this);
1806 #else
1807                 __e = iterator(__prev);
1808 #endif
1809             }
1810             throw;
1811         }
1812 #endif  // _LIBCPP_NO_EXCEPTIONS
1813         __link_nodes(static_cast<__node&>(base::__end_), *__r.__ptr_, *__e.__ptr_);
1814         base::__sz() += __ds;
1815     }
1816 }
1817
1818 template <class _Tp, class _Alloc>
1819 void
1820 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
1821 {
1822     _LIBCPP_ASSERT(this != &__c,
1823                    "list::splice(iterator, list) called with this == &list");
1824 #if _LIBCPP_DEBUG_LEVEL >= 2
1825     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1826         "list::splice(iterator, list) called with an iterator not"
1827         " referring to this list");
1828 #endif
1829     if (!__c.empty())
1830     {
1831         __node& __f = *__c.__end_.__next_;
1832         __node& __l = *__c.__end_.__prev_;
1833         base::__unlink_nodes(__f, __l);
1834         __link_nodes(const_cast<__node&>(*__p.__ptr_), __f, __l);
1835         base::__sz() += __c.__sz();
1836         __c.__sz() = 0;
1837 #if _LIBCPP_DEBUG_LEVEL >= 2
1838         __libcpp_db* __db = __get_db();
1839         __c_node* __cn1 = __db->__find_c_and_lock(this);
1840         __c_node* __cn2 = __db->__find_c(&__c);
1841         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1842         {
1843             --__p;
1844             iterator* __i = static_cast<iterator*>((*__p)->__i_);
1845             if (__i->__ptr_ != static_cast<__node_pointer>(&__c.__end_))
1846             {
1847                 __cn1->__add(*__p);
1848                 (*__p)->__c_ = __cn1;
1849                 if (--__cn2->end_ != __p)
1850                     memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1851             }
1852         }
1853         __db->unlock();
1854 #endif
1855     }
1856 }
1857
1858 template <class _Tp, class _Alloc>
1859 void
1860 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
1861 {
1862 #if _LIBCPP_DEBUG_LEVEL >= 2
1863     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1864         "list::splice(iterator, list, iterator) called with first iterator not"
1865         " referring to this list");
1866     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c,
1867         "list::splice(iterator, list, iterator) called with second iterator not"
1868         " referring to list argument");
1869     _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i),
1870         "list::splice(iterator, list, iterator) called with second iterator not"
1871         " derefereceable");
1872 #endif
1873     if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
1874     {
1875         __node& __f = const_cast<__node&>(*__i.__ptr_);
1876         base::__unlink_nodes(__f, __f);
1877         __link_nodes(const_cast<__node&>(*__p.__ptr_), __f, __f);
1878         --__c.__sz();
1879         ++base::__sz();
1880 #if _LIBCPP_DEBUG_LEVEL >= 2
1881         __libcpp_db* __db = __get_db();
1882         __c_node* __cn1 = __db->__find_c_and_lock(this);
1883         __c_node* __cn2 = __db->__find_c(&__c);
1884         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1885         {
1886             --__p;
1887             iterator* __j = static_cast<iterator*>((*__p)->__i_);
1888             if (__j->__ptr_ == &__f)
1889             {
1890                 __cn1->__add(*__p);
1891                 (*__p)->__c_ = __cn1;
1892                 if (--__cn2->end_ != __p)
1893                     memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1894             }
1895         }
1896         __db->unlock();
1897 #endif
1898     }
1899 }
1900
1901 template <class _Tp, class _Alloc>
1902 void
1903 list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
1904 {
1905 #if _LIBCPP_DEBUG_LEVEL >= 2
1906     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1907         "list::splice(iterator, list, iterator, iterator) called with first iterator not"
1908         " referring to this list");
1909     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c,
1910         "list::splice(iterator, list, iterator, iterator) called with second iterator not"
1911         " referring to list argument");
1912     if (this == &__c)
1913     {
1914         for (const_iterator __i = __f; __i != __l; ++__i)
1915             _LIBCPP_ASSERT(__i != __p,
1916                            "list::splice(iterator, list, iterator, iterator)"
1917                            " called with the first iterator within the range"
1918                            " of the second and third iterators");
1919     }
1920 #endif
1921     if (__f != __l)
1922     {
1923         if (this != &__c)
1924         {
1925             size_type __s = _VSTD::distance(__f, __l);
1926             __c.__sz() -= __s;
1927             base::__sz() += __s;
1928         }
1929         __node& __first = const_cast<__node&>(*__f.__ptr_);
1930         --__l;
1931         __node& __last = const_cast<__node&>(*__l.__ptr_);
1932         base::__unlink_nodes(__first, __last);
1933         __link_nodes(const_cast<__node&>(*__p.__ptr_), __first, __last);
1934 #if _LIBCPP_DEBUG_LEVEL >= 2
1935         __libcpp_db* __db = __get_db();
1936         __c_node* __cn1 = __db->__find_c_and_lock(this);
1937         __c_node* __cn2 = __db->__find_c(&__c);
1938         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1939         {
1940             --__p;
1941             iterator* __j = static_cast<iterator*>((*__p)->__i_);
1942             for (__node_pointer __k = const_cast<__node_pointer>(__f.__ptr_);
1943                                           __k != __l.__ptr_; __k = __k->__next_)
1944             {
1945                 if (__j->__ptr_ == __k)
1946                 {
1947                     __cn1->__add(*__p);
1948                     (*__p)->__c_ = __cn1;
1949                     if (--__cn2->end_ != __p)
1950                         memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1951                 }
1952             }
1953         }
1954         __db->unlock();
1955 #endif
1956     }
1957 }
1958
1959 template <class _Tp, class _Alloc>
1960 void
1961 list<_Tp, _Alloc>::remove(const value_type& __x)
1962 {
1963     for (iterator __i = begin(), __e = end(); __i != __e;)
1964     {
1965         if (*__i == __x)
1966         {
1967             iterator __j = _VSTD::next(__i);
1968             for (; __j != __e && *__j == __x; ++__j)
1969                 ;
1970             __i = erase(__i, __j);
1971         }
1972         else
1973             ++__i;
1974     }
1975 }
1976
1977 template <class _Tp, class _Alloc>
1978 template <class _Pred>
1979 void
1980 list<_Tp, _Alloc>::remove_if(_Pred __pred)
1981 {
1982     for (iterator __i = begin(), __e = end(); __i != __e;)
1983     {
1984         if (__pred(*__i))
1985         {
1986             iterator __j = _VSTD::next(__i);
1987             for (; __j != __e && __pred(*__j); ++__j)
1988                 ;
1989             __i = erase(__i, __j);
1990         }
1991         else
1992             ++__i;
1993     }
1994 }
1995
1996 template <class _Tp, class _Alloc>
1997 inline _LIBCPP_INLINE_VISIBILITY
1998 void
1999 list<_Tp, _Alloc>::unique()
2000 {
2001     unique(__equal_to<value_type>());
2002 }
2003
2004 template <class _Tp, class _Alloc>
2005 template <class _BinaryPred>
2006 void
2007 list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
2008 {
2009     for (iterator __i = begin(), __e = end(); __i != __e;)
2010     {
2011         iterator __j = _VSTD::next(__i);
2012         for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
2013             ;
2014         if (++__i != __j)
2015             __i = erase(__i, __j);
2016     }
2017 }
2018
2019 template <class _Tp, class _Alloc>
2020 inline _LIBCPP_INLINE_VISIBILITY
2021 void
2022 list<_Tp, _Alloc>::merge(list& __c)
2023 {
2024     merge(__c, __less<value_type>());
2025 }
2026
2027 template <class _Tp, class _Alloc>
2028 template <class _Comp>
2029 void
2030 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2031 {
2032     if (this != &__c)
2033     {
2034         iterator __f1 = begin();
2035         iterator __e1 = end();
2036         iterator __f2 = __c.begin();
2037         iterator __e2 = __c.end();
2038         while (__f1 != __e1 && __f2 != __e2)
2039         {
2040             if (__comp(*__f2, *__f1))
2041             {
2042                 size_type __ds = 1;
2043                 iterator __m2 = _VSTD::next(__f2);
2044                 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
2045                     ;
2046                 base::__sz() += __ds;
2047                 __c.__sz() -= __ds;
2048                 __node& __f = *__f2.__ptr_;
2049                 __node& __l = *__m2.__ptr_->__prev_;
2050                 __f2 = __m2;
2051                 base::__unlink_nodes(__f, __l);
2052                 __m2 = _VSTD::next(__f1);
2053                 __link_nodes(*__f1.__ptr_, __f, __l);
2054                 __f1 = __m2;
2055             }
2056             else
2057                 ++__f1;
2058         }
2059         splice(__e1, __c);
2060 #if _LIBCPP_DEBUG_LEVEL >= 2
2061         __libcpp_db* __db = __get_db();
2062         __c_node* __cn1 = __db->__find_c_and_lock(this);
2063         __c_node* __cn2 = __db->__find_c(&__c);
2064         for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2065         {
2066             --__p;
2067             iterator* __i = static_cast<iterator*>((*__p)->__i_);
2068             if (__i->__ptr_ != static_cast<__node_pointer>(&__c.__end_))
2069             {
2070                 __cn1->__add(*__p);
2071                 (*__p)->__c_ = __cn1;
2072                 if (--__cn2->end_ != __p)
2073                     memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2074             }
2075         }
2076         __db->unlock();
2077 #endif
2078     }
2079 }
2080
2081 template <class _Tp, class _Alloc>
2082 inline _LIBCPP_INLINE_VISIBILITY
2083 void
2084 list<_Tp, _Alloc>::sort()
2085 {
2086     sort(__less<value_type>());
2087 }
2088
2089 template <class _Tp, class _Alloc>
2090 template <class _Comp>
2091 inline _LIBCPP_INLINE_VISIBILITY
2092 void
2093 list<_Tp, _Alloc>::sort(_Comp __comp)
2094 {
2095     __sort(begin(), end(), base::__sz(), __comp);
2096 }
2097
2098 template <class _Tp, class _Alloc>
2099 template <class _Comp>
2100 typename list<_Tp, _Alloc>::iterator
2101 list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
2102 {
2103     switch (__n)
2104     {
2105     case 0:
2106     case 1:
2107         return __f1;
2108     case 2:
2109         if (__comp(*--__e2, *__f1))
2110         {
2111             __node& __f = *__e2.__ptr_;
2112             base::__unlink_nodes(__f, __f);
2113             __link_nodes(*__f1.__ptr_, __f, __f);
2114             return __e2;
2115         }
2116         return __f1;
2117     }
2118     size_type __n2 = __n / 2;
2119     iterator __e1 = _VSTD::next(__f1, __n2);
2120     iterator  __r = __f1 = __sort(__f1, __e1, __n2, __comp);
2121     iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2122     if (__comp(*__f2, *__f1))
2123     {
2124         iterator __m2 = _VSTD::next(__f2);
2125         for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2126             ;
2127         __node& __f = *__f2.__ptr_;
2128         __node& __l = *__m2.__ptr_->__prev_;
2129         __r = __f2;
2130         __e1 = __f2 = __m2;
2131         base::__unlink_nodes(__f, __l);
2132         __m2 = _VSTD::next(__f1);
2133         __link_nodes(*__f1.__ptr_, __f, __l);
2134         __f1 = __m2;
2135     }
2136     else
2137         ++__f1;
2138     while (__f1 != __e1 && __f2 != __e2)
2139     {
2140         if (__comp(*__f2, *__f1))
2141         {
2142             iterator __m2 = _VSTD::next(__f2);
2143             for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2144                 ;
2145             __node& __f = *__f2.__ptr_;
2146             __node& __l = *__m2.__ptr_->__prev_;
2147             if (__e1 == __f2)
2148                 __e1 = __m2;
2149             __f2 = __m2;
2150             base::__unlink_nodes(__f, __l);
2151             __m2 = _VSTD::next(__f1);
2152             __link_nodes(*__f1.__ptr_, __f, __l);
2153             __f1 = __m2;
2154         }
2155         else
2156             ++__f1;
2157     }
2158     return __r;
2159 }
2160
2161 template <class _Tp, class _Alloc>
2162 void
2163 list<_Tp, _Alloc>::reverse() _NOEXCEPT
2164 {
2165     if (base::__sz() > 1)
2166     {
2167         iterator __e = end();
2168         for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
2169         {
2170             _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
2171             __i.__ptr_ = __i.__ptr_->__prev_;
2172         }
2173         _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
2174     }
2175 }
2176
2177 template <class _Tp, class _Alloc>
2178 bool
2179 list<_Tp, _Alloc>::__invariants() const
2180 {
2181     return size() == _VSTD::distance(begin(), end());
2182 }
2183
2184 #if _LIBCPP_DEBUG_LEVEL >= 2
2185
2186 template <class _Tp, class _Alloc>
2187 bool
2188 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
2189 {
2190     return __i->__ptr_ != &this->__end_;
2191 }
2192
2193 template <class _Tp, class _Alloc>
2194 bool
2195 list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
2196 {
2197     return !empty() &&  __i->__ptr_ != base::__end_.__next_;
2198 }
2199
2200 template <class _Tp, class _Alloc>
2201 bool
2202 list<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2203 {
2204     return false;
2205 }
2206
2207 template <class _Tp, class _Alloc>
2208 bool
2209 list<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2210 {
2211     return false;
2212 }
2213
2214 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
2215
2216 template <class _Tp, class _Alloc>
2217 inline _LIBCPP_INLINE_VISIBILITY
2218 bool
2219 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2220 {
2221     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2222 }
2223
2224 template <class _Tp, class _Alloc>
2225 inline _LIBCPP_INLINE_VISIBILITY
2226 bool
2227 operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2228 {
2229     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2230 }
2231
2232 template <class _Tp, class _Alloc>
2233 inline _LIBCPP_INLINE_VISIBILITY
2234 bool
2235 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2236 {
2237     return !(__x == __y);
2238 }
2239
2240 template <class _Tp, class _Alloc>
2241 inline _LIBCPP_INLINE_VISIBILITY
2242 bool
2243 operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2244 {
2245     return __y < __x;
2246 }
2247
2248 template <class _Tp, class _Alloc>
2249 inline _LIBCPP_INLINE_VISIBILITY
2250 bool
2251 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2252 {
2253     return !(__x < __y);
2254 }
2255
2256 template <class _Tp, class _Alloc>
2257 inline _LIBCPP_INLINE_VISIBILITY
2258 bool
2259 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2260 {
2261     return !(__y < __x);
2262 }
2263
2264 template <class _Tp, class _Alloc>
2265 inline _LIBCPP_INLINE_VISIBILITY
2266 void
2267 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2268     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2269 {
2270     __x.swap(__y);
2271 }
2272
2273 _LIBCPP_END_NAMESPACE_STD
2274
2275 #endif  // _LIBCPP_LIST