contrib/libc++/include/memory

   1 // -*- C++ -*-
   2 //===-------------------------- memory ------------------------------------===//
   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_MEMORY
  12 #define _LIBCPP_MEMORY
  13
  14 /*
  15     memory synopsis
  16
  17 namespace std
  18 {
  19
  20 struct allocator_arg_t { };
  21 constexpr allocator_arg_t allocator_arg = allocator_arg_t();
  22
  23 template <class T, class Alloc> struct uses_allocator;
  24
  25 template <class Ptr>
  26 struct pointer_traits
  27 {
  28     typedef Ptr pointer;
  29     typedef <details> element_type;
  30     typedef <details> difference_type;
  31
  32     template <class U> using rebind = <details>;
  33
  34     static pointer pointer_to(<details>);
  35 };
  36
  37 template <class T>
  38 struct pointer_traits<T*>
  39 {
  40     typedef T* pointer;
  41     typedef T element_type;
  42     typedef ptrdiff_t difference_type;
  43
  44     template <class U> using rebind = U*;
  45
  46     static pointer pointer_to(<details>) noexcept;
  47 };
  48
  49 template <class Alloc>
  50 struct allocator_traits
  51 {
  52     typedef Alloc                        allocator_type;
  53     typedef typename allocator_type::value_type
  54                                          value_type;
  55
  56     typedef Alloc::pointer | value_type* pointer;
  57     typedef Alloc::const_pointer
  58           | pointer_traits<pointer>::rebind<const value_type>
  59                                          const_pointer;
  60     typedef Alloc::void_pointer
  61           | pointer_traits<pointer>::rebind<void>
  62                                          void_pointer;
  63     typedef Alloc::const_void_pointer
  64           | pointer_traits<pointer>::rebind<const void>
  65                                          const_void_pointer;
  66     typedef Alloc::difference_type
  67           | pointer_traits<pointer>::difference_type
  68                                          difference_type;
  69     typedef Alloc::size_type
  70           | make_unsigned<difference_type>::type
  71                                          size_type;
  72     typedef Alloc::propagate_on_container_copy_assignment
  73           | false_type                   propagate_on_container_copy_assignment;
  74     typedef Alloc::propagate_on_container_move_assignment
  75           | false_type                   propagate_on_container_move_assignment;
  76     typedef Alloc::propagate_on_container_swap
  77           | false_type                   propagate_on_container_swap;
  78     typedef Alloc::is_always_equal
  79           | is_empty                     is_always_equal;
  80
  81     template <class T> using rebind_alloc  = Alloc::rebind<U>::other | Alloc<T, Args...>;
  82     template <class T> using rebind_traits = allocator_traits<rebind_alloc<T>>;
  83
  84     static pointer allocate(allocator_type& a, size_type n);
  85     static pointer allocate(allocator_type& a, size_type n, const_void_pointer hint);
  86
  87     static void deallocate(allocator_type& a, pointer p, size_type n) noexcept;
  88
  89     template <class T, class... Args>
  90         static void construct(allocator_type& a, T* p, Args&&... args);
  91
  92     template <class T>
  93         static void destroy(allocator_type& a, T* p);
  94
  95     static size_type max_size(const allocator_type& a); // noexcept in C++14
  96
  97     static allocator_type
  98         select_on_container_copy_construction(const allocator_type& a);
  99 };
 100
 101 template <>
 102 class allocator<void>
 103 {
 104 public:
 105     typedef void*                                 pointer;
 106     typedef const void*                           const_pointer;
 107     typedef void                                  value_type;
 108
 109     template <class _Up> struct rebind {typedef allocator<_Up> other;};
 110 };
 111
 112 template <class T>
 113 class allocator
 114 {
 115 public:
 116     typedef size_t                                size_type;
 117     typedef ptrdiff_t                             difference_type;
 118     typedef T*                                    pointer;
 119     typedef const T*                              const_pointer;
 120     typedef typename add_lvalue_reference<T>::type       reference;
 121     typedef typename add_lvalue_reference<const T>::type const_reference;
 122     typedef T                                     value_type;
 123
 124     template <class U> struct rebind {typedef allocator<U> other;};
 125
 126     allocator() noexcept;
 127     allocator(const allocator&) noexcept;
 128     template <class U> allocator(const allocator<U>&) noexcept;
 129     ~allocator();
 130     pointer address(reference x) const noexcept;
 131     const_pointer address(const_reference x) const noexcept;
 132     pointer allocate(size_type, allocator<void>::const_pointer hint = 0);
 133     void deallocate(pointer p, size_type n) noexcept;
 134     size_type max_size() const noexcept;
 135     template<class U, class... Args>
 136         void construct(U* p, Args&&... args);
 137     template <class U>
 138         void destroy(U* p);
 139 };
 140
 141 template <class T, class U>
 142 bool operator==(const allocator<T>&, const allocator<U>&) noexcept;
 143
 144 template <class T, class U>
 145 bool operator!=(const allocator<T>&, const allocator<U>&) noexcept;
 146
 147 template <class OutputIterator, class T>
 148 class raw_storage_iterator
 149     : public iterator<output_iterator_tag,
 150                       T,                               // purposefully not C++03
 151                       ptrdiff_t,                       // purposefully not C++03
 152                       T*,                              // purposefully not C++03
 153                       raw_storage_iterator&>           // purposefully not C++03
 154 {
 155 public:
 156     explicit raw_storage_iterator(OutputIterator x);
 157     raw_storage_iterator& operator*();
 158     raw_storage_iterator& operator=(const T& element);
 159     raw_storage_iterator& operator++();
 160     raw_storage_iterator  operator++(int);
 161 };
 162
 163 template <class T> pair<T*,ptrdiff_t> get_temporary_buffer(ptrdiff_t n) noexcept;
 164 template <class T> void               return_temporary_buffer(T* p) noexcept;
 165
 166 template <class T> T* addressof(T& r) noexcept;
 167 template <class T> T* addressof(const T&& r) noexcept = delete;
 168
 169 template <class InputIterator, class ForwardIterator>
 170 ForwardIterator
 171 uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);
 172
 173 template <class InputIterator, class Size, class ForwardIterator>
 174 ForwardIterator
 175 uninitialized_copy_n(InputIterator first, Size n, ForwardIterator result);
 176
 177 template <class ForwardIterator, class T>
 178 void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);
 179
 180 template <class ForwardIterator, class Size, class T>
 181 ForwardIterator
 182 uninitialized_fill_n(ForwardIterator first, Size n, const T& x);
 183
 184 template <class T>
 185 void destroy_at(T* location);
 186
 187 template <class ForwardIterator>
 188  void destroy(ForwardIterator first, ForwardIterator last);
 189
 190 template <class ForwardIterator, class Size>
 191  ForwardIterator destroy_n(ForwardIterator first, Size n);
 192
 193 template <class InputIterator, class ForwardIterator>
 194  ForwardIterator uninitialized_move(InputIterator first, InputIterator last, ForwardIterator result);
 195
 196 template <class InputIterator, class Size, class ForwardIterator>
 197  pair<InputIterator,ForwardIterator> uninitialized_move_n(InputIterator first, Size n, ForwardIterator result);
 198
 199 template <class ForwardIterator>
 200  void uninitialized_value_construct(ForwardIterator first, ForwardIterator last);
 201
 202 template <class ForwardIterator, class Size>
 203  ForwardIterator uninitialized_value_construct_n(ForwardIterator first, Size n);
 204
 205 template <class ForwardIterator>
 206  void uninitialized_default_construct(ForwardIterator first, ForwardIterator last);
 207
 208 template <class ForwardIterator, class Size>
 209  ForwardIterator uninitialized_default_construct_n(ForwardIterator first, Size n);
 210
 211 template <class Y> struct auto_ptr_ref {};      // removed in C++17
 212
 213 template<class X>
 214 class auto_ptr                                  // removed in C++17
 215 {
 216 public:
 217     typedef X element_type;
 218
 219     explicit auto_ptr(X* p =0) throw();
 220     auto_ptr(auto_ptr&) throw();
 221     template<class Y> auto_ptr(auto_ptr<Y>&) throw();
 222     auto_ptr& operator=(auto_ptr&) throw();
 223     template<class Y> auto_ptr& operator=(auto_ptr<Y>&) throw();
 224     auto_ptr& operator=(auto_ptr_ref<X> r) throw();
 225     ~auto_ptr() throw();
 226
 227     typename add_lvalue_reference<X>::type operator*() const throw();
 228     X* operator->() const throw();
 229     X* get() const throw();
 230     X* release() throw();
 231     void reset(X* p =0) throw();
 232
 233     auto_ptr(auto_ptr_ref<X>) throw();
 234     template<class Y> operator auto_ptr_ref<Y>() throw();
 235     template<class Y> operator auto_ptr<Y>() throw();
 236 };
 237
 238 template <class T>
 239 struct default_delete
 240 {
 241     constexpr default_delete() noexcept = default;
 242     template <class U> default_delete(const default_delete<U>&) noexcept;
 243
 244     void operator()(T*) const noexcept;
 245 };
 246
 247 template <class T>
 248 struct default_delete<T[]>
 249 {
 250     constexpr default_delete() noexcept = default;
 251     void operator()(T*) const noexcept;
 252     template <class U> void operator()(U*) const = delete;
 253 };
 254
 255 template <class T, class D = default_delete<T>>
 256 class unique_ptr
 257 {
 258 public:
 259     typedef see below pointer;
 260     typedef T element_type;
 261     typedef D deleter_type;
 262
 263     // constructors
 264     constexpr unique_ptr() noexcept;
 265     explicit unique_ptr(pointer p) noexcept;
 266     unique_ptr(pointer p, see below d1) noexcept;
 267     unique_ptr(pointer p, see below d2) noexcept;
 268     unique_ptr(unique_ptr&& u) noexcept;
 269     unique_ptr(nullptr_t) noexcept : unique_ptr() { }
 270     template <class U, class E>
 271         unique_ptr(unique_ptr<U, E>&& u) noexcept;
 272     template <class U>
 273         unique_ptr(auto_ptr<U>&& u) noexcept;       // removed in C++17
 274
 275     // destructor
 276     ~unique_ptr();
 277
 278     // assignment
 279     unique_ptr& operator=(unique_ptr&& u) noexcept;
 280     template <class U, class E> unique_ptr& operator=(unique_ptr<U, E>&& u) noexcept;
 281     unique_ptr& operator=(nullptr_t) noexcept;
 282
 283     // observers
 284     typename add_lvalue_reference<T>::type operator*() const;
 285     pointer operator->() const noexcept;
 286     pointer get() const noexcept;
 287     deleter_type& get_deleter() noexcept;
 288     const deleter_type& get_deleter() const noexcept;
 289     explicit operator bool() const noexcept;
 290
 291     // modifiers
 292     pointer release() noexcept;
 293     void reset(pointer p = pointer()) noexcept;
 294     void swap(unique_ptr& u) noexcept;
 295 };
 296
 297 template <class T, class D>
 298 class unique_ptr<T[], D>
 299 {
 300 public:
 301     typedef implementation-defined pointer;
 302     typedef T element_type;
 303     typedef D deleter_type;
 304
 305     // constructors
 306     constexpr unique_ptr() noexcept;
 307     explicit unique_ptr(pointer p) noexcept;
 308     unique_ptr(pointer p, see below d) noexcept;
 309     unique_ptr(pointer p, see below d) noexcept;
 310     unique_ptr(unique_ptr&& u) noexcept;
 311     unique_ptr(nullptr_t) noexcept : unique_ptr() { }
 312
 313     // destructor
 314     ~unique_ptr();
 315
 316     // assignment
 317     unique_ptr& operator=(unique_ptr&& u) noexcept;
 318     unique_ptr& operator=(nullptr_t) noexcept;
 319
 320     // observers
 321     T& operator[](size_t i) const;
 322     pointer get() const noexcept;
 323     deleter_type& get_deleter() noexcept;
 324     const deleter_type& get_deleter() const noexcept;
 325     explicit operator bool() const noexcept;
 326
 327     // modifiers
 328     pointer release() noexcept;
 329     void reset(pointer p = pointer()) noexcept;
 330     void reset(nullptr_t) noexcept;
 331     template <class U> void reset(U) = delete;
 332     void swap(unique_ptr& u) noexcept;
 333 };
 334
 335 template <class T, class D>
 336     void swap(unique_ptr<T, D>& x, unique_ptr<T, D>& y) noexcept;
 337
 338 template <class T1, class D1, class T2, class D2>
 339     bool operator==(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);
 340 template <class T1, class D1, class T2, class D2>
 341     bool operator!=(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);
 342 template <class T1, class D1, class T2, class D2>
 343     bool operator<(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);
 344 template <class T1, class D1, class T2, class D2>
 345     bool operator<=(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);
 346 template <class T1, class D1, class T2, class D2>
 347     bool operator>(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);
 348 template <class T1, class D1, class T2, class D2>
 349     bool operator>=(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);
 350
 351 template <class T, class D>
 352     bool operator==(const unique_ptr<T, D>& x, nullptr_t) noexcept;
 353 template <class T, class D>
 354     bool operator==(nullptr_t, const unique_ptr<T, D>& y) noexcept;
 355 template <class T, class D>
 356     bool operator!=(const unique_ptr<T, D>& x, nullptr_t) noexcept;
 357 template <class T, class D>
 358     bool operator!=(nullptr_t, const unique_ptr<T, D>& y) noexcept;
 359
 360 template <class T, class D>
 361     bool operator<(const unique_ptr<T, D>& x, nullptr_t);
 362 template <class T, class D>
 363     bool operator<(nullptr_t, const unique_ptr<T, D>& y);
 364 template <class T, class D>
 365     bool operator<=(const unique_ptr<T, D>& x, nullptr_t);
 366 template <class T, class D>
 367     bool operator<=(nullptr_t, const unique_ptr<T, D>& y);
 368 template <class T, class D>
 369     bool operator>(const unique_ptr<T, D>& x, nullptr_t);
 370 template <class T, class D>
 371     bool operator>(nullptr_t, const unique_ptr<T, D>& y);
 372 template <class T, class D>
 373     bool operator>=(const unique_ptr<T, D>& x, nullptr_t);
 374 template <class T, class D>
 375     bool operator>=(nullptr_t, const unique_ptr<T, D>& y);
 376
 377 class bad_weak_ptr
 378     : public std::exception
 379 {
 380     bad_weak_ptr() noexcept;
 381 };
 382
 383 template<class T, class... Args> unique_ptr<T> make_unique(Args&&... args);     // C++14
 384 template<class T>                unique_ptr<T> make_unique(size_t n);           // C++14
 385 template<class T, class... Args> unspecified   make_unique(Args&&...) = delete; // C++14, T == U[N]
 386
 387 template<class T>
 388 class shared_ptr
 389 {
 390 public:
 391     typedef T element_type;
 392     typedef weak_ptr<T> weak_type; // C++17
 393
 394     // constructors:
 395     constexpr shared_ptr() noexcept;
 396     template<class Y> explicit shared_ptr(Y* p);
 397     template<class Y, class D> shared_ptr(Y* p, D d);
 398     template<class Y, class D, class A> shared_ptr(Y* p, D d, A a);
 399     template <class D> shared_ptr(nullptr_t p, D d);
 400     template <class D, class A> shared_ptr(nullptr_t p, D d, A a);
 401     template<class Y> shared_ptr(const shared_ptr<Y>& r, T *p) noexcept;
 402     shared_ptr(const shared_ptr& r) noexcept;
 403     template<class Y> shared_ptr(const shared_ptr<Y>& r) noexcept;
 404     shared_ptr(shared_ptr&& r) noexcept;
 405     template<class Y> shared_ptr(shared_ptr<Y>&& r) noexcept;
 406     template<class Y> explicit shared_ptr(const weak_ptr<Y>& r);
 407     template<class Y> shared_ptr(auto_ptr<Y>&& r);          // removed in C++17
 408     template <class Y, class D> shared_ptr(unique_ptr<Y, D>&& r);
 409     shared_ptr(nullptr_t) : shared_ptr() { }
 410
 411     // destructor:
 412     ~shared_ptr();
 413
 414     // assignment:
 415     shared_ptr& operator=(const shared_ptr& r) noexcept;
 416     template<class Y> shared_ptr& operator=(const shared_ptr<Y>& r) noexcept;
 417     shared_ptr& operator=(shared_ptr&& r) noexcept;
 418     template<class Y> shared_ptr& operator=(shared_ptr<Y>&& r);
 419     template<class Y> shared_ptr& operator=(auto_ptr<Y>&& r); // removed in C++17
 420     template <class Y, class D> shared_ptr& operator=(unique_ptr<Y, D>&& r);
 421
 422     // modifiers:
 423     void swap(shared_ptr& r) noexcept;
 424     void reset() noexcept;
 425     template<class Y> void reset(Y* p);
 426     template<class Y, class D> void reset(Y* p, D d);
 427     template<class Y, class D, class A> void reset(Y* p, D d, A a);
 428
 429     // observers:
 430     T* get() const noexcept;
 431     T& operator*() const noexcept;
 432     T* operator->() const noexcept;
 433     long use_count() const noexcept;
 434     bool unique() const noexcept;
 435     explicit operator bool() const noexcept;
 436     template<class U> bool owner_before(shared_ptr<U> const& b) const noexcept;
 437     template<class U> bool owner_before(weak_ptr<U> const& b) const noexcept;
 438 };
 439
 440 // shared_ptr comparisons:
 441 template<class T, class U>
 442     bool operator==(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;
 443 template<class T, class U>
 444     bool operator!=(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;
 445 template<class T, class U>
 446     bool operator<(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;
 447 template<class T, class U>
 448     bool operator>(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;
 449 template<class T, class U>
 450     bool operator<=(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;
 451 template<class T, class U>
 452     bool operator>=(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;
 453
 454 template <class T>
 455     bool operator==(const shared_ptr<T>& x, nullptr_t) noexcept;
 456 template <class T>
 457     bool operator==(nullptr_t, const shared_ptr<T>& y) noexcept;
 458 template <class T>
 459     bool operator!=(const shared_ptr<T>& x, nullptr_t) noexcept;
 460 template <class T>
 461     bool operator!=(nullptr_t, const shared_ptr<T>& y) noexcept;
 462 template <class T>
 463     bool operator<(const shared_ptr<T>& x, nullptr_t) noexcept;
 464 template <class T>
 465 bool operator<(nullptr_t, const shared_ptr<T>& y) noexcept;
 466 template <class T>
 467     bool operator<=(const shared_ptr<T>& x, nullptr_t) noexcept;
 468 template <class T>
 469     bool operator<=(nullptr_t, const shared_ptr<T>& y) noexcept;
 470 template <class T>
 471     bool operator>(const shared_ptr<T>& x, nullptr_t) noexcept;
 472 template <class T>
 473     bool operator>(nullptr_t, const shared_ptr<T>& y) noexcept;
 474 template <class T>
 475     bool operator>=(const shared_ptr<T>& x, nullptr_t) noexcept;
 476 template <class T>
 477     bool operator>=(nullptr_t, const shared_ptr<T>& y) noexcept;
 478
 479 // shared_ptr specialized algorithms:
 480 template<class T> void swap(shared_ptr<T>& a, shared_ptr<T>& b) noexcept;
 481
 482 // shared_ptr casts:
 483 template<class T, class U>
 484     shared_ptr<T> static_pointer_cast(shared_ptr<U> const& r) noexcept;
 485 template<class T, class U>
 486     shared_ptr<T> dynamic_pointer_cast(shared_ptr<U> const& r) noexcept;
 487 template<class T, class U>
 488     shared_ptr<T> const_pointer_cast(shared_ptr<U> const& r) noexcept;
 489
 490 // shared_ptr I/O:
 491 template<class E, class T, class Y>
 492     basic_ostream<E, T>& operator<< (basic_ostream<E, T>& os, shared_ptr<Y> const& p);
 493
 494 // shared_ptr get_deleter:
 495 template<class D, class T> D* get_deleter(shared_ptr<T> const& p) noexcept;
 496
 497 template<class T, class... Args>
 498     shared_ptr<T> make_shared(Args&&... args);
 499 template<class T, class A, class... Args>
 500     shared_ptr<T> allocate_shared(const A& a, Args&&... args);
 501
 502 template<class T>
 503 class weak_ptr
 504 {
 505 public:
 506     typedef T element_type;
 507
 508     // constructors
 509     constexpr weak_ptr() noexcept;
 510     template<class Y> weak_ptr(shared_ptr<Y> const& r) noexcept;
 511     weak_ptr(weak_ptr const& r) noexcept;
 512     template<class Y> weak_ptr(weak_ptr<Y> const& r) noexcept;
 513     weak_ptr(weak_ptr&& r) noexcept;                      // C++14
 514     template<class Y> weak_ptr(weak_ptr<Y>&& r) noexcept; // C++14
 515
 516     // destructor
 517     ~weak_ptr();
 518
 519     // assignment
 520     weak_ptr& operator=(weak_ptr const& r) noexcept;
 521     template<class Y> weak_ptr& operator=(weak_ptr<Y> const& r) noexcept;
 522     template<class Y> weak_ptr& operator=(shared_ptr<Y> const& r) noexcept;
 523     weak_ptr& operator=(weak_ptr&& r) noexcept;                      // C++14
 524     template<class Y> weak_ptr& operator=(weak_ptr<Y>&& r) noexcept; // C++14
 525
 526     // modifiers
 527     void swap(weak_ptr& r) noexcept;
 528     void reset() noexcept;
 529
 530     // observers
 531     long use_count() const noexcept;
 532     bool expired() const noexcept;
 533     shared_ptr<T> lock() const noexcept;
 534     template<class U> bool owner_before(shared_ptr<U> const& b) const noexcept;
 535     template<class U> bool owner_before(weak_ptr<U> const& b) const noexcept;
 536 };
 537
 538 // weak_ptr specialized algorithms:
 539 template<class T> void swap(weak_ptr<T>& a, weak_ptr<T>& b) noexcept;
 540
 541 // class owner_less:
 542 template<class T> struct owner_less;
 543
 544 template<class T>
 545 struct owner_less<shared_ptr<T>>
 546     : binary_function<shared_ptr<T>, shared_ptr<T>, bool>
 547 {
 548     typedef bool result_type;
 549     bool operator()(shared_ptr<T> const&, shared_ptr<T> const&) const noexcept;
 550     bool operator()(shared_ptr<T> const&, weak_ptr<T> const&) const noexcept;
 551     bool operator()(weak_ptr<T> const&, shared_ptr<T> const&) const noexcept;
 552 };
 553
 554 template<class T>
 555 struct owner_less<weak_ptr<T>>
 556     : binary_function<weak_ptr<T>, weak_ptr<T>, bool>
 557 {
 558     typedef bool result_type;
 559     bool operator()(weak_ptr<T> const&, weak_ptr<T> const&) const noexcept;
 560     bool operator()(shared_ptr<T> const&, weak_ptr<T> const&) const noexcept;
 561     bool operator()(weak_ptr<T> const&, shared_ptr<T> const&) const noexcept;
 562 };
 563
 564 template <>  // Added in C++14
 565 struct owner_less<void>
 566 {
 567     template <class _Tp, class _Up>
 568     bool operator()( shared_ptr<_Tp> const& __x, shared_ptr<_Up> const& __y) const noexcept;
 569     template <class _Tp, class _Up>
 570     bool operator()( shared_ptr<_Tp> const& __x,   weak_ptr<_Up> const& __y) const noexcept;
 571     template <class _Tp, class _Up>
 572     bool operator()(   weak_ptr<_Tp> const& __x, shared_ptr<_Up> const& __y) const noexcept;
 573     template <class _Tp, class _Up>
 574     bool operator()(   weak_ptr<_Tp> const& __x,   weak_ptr<_Up> const& __y) const noexcept;
 575
 576     typedef void is_transparent;
 577 };
 578
 579 template<class T>
 580 class enable_shared_from_this
 581 {
 582 protected:
 583     constexpr enable_shared_from_this() noexcept;
 584     enable_shared_from_this(enable_shared_from_this const&) noexcept;
 585     enable_shared_from_this& operator=(enable_shared_from_this const&) noexcept;
 586     ~enable_shared_from_this();
 587 public:
 588     shared_ptr<T> shared_from_this();
 589     shared_ptr<T const> shared_from_this() const;
 590 };
 591
 592 template<class T>
 593     bool atomic_is_lock_free(const shared_ptr<T>* p);
 594 template<class T>
 595     shared_ptr<T> atomic_load(const shared_ptr<T>* p);
 596 template<class T>
 597     shared_ptr<T> atomic_load_explicit(const shared_ptr<T>* p, memory_order mo);
 598 template<class T>
 599     void atomic_store(shared_ptr<T>* p, shared_ptr<T> r);
 600 template<class T>
 601     void atomic_store_explicit(shared_ptr<T>* p, shared_ptr<T> r, memory_order mo);
 602 template<class T>
 603     shared_ptr<T> atomic_exchange(shared_ptr<T>* p, shared_ptr<T> r);
 604 template<class T>
 605     shared_ptr<T>
 606     atomic_exchange_explicit(shared_ptr<T>* p, shared_ptr<T> r, memory_order mo);
 607 template<class T>
 608     bool
 609     atomic_compare_exchange_weak(shared_ptr<T>* p, shared_ptr<T>* v, shared_ptr<T> w);
 610 template<class T>
 611     bool
 612     atomic_compare_exchange_strong( shared_ptr<T>* p, shared_ptr<T>* v, shared_ptr<T> w);
 613 template<class T>
 614     bool
 615     atomic_compare_exchange_weak_explicit(shared_ptr<T>* p, shared_ptr<T>* v,
 616                                           shared_ptr<T> w, memory_order success,
 617                                           memory_order failure);
 618 template<class T>
 619     bool
 620     atomic_compare_exchange_strong_explicit(shared_ptr<T>* p, shared_ptr<T>* v,
 621                                             shared_ptr<T> w, memory_order success,
 622                                             memory_order failure);
 623 // Hash support
 624 template <class T> struct hash;
 625 template <class T, class D> struct hash<unique_ptr<T, D> >;
 626 template <class T> struct hash<shared_ptr<T> >;
 627
 628 // Pointer safety
 629 enum class pointer_safety { relaxed, preferred, strict };
 630 void declare_reachable(void *p);
 631 template <class T> T *undeclare_reachable(T *p);
 632 void declare_no_pointers(char *p, size_t n);
 633 void undeclare_no_pointers(char *p, size_t n);
 634 pointer_safety get_pointer_safety() noexcept;
 635
 636 void* align(size_t alignment, size_t size, void*& ptr, size_t& space);
 637
 638 }  // std
 639
 640 */
 641
 642 #include <__config>
 643 #include <type_traits>
 644 #include <typeinfo>
 645 #include <cstddef>
 646 #include <cstdint>
 647 #include <new>
 648 #include <utility>
 649 #include <limits>
 650 #include <iterator>
 651 #include <__functional_base>
 652 #include <iosfwd>
 653 #include <tuple>
 654 #include <stdexcept>
 655 #include <cstring>
 656 #include <cassert>
 657 #if !defined(_LIBCPP_HAS_NO_ATOMIC_HEADER)
 658 #  include <atomic>
 659 #endif
 660
 661 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 662 #pragma GCC system_header
 663 #endif
 664
 665 _LIBCPP_PUSH_MACROS
 666 #include <__undef_macros>
 667
 668
 669 _LIBCPP_BEGIN_NAMESPACE_STD
 670
 671 template <class _ValueType>
 672 inline _LIBCPP_ALWAYS_INLINE
 673 _ValueType __libcpp_relaxed_load(_ValueType const* __value) {
 674 #if !defined(_LIBCPP_HAS_NO_THREADS) && \
 675     defined(__ATOMIC_RELAXED) &&        \
 676     (__has_builtin(__atomic_load_n) || _GNUC_VER >= 407)
 677     return __atomic_load_n(__value, __ATOMIC_RELAXED);
 678 #else
 679     return *__value;
 680 #endif
 681 }
 682
 683 template <class _ValueType>
 684 inline _LIBCPP_ALWAYS_INLINE
 685 _ValueType __libcpp_acquire_load(_ValueType const* __value) {
 686 #if !defined(_LIBCPP_HAS_NO_THREADS) && \
 687     defined(__ATOMIC_ACQUIRE) &&        \
 688     (__has_builtin(__atomic_load_n) || _GNUC_VER >= 407)
 689     return __atomic_load_n(__value, __ATOMIC_ACQUIRE);
 690 #else
 691     return *__value;
 692 #endif
 693 }
 694
 695 // addressof moved to <type_traits>
 696
 697 template <class _Tp> class allocator;
 698
 699 template <>
 700 class _LIBCPP_TEMPLATE_VIS allocator<void>
 701 {
 702 public:
 703     typedef void*             pointer;
 704     typedef const void*       const_pointer;
 705     typedef void              value_type;
 706
 707     template <class _Up> struct rebind {typedef allocator<_Up> other;};
 708 };
 709
 710 template <>
 711 class _LIBCPP_TEMPLATE_VIS allocator<const void>
 712 {
 713 public:
 714     typedef const void*       pointer;
 715     typedef const void*       const_pointer;
 716     typedef const void        value_type;
 717
 718     template <class _Up> struct rebind {typedef allocator<_Up> other;};
 719 };
 720
 721 // pointer_traits
 722
 723 template <class _Tp, class = void>
 724 struct __has_element_type : false_type {};
 725
 726 template <class _Tp>
 727 struct __has_element_type<_Tp,
 728               typename __void_t<typename _Tp::element_type>::type> : true_type {};
 729
 730 template <class _Ptr, bool = __has_element_type<_Ptr>::value>
 731 struct __pointer_traits_element_type;
 732
 733 template <class _Ptr>
 734 struct __pointer_traits_element_type<_Ptr, true>
 735 {
 736     typedef typename _Ptr::element_type type;
 737 };
 738
 739 #ifndef _LIBCPP_HAS_NO_VARIADICS
 740
 741 template <template <class, class...> class _Sp, class _Tp, class ..._Args>
 742 struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, true>
 743 {
 744     typedef typename _Sp<_Tp, _Args...>::element_type type;
 745 };
 746
 747 template <template <class, class...> class _Sp, class _Tp, class ..._Args>
 748 struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, false>
 749 {
 750     typedef _Tp type;
 751 };
 752
 753 #else  // _LIBCPP_HAS_NO_VARIADICS
 754
 755 template <template <class> class _Sp, class _Tp>
 756 struct __pointer_traits_element_type<_Sp<_Tp>, true>
 757 {
 758     typedef typename _Sp<_Tp>::element_type type;
 759 };
 760
 761 template <template <class> class _Sp, class _Tp>
 762 struct __pointer_traits_element_type<_Sp<_Tp>, false>
 763 {
 764     typedef _Tp type;
 765 };
 766
 767 template <template <class, class> class _Sp, class _Tp, class _A0>
 768 struct __pointer_traits_element_type<_Sp<_Tp, _A0>, true>
 769 {
 770     typedef typename _Sp<_Tp, _A0>::element_type type;
 771 };
 772
 773 template <template <class, class> class _Sp, class _Tp, class _A0>
 774 struct __pointer_traits_element_type<_Sp<_Tp, _A0>, false>
 775 {
 776     typedef _Tp type;
 777 };
 778
 779 template <template <class, class, class> class _Sp, class _Tp, class _A0, class _A1>
 780 struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1>, true>
 781 {
 782     typedef typename _Sp<_Tp, _A0, _A1>::element_type type;
 783 };
 784
 785 template <template <class, class, class> class _Sp, class _Tp, class _A0, class _A1>
 786 struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1>, false>
 787 {
 788     typedef _Tp type;
 789 };
 790
 791 template <template <class, class, class, class> class _Sp, class _Tp, class _A0,
 792                                                            class _A1, class _A2>
 793 struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1, _A2>, true>
 794 {
 795     typedef typename _Sp<_Tp, _A0, _A1, _A2>::element_type type;
 796 };
 797
 798 template <template <class, class, class, class> class _Sp, class _Tp, class _A0,
 799                                                            class _A1, class _A2>
 800 struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1, _A2>, false>
 801 {
 802     typedef _Tp type;
 803 };
 804
 805 #endif  // _LIBCPP_HAS_NO_VARIADICS
 806
 807 template <class _Tp, class = void>
 808 struct __has_difference_type : false_type {};
 809
 810 template <class _Tp>
 811 struct __has_difference_type<_Tp,
 812             typename __void_t<typename _Tp::difference_type>::type> : true_type {};
 813
 814 template <class _Ptr, bool = __has_difference_type<_Ptr>::value>
 815 struct __pointer_traits_difference_type
 816 {
 817     typedef ptrdiff_t type;
 818 };
 819
 820 template <class _Ptr>
 821 struct __pointer_traits_difference_type<_Ptr, true>
 822 {
 823     typedef typename _Ptr::difference_type type;
 824 };
 825
 826 template <class _Tp, class _Up>
 827 struct __has_rebind
 828 {
 829 private:
 830     struct __two {char __lx; char __lxx;};
 831     template <class _Xp> static __two __test(...);
 832     template <class _Xp> static char __test(typename _Xp::template rebind<_Up>* = 0);
 833 public:
 834     static const bool value = sizeof(__test<_Tp>(0)) == 1;
 835 };
 836
 837 template <class _Tp, class _Up, bool = __has_rebind<_Tp, _Up>::value>
 838 struct __pointer_traits_rebind
 839 {
 840 #ifndef _LIBCPP_CXX03_LANG
 841     typedef typename _Tp::template rebind<_Up> type;
 842 #else
 843     typedef typename _Tp::template rebind<_Up>::other type;
 844 #endif
 845 };
 846
 847 #ifndef _LIBCPP_HAS_NO_VARIADICS
 848
 849 template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>
 850 struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, true>
 851 {
 852 #ifndef _LIBCPP_CXX03_LANG
 853     typedef typename _Sp<_Tp, _Args...>::template rebind<_Up> type;
 854 #else
 855     typedef typename _Sp<_Tp, _Args...>::template rebind<_Up>::other type;
 856 #endif
 857 };
 858
 859 template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>
 860 struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, false>
 861 {
 862     typedef _Sp<_Up, _Args...> type;
 863 };
 864
 865 #else  // _LIBCPP_HAS_NO_VARIADICS
 866
 867 template <template <class> class _Sp, class _Tp, class _Up>
 868 struct __pointer_traits_rebind<_Sp<_Tp>, _Up, true>
 869 {
 870 #ifndef _LIBCPP_CXX03_LANG
 871     typedef typename _Sp<_Tp>::template rebind<_Up> type;
 872 #else
 873     typedef typename _Sp<_Tp>::template rebind<_Up>::other type;
 874 #endif
 875 };
 876
 877 template <template <class> class _Sp, class _Tp, class _Up>
 878 struct __pointer_traits_rebind<_Sp<_Tp>, _Up, false>
 879 {
 880     typedef _Sp<_Up> type;
 881 };
 882
 883 template <template <class, class> class _Sp, class _Tp, class _A0, class _Up>
 884 struct __pointer_traits_rebind<_Sp<_Tp, _A0>, _Up, true>
 885 {
 886 #ifndef _LIBCPP_CXX03_LANG
 887     typedef typename _Sp<_Tp, _A0>::template rebind<_Up> type;
 888 #else
 889     typedef typename _Sp<_Tp, _A0>::template rebind<_Up>::other type;
 890 #endif
 891 };
 892
 893 template <template <class, class> class _Sp, class _Tp, class _A0, class _Up>
 894 struct __pointer_traits_rebind<_Sp<_Tp, _A0>, _Up, false>
 895 {
 896     typedef _Sp<_Up, _A0> type;
 897 };
 898
 899 template <template <class, class, class> class _Sp, class _Tp, class _A0,
 900                                          class _A1, class _Up>
 901 struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1>, _Up, true>
 902 {
 903 #ifndef _LIBCPP_CXX03_LANG
 904     typedef typename _Sp<_Tp, _A0, _A1>::template rebind<_Up> type;
 905 #else
 906     typedef typename _Sp<_Tp, _A0, _A1>::template rebind<_Up>::other type;
 907 #endif
 908 };
 909
 910 template <template <class, class, class> class _Sp, class _Tp, class _A0,
 911                                          class _A1, class _Up>
 912 struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1>, _Up, false>
 913 {
 914     typedef _Sp<_Up, _A0, _A1> type;
 915 };
 916
 917 template <template <class, class, class, class> class _Sp, class _Tp, class _A0,
 918                                                 class _A1, class _A2, class _Up>
 919 struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1, _A2>, _Up, true>
 920 {
 921 #ifndef _LIBCPP_CXX03_LANG
 922     typedef typename _Sp<_Tp, _A0, _A1, _A2>::template rebind<_Up> type;
 923 #else
 924     typedef typename _Sp<_Tp, _A0, _A1, _A2>::template rebind<_Up>::other type;
 925 #endif
 926 };
 927
 928 template <template <class, class, class, class> class _Sp, class _Tp, class _A0,
 929                                                 class _A1, class _A2, class _Up>
 930 struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1, _A2>, _Up, false>
 931 {
 932     typedef _Sp<_Up, _A0, _A1, _A2> type;
 933 };
 934
 935 #endif  // _LIBCPP_HAS_NO_VARIADICS
 936
 937 template <class _Ptr>
 938 struct _LIBCPP_TEMPLATE_VIS pointer_traits
 939 {
 940     typedef _Ptr                                                     pointer;
 941     typedef typename __pointer_traits_element_type<pointer>::type    element_type;
 942     typedef typename __pointer_traits_difference_type<pointer>::type difference_type;
 943
 944 #ifndef _LIBCPP_CXX03_LANG
 945     template <class _Up> using rebind = typename __pointer_traits_rebind<pointer, _Up>::type;
 946 #else
 947     template <class _Up> struct rebind
 948         {typedef typename __pointer_traits_rebind<pointer, _Up>::type other;};
 949 #endif  // _LIBCPP_CXX03_LANG
 950
 951 private:
 952     struct __nat {};
 953 public:
 954     _LIBCPP_INLINE_VISIBILITY
 955     static pointer pointer_to(typename conditional<is_void<element_type>::value,
 956                                            __nat, element_type>::type& __r)
 957         {return pointer::pointer_to(__r);}
 958 };
 959
 960 template <class _Tp>
 961 struct _LIBCPP_TEMPLATE_VIS pointer_traits<_Tp*>
 962 {
 963     typedef _Tp*      pointer;
 964     typedef _Tp       element_type;
 965     typedef ptrdiff_t difference_type;
 966
 967 #ifndef _LIBCPP_CXX03_LANG
 968     template <class _Up> using rebind = _Up*;
 969 #else
 970     template <class _Up> struct rebind {typedef _Up* other;};
 971 #endif
 972
 973 private:
 974     struct __nat {};
 975 public:
 976     _LIBCPP_INLINE_VISIBILITY
 977     static pointer pointer_to(typename conditional<is_void<element_type>::value,
 978                                       __nat, element_type>::type& __r) _NOEXCEPT
 979         {return _VSTD::addressof(__r);}
 980 };
 981
 982 template <class _From, class _To>
 983 struct __rebind_pointer {
 984 #ifndef _LIBCPP_CXX03_LANG
 985     typedef typename pointer_traits<_From>::template rebind<_To>        type;
 986 #else
 987     typedef typename pointer_traits<_From>::template rebind<_To>::other type;
 988 #endif
 989 };
 990
 991 // allocator_traits
 992
 993 template <class _Tp, class = void>
 994 struct __has_pointer_type : false_type {};
 995
 996 template <class _Tp>
 997 struct __has_pointer_type<_Tp,
 998           typename __void_t<typename _Tp::pointer>::type> : true_type {};
 999
1000 namespace __pointer_type_imp
1001 {
1002
1003 template <class _Tp, class _Dp, bool = __has_pointer_type<_Dp>::value>
1004 struct __pointer_type
1005 {
1006     typedef typename _Dp::pointer type;
1007 };
1008
1009 template <class _Tp, class _Dp>
1010 struct __pointer_type<_Tp, _Dp, false>
1011 {
1012     typedef _Tp* type;
1013 };
1014
1015 }  // __pointer_type_imp
1016
1017 template <class _Tp, class _Dp>
1018 struct __pointer_type
1019 {
1020     typedef typename __pointer_type_imp::__pointer_type<_Tp, typename remove_reference<_Dp>::type>::type type;
1021 };
1022
1023 template <class _Tp, class = void>
1024 struct __has_const_pointer : false_type {};
1025
1026 template <class _Tp>
1027 struct __has_const_pointer<_Tp,
1028             typename __void_t<typename _Tp::const_pointer>::type> : true_type {};
1029
1030 template <class _Tp, class _Ptr, class _Alloc, bool = __has_const_pointer<_Alloc>::value>
1031 struct __const_pointer
1032 {
1033     typedef typename _Alloc::const_pointer type;
1034 };
1035
1036 template <class _Tp, class _Ptr, class _Alloc>
1037 struct __const_pointer<_Tp, _Ptr, _Alloc, false>
1038 {
1039 #ifndef _LIBCPP_CXX03_LANG
1040     typedef typename pointer_traits<_Ptr>::template rebind<const _Tp> type;
1041 #else
1042     typedef typename pointer_traits<_Ptr>::template rebind<const _Tp>::other type;
1043 #endif
1044 };
1045
1046 template <class _Tp, class = void>
1047 struct __has_void_pointer : false_type {};
1048
1049 template <class _Tp>
1050 struct __has_void_pointer<_Tp,
1051                typename __void_t<typename _Tp::void_pointer>::type> : true_type {};
1052
1053 template <class _Ptr, class _Alloc, bool = __has_void_pointer<_Alloc>::value>
1054 struct __void_pointer
1055 {
1056     typedef typename _Alloc::void_pointer type;
1057 };
1058
1059 template <class _Ptr, class _Alloc>
1060 struct __void_pointer<_Ptr, _Alloc, false>
1061 {
1062 #ifndef _LIBCPP_CXX03_LANG
1063     typedef typename pointer_traits<_Ptr>::template rebind<void> type;
1064 #else
1065     typedef typename pointer_traits<_Ptr>::template rebind<void>::other type;
1066 #endif
1067 };
1068
1069 template <class _Tp, class = void>
1070 struct __has_const_void_pointer : false_type {};
1071
1072 template <class _Tp>
1073 struct __has_const_void_pointer<_Tp,
1074             typename __void_t<typename _Tp::const_void_pointer>::type> : true_type {};
1075
1076 template <class _Ptr, class _Alloc, bool = __has_const_void_pointer<_Alloc>::value>
1077 struct __const_void_pointer
1078 {
1079     typedef typename _Alloc::const_void_pointer type;
1080 };
1081
1082 template <class _Ptr, class _Alloc>
1083 struct __const_void_pointer<_Ptr, _Alloc, false>
1084 {
1085 #ifndef _LIBCPP_CXX03_LANG
1086     typedef typename pointer_traits<_Ptr>::template rebind<const void> type;
1087 #else
1088     typedef typename pointer_traits<_Ptr>::template rebind<const void>::other type;
1089 #endif
1090 };
1091
1092 template <class _Tp>
1093 inline _LIBCPP_INLINE_VISIBILITY
1094 _Tp*
1095 __to_raw_pointer(_Tp* __p) _NOEXCEPT
1096 {
1097     return __p;
1098 }
1099
1100 template <class _Pointer>
1101 inline _LIBCPP_INLINE_VISIBILITY
1102 typename pointer_traits<_Pointer>::element_type*
1103 __to_raw_pointer(_Pointer __p) _NOEXCEPT
1104 {
1105     return _VSTD::__to_raw_pointer(__p.operator->());
1106 }
1107
1108 template <class _Tp, class = void>
1109 struct __has_size_type : false_type {};
1110
1111 template <class _Tp>
1112 struct __has_size_type<_Tp,
1113                typename __void_t<typename _Tp::size_type>::type> : true_type {};
1114
1115 template <class _Alloc, class _DiffType, bool = __has_size_type<_Alloc>::value>
1116 struct __size_type
1117 {
1118     typedef typename make_unsigned<_DiffType>::type type;
1119 };
1120
1121 template <class _Alloc, class _DiffType>
1122 struct __size_type<_Alloc, _DiffType, true>
1123 {
1124     typedef typename _Alloc::size_type type;
1125 };
1126
1127 template <class _Tp, class = void>
1128 struct __has_propagate_on_container_copy_assignment : false_type {};
1129
1130 template <class _Tp>
1131 struct __has_propagate_on_container_copy_assignment<_Tp,
1132     typename __void_t<typename _Tp::propagate_on_container_copy_assignment>::type>
1133         : true_type {};
1134
1135 template <class _Alloc, bool = __has_propagate_on_container_copy_assignment<_Alloc>::value>
1136 struct __propagate_on_container_copy_assignment
1137 {
1138     typedef false_type type;
1139 };
1140
1141 template <class _Alloc>
1142 struct __propagate_on_container_copy_assignment<_Alloc, true>
1143 {
1144     typedef typename _Alloc::propagate_on_container_copy_assignment type;
1145 };
1146
1147 template <class _Tp, class = void>
1148 struct __has_propagate_on_container_move_assignment : false_type {};
1149
1150 template <class _Tp>
1151 struct __has_propagate_on_container_move_assignment<_Tp,
1152            typename __void_t<typename _Tp::propagate_on_container_move_assignment>::type>
1153                : true_type {};
1154
1155 template <class _Alloc, bool = __has_propagate_on_container_move_assignment<_Alloc>::value>
1156 struct __propagate_on_container_move_assignment
1157 {
1158     typedef false_type type;
1159 };
1160
1161 template <class _Alloc>
1162 struct __propagate_on_container_move_assignment<_Alloc, true>
1163 {
1164     typedef typename _Alloc::propagate_on_container_move_assignment type;
1165 };
1166
1167 template <class _Tp, class = void>
1168 struct __has_propagate_on_container_swap : false_type {};
1169
1170 template <class _Tp>
1171 struct __has_propagate_on_container_swap<_Tp,
1172            typename __void_t<typename _Tp::propagate_on_container_swap>::type>
1173                : true_type {};
1174
1175 template <class _Alloc, bool = __has_propagate_on_container_swap<_Alloc>::value>
1176 struct __propagate_on_container_swap
1177 {
1178     typedef false_type type;
1179 };
1180
1181 template <class _Alloc>
1182 struct __propagate_on_container_swap<_Alloc, true>
1183 {
1184     typedef typename _Alloc::propagate_on_container_swap type;
1185 };
1186
1187 template <class _Tp, class = void>
1188 struct __has_is_always_equal : false_type {};
1189
1190 template <class _Tp>
1191 struct __has_is_always_equal<_Tp,
1192            typename __void_t<typename _Tp::is_always_equal>::type>
1193                : true_type {};
1194
1195 template <class _Alloc, bool = __has_is_always_equal<_Alloc>::value>
1196 struct __is_always_equal
1197 {
1198     typedef typename _VSTD::is_empty<_Alloc>::type type;
1199 };
1200
1201 template <class _Alloc>
1202 struct __is_always_equal<_Alloc, true>
1203 {
1204     typedef typename _Alloc::is_always_equal type;
1205 };
1206
1207 template <class _Tp, class _Up, bool = __has_rebind<_Tp, _Up>::value>
1208 struct __has_rebind_other
1209 {
1210 private:
1211     struct __two {char __lx; char __lxx;};
1212     template <class _Xp> static __two __test(...);
1213     template <class _Xp> static char __test(typename _Xp::template rebind<_Up>::other* = 0);
1214 public:
1215     static const bool value = sizeof(__test<_Tp>(0)) == 1;
1216 };
1217
1218 template <class _Tp, class _Up>
1219 struct __has_rebind_other<_Tp, _Up, false>
1220 {
1221     static const bool value = false;
1222 };
1223
1224 template <class _Tp, class _Up, bool = __has_rebind_other<_Tp, _Up>::value>
1225 struct __allocator_traits_rebind
1226 {
1227     typedef typename _Tp::template rebind<_Up>::other type;
1228 };
1229
1230 #ifndef _LIBCPP_HAS_NO_VARIADICS
1231
1232 template <template <class, class...> class _Alloc, class _Tp, class ..._Args, class _Up>
1233 struct __allocator_traits_rebind<_Alloc<_Tp, _Args...>, _Up, true>
1234 {
1235     typedef typename _Alloc<_Tp, _Args...>::template rebind<_Up>::other type;
1236 };
1237
1238 template <template <class, class...> class _Alloc, class _Tp, class ..._Args, class _Up>
1239 struct __allocator_traits_rebind<_Alloc<_Tp, _Args...>, _Up, false>
1240 {
1241     typedef _Alloc<_Up, _Args...> type;
1242 };
1243
1244 #else  // _LIBCPP_HAS_NO_VARIADICS
1245
1246 template <template <class> class _Alloc, class _Tp, class _Up>
1247 struct __allocator_traits_rebind<_Alloc<_Tp>, _Up, true>
1248 {
1249     typedef typename _Alloc<_Tp>::template rebind<_Up>::other type;
1250 };
1251
1252 template <template <class> class _Alloc, class _Tp, class _Up>
1253 struct __allocator_traits_rebind<_Alloc<_Tp>, _Up, false>
1254 {
1255     typedef _Alloc<_Up> type;
1256 };
1257
1258 template <template <class, class> class _Alloc, class _Tp, class _A0, class _Up>
1259 struct __allocator_traits_rebind<_Alloc<_Tp, _A0>, _Up, true>
1260 {
1261     typedef typename _Alloc<_Tp, _A0>::template rebind<_Up>::other type;
1262 };
1263
1264 template <template <class, class> class _Alloc, class _Tp, class _A0, class _Up>
1265 struct __allocator_traits_rebind<_Alloc<_Tp, _A0>, _Up, false>
1266 {
1267     typedef _Alloc<_Up, _A0> type;
1268 };
1269
1270 template <template <class, class, class> class _Alloc, class _Tp, class _A0,
1271                                          class _A1, class _Up>
1272 struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1>, _Up, true>
1273 {
1274     typedef typename _Alloc<_Tp, _A0, _A1>::template rebind<_Up>::other type;
1275 };
1276
1277 template <template <class, class, class> class _Alloc, class _Tp, class _A0,
1278                                          class _A1, class _Up>
1279 struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1>, _Up, false>
1280 {
1281     typedef _Alloc<_Up, _A0, _A1> type;
1282 };
1283
1284 template <template <class, class, class, class> class _Alloc, class _Tp, class _A0,
1285                                                 class _A1, class _A2, class _Up>
1286 struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1, _A2>, _Up, true>
1287 {
1288     typedef typename _Alloc<_Tp, _A0, _A1, _A2>::template rebind<_Up>::other type;
1289 };
1290
1291 template <template <class, class, class, class> class _Alloc, class _Tp, class _A0,
1292                                                 class _A1, class _A2, class _Up>
1293 struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1, _A2>, _Up, false>
1294 {
1295     typedef _Alloc<_Up, _A0, _A1, _A2> type;
1296 };
1297
1298 #endif  // _LIBCPP_HAS_NO_VARIADICS
1299
1300 #ifndef _LIBCPP_CXX03_LANG
1301
1302 template <class _Alloc, class _SizeType, class _ConstVoidPtr>
1303 auto
1304 __has_allocate_hint_test(_Alloc&& __a, _SizeType&& __sz, _ConstVoidPtr&& __p)
1305     -> decltype(__a.allocate(__sz, __p), true_type());
1306
1307 template <class _Alloc, class _SizeType, class _ConstVoidPtr>
1308 auto
1309 __has_allocate_hint_test(const _Alloc& __a, _SizeType&& __sz, _ConstVoidPtr&& __p)
1310     -> false_type;
1311
1312 template <class _Alloc, class _SizeType, class _ConstVoidPtr>
1313 struct __has_allocate_hint
1314     : integral_constant<bool,
1315         is_same<
1316             decltype(__has_allocate_hint_test(declval<_Alloc>(),
1317                                           declval<_SizeType>(),
1318                                           declval<_ConstVoidPtr>())),
1319             true_type>::value>
1320 {
1321 };
1322
1323 #else  // _LIBCPP_CXX03_LANG
1324
1325 template <class _Alloc, class _SizeType, class _ConstVoidPtr>
1326 struct __has_allocate_hint
1327     : true_type
1328 {
1329 };
1330
1331 #endif  // _LIBCPP_CXX03_LANG
1332
1333 #if !defined(_LIBCPP_CXX03_LANG)
1334
1335 template <class _Alloc, class _Tp, class ..._Args>
1336 decltype(_VSTD::declval<_Alloc>().construct(_VSTD::declval<_Tp*>(),
1337                                            _VSTD::declval<_Args>()...),
1338                                            true_type())
1339 __has_construct_test(_Alloc&& __a, _Tp* __p, _Args&& ...__args);
1340
1341 template <class _Alloc, class _Pointer, class ..._Args>
1342 false_type
1343 __has_construct_test(const _Alloc& __a, _Pointer&& __p, _Args&& ...__args);
1344
1345 template <class _Alloc, class _Pointer, class ..._Args>
1346 struct __has_construct
1347     : integral_constant<bool,
1348         is_same<
1349             decltype(__has_construct_test(declval<_Alloc>(),
1350                                           declval<_Pointer>(),
1351                                           declval<_Args>()...)),
1352             true_type>::value>
1353 {
1354 };
1355
1356 template <class _Alloc, class _Pointer>
1357 auto
1358 __has_destroy_test(_Alloc&& __a, _Pointer&& __p)
1359     -> decltype(__a.destroy(__p), true_type());
1360
1361 template <class _Alloc, class _Pointer>
1362 auto
1363 __has_destroy_test(const _Alloc& __a, _Pointer&& __p)
1364     -> false_type;
1365
1366 template <class _Alloc, class _Pointer>
1367 struct __has_destroy
1368     : integral_constant<bool,
1369         is_same<
1370             decltype(__has_destroy_test(declval<_Alloc>(),
1371                                         declval<_Pointer>())),
1372             true_type>::value>
1373 {
1374 };
1375
1376 template <class _Alloc>
1377 auto
1378 __has_max_size_test(_Alloc&& __a)
1379     -> decltype(__a.max_size(), true_type());
1380
1381 template <class _Alloc>
1382 auto
1383 __has_max_size_test(const volatile _Alloc& __a)
1384     -> false_type;
1385
1386 template <class _Alloc>
1387 struct __has_max_size
1388     : integral_constant<bool,
1389         is_same<
1390             decltype(__has_max_size_test(declval<_Alloc&>())),
1391             true_type>::value>
1392 {
1393 };
1394
1395 template <class _Alloc>
1396 auto
1397 __has_select_on_container_copy_construction_test(_Alloc&& __a)
1398     -> decltype(__a.select_on_container_copy_construction(), true_type());
1399
1400 template <class _Alloc>
1401 auto
1402 __has_select_on_container_copy_construction_test(const volatile _Alloc& __a)
1403     -> false_type;
1404
1405 template <class _Alloc>
1406 struct __has_select_on_container_copy_construction
1407     : integral_constant<bool,
1408         is_same<
1409             decltype(__has_select_on_container_copy_construction_test(declval<_Alloc&>())),
1410             true_type>::value>
1411 {
1412 };
1413
1414 #else  // _LIBCPP_CXX03_LANG
1415
1416 #ifndef _LIBCPP_HAS_NO_VARIADICS
1417
1418 template <class _Alloc, class _Pointer, class ..._Args>
1419 struct __has_construct
1420     : false_type
1421 {
1422 };
1423
1424 #else  // _LIBCPP_HAS_NO_VARIADICS
1425
1426 template <class _Alloc, class _Pointer, class _Args>
1427 struct __has_construct
1428     : false_type
1429 {
1430 };
1431
1432 #endif  // _LIBCPP_HAS_NO_VARIADICS
1433
1434 template <class _Alloc, class _Pointer>
1435 struct __has_destroy
1436     : false_type
1437 {
1438 };
1439
1440 template <class _Alloc>
1441 struct __has_max_size
1442     : true_type
1443 {
1444 };
1445
1446 template <class _Alloc>
1447 struct __has_select_on_container_copy_construction
1448     : false_type
1449 {
1450 };
1451
1452 #endif  // _LIBCPP_CXX03_LANG
1453
1454 template <class _Alloc, class _Ptr, bool = __has_difference_type<_Alloc>::value>
1455 struct __alloc_traits_difference_type
1456 {
1457     typedef typename pointer_traits<_Ptr>::difference_type type;
1458 };
1459
1460 template <class _Alloc, class _Ptr>
1461 struct __alloc_traits_difference_type<_Alloc, _Ptr, true>
1462 {
1463     typedef typename _Alloc::difference_type type;
1464 };
1465
1466 template <class _Alloc>
1467 struct _LIBCPP_TEMPLATE_VIS allocator_traits
1468 {
1469     typedef _Alloc                              allocator_type;
1470     typedef typename allocator_type::value_type value_type;
1471
1472     typedef typename __pointer_type<value_type, allocator_type>::type pointer;
1473     typedef typename __const_pointer<value_type, pointer, allocator_type>::type const_pointer;
1474     typedef typename __void_pointer<pointer, allocator_type>::type void_pointer;
1475     typedef typename __const_void_pointer<pointer, allocator_type>::type const_void_pointer;
1476
1477     typedef typename __alloc_traits_difference_type<allocator_type, pointer>::type difference_type;
1478     typedef typename __size_type<allocator_type, difference_type>::type size_type;
1479
1480     typedef typename __propagate_on_container_copy_assignment<allocator_type>::type
1481                      propagate_on_container_copy_assignment;
1482     typedef typename __propagate_on_container_move_assignment<allocator_type>::type
1483                      propagate_on_container_move_assignment;
1484     typedef typename __propagate_on_container_swap<allocator_type>::type
1485                      propagate_on_container_swap;
1486     typedef typename __is_always_equal<allocator_type>::type
1487                      is_always_equal;
1488
1489 #ifndef _LIBCPP_CXX03_LANG
1490     template <class _Tp> using rebind_alloc =
1491                   typename __allocator_traits_rebind<allocator_type, _Tp>::type;
1492     template <class _Tp> using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
1493 #else  // _LIBCPP_CXX03_LANG
1494     template <class _Tp> struct rebind_alloc
1495         {typedef typename __allocator_traits_rebind<allocator_type, _Tp>::type other;};
1496     template <class _Tp> struct rebind_traits
1497         {typedef allocator_traits<typename rebind_alloc<_Tp>::other> other;};
1498 #endif  // _LIBCPP_CXX03_LANG
1499
1500     _LIBCPP_INLINE_VISIBILITY
1501     static pointer allocate(allocator_type& __a, size_type __n)
1502         {return __a.allocate(__n);}
1503     _LIBCPP_INLINE_VISIBILITY
1504     static pointer allocate(allocator_type& __a, size_type __n, const_void_pointer __hint)
1505         {return __allocate(__a, __n, __hint,
1506             __has_allocate_hint<allocator_type, size_type, const_void_pointer>());}
1507
1508     _LIBCPP_INLINE_VISIBILITY
1509     static void deallocate(allocator_type& __a, pointer __p, size_type __n) _NOEXCEPT
1510         {__a.deallocate(__p, __n);}
1511
1512 #ifndef _LIBCPP_HAS_NO_VARIADICS
1513     template <class _Tp, class... _Args>
1514         _LIBCPP_INLINE_VISIBILITY
1515         static void construct(allocator_type& __a, _Tp* __p, _Args&&... __args)
1516             {__construct(__has_construct<allocator_type, _Tp*, _Args...>(),
1517                          __a, __p, _VSTD::forward<_Args>(__args)...);}
1518 #else  // _LIBCPP_HAS_NO_VARIADICS
1519     template <class _Tp>
1520         _LIBCPP_INLINE_VISIBILITY
1521         static void construct(allocator_type&, _Tp* __p)
1522             {
1523                 ::new ((void*)__p) _Tp();
1524             }
1525     template <class _Tp, class _A0>
1526         _LIBCPP_INLINE_VISIBILITY
1527         static void construct(allocator_type&, _Tp* __p, const _A0& __a0)
1528             {
1529                 ::new ((void*)__p) _Tp(__a0);
1530             }
1531     template <class _Tp, class _A0, class _A1>
1532         _LIBCPP_INLINE_VISIBILITY
1533         static void construct(allocator_type&, _Tp* __p, const _A0& __a0,
1534                               const _A1& __a1)
1535             {
1536                 ::new ((void*)__p) _Tp(__a0, __a1);
1537             }
1538     template <class _Tp, class _A0, class _A1, class _A2>
1539         _LIBCPP_INLINE_VISIBILITY
1540         static void construct(allocator_type&, _Tp* __p, const _A0& __a0,
1541                               const _A1& __a1, const _A2& __a2)
1542             {
1543                 ::new ((void*)__p) _Tp(__a0, __a1, __a2);
1544             }
1545 #endif  // _LIBCPP_HAS_NO_VARIADICS
1546
1547     template <class _Tp>
1548         _LIBCPP_INLINE_VISIBILITY
1549         static void destroy(allocator_type& __a, _Tp* __p)
1550             {__destroy(__has_destroy<allocator_type, _Tp*>(), __a, __p);}
1551
1552     _LIBCPP_INLINE_VISIBILITY
1553     static size_type max_size(const allocator_type& __a) _NOEXCEPT
1554         {return __max_size(__has_max_size<const allocator_type>(), __a);}
1555
1556     _LIBCPP_INLINE_VISIBILITY
1557     static allocator_type
1558         select_on_container_copy_construction(const allocator_type& __a)
1559             {return __select_on_container_copy_construction(
1560                 __has_select_on_container_copy_construction<const allocator_type>(),
1561                 __a);}
1562
1563     template <class _Ptr>
1564         _LIBCPP_INLINE_VISIBILITY
1565         static
1566         void
1567         __construct_forward(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __begin2)
1568         {
1569             for (; __begin1 != __end1; ++__begin1, ++__begin2)
1570                 construct(__a, _VSTD::__to_raw_pointer(__begin2), _VSTD::move_if_noexcept(*__begin1));
1571         }
1572
1573     template <class _Tp>
1574         _LIBCPP_INLINE_VISIBILITY
1575         static
1576         typename enable_if
1577         <
1578             (is_same<allocator_type, allocator<_Tp> >::value
1579                 || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
1580              is_trivially_move_constructible<_Tp>::value,
1581             void
1582         >::type
1583         __construct_forward(allocator_type&, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2)
1584         {
1585             ptrdiff_t _Np = __end1 - __begin1;
1586             if (_Np > 0)
1587             {
1588                 _VSTD::memcpy(__begin2, __begin1, _Np * sizeof(_Tp));
1589                 __begin2 += _Np;
1590             }
1591         }
1592
1593     template <class _Iter, class _Ptr>
1594         _LIBCPP_INLINE_VISIBILITY
1595         static
1596         void
1597         __construct_range_forward(allocator_type& __a, _Iter __begin1, _Iter __end1, _Ptr& __begin2)
1598         {
1599             for (; __begin1 != __end1; ++__begin1, (void) ++__begin2)
1600                 construct(__a, _VSTD::__to_raw_pointer(__begin2), *__begin1);
1601         }
1602
1603     template <class _Tp>
1604         _LIBCPP_INLINE_VISIBILITY
1605         static
1606         typename enable_if
1607         <
1608             (is_same<allocator_type, allocator<_Tp> >::value
1609                 || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
1610              is_trivially_move_constructible<_Tp>::value,
1611             void
1612         >::type
1613         __construct_range_forward(allocator_type&, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2)
1614         {
1615             typedef typename remove_const<_Tp>::type _Vp;
1616             ptrdiff_t _Np = __end1 - __begin1;
1617             if (_Np > 0)
1618             {
1619                 _VSTD::memcpy(const_cast<_Vp*>(__begin2), __begin1, _Np * sizeof(_Tp));
1620                 __begin2 += _Np;
1621             }
1622         }
1623
1624     template <class _Ptr>
1625         _LIBCPP_INLINE_VISIBILITY
1626         static
1627         void
1628         __construct_backward(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __end2)
1629         {
1630             while (__end1 != __begin1)
1631             {
1632                 construct(__a, _VSTD::__to_raw_pointer(__end2-1), _VSTD::move_if_noexcept(*--__end1));
1633                 --__end2;
1634             }
1635         }
1636
1637     template <class _Tp>
1638         _LIBCPP_INLINE_VISIBILITY
1639         static
1640         typename enable_if
1641         <
1642             (is_same<allocator_type, allocator<_Tp> >::value
1643                 || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
1644              is_trivially_move_constructible<_Tp>::value,
1645             void
1646         >::type
1647         __construct_backward(allocator_type&, _Tp* __begin1, _Tp* __end1, _Tp*& __end2)
1648         {
1649             ptrdiff_t _Np = __end1 - __begin1;
1650             __end2 -= _Np;
1651             if (_Np > 0)
1652                 _VSTD::memcpy(__end2, __begin1, _Np * sizeof(_Tp));
1653         }
1654
1655 private:
1656
1657     _LIBCPP_INLINE_VISIBILITY
1658     static pointer __allocate(allocator_type& __a, size_type __n,
1659         const_void_pointer __hint, true_type)
1660         {return __a.allocate(__n, __hint);}
1661     _LIBCPP_INLINE_VISIBILITY
1662     static pointer __allocate(allocator_type& __a, size_type __n,
1663         const_void_pointer, false_type)
1664         {return __a.allocate(__n);}
1665
1666 #ifndef _LIBCPP_HAS_NO_VARIADICS
1667     template <class _Tp, class... _Args>
1668         _LIBCPP_INLINE_VISIBILITY
1669         static void __construct(true_type, allocator_type& __a, _Tp* __p, _Args&&... __args)
1670             {__a.construct(__p, _VSTD::forward<_Args>(__args)...);}
1671     template <class _Tp, class... _Args>
1672         _LIBCPP_INLINE_VISIBILITY
1673         static void __construct(false_type, allocator_type&, _Tp* __p, _Args&&... __args)
1674             {
1675                 ::new ((void*)__p) _Tp(_VSTD::forward<_Args>(__args)...);
1676             }
1677 #endif  // _LIBCPP_HAS_NO_VARIADICS
1678
1679     template <class _Tp>
1680         _LIBCPP_INLINE_VISIBILITY
1681         static void __destroy(true_type, allocator_type& __a, _Tp* __p)
1682             {__a.destroy(__p);}
1683     template <class _Tp>
1684         _LIBCPP_INLINE_VISIBILITY
1685         static void __destroy(false_type, allocator_type&, _Tp* __p)
1686             {
1687                 __p->~_Tp();
1688             }
1689
1690     _LIBCPP_INLINE_VISIBILITY
1691     static size_type __max_size(true_type, const allocator_type& __a)
1692             {return __a.max_size();}
1693     _LIBCPP_INLINE_VISIBILITY
1694     static size_type __max_size(false_type, const allocator_type&)
1695             {return numeric_limits<size_type>::max() / sizeof(value_type);}
1696
1697     _LIBCPP_INLINE_VISIBILITY
1698     static allocator_type
1699         __select_on_container_copy_construction(true_type, const allocator_type& __a)
1700             {return __a.select_on_container_copy_construction();}
1701     _LIBCPP_INLINE_VISIBILITY
1702     static allocator_type
1703         __select_on_container_copy_construction(false_type, const allocator_type& __a)
1704             {return __a;}
1705 };
1706
1707 template <class _Traits, class _Tp>
1708 struct __rebind_alloc_helper
1709 {
1710 #ifndef _LIBCPP_CXX03_LANG
1711     typedef typename _Traits::template rebind_alloc<_Tp>        type;
1712 #else
1713     typedef typename _Traits::template rebind_alloc<_Tp>::other type;
1714 #endif
1715 };
1716
1717 // allocator
1718
1719 template <class _Tp>
1720 class _LIBCPP_TEMPLATE_VIS allocator
1721 {
1722 public:
1723     typedef size_t            size_type;
1724     typedef ptrdiff_t         difference_type;
1725     typedef _Tp*              pointer;
1726     typedef const _Tp*        const_pointer;
1727     typedef _Tp&              reference;
1728     typedef const _Tp&        const_reference;
1729     typedef _Tp               value_type;
1730
1731     typedef true_type propagate_on_container_move_assignment;
1732     typedef true_type is_always_equal;
1733
1734     template <class _Up> struct rebind {typedef allocator<_Up> other;};
1735
1736     _LIBCPP_INLINE_VISIBILITY allocator() _NOEXCEPT {}
1737     template <class _Up> _LIBCPP_INLINE_VISIBILITY allocator(const allocator<_Up>&) _NOEXCEPT {}
1738     _LIBCPP_INLINE_VISIBILITY pointer address(reference __x) const _NOEXCEPT
1739         {return _VSTD::addressof(__x);}
1740     _LIBCPP_INLINE_VISIBILITY const_pointer address(const_reference __x) const _NOEXCEPT
1741         {return _VSTD::addressof(__x);}
1742     _LIBCPP_INLINE_VISIBILITY pointer allocate(size_type __n, allocator<void>::const_pointer = 0)
1743         {
1744         if (__n > max_size())
1745             __throw_length_error("allocator<T>::allocate(size_t n)"
1746                                  " 'n' exceeds maximum supported size");
1747         return static_cast<pointer>(_VSTD::__allocate(__n * sizeof(_Tp)));
1748         }
1749     _LIBCPP_INLINE_VISIBILITY void deallocate(pointer __p, size_type) _NOEXCEPT
1750         {_VSTD::__libcpp_deallocate((void*)__p);}
1751     _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT
1752         {return size_type(~0) / sizeof(_Tp);}
1753 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1754     template <class _Up, class... _Args>
1755         _LIBCPP_INLINE_VISIBILITY
1756         void
1757         construct(_Up* __p, _Args&&... __args)
1758         {
1759             ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
1760         }
1761 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1762         _LIBCPP_INLINE_VISIBILITY
1763         void
1764         construct(pointer __p)
1765         {
1766             ::new((void*)__p) _Tp();
1767         }
1768 # if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1769
1770     template <class _A0>
1771         _LIBCPP_INLINE_VISIBILITY
1772         void
1773         construct(pointer __p, _A0& __a0)
1774         {
1775             ::new((void*)__p) _Tp(__a0);
1776         }
1777     template <class _A0>
1778         _LIBCPP_INLINE_VISIBILITY
1779         void
1780         construct(pointer __p, const _A0& __a0)
1781         {
1782             ::new((void*)__p) _Tp(__a0);
1783         }
1784 # endif  // defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1785     template <class _A0, class _A1>
1786         _LIBCPP_INLINE_VISIBILITY
1787         void
1788         construct(pointer __p, _A0& __a0, _A1& __a1)
1789         {
1790             ::new((void*)__p) _Tp(__a0, __a1);
1791         }
1792     template <class _A0, class _A1>
1793         _LIBCPP_INLINE_VISIBILITY
1794         void
1795         construct(pointer __p, const _A0& __a0, _A1& __a1)
1796         {
1797             ::new((void*)__p) _Tp(__a0, __a1);
1798         }
1799     template <class _A0, class _A1>
1800         _LIBCPP_INLINE_VISIBILITY
1801         void
1802         construct(pointer __p, _A0& __a0, const _A1& __a1)
1803         {
1804             ::new((void*)__p) _Tp(__a0, __a1);
1805         }
1806     template <class _A0, class _A1>
1807         _LIBCPP_INLINE_VISIBILITY
1808         void
1809         construct(pointer __p, const _A0& __a0, const _A1& __a1)
1810         {
1811             ::new((void*)__p) _Tp(__a0, __a1);
1812         }
1813 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1814     _LIBCPP_INLINE_VISIBILITY void destroy(pointer __p) {__p->~_Tp();}
1815 };
1816
1817 template <class _Tp>
1818 class _LIBCPP_TEMPLATE_VIS allocator<const _Tp>
1819 {
1820 public:
1821     typedef size_t            size_type;
1822     typedef ptrdiff_t         difference_type;
1823     typedef const _Tp*        pointer;
1824     typedef const _Tp*        const_pointer;
1825     typedef const _Tp&        reference;
1826     typedef const _Tp&        const_reference;
1827     typedef const _Tp         value_type;
1828
1829     typedef true_type propagate_on_container_move_assignment;
1830     typedef true_type is_always_equal;
1831
1832     template <class _Up> struct rebind {typedef allocator<_Up> other;};
1833
1834     _LIBCPP_INLINE_VISIBILITY allocator() _NOEXCEPT {}
1835     template <class _Up> _LIBCPP_INLINE_VISIBILITY allocator(const allocator<_Up>&) _NOEXCEPT {}
1836     _LIBCPP_INLINE_VISIBILITY const_pointer address(const_reference __x) const _NOEXCEPT
1837         {return _VSTD::addressof(__x);}
1838     _LIBCPP_INLINE_VISIBILITY pointer allocate(size_type __n, allocator<void>::const_pointer = 0)
1839     {
1840         if (__n > max_size())
1841             __throw_length_error("allocator<const T>::allocate(size_t n)"
1842                                  " 'n' exceeds maximum supported size");
1843         return static_cast<pointer>(_VSTD::__allocate(__n * sizeof(_Tp)));
1844     }
1845     _LIBCPP_INLINE_VISIBILITY void deallocate(pointer __p, size_type) _NOEXCEPT
1846         {_VSTD::__libcpp_deallocate((void*) const_cast<_Tp *>(__p));}
1847     _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT
1848         {return size_type(~0) / sizeof(_Tp);}
1849 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1850     template <class _Up, class... _Args>
1851         _LIBCPP_INLINE_VISIBILITY
1852         void
1853         construct(_Up* __p, _Args&&... __args)
1854         {
1855             ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
1856         }
1857 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1858         _LIBCPP_INLINE_VISIBILITY
1859         void
1860         construct(pointer __p)
1861         {
1862             ::new((void*) const_cast<_Tp *>(__p)) _Tp();
1863         }
1864 # if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1865
1866     template <class _A0>
1867         _LIBCPP_INLINE_VISIBILITY
1868         void
1869         construct(pointer __p, _A0& __a0)
1870         {
1871             ::new((void*) const_cast<_Tp *>(__p)) _Tp(__a0);
1872         }
1873     template <class _A0>
1874         _LIBCPP_INLINE_VISIBILITY
1875         void
1876         construct(pointer __p, const _A0& __a0)
1877         {
1878             ::new((void*) const_cast<_Tp *>(__p)) _Tp(__a0);
1879         }
1880 # endif  // defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1881     template <class _A0, class _A1>
1882         _LIBCPP_INLINE_VISIBILITY
1883         void
1884         construct(pointer __p, _A0& __a0, _A1& __a1)
1885         {
1886             ::new((void*) const_cast<_Tp *>(__p)) _Tp(__a0, __a1);
1887         }
1888     template <class _A0, class _A1>
1889         _LIBCPP_INLINE_VISIBILITY
1890         void
1891         construct(pointer __p, const _A0& __a0, _A1& __a1)
1892         {
1893             ::new((void*) const_cast<_Tp *>(__p)) _Tp(__a0, __a1);
1894         }
1895     template <class _A0, class _A1>
1896         _LIBCPP_INLINE_VISIBILITY
1897         void
1898         construct(pointer __p, _A0& __a0, const _A1& __a1)
1899         {
1900             ::new((void*) const_cast<_Tp *>(__p)) _Tp(__a0, __a1);
1901         }
1902     template <class _A0, class _A1>
1903         _LIBCPP_INLINE_VISIBILITY
1904         void
1905         construct(pointer __p, const _A0& __a0, const _A1& __a1)
1906         {
1907             ::new((void*) const_cast<_Tp *>(__p)) _Tp(__a0, __a1);
1908         }
1909 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1910     _LIBCPP_INLINE_VISIBILITY void destroy(pointer __p) {__p->~_Tp();}
1911 };
1912
1913 template <class _Tp, class _Up>
1914 inline _LIBCPP_INLINE_VISIBILITY
1915 bool operator==(const allocator<_Tp>&, const allocator<_Up>&) _NOEXCEPT {return true;}
1916
1917 template <class _Tp, class _Up>
1918 inline _LIBCPP_INLINE_VISIBILITY
1919 bool operator!=(const allocator<_Tp>&, const allocator<_Up>&) _NOEXCEPT {return false;}
1920
1921 template <class _OutputIterator, class _Tp>
1922 class _LIBCPP_TEMPLATE_VIS raw_storage_iterator
1923     : public iterator<output_iterator_tag,
1924                       _Tp,                                         // purposefully not C++03
1925                       ptrdiff_t,                                   // purposefully not C++03
1926                       _Tp*,                                        // purposefully not C++03
1927                       raw_storage_iterator<_OutputIterator, _Tp>&> // purposefully not C++03
1928 {
1929 private:
1930     _OutputIterator __x_;
1931 public:
1932     _LIBCPP_INLINE_VISIBILITY explicit raw_storage_iterator(_OutputIterator __x) : __x_(__x) {}
1933     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator*() {return *this;}
1934     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator=(const _Tp& __element)
1935         {::new(&*__x_) _Tp(__element); return *this;}
1936 #if _LIBCPP_STD_VER >= 14
1937     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator=(_Tp&& __element)
1938         {::new(&*__x_) _Tp(_VSTD::move(__element)); return *this;}
1939 #endif
1940     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator++() {++__x_; return *this;}
1941     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator  operator++(int)
1942         {raw_storage_iterator __t(*this); ++__x_; return __t;}
1943 #if _LIBCPP_STD_VER >= 14
1944     _LIBCPP_INLINE_VISIBILITY _OutputIterator base() const { return __x_; }
1945 #endif
1946 };
1947
1948 template <class _Tp>
1949 pair<_Tp*, ptrdiff_t>
1950 get_temporary_buffer(ptrdiff_t __n) _NOEXCEPT
1951 {
1952     pair<_Tp*, ptrdiff_t> __r(0, 0);
1953     const ptrdiff_t __m = (~ptrdiff_t(0) ^
1954                            ptrdiff_t(ptrdiff_t(1) << (sizeof(ptrdiff_t) * __CHAR_BIT__ - 1)))
1955                            / sizeof(_Tp);
1956     if (__n > __m)
1957         __n = __m;
1958     while (__n > 0)
1959     {
1960         __r.first = static_cast<_Tp*>(::operator new(__n * sizeof(_Tp), nothrow));
1961         if (__r.first)
1962         {
1963             __r.second = __n;
1964             break;
1965         }
1966         __n /= 2;
1967     }
1968     return __r;
1969 }
1970
1971 template <class _Tp>
1972 inline _LIBCPP_INLINE_VISIBILITY
1973 void return_temporary_buffer(_Tp* __p) _NOEXCEPT {::operator delete(__p);}
1974
1975 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR)
1976 template <class _Tp>
1977 struct auto_ptr_ref
1978 {
1979     _Tp* __ptr_;
1980 };
1981
1982 template<class _Tp>
1983 class _LIBCPP_TEMPLATE_VIS auto_ptr
1984 {
1985 private:
1986     _Tp* __ptr_;
1987 public:
1988     typedef _Tp element_type;
1989
1990     _LIBCPP_INLINE_VISIBILITY explicit auto_ptr(_Tp* __p = 0) throw() : __ptr_(__p) {}
1991     _LIBCPP_INLINE_VISIBILITY auto_ptr(auto_ptr& __p) throw() : __ptr_(__p.release()) {}
1992     template<class _Up> _LIBCPP_INLINE_VISIBILITY auto_ptr(auto_ptr<_Up>& __p) throw()
1993         : __ptr_(__p.release()) {}
1994     _LIBCPP_INLINE_VISIBILITY auto_ptr& operator=(auto_ptr& __p) throw()
1995         {reset(__p.release()); return *this;}
1996     template<class _Up> _LIBCPP_INLINE_VISIBILITY auto_ptr& operator=(auto_ptr<_Up>& __p) throw()
1997         {reset(__p.release()); return *this;}
1998     _LIBCPP_INLINE_VISIBILITY auto_ptr& operator=(auto_ptr_ref<_Tp> __p) throw()
1999         {reset(__p.__ptr_); return *this;}
2000     _LIBCPP_INLINE_VISIBILITY ~auto_ptr() throw() {delete __ptr_;}
2001
2002     _LIBCPP_INLINE_VISIBILITY _Tp& operator*() const throw()
2003         {return *__ptr_;}
2004     _LIBCPP_INLINE_VISIBILITY _Tp* operator->() const throw() {return __ptr_;}
2005     _LIBCPP_INLINE_VISIBILITY _Tp* get() const throw() {return __ptr_;}
2006     _LIBCPP_INLINE_VISIBILITY _Tp* release() throw()
2007     {
2008         _Tp* __t = __ptr_;
2009         __ptr_ = 0;
2010         return __t;
2011     }
2012     _LIBCPP_INLINE_VISIBILITY void reset(_Tp* __p = 0) throw()
2013     {
2014         if (__ptr_ != __p)
2015             delete __ptr_;
2016         __ptr_ = __p;
2017     }
2018
2019     _LIBCPP_INLINE_VISIBILITY auto_ptr(auto_ptr_ref<_Tp> __p) throw() : __ptr_(__p.__ptr_) {}
2020     template<class _Up> _LIBCPP_INLINE_VISIBILITY operator auto_ptr_ref<_Up>() throw()
2021         {auto_ptr_ref<_Up> __t; __t.__ptr_ = release(); return __t;}
2022     template<class _Up> _LIBCPP_INLINE_VISIBILITY operator auto_ptr<_Up>() throw()
2023         {return auto_ptr<_Up>(release());}
2024 };
2025
2026 template <>
2027 class _LIBCPP_TEMPLATE_VIS auto_ptr<void>
2028 {
2029 public:
2030     typedef void element_type;
2031 };
2032 #endif
2033
2034 template <class _Tp, int _Idx,
2035           bool _CanBeEmptyBase =
2036               is_empty<_Tp>::value && !__libcpp_is_final<_Tp>::value>
2037 struct __compressed_pair_elem {
2038   typedef _Tp _ParamT;
2039   typedef _Tp& reference;
2040   typedef const _Tp& const_reference;
2041
2042 #ifndef _LIBCPP_CXX03_LANG
2043   constexpr __compressed_pair_elem() : __value_() {}
2044
2045   template <class _Up, class = typename enable_if<
2046       !is_same<__compressed_pair_elem, typename decay<_Up>::type>::value
2047   >::type>
2048   constexpr explicit
2049   __compressed_pair_elem(_Up&& __u)
2050       : __value_(_VSTD::forward<_Up>(__u)){};
2051
2052   template <class... _Args, size_t... _Indexes>
2053   _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
2054   __compressed_pair_elem(piecewise_construct_t, tuple<_Args...> __args,
2055                          __tuple_indices<_Indexes...>)
2056       : __value_(_VSTD::forward<_Args>(_VSTD::get<_Indexes>(__args))...) {}
2057 #else
2058   __compressed_pair_elem() : __value_() {}
2059   __compressed_pair_elem(_ParamT __p) : __value_(std::forward<_ParamT>(__p)) {}
2060 #endif
2061
2062   reference __get() _NOEXCEPT { return __value_; }
2063   const_reference __get() const _NOEXCEPT { return __value_; }
2064
2065 private:
2066   _Tp __value_;
2067 };
2068
2069 template <class _Tp, int _Idx>
2070 struct __compressed_pair_elem<_Tp, _Idx, true> : private _Tp {
2071   typedef _Tp _ParamT;
2072   typedef _Tp& reference;
2073   typedef const _Tp& const_reference;
2074   typedef _Tp __value_type;
2075
2076 #ifndef _LIBCPP_CXX03_LANG
2077   constexpr __compressed_pair_elem() = default;
2078
2079   template <class _Up, class = typename enable_if<
2080         !is_same<__compressed_pair_elem, typename decay<_Up>::type>::value
2081   >::type>
2082   constexpr explicit
2083   __compressed_pair_elem(_Up&& __u)
2084       : __value_type(_VSTD::forward<_Up>(__u)){};
2085
2086   template <class... _Args, size_t... _Indexes>
2087   _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
2088   __compressed_pair_elem(piecewise_construct_t, tuple<_Args...> __args,
2089                          __tuple_indices<_Indexes...>)
2090       : __value_type(_VSTD::forward<_Args>(_VSTD::get<_Indexes>(__args))...) {}
2091 #else
2092   __compressed_pair_elem() : __value_type() {}
2093   __compressed_pair_elem(_ParamT __p)
2094       : __value_type(std::forward<_ParamT>(__p)) {}
2095 #endif
2096
2097   reference __get() _NOEXCEPT { return *this; }
2098   const_reference __get() const _NOEXCEPT { return *this; }
2099 };
2100
2101 // Tag used to construct the second element of the compressed pair.
2102 struct __second_tag {};
2103
2104 template <class _T1, class _T2>
2105 class __compressed_pair : private __compressed_pair_elem<_T1, 0>,
2106                           private __compressed_pair_elem<_T2, 1> {
2107   typedef __compressed_pair_elem<_T1, 0> _Base1;
2108   typedef __compressed_pair_elem<_T2, 1> _Base2;
2109
2110   // NOTE: This static assert should never fire because __compressed_pair
2111   // is *almost never* used in a scenario where it's possible for T1 == T2.
2112   // (The exception is std::function where it is possible that the function
2113   //  object and the allocator have the same type).
2114   static_assert((!is_same<_T1, _T2>::value),
2115     "__compressed_pair cannot be instantated when T1 and T2 are the same type; "
2116     "The current implementation is NOT ABI-compatible with the previous "
2117     "implementation for this configuration");
2118
2119 public:
2120 #ifndef _LIBCPP_CXX03_LANG
2121   template <bool _Dummy = true,
2122       class = typename enable_if<
2123           __dependent_type<is_default_constructible<_T1>, _Dummy>::value &&
2124           __dependent_type<is_default_constructible<_T2>, _Dummy>::value
2125       >::type
2126   >
2127   _LIBCPP_INLINE_VISIBILITY
2128   constexpr __compressed_pair() {}
2129
2130   template <class _Tp, typename enable_if<!is_same<typename decay<_Tp>::type,
2131                                                    __compressed_pair>::value,
2132                                           bool>::type = true>
2133   _LIBCPP_INLINE_VISIBILITY constexpr explicit
2134   __compressed_pair(_Tp&& __t)
2135       : _Base1(std::forward<_Tp>(__t)), _Base2() {}
2136
2137   template <class _Tp>
2138   _LIBCPP_INLINE_VISIBILITY constexpr
2139   __compressed_pair(__second_tag, _Tp&& __t)
2140       : _Base1(), _Base2(std::forward<_Tp>(__t)) {}
2141
2142   template <class _U1, class _U2>
2143   _LIBCPP_INLINE_VISIBILITY constexpr
2144   __compressed_pair(_U1&& __t1, _U2&& __t2)
2145       : _Base1(std::forward<_U1>(__t1)), _Base2(std::forward<_U2>(__t2)) {}
2146
2147   template <class... _Args1, class... _Args2>
2148   _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
2149   __compressed_pair(piecewise_construct_t __pc, tuple<_Args1...> __first_args,
2150                     tuple<_Args2...> __second_args)
2151       : _Base1(__pc, _VSTD::move(__first_args),
2152                typename __make_tuple_indices<sizeof...(_Args1)>::type()),
2153         _Base2(__pc, _VSTD::move(__second_args),
2154                typename __make_tuple_indices<sizeof...(_Args2)>::type()) {}
2155
2156 #else
2157   _LIBCPP_INLINE_VISIBILITY
2158   __compressed_pair() {}
2159
2160   _LIBCPP_INLINE_VISIBILITY explicit
2161   __compressed_pair(_T1 __t1) : _Base1(_VSTD::forward<_T1>(__t1)) {}
2162
2163   _LIBCPP_INLINE_VISIBILITY
2164   __compressed_pair(__second_tag, _T2 __t2)
2165       : _Base1(), _Base2(_VSTD::forward<_T2>(__t2)) {}
2166
2167   _LIBCPP_INLINE_VISIBILITY
2168   __compressed_pair(_T1 __t1, _T2 __t2)
2169       : _Base1(_VSTD::forward<_T1>(__t1)), _Base2(_VSTD::forward<_T2>(__t2)) {}
2170 #endif
2171
2172   _LIBCPP_INLINE_VISIBILITY
2173   typename _Base1::reference first() _NOEXCEPT {
2174     return static_cast<_Base1&>(*this).__get();
2175   }
2176
2177   _LIBCPP_INLINE_VISIBILITY
2178   typename _Base1::const_reference first() const _NOEXCEPT {
2179     return static_cast<_Base1 const&>(*this).__get();
2180   }
2181
2182   _LIBCPP_INLINE_VISIBILITY
2183   typename _Base2::reference second() _NOEXCEPT {
2184     return static_cast<_Base2&>(*this).__get();
2185   }
2186
2187   _LIBCPP_INLINE_VISIBILITY
2188   typename _Base2::const_reference second() const _NOEXCEPT {
2189     return static_cast<_Base2 const&>(*this).__get();
2190   }
2191
2192   _LIBCPP_INLINE_VISIBILITY
2193   void swap(__compressed_pair& __x)
2194     _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2195                __is_nothrow_swappable<_T2>::value)
2196   {
2197     using std::swap;
2198     swap(first(), __x.first());
2199     swap(second(), __x.second());
2200   }
2201 };
2202
2203 template <class _T1, class _T2>
2204 inline _LIBCPP_INLINE_VISIBILITY
2205 void swap(__compressed_pair<_T1, _T2>& __x, __compressed_pair<_T1, _T2>& __y)
2206     _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2207                __is_nothrow_swappable<_T2>::value) {
2208   __x.swap(__y);
2209 }
2210
2211 // default_delete
2212
2213 template <class _Tp>
2214 struct _LIBCPP_TEMPLATE_VIS default_delete {
2215     static_assert(!is_function<_Tp>::value,
2216                   "default_delete cannot be instantiated for function types");
2217 #ifndef _LIBCPP_CXX03_LANG
2218   _LIBCPP_INLINE_VISIBILITY constexpr default_delete() noexcept = default;
2219 #else
2220   _LIBCPP_INLINE_VISIBILITY default_delete() {}
2221 #endif
2222   template <class _Up>
2223   _LIBCPP_INLINE_VISIBILITY
2224   default_delete(const default_delete<_Up>&,
2225                  typename enable_if<is_convertible<_Up*, _Tp*>::value>::type* =
2226                      0) _NOEXCEPT {}
2227
2228   _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __ptr) const _NOEXCEPT {
2229     static_assert(sizeof(_Tp) > 0,
2230                   "default_delete can not delete incomplete type");
2231     static_assert(!is_void<_Tp>::value,
2232                   "default_delete can not delete incomplete type");
2233     delete __ptr;
2234   }
2235 };
2236
2237 template <class _Tp>
2238 struct _LIBCPP_TEMPLATE_VIS default_delete<_Tp[]> {
2239 private:
2240   template <class _Up>
2241   struct _EnableIfConvertible
2242       : enable_if<is_convertible<_Up(*)[], _Tp(*)[]>::value> {};
2243
2244 public:
2245 #ifndef _LIBCPP_CXX03_LANG
2246   _LIBCPP_INLINE_VISIBILITY constexpr default_delete() noexcept = default;
2247 #else
2248   _LIBCPP_INLINE_VISIBILITY default_delete() {}
2249 #endif
2250
2251   template <class _Up>
2252   _LIBCPP_INLINE_VISIBILITY
2253   default_delete(const default_delete<_Up[]>&,
2254                  typename _EnableIfConvertible<_Up>::type* = 0) _NOEXCEPT {}
2255
2256   template <class _Up>
2257   _LIBCPP_INLINE_VISIBILITY
2258   typename _EnableIfConvertible<_Up>::type
2259   operator()(_Up* __ptr) const _NOEXCEPT {
2260     static_assert(sizeof(_Tp) > 0,
2261                   "default_delete can not delete incomplete type");
2262     static_assert(!is_void<_Tp>::value,
2263                   "default_delete can not delete void type");
2264     delete[] __ptr;
2265   }
2266 };
2267
2268
2269
2270 #ifndef _LIBCPP_CXX03_LANG
2271 template <class _Deleter>
2272 struct __unique_ptr_deleter_sfinae {
2273   static_assert(!is_reference<_Deleter>::value, "incorrect specialization");
2274   typedef const _Deleter& __lval_ref_type;
2275   typedef _Deleter&& __good_rval_ref_type;
2276   typedef true_type __enable_rval_overload;
2277 };
2278
2279 template <class _Deleter>
2280 struct __unique_ptr_deleter_sfinae<_Deleter const&> {
2281   typedef const _Deleter& __lval_ref_type;
2282   typedef const _Deleter&& __bad_rval_ref_type;
2283   typedef false_type __enable_rval_overload;
2284 };
2285
2286 template <class _Deleter>
2287 struct __unique_ptr_deleter_sfinae<_Deleter&> {
2288   typedef _Deleter& __lval_ref_type;
2289   typedef _Deleter&& __bad_rval_ref_type;
2290   typedef false_type __enable_rval_overload;
2291 };
2292 #endif // !defined(_LIBCPP_CXX03_LANG)
2293
2294 template <class _Tp, class _Dp = default_delete<_Tp> >
2295 class _LIBCPP_TEMPLATE_VIS unique_ptr {
2296 public:
2297   typedef _Tp element_type;
2298   typedef _Dp deleter_type;
2299   typedef typename __pointer_type<_Tp, deleter_type>::type pointer;
2300
2301   static_assert(!is_rvalue_reference<deleter_type>::value,
2302                 "the specified deleter type cannot be an rvalue reference");
2303
2304 private:
2305   __compressed_pair<pointer, deleter_type> __ptr_;
2306
2307   struct __nat { int __for_bool_; };
2308
2309 #ifndef _LIBCPP_CXX03_LANG
2310   typedef __unique_ptr_deleter_sfinae<_Dp> _DeleterSFINAE;
2311
2312   template <bool _Dummy>
2313   using _LValRefType =
2314       typename __dependent_type<_DeleterSFINAE, _Dummy>::__lval_ref_type;
2315
2316   template <bool _Dummy>
2317   using _GoodRValRefType =
2318       typename __dependent_type<_DeleterSFINAE, _Dummy>::__good_rval_ref_type;
2319
2320   template <bool _Dummy>
2321   using _BadRValRefType =
2322       typename __dependent_type<_DeleterSFINAE, _Dummy>::__bad_rval_ref_type;
2323
2324   template <bool _Dummy, class _Deleter = typename __dependent_type<
2325                              __identity<deleter_type>, _Dummy>::type>
2326   using _EnableIfDeleterDefaultConstructible =
2327       typename enable_if<is_default_constructible<_Deleter>::value &&
2328                          !is_pointer<_Deleter>::value>::type;
2329
2330   template <class _ArgType>
2331   using _EnableIfDeleterConstructible =
2332       typename enable_if<is_constructible<deleter_type, _ArgType>::value>::type;
2333
2334   template <class _UPtr, class _Up>
2335   using _EnableIfMoveConvertible = typename enable_if<
2336       is_convertible<typename _UPtr::pointer, pointer>::value &&
2337       !is_array<_Up>::value
2338   >::type;
2339
2340   template <class _UDel>
2341   using _EnableIfDeleterConvertible = typename enable_if<
2342       (is_reference<_Dp>::value && is_same<_Dp, _UDel>::value) ||
2343       (!is_reference<_Dp>::value && is_convertible<_UDel, _Dp>::value)
2344     >::type;
2345
2346   template <class _UDel>
2347   using _EnableIfDeleterAssignable = typename enable_if<
2348       is_assignable<_Dp&, _UDel&&>::value
2349     >::type;
2350
2351 public:
2352   template <bool _Dummy = true,
2353             class = _EnableIfDeleterDefaultConstructible<_Dummy>>
2354   _LIBCPP_INLINE_VISIBILITY
2355   constexpr unique_ptr() noexcept : __ptr_(pointer()) {}
2356
2357   template <bool _Dummy = true,
2358             class = _EnableIfDeleterDefaultConstructible<_Dummy>>
2359   _LIBCPP_INLINE_VISIBILITY
2360   constexpr unique_ptr(nullptr_t) noexcept : __ptr_(pointer()) {}
2361
2362   template <bool _Dummy = true,
2363             class = _EnableIfDeleterDefaultConstructible<_Dummy>>
2364   _LIBCPP_INLINE_VISIBILITY
2365   explicit unique_ptr(pointer __p) noexcept : __ptr_(__p) {}
2366
2367   template <bool _Dummy = true,
2368             class = _EnableIfDeleterConstructible<_LValRefType<_Dummy>>>
2369   _LIBCPP_INLINE_VISIBILITY
2370   unique_ptr(pointer __p, _LValRefType<_Dummy> __d) noexcept
2371       : __ptr_(__p, __d) {}
2372
2373   template <bool _Dummy = true,
2374             class = _EnableIfDeleterConstructible<_GoodRValRefType<_Dummy>>>
2375   _LIBCPP_INLINE_VISIBILITY
2376   unique_ptr(pointer __p, _GoodRValRefType<_Dummy> __d) noexcept
2377       : __ptr_(__p, _VSTD::move(__d)) {
2378     static_assert(!is_reference<deleter_type>::value,
2379                   "rvalue deleter bound to reference");
2380   }
2381
2382   template <bool _Dummy = true,
2383             class = _EnableIfDeleterConstructible<_BadRValRefType<_Dummy>>>
2384   _LIBCPP_INLINE_VISIBILITY
2385   unique_ptr(pointer __p, _BadRValRefType<_Dummy> __d) = delete;
2386
2387   _LIBCPP_INLINE_VISIBILITY
2388   unique_ptr(unique_ptr&& __u) noexcept
2389       : __ptr_(__u.release(), _VSTD::forward<deleter_type>(__u.get_deleter())) {
2390   }
2391
2392   template <class _Up, class _Ep,
2393       class = _EnableIfMoveConvertible<unique_ptr<_Up, _Ep>, _Up>,
2394       class = _EnableIfDeleterConvertible<_Ep>
2395   >
2396   _LIBCPP_INLINE_VISIBILITY
2397   unique_ptr(unique_ptr<_Up, _Ep>&& __u) _NOEXCEPT
2398       : __ptr_(__u.release(), _VSTD::forward<_Ep>(__u.get_deleter())) {}
2399
2400 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR)
2401   template <class _Up>
2402   _LIBCPP_INLINE_VISIBILITY
2403   unique_ptr(auto_ptr<_Up>&& __p,
2404              typename enable_if<is_convertible<_Up*, _Tp*>::value &&
2405                                     is_same<_Dp, default_delete<_Tp>>::value,
2406                                 __nat>::type = __nat()) _NOEXCEPT
2407       : __ptr_(__p.release()) {}
2408 #endif
2409
2410   _LIBCPP_INLINE_VISIBILITY
2411   unique_ptr& operator=(unique_ptr&& __u) _NOEXCEPT {
2412     reset(__u.release());
2413     __ptr_.second() = _VSTD::forward<deleter_type>(__u.get_deleter());
2414     return *this;
2415   }
2416
2417   template <class _Up, class _Ep,
2418       class = _EnableIfMoveConvertible<unique_ptr<_Up, _Ep>, _Up>,
2419       class = _EnableIfDeleterAssignable<_Ep>
2420   >
2421   _LIBCPP_INLINE_VISIBILITY
2422   unique_ptr& operator=(unique_ptr<_Up, _Ep>&& __u) _NOEXCEPT {
2423     reset(__u.release());
2424     __ptr_.second() = _VSTD::forward<_Ep>(__u.get_deleter());
2425     return *this;
2426   }
2427
2428 #else  // _LIBCPP_CXX03_LANG
2429 private:
2430   unique_ptr(unique_ptr&);
2431   template <class _Up, class _Ep> unique_ptr(unique_ptr<_Up, _Ep>&);
2432
2433   unique_ptr& operator=(unique_ptr&);
2434   template <class _Up, class _Ep> unique_ptr& operator=(unique_ptr<_Up, _Ep>&);
2435
2436 public:
2437   _LIBCPP_INLINE_VISIBILITY
2438   unique_ptr() : __ptr_(pointer())
2439   {
2440     static_assert(!is_pointer<deleter_type>::value,
2441                   "unique_ptr constructed with null function pointer deleter");
2442     static_assert(is_default_constructible<deleter_type>::value,
2443                   "unique_ptr::deleter_type is not default constructible");
2444   }
2445   _LIBCPP_INLINE_VISIBILITY
2446   unique_ptr(nullptr_t) : __ptr_(pointer())
2447   {
2448     static_assert(!is_pointer<deleter_type>::value,
2449                   "unique_ptr constructed with null function pointer deleter");
2450   }
2451   _LIBCPP_INLINE_VISIBILITY
2452   explicit unique_ptr(pointer __p)
2453       : __ptr_(_VSTD::move(__p)) {
2454     static_assert(!is_pointer<deleter_type>::value,
2455                   "unique_ptr constructed with null function pointer deleter");
2456   }
2457
2458   _LIBCPP_INLINE_VISIBILITY
2459   operator __rv<unique_ptr>() {
2460     return __rv<unique_ptr>(*this);
2461   }
2462
2463   _LIBCPP_INLINE_VISIBILITY
2464   unique_ptr(__rv<unique_ptr> __u)
2465       : __ptr_(__u->release(),
2466                _VSTD::forward<deleter_type>(__u->get_deleter())) {}
2467
2468   template <class _Up, class _Ep>
2469   _LIBCPP_INLINE_VISIBILITY
2470   typename enable_if<
2471       !is_array<_Up>::value &&
2472           is_convertible<typename unique_ptr<_Up, _Ep>::pointer,
2473                          pointer>::value &&
2474           is_assignable<deleter_type&, _Ep&>::value,
2475       unique_ptr&>::type
2476   operator=(unique_ptr<_Up, _Ep> __u) {
2477     reset(__u.release());
2478     __ptr_.second() = _VSTD::forward<_Ep>(__u.get_deleter());
2479     return *this;
2480   }
2481
2482   _LIBCPP_INLINE_VISIBILITY
2483   unique_ptr(pointer __p, deleter_type __d)
2484       : __ptr_(_VSTD::move(__p), _VSTD::move(__d)) {}
2485 #endif // _LIBCPP_CXX03_LANG
2486
2487 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR)
2488   template <class _Up>
2489   _LIBCPP_INLINE_VISIBILITY
2490       typename enable_if<is_convertible<_Up*, _Tp*>::value &&
2491                              is_same<_Dp, default_delete<_Tp> >::value,
2492                          unique_ptr&>::type
2493       operator=(auto_ptr<_Up> __p) {
2494     reset(__p.release());
2495     return *this;
2496   }
2497 #endif
2498
2499   _LIBCPP_INLINE_VISIBILITY
2500   ~unique_ptr() { reset(); }
2501
2502   _LIBCPP_INLINE_VISIBILITY
2503   unique_ptr& operator=(nullptr_t) _NOEXCEPT {
2504     reset();
2505     return *this;
2506   }
2507
2508   _LIBCPP_INLINE_VISIBILITY
2509   typename add_lvalue_reference<_Tp>::type
2510   operator*() const {
2511     return *__ptr_.first();
2512   }
2513   _LIBCPP_INLINE_VISIBILITY
2514   pointer operator->() const _NOEXCEPT {
2515     return __ptr_.first();
2516   }
2517   _LIBCPP_INLINE_VISIBILITY
2518   pointer get() const _NOEXCEPT {
2519     return __ptr_.first();
2520   }
2521   _LIBCPP_INLINE_VISIBILITY
2522   deleter_type& get_deleter() _NOEXCEPT {
2523     return __ptr_.second();
2524   }
2525   _LIBCPP_INLINE_VISIBILITY
2526   const deleter_type& get_deleter() const _NOEXCEPT {
2527     return __ptr_.second();
2528   }
2529   _LIBCPP_INLINE_VISIBILITY
2530   _LIBCPP_EXPLICIT operator bool() const _NOEXCEPT {
2531     return __ptr_.first() != nullptr;
2532   }
2533
2534   _LIBCPP_INLINE_VISIBILITY
2535   pointer release() _NOEXCEPT {
2536     pointer __t = __ptr_.first();
2537     __ptr_.first() = pointer();
2538     return __t;
2539   }
2540
2541   _LIBCPP_INLINE_VISIBILITY
2542   void reset(pointer __p = pointer()) _NOEXCEPT {
2543     pointer __tmp = __ptr_.first();
2544     __ptr_.first() = __p;
2545     if (__tmp)
2546       __ptr_.second()(__tmp);
2547   }
2548
2549   _LIBCPP_INLINE_VISIBILITY
2550   void swap(unique_ptr& __u) _NOEXCEPT {
2551     __ptr_.swap(__u.__ptr_);
2552   }
2553 };
2554
2555
2556 template <class _Tp, class _Dp>
2557 class _LIBCPP_TEMPLATE_VIS unique_ptr<_Tp[], _Dp> {
2558 public:
2559   typedef _Tp element_type;
2560   typedef _Dp deleter_type;
2561   typedef typename __pointer_type<_Tp, deleter_type>::type pointer;
2562
2563 private:
2564   __compressed_pair<pointer, deleter_type> __ptr_;
2565
2566   template <class _From>
2567   struct _CheckArrayPointerConversion : is_same<_From, pointer> {};
2568
2569   template <class _FromElem>
2570   struct _CheckArrayPointerConversion<_FromElem*>
2571       : integral_constant<bool,
2572           is_same<_FromElem*, pointer>::value ||
2573             (is_same<pointer, element_type*>::value &&
2574              is_convertible<_FromElem(*)[], element_type(*)[]>::value)
2575       >
2576   {};
2577
2578 #ifndef _LIBCPP_CXX03_LANG
2579   typedef __unique_ptr_deleter_sfinae<_Dp> _DeleterSFINAE;
2580
2581   template <bool _Dummy>
2582   using _LValRefType =
2583       typename __dependent_type<_DeleterSFINAE, _Dummy>::__lval_ref_type;
2584
2585   template <bool _Dummy>
2586   using _GoodRValRefType =
2587       typename __dependent_type<_DeleterSFINAE, _Dummy>::__good_rval_ref_type;
2588
2589   template <bool _Dummy>
2590   using _BadRValRefType =
2591       typename __dependent_type<_DeleterSFINAE, _Dummy>::__bad_rval_ref_type;
2592
2593   template <bool _Dummy, class _Deleter = typename __dependent_type<
2594                              __identity<deleter_type>, _Dummy>::type>
2595   using _EnableIfDeleterDefaultConstructible =
2596       typename enable_if<is_default_constructible<_Deleter>::value &&
2597                          !is_pointer<_Deleter>::value>::type;
2598
2599   template <class _ArgType>
2600   using _EnableIfDeleterConstructible =
2601       typename enable_if<is_constructible<deleter_type, _ArgType>::value>::type;
2602
2603   template <class _Pp>
2604   using _EnableIfPointerConvertible = typename enable_if<
2605       _CheckArrayPointerConversion<_Pp>::value
2606   >::type;
2607
2608   template <class _UPtr, class _Up,
2609         class _ElemT = typename _UPtr::element_type>
2610   using _EnableIfMoveConvertible = typename enable_if<
2611       is_array<_Up>::value &&
2612       is_same<pointer, element_type*>::value &&
2613       is_same<typename _UPtr::pointer, _ElemT*>::value &&
2614       is_convertible<_ElemT(*)[], element_type(*)[]>::value
2615     >::type;
2616
2617   template <class _UDel>
2618   using _EnableIfDeleterConvertible = typename enable_if<
2619       (is_reference<_Dp>::value && is_same<_Dp, _UDel>::value) ||
2620       (!is_reference<_Dp>::value && is_convertible<_UDel, _Dp>::value)
2621     >::type;
2622
2623   template <class _UDel>
2624   using _EnableIfDeleterAssignable = typename enable_if<
2625       is_assignable<_Dp&, _UDel&&>::value
2626     >::type;
2627
2628 public:
2629   template <bool _Dummy = true,
2630             class = _EnableIfDeleterDefaultConstructible<_Dummy>>
2631   _LIBCPP_INLINE_VISIBILITY
2632   constexpr unique_ptr() noexcept : __ptr_(pointer()) {}
2633
2634   template <bool _Dummy = true,
2635             class = _EnableIfDeleterDefaultConstructible<_Dummy>>
2636   _LIBCPP_INLINE_VISIBILITY
2637   constexpr unique_ptr(nullptr_t) noexcept : __ptr_(pointer()) {}
2638
2639   template <class _Pp, bool _Dummy = true,
2640             class = _EnableIfDeleterDefaultConstructible<_Dummy>,
2641             class = _EnableIfPointerConvertible<_Pp>>
2642   _LIBCPP_INLINE_VISIBILITY
2643   explicit unique_ptr(_Pp __p) noexcept
2644       : __ptr_(__p) {}
2645
2646   template <class _Pp, bool _Dummy = true,
2647             class = _EnableIfDeleterConstructible<_LValRefType<_Dummy>>,
2648             class = _EnableIfPointerConvertible<_Pp>>
2649   _LIBCPP_INLINE_VISIBILITY
2650   unique_ptr(_Pp __p, _LValRefType<_Dummy> __d) noexcept
2651       : __ptr_(__p, __d) {}
2652
2653   template <bool _Dummy = true,
2654             class = _EnableIfDeleterConstructible<_LValRefType<_Dummy>>>
2655   _LIBCPP_INLINE_VISIBILITY
2656   unique_ptr(nullptr_t, _LValRefType<_Dummy> __d) noexcept
2657       : __ptr_(nullptr, __d) {}
2658
2659   template <class _Pp, bool _Dummy = true,
2660             class = _EnableIfDeleterConstructible<_GoodRValRefType<_Dummy>>,
2661             class = _EnableIfPointerConvertible<_Pp>>
2662   _LIBCPP_INLINE_VISIBILITY
2663   unique_ptr(_Pp __p, _GoodRValRefType<_Dummy> __d) noexcept
2664       : __ptr_(__p, _VSTD::move(__d)) {
2665     static_assert(!is_reference<deleter_type>::value,
2666                   "rvalue deleter bound to reference");
2667   }
2668
2669   template <bool _Dummy = true,
2670             class = _EnableIfDeleterConstructible<_GoodRValRefType<_Dummy>>>
2671   _LIBCPP_INLINE_VISIBILITY
2672   unique_ptr(nullptr_t, _GoodRValRefType<_Dummy> __d) noexcept
2673       : __ptr_(nullptr, _VSTD::move(__d)) {
2674     static_assert(!is_reference<deleter_type>::value,
2675                   "rvalue deleter bound to reference");
2676   }
2677
2678   template <class _Pp, bool _Dummy = true,
2679             class = _EnableIfDeleterConstructible<_BadRValRefType<_Dummy>>,
2680             class = _EnableIfPointerConvertible<_Pp>>
2681   _LIBCPP_INLINE_VISIBILITY
2682   unique_ptr(_Pp __p, _BadRValRefType<_Dummy> __d) = delete;
2683
2684   _LIBCPP_INLINE_VISIBILITY
2685   unique_ptr(unique_ptr&& __u) noexcept
2686       : __ptr_(__u.release(), _VSTD::forward<deleter_type>(__u.get_deleter())) {
2687   }
2688
2689   _LIBCPP_INLINE_VISIBILITY
2690   unique_ptr& operator=(unique_ptr&& __u) noexcept {
2691     reset(__u.release());
2692     __ptr_.second() = _VSTD::forward<deleter_type>(__u.get_deleter());
2693     return *this;
2694   }
2695
2696   template <class _Up, class _Ep,
2697       class = _EnableIfMoveConvertible<unique_ptr<_Up, _Ep>, _Up>,
2698       class = _EnableIfDeleterConvertible<_Ep>
2699   >
2700   _LIBCPP_INLINE_VISIBILITY
2701   unique_ptr(unique_ptr<_Up, _Ep>&& __u) noexcept
2702       : __ptr_(__u.release(), _VSTD::forward<_Ep>(__u.get_deleter())) {
2703   }
2704
2705   template <class _Up, class _Ep,
2706       class = _EnableIfMoveConvertible<unique_ptr<_Up, _Ep>, _Up>,
2707       class = _EnableIfDeleterAssignable<_Ep>
2708   >
2709   _LIBCPP_INLINE_VISIBILITY
2710   unique_ptr&
2711   operator=(unique_ptr<_Up, _Ep>&& __u) noexcept {
2712     reset(__u.release());
2713     __ptr_.second() = _VSTD::forward<_Ep>(__u.get_deleter());
2714     return *this;
2715   }
2716
2717 #else // _LIBCPP_CXX03_LANG
2718 private:
2719   template <class _Up> explicit unique_ptr(_Up);
2720
2721   unique_ptr(unique_ptr&);
2722   template <class _Up> unique_ptr(unique_ptr<_Up>&);
2723
2724   unique_ptr& operator=(unique_ptr&);
2725   template <class _Up> unique_ptr& operator=(unique_ptr<_Up>&);
2726
2727   template <class _Up>
2728   unique_ptr(_Up __u,
2729              typename conditional<
2730                  is_reference<deleter_type>::value, deleter_type,
2731                  typename add_lvalue_reference<const deleter_type>::type>::type,
2732              typename enable_if<is_convertible<_Up, pointer>::value,
2733                                 __nat>::type = __nat());
2734 public:
2735   _LIBCPP_INLINE_VISIBILITY
2736   unique_ptr() : __ptr_(pointer()) {
2737     static_assert(!is_pointer<deleter_type>::value,
2738                   "unique_ptr constructed with null function pointer deleter");
2739   }
2740   _LIBCPP_INLINE_VISIBILITY
2741   unique_ptr(nullptr_t) : __ptr_(pointer()) {
2742     static_assert(!is_pointer<deleter_type>::value,
2743                   "unique_ptr constructed with null function pointer deleter");
2744   }
2745
2746   _LIBCPP_INLINE_VISIBILITY
2747   explicit unique_ptr(pointer __p) : __ptr_(__p) {
2748     static_assert(!is_pointer<deleter_type>::value,
2749                   "unique_ptr constructed with null function pointer deleter");
2750   }
2751
2752   _LIBCPP_INLINE_VISIBILITY
2753   unique_ptr(pointer __p, deleter_type __d)
2754       : __ptr_(__p, _VSTD::forward<deleter_type>(__d)) {}
2755
2756   _LIBCPP_INLINE_VISIBILITY
2757   unique_ptr(nullptr_t, deleter_type __d)
2758       : __ptr_(pointer(), _VSTD::forward<deleter_type>(__d)) {}
2759
2760   _LIBCPP_INLINE_VISIBILITY
2761   operator __rv<unique_ptr>() {
2762     return __rv<unique_ptr>(*this);
2763   }
2764
2765   _LIBCPP_INLINE_VISIBILITY
2766   unique_ptr(__rv<unique_ptr> __u)
2767       : __ptr_(__u->release(),
2768                _VSTD::forward<deleter_type>(__u->get_deleter())) {}
2769
2770   _LIBCPP_INLINE_VISIBILITY
2771   unique_ptr& operator=(__rv<unique_ptr> __u) {
2772     reset(__u->release());
2773     __ptr_.second() = _VSTD::forward<deleter_type>(__u->get_deleter());
2774     return *this;
2775   }
2776
2777 #endif // _LIBCPP_CXX03_LANG
2778
2779 public:
2780   _LIBCPP_INLINE_VISIBILITY
2781   ~unique_ptr() { reset(); }
2782
2783   _LIBCPP_INLINE_VISIBILITY
2784   unique_ptr& operator=(nullptr_t) _NOEXCEPT {
2785     reset();
2786     return *this;
2787   }
2788
2789   _LIBCPP_INLINE_VISIBILITY
2790   typename add_lvalue_reference<_Tp>::type
2791   operator[](size_t __i) const {
2792     return __ptr_.first()[__i];
2793   }
2794   _LIBCPP_INLINE_VISIBILITY
2795   pointer get() const _NOEXCEPT {
2796     return __ptr_.first();
2797   }
2798
2799   _LIBCPP_INLINE_VISIBILITY
2800   deleter_type& get_deleter() _NOEXCEPT {
2801     return __ptr_.second();
2802   }
2803
2804   _LIBCPP_INLINE_VISIBILITY
2805   const deleter_type& get_deleter() const _NOEXCEPT {
2806     return __ptr_.second();
2807   }
2808   _LIBCPP_INLINE_VISIBILITY
2809   _LIBCPP_EXPLICIT operator bool() const _NOEXCEPT {
2810     return __ptr_.first() != nullptr;
2811   }
2812
2813   _LIBCPP_INLINE_VISIBILITY
2814   pointer release() _NOEXCEPT {
2815     pointer __t = __ptr_.first();
2816     __ptr_.first() = pointer();
2817     return __t;
2818   }
2819
2820   template <class _Pp>
2821   _LIBCPP_INLINE_VISIBILITY
2822   typename enable_if<
2823       _CheckArrayPointerConversion<_Pp>::value
2824   >::type
2825   reset(_Pp __p) _NOEXCEPT {
2826     pointer __tmp = __ptr_.first();
2827     __ptr_.first() = __p;
2828     if (__tmp)
2829       __ptr_.second()(__tmp);
2830   }
2831
2832   _LIBCPP_INLINE_VISIBILITY
2833   void reset(nullptr_t = nullptr) _NOEXCEPT {
2834     pointer __tmp = __ptr_.first();
2835     __ptr_.first() = nullptr;
2836     if (__tmp)
2837       __ptr_.second()(__tmp);
2838   }
2839
2840   _LIBCPP_INLINE_VISIBILITY
2841   void swap(unique_ptr& __u) _NOEXCEPT {
2842     __ptr_.swap(__u.__ptr_);
2843   }
2844
2845 };
2846
2847 template <class _Tp, class _Dp>
2848 inline _LIBCPP_INLINE_VISIBILITY
2849 typename enable_if<
2850     __is_swappable<_Dp>::value,
2851     void
2852 >::type
2853 swap(unique_ptr<_Tp, _Dp>& __x, unique_ptr<_Tp, _Dp>& __y) _NOEXCEPT {__x.swap(__y);}
2854
2855 template <class _T1, class _D1, class _T2, class _D2>
2856 inline _LIBCPP_INLINE_VISIBILITY
2857 bool
2858 operator==(const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return __x.get() == __y.get();}
2859
2860 template <class _T1, class _D1, class _T2, class _D2>
2861 inline _LIBCPP_INLINE_VISIBILITY
2862 bool
2863 operator!=(const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return !(__x == __y);}
2864
2865 template <class _T1, class _D1, class _T2, class _D2>
2866 inline _LIBCPP_INLINE_VISIBILITY
2867 bool
2868 operator< (const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y)
2869 {
2870     typedef typename unique_ptr<_T1, _D1>::pointer _P1;
2871     typedef typename unique_ptr<_T2, _D2>::pointer _P2;
2872     typedef typename common_type<_P1, _P2>::type _Vp;
2873     return less<_Vp>()(__x.get(), __y.get());
2874 }
2875
2876 template <class _T1, class _D1, class _T2, class _D2>
2877 inline _LIBCPP_INLINE_VISIBILITY
2878 bool
2879 operator> (const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return __y < __x;}
2880
2881 template <class _T1, class _D1, class _T2, class _D2>
2882 inline _LIBCPP_INLINE_VISIBILITY
2883 bool
2884 operator<=(const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return !(__y < __x);}
2885
2886 template <class _T1, class _D1, class _T2, class _D2>
2887 inline _LIBCPP_INLINE_VISIBILITY
2888 bool
2889 operator>=(const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return !(__x < __y);}
2890
2891 template <class _T1, class _D1>
2892 inline _LIBCPP_INLINE_VISIBILITY
2893 bool
2894 operator==(const unique_ptr<_T1, _D1>& __x, nullptr_t) _NOEXCEPT
2895 {
2896     return !__x;
2897 }
2898
2899 template <class _T1, class _D1>
2900 inline _LIBCPP_INLINE_VISIBILITY
2901 bool
2902 operator==(nullptr_t, const unique_ptr<_T1, _D1>& __x) _NOEXCEPT
2903 {
2904     return !__x;
2905 }
2906
2907 template <class _T1, class _D1>
2908 inline _LIBCPP_INLINE_VISIBILITY
2909 bool
2910 operator!=(const unique_ptr<_T1, _D1>& __x, nullptr_t) _NOEXCEPT
2911 {
2912     return static_cast<bool>(__x);
2913 }
2914
2915 template <class _T1, class _D1>
2916 inline _LIBCPP_INLINE_VISIBILITY
2917 bool
2918 operator!=(nullptr_t, const unique_ptr<_T1, _D1>& __x) _NOEXCEPT
2919 {
2920     return static_cast<bool>(__x);
2921 }
2922
2923 template <class _T1, class _D1>
2924 inline _LIBCPP_INLINE_VISIBILITY
2925 bool
2926 operator<(const unique_ptr<_T1, _D1>& __x, nullptr_t)
2927 {
2928     typedef typename unique_ptr<_T1, _D1>::pointer _P1;
2929     return less<_P1>()(__x.get(), nullptr);
2930 }
2931
2932 template <class _T1, class _D1>
2933 inline _LIBCPP_INLINE_VISIBILITY
2934 bool
2935 operator<(nullptr_t, const unique_ptr<_T1, _D1>& __x)
2936 {
2937     typedef typename unique_ptr<_T1, _D1>::pointer _P1;
2938     return less<_P1>()(nullptr, __x.get());
2939 }
2940
2941 template <class _T1, class _D1>
2942 inline _LIBCPP_INLINE_VISIBILITY
2943 bool
2944 operator>(const unique_ptr<_T1, _D1>& __x, nullptr_t)
2945 {
2946     return nullptr < __x;
2947 }
2948
2949 template <class _T1, class _D1>
2950 inline _LIBCPP_INLINE_VISIBILITY
2951 bool
2952 operator>(nullptr_t, const unique_ptr<_T1, _D1>& __x)
2953 {
2954     return __x < nullptr;
2955 }
2956
2957 template <class _T1, class _D1>
2958 inline _LIBCPP_INLINE_VISIBILITY
2959 bool
2960 operator<=(const unique_ptr<_T1, _D1>& __x, nullptr_t)
2961 {
2962     return !(nullptr < __x);
2963 }
2964
2965 template <class _T1, class _D1>
2966 inline _LIBCPP_INLINE_VISIBILITY
2967 bool
2968 operator<=(nullptr_t, const unique_ptr<_T1, _D1>& __x)
2969 {
2970     return !(__x < nullptr);
2971 }
2972
2973 template <class _T1, class _D1>
2974 inline _LIBCPP_INLINE_VISIBILITY
2975 bool
2976 operator>=(const unique_ptr<_T1, _D1>& __x, nullptr_t)
2977 {
2978     return !(__x < nullptr);
2979 }
2980
2981 template <class _T1, class _D1>
2982 inline _LIBCPP_INLINE_VISIBILITY
2983 bool
2984 operator>=(nullptr_t, const unique_ptr<_T1, _D1>& __x)
2985 {
2986     return !(nullptr < __x);
2987 }
2988
2989 #ifdef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2990
2991 template <class _Tp, class _Dp>
2992 inline _LIBCPP_INLINE_VISIBILITY
2993 unique_ptr<_Tp, _Dp>
2994 move(unique_ptr<_Tp, _Dp>& __t)
2995 {
2996     return unique_ptr<_Tp, _Dp>(__rv<unique_ptr<_Tp, _Dp> >(__t));
2997 }
2998
2999 #endif
3000
3001 #if _LIBCPP_STD_VER > 11
3002
3003 template<class _Tp>
3004 struct __unique_if
3005 {
3006     typedef unique_ptr<_Tp> __unique_single;
3007 };
3008
3009 template<class _Tp>
3010 struct __unique_if<_Tp[]>
3011 {
3012     typedef unique_ptr<_Tp[]> __unique_array_unknown_bound;
3013 };
3014
3015 template<class _Tp, size_t _Np>
3016 struct __unique_if<_Tp[_Np]>
3017 {
3018     typedef void __unique_array_known_bound;
3019 };
3020
3021 template<class _Tp, class... _Args>
3022 inline _LIBCPP_INLINE_VISIBILITY
3023 typename __unique_if<_Tp>::__unique_single
3024 make_unique(_Args&&... __args)
3025 {
3026     return unique_ptr<_Tp>(new _Tp(_VSTD::forward<_Args>(__args)...));
3027 }
3028
3029 template<class _Tp>
3030 inline _LIBCPP_INLINE_VISIBILITY
3031 typename __unique_if<_Tp>::__unique_array_unknown_bound
3032 make_unique(size_t __n)
3033 {
3034     typedef typename remove_extent<_Tp>::type _Up;
3035     return unique_ptr<_Tp>(new _Up[__n]());
3036 }
3037
3038 template<class _Tp, class... _Args>
3039     typename __unique_if<_Tp>::__unique_array_known_bound
3040     make_unique(_Args&&...) = delete;
3041
3042 #endif  // _LIBCPP_STD_VER > 11
3043
3044 template <class _Tp, class _Dp>
3045 #ifdef _LIBCPP_CXX03_LANG
3046 struct _LIBCPP_TEMPLATE_VIS hash<unique_ptr<_Tp, _Dp> >
3047 #else
3048 struct _LIBCPP_TEMPLATE_VIS hash<__enable_hash_helper<
3049     unique_ptr<_Tp, _Dp>, typename unique_ptr<_Tp, _Dp>::pointer>>
3050 #endif
3051 {
3052     typedef unique_ptr<_Tp, _Dp> argument_type;
3053     typedef size_t               result_type;
3054     _LIBCPP_INLINE_VISIBILITY
3055     result_type operator()(const argument_type& __ptr) const
3056     {
3057         typedef typename argument_type::pointer pointer;
3058         return hash<pointer>()(__ptr.get());
3059     }
3060 };
3061
3062 struct __destruct_n
3063 {
3064 private:
3065     size_t __size_;
3066
3067     template <class _Tp>
3068     _LIBCPP_INLINE_VISIBILITY void __process(_Tp* __p, false_type) _NOEXCEPT
3069         {for (size_t __i = 0; __i < __size_; ++__i, ++__p) __p->~_Tp();}
3070
3071     template <class _Tp>
3072     _LIBCPP_INLINE_VISIBILITY void __process(_Tp*, true_type) _NOEXCEPT
3073         {}
3074
3075     _LIBCPP_INLINE_VISIBILITY void __incr(false_type) _NOEXCEPT
3076         {++__size_;}
3077     _LIBCPP_INLINE_VISIBILITY void __incr(true_type) _NOEXCEPT
3078         {}
3079
3080     _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, false_type) _NOEXCEPT
3081         {__size_ = __s;}
3082     _LIBCPP_INLINE_VISIBILITY void __set(size_t, true_type) _NOEXCEPT
3083         {}
3084 public:
3085     _LIBCPP_INLINE_VISIBILITY explicit __destruct_n(size_t __s) _NOEXCEPT
3086         : __size_(__s) {}
3087
3088     template <class _Tp>
3089     _LIBCPP_INLINE_VISIBILITY void __incr(_Tp*) _NOEXCEPT
3090         {__incr(integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
3091
3092     template <class _Tp>
3093     _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, _Tp*) _NOEXCEPT
3094         {__set(__s, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
3095
3096     template <class _Tp>
3097     _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) _NOEXCEPT
3098         {__process(__p, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
3099 };
3100
3101 template <class _Alloc>
3102 class __allocator_destructor
3103 {
3104     typedef allocator_traits<_Alloc> __alloc_traits;
3105 public:
3106     typedef typename __alloc_traits::pointer pointer;
3107     typedef typename __alloc_traits::size_type size_type;
3108 private:
3109     _Alloc& __alloc_;
3110     size_type __s_;
3111 public:
3112     _LIBCPP_INLINE_VISIBILITY __allocator_destructor(_Alloc& __a, size_type __s)
3113              _NOEXCEPT
3114         : __alloc_(__a), __s_(__s) {}
3115     _LIBCPP_INLINE_VISIBILITY
3116     void operator()(pointer __p) _NOEXCEPT
3117         {__alloc_traits::deallocate(__alloc_, __p, __s_);}
3118 };
3119
3120 template <class _InputIterator, class _ForwardIterator>
3121 _ForwardIterator
3122 uninitialized_copy(_InputIterator __f, _InputIterator __l, _ForwardIterator __r)
3123 {
3124     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3125 #ifndef _LIBCPP_NO_EXCEPTIONS
3126     _ForwardIterator __s = __r;
3127     try
3128     {
3129 #endif
3130         for (; __f != __l; ++__f, (void) ++__r)
3131             ::new (static_cast<void*>(_VSTD::addressof(*__r))) value_type(*__f);
3132 #ifndef _LIBCPP_NO_EXCEPTIONS
3133     }
3134     catch (...)
3135     {
3136         for (; __s != __r; ++__s)
3137             __s->~value_type();
3138         throw;
3139     }
3140 #endif
3141     return __r;
3142 }
3143
3144 template <class _InputIterator, class _Size, class _ForwardIterator>
3145 _ForwardIterator
3146 uninitialized_copy_n(_InputIterator __f, _Size __n, _ForwardIterator __r)
3147 {
3148     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3149 #ifndef _LIBCPP_NO_EXCEPTIONS
3150     _ForwardIterator __s = __r;
3151     try
3152     {
3153 #endif
3154         for (; __n > 0; ++__f, (void) ++__r, (void) --__n)
3155             ::new (static_cast<void*>(_VSTD::addressof(*__r))) value_type(*__f);
3156 #ifndef _LIBCPP_NO_EXCEPTIONS
3157     }
3158     catch (...)
3159     {
3160         for (; __s != __r; ++__s)
3161             __s->~value_type();
3162         throw;
3163     }
3164 #endif
3165     return __r;
3166 }
3167
3168 template <class _ForwardIterator, class _Tp>
3169 void
3170 uninitialized_fill(_ForwardIterator __f, _ForwardIterator __l, const _Tp& __x)
3171 {
3172     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3173 #ifndef _LIBCPP_NO_EXCEPTIONS
3174     _ForwardIterator __s = __f;
3175     try
3176     {
3177 #endif
3178         for (; __f != __l; ++__f)
3179             ::new (static_cast<void*>(_VSTD::addressof(*__f))) value_type(__x);
3180 #ifndef _LIBCPP_NO_EXCEPTIONS
3181     }
3182     catch (...)
3183     {
3184         for (; __s != __f; ++__s)
3185             __s->~value_type();
3186         throw;
3187     }
3188 #endif
3189 }
3190
3191 template <class _ForwardIterator, class _Size, class _Tp>
3192 _ForwardIterator
3193 uninitialized_fill_n(_ForwardIterator __f, _Size __n, const _Tp& __x)
3194 {
3195     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3196 #ifndef _LIBCPP_NO_EXCEPTIONS
3197     _ForwardIterator __s = __f;
3198     try
3199     {
3200 #endif
3201         for (; __n > 0; ++__f, (void) --__n)
3202             ::new (static_cast<void*>(_VSTD::addressof(*__f))) value_type(__x);
3203 #ifndef _LIBCPP_NO_EXCEPTIONS
3204     }
3205     catch (...)
3206     {
3207         for (; __s != __f; ++__s)
3208             __s->~value_type();
3209         throw;
3210     }
3211 #endif
3212     return __f;
3213 }
3214
3215 #if _LIBCPP_STD_VER > 14
3216
3217 template <class _Tp>
3218 inline _LIBCPP_INLINE_VISIBILITY
3219 void destroy_at(_Tp* __loc) {
3220     _LIBCPP_ASSERT(__loc, "null pointer given to destroy_at");
3221     __loc->~_Tp();
3222 }
3223
3224 template <class _ForwardIterator>
3225 inline _LIBCPP_INLINE_VISIBILITY
3226 void destroy(_ForwardIterator __first, _ForwardIterator __last) {
3227     for (; __first != __last; ++__first)
3228         _VSTD::destroy_at(_VSTD::addressof(*__first));
3229 }
3230
3231 template <class _ForwardIterator, class _Size>
3232 inline _LIBCPP_INLINE_VISIBILITY
3233 _ForwardIterator destroy_n(_ForwardIterator __first, _Size __n) {
3234     for (; __n > 0; (void)++__first, --__n)
3235         _VSTD::destroy_at(_VSTD::addressof(*__first));
3236     return __first;
3237 }
3238
3239 template <class _ForwardIterator>
3240 inline _LIBCPP_INLINE_VISIBILITY
3241 void uninitialized_default_construct(_ForwardIterator __first, _ForwardIterator __last) {
3242     using _Vt = typename iterator_traits<_ForwardIterator>::value_type;
3243     auto __idx = __first;
3244 #ifndef _LIBCPP_NO_EXCEPTIONS
3245     try {
3246 #endif
3247     for (; __idx != __last; ++__idx)
3248         ::new((void*)_VSTD::addressof(*__idx)) _Vt;
3249 #ifndef _LIBCPP_NO_EXCEPTIONS
3250     } catch (...) {
3251         _VSTD::destroy(__first, __idx);
3252         throw;
3253     }
3254 #endif
3255 }
3256
3257 template <class _ForwardIterator, class _Size>
3258 inline _LIBCPP_INLINE_VISIBILITY
3259 _ForwardIterator uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {
3260     using _Vt = typename iterator_traits<_ForwardIterator>::value_type;
3261     auto __idx = __first;
3262 #ifndef _LIBCPP_NO_EXCEPTIONS
3263     try {
3264 #endif
3265     for (; __n > 0; (void)++__idx, --__n)
3266         ::new((void*)_VSTD::addressof(*__idx)) _Vt;
3267     return __idx;
3268 #ifndef _LIBCPP_NO_EXCEPTIONS
3269     } catch (...) {
3270         _VSTD::destroy(__first, __idx);
3271         throw;
3272     }
3273 #endif
3274 }
3275
3276
3277 template <class _ForwardIterator>
3278 inline _LIBCPP_INLINE_VISIBILITY
3279 void uninitialized_value_construct(_ForwardIterator __first, _ForwardIterator __last) {
3280     using _Vt = typename iterator_traits<_ForwardIterator>::value_type;
3281     auto __idx = __first;
3282 #ifndef _LIBCPP_NO_EXCEPTIONS
3283     try {
3284 #endif
3285     for (; __idx != __last; ++__idx)
3286         ::new((void*)_VSTD::addressof(*__idx)) _Vt();
3287 #ifndef _LIBCPP_NO_EXCEPTIONS
3288     } catch (...) {
3289         _VSTD::destroy(__first, __idx);
3290         throw;
3291     }
3292 #endif
3293 }
3294
3295 template <class _ForwardIterator, class _Size>
3296 inline _LIBCPP_INLINE_VISIBILITY
3297 _ForwardIterator uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) {
3298     using _Vt = typename iterator_traits<_ForwardIterator>::value_type;
3299     auto __idx = __first;
3300 #ifndef _LIBCPP_NO_EXCEPTIONS
3301     try {
3302 #endif
3303     for (; __n > 0; (void)++__idx, --__n)
3304         ::new((void*)_VSTD::addressof(*__idx)) _Vt();
3305     return __idx;
3306 #ifndef _LIBCPP_NO_EXCEPTIONS
3307     } catch (...) {
3308         _VSTD::destroy(__first, __idx);
3309         throw;
3310     }
3311 #endif
3312 }
3313
3314
3315 template <class _InputIt, class _ForwardIt>
3316 inline _LIBCPP_INLINE_VISIBILITY
3317 _ForwardIt uninitialized_move(_InputIt __first, _InputIt __last, _ForwardIt __first_res) {
3318     using _Vt = typename iterator_traits<_ForwardIt>::value_type;
3319     auto __idx = __first_res;
3320 #ifndef _LIBCPP_NO_EXCEPTIONS
3321     try {
3322 #endif
3323     for (; __first != __last; (void)++__idx, ++__first)
3324         ::new((void*)_VSTD::addressof(*__idx)) _Vt(std::move(*__first));
3325     return __idx;
3326 #ifndef _LIBCPP_NO_EXCEPTIONS
3327     } catch (...) {
3328         _VSTD::destroy(__first_res, __idx);
3329         throw;
3330     }
3331 #endif
3332 }
3333
3334 template <class _InputIt, class _Size, class _ForwardIt>
3335 inline _LIBCPP_INLINE_VISIBILITY
3336 pair<_InputIt, _ForwardIt>
3337 uninitialized_move_n(_InputIt __first, _Size __n, _ForwardIt __first_res) {
3338     using _Vt = typename iterator_traits<_ForwardIt>::value_type;
3339     auto __idx = __first_res;
3340 #ifndef _LIBCPP_NO_EXCEPTIONS
3341     try {
3342 #endif
3343     for (; __n > 0; ++__idx, (void)++__first, --__n)
3344         ::new((void*)_VSTD::addressof(*__idx)) _Vt(std::move(*__first));
3345     return {__first, __idx};
3346 #ifndef _LIBCPP_NO_EXCEPTIONS
3347     } catch (...) {
3348         _VSTD::destroy(__first_res, __idx);
3349         throw;
3350     }
3351 #endif
3352 }
3353
3354
3355 #endif // _LIBCPP_STD_VER > 14
3356
3357 // NOTE: Relaxed and acq/rel atomics (for increment and decrement respectively)
3358 // should be sufficient for thread safety.
3359 // See https://bugs.llvm.org/show_bug.cgi?id=22803
3360 #if defined(__clang__) && __has_builtin(__atomic_add_fetch)          \
3361                        && defined(__ATOMIC_RELAXED)                  \
3362                        && defined(__ATOMIC_ACQ_REL)
3363 #   define _LIBCPP_HAS_BUILTIN_ATOMIC_SUPPORT
3364 #elif !defined(__clang__) && defined(_GNUC_VER) && _GNUC_VER >= 407
3365 #   define _LIBCPP_HAS_BUILTIN_ATOMIC_SUPPORT
3366 #endif
3367
3368 template <class _Tp>
3369 inline _LIBCPP_INLINE_VISIBILITY _Tp
3370 __libcpp_atomic_refcount_increment(_Tp& __t) _NOEXCEPT
3371 {
3372 #if defined(_LIBCPP_HAS_BUILTIN_ATOMIC_SUPPORT) && !defined(_LIBCPP_HAS_NO_THREADS)
3373     return __atomic_add_fetch(&__t, 1, __ATOMIC_RELAXED);
3374 #else
3375     return __t += 1;
3376 #endif
3377 }
3378
3379 template <class _Tp>
3380 inline _LIBCPP_INLINE_VISIBILITY _Tp
3381 __libcpp_atomic_refcount_decrement(_Tp& __t) _NOEXCEPT
3382 {
3383 #if defined(_LIBCPP_HAS_BUILTIN_ATOMIC_SUPPORT) && !defined(_LIBCPP_HAS_NO_THREADS)
3384     return __atomic_add_fetch(&__t, -1, __ATOMIC_ACQ_REL);
3385 #else
3386     return __t -= 1;
3387 #endif
3388 }
3389
3390 class _LIBCPP_EXCEPTION_ABI bad_weak_ptr
3391     : public std::exception
3392 {
3393 public:
3394     virtual ~bad_weak_ptr() _NOEXCEPT;
3395     virtual const char* what() const  _NOEXCEPT;
3396 };
3397
3398 _LIBCPP_NORETURN inline _LIBCPP_ALWAYS_INLINE
3399 void __throw_bad_weak_ptr()
3400 {
3401 #ifndef _LIBCPP_NO_EXCEPTIONS
3402     throw bad_weak_ptr();
3403 #else
3404     _VSTD::abort();
3405 #endif
3406 }
3407
3408 template<class _Tp> class _LIBCPP_TEMPLATE_VIS weak_ptr;
3409
3410 class _LIBCPP_TYPE_VIS __shared_count
3411 {
3412     __shared_count(const __shared_count&);
3413     __shared_count& operator=(const __shared_count&);
3414
3415 protected:
3416     long __shared_owners_;
3417     virtual ~__shared_count();
3418 private:
3419     virtual void __on_zero_shared() _NOEXCEPT = 0;
3420
3421 public:
3422     _LIBCPP_INLINE_VISIBILITY
3423     explicit __shared_count(long __refs = 0) _NOEXCEPT
3424         : __shared_owners_(__refs) {}
3425
3426 #if defined(_LIBCPP_BUILDING_MEMORY) && \
3427     defined(_LIBCPP_DEPRECATED_ABI_LEGACY_LIBRARY_DEFINITIONS_FOR_INLINE_FUNCTIONS)
3428     void __add_shared() _NOEXCEPT;
3429     bool __release_shared() _NOEXCEPT;
3430 #else
3431     _LIBCPP_INLINE_VISIBILITY
3432     void __add_shared() _NOEXCEPT {
3433       __libcpp_atomic_refcount_increment(__shared_owners_);
3434     }
3435     _LIBCPP_INLINE_VISIBILITY
3436     bool __release_shared() _NOEXCEPT {
3437       if (__libcpp_atomic_refcount_decrement(__shared_owners_) == -1) {
3438         __on_zero_shared();
3439         return true;
3440       }
3441       return false;
3442     }
3443 #endif
3444     _LIBCPP_INLINE_VISIBILITY
3445     long use_count() const _NOEXCEPT {
3446         return __libcpp_relaxed_load(&__shared_owners_) + 1;
3447     }
3448 };
3449
3450 class _LIBCPP_TYPE_VIS __shared_weak_count
3451     : private __shared_count
3452 {
3453     long __shared_weak_owners_;
3454
3455 public:
3456     _LIBCPP_INLINE_VISIBILITY
3457     explicit __shared_weak_count(long __refs = 0) _NOEXCEPT
3458         : __shared_count(__refs),
3459           __shared_weak_owners_(__refs) {}
3460 protected:
3461     virtual ~__shared_weak_count();
3462
3463 public:
3464 #if defined(_LIBCPP_BUILDING_MEMORY) && \
3465     defined(_LIBCPP_DEPRECATED_ABI_LEGACY_LIBRARY_DEFINITIONS_FOR_INLINE_FUNCTIONS)
3466     void __add_shared() _NOEXCEPT;
3467     void __add_weak() _NOEXCEPT;
3468     void __release_shared() _NOEXCEPT;
3469 #else
3470     _LIBCPP_INLINE_VISIBILITY
3471     void __add_shared() _NOEXCEPT {
3472       __shared_count::__add_shared();
3473     }
3474     _LIBCPP_INLINE_VISIBILITY
3475     void __add_weak() _NOEXCEPT {
3476       __libcpp_atomic_refcount_increment(__shared_weak_owners_);
3477     }
3478     _LIBCPP_INLINE_VISIBILITY
3479     void __release_shared() _NOEXCEPT {
3480       if (__shared_count::__release_shared())
3481         __release_weak();
3482     }
3483 #endif
3484     void __release_weak() _NOEXCEPT;
3485     _LIBCPP_INLINE_VISIBILITY
3486     long use_count() const _NOEXCEPT {return __shared_count::use_count();}
3487     __shared_weak_count* lock() _NOEXCEPT;
3488
3489     // Define the function out only if we build static libc++ without RTTI.
3490     // Otherwise we may break clients who need to compile their projects with
3491     // -fno-rtti and yet link against a libc++.dylib compiled
3492     // without -fno-rtti.
3493 #if !defined(_LIBCPP_NO_RTTI) || !defined(_LIBCPP_BUILD_STATIC)
3494     virtual const void* __get_deleter(const type_info&) const _NOEXCEPT;
3495 #endif
3496 private:
3497     virtual void __on_zero_shared_weak() _NOEXCEPT = 0;
3498 };
3499
3500 template <class _Tp, class _Dp, class _Alloc>
3501 class __shared_ptr_pointer
3502     : public __shared_weak_count
3503 {
3504     __compressed_pair<__compressed_pair<_Tp, _Dp>, _Alloc> __data_;
3505 public:
3506     _LIBCPP_INLINE_VISIBILITY
3507     __shared_ptr_pointer(_Tp __p, _Dp __d, _Alloc __a)
3508         :  __data_(__compressed_pair<_Tp, _Dp>(__p, _VSTD::move(__d)), _VSTD::move(__a)) {}
3509
3510 #ifndef _LIBCPP_NO_RTTI
3511     virtual const void* __get_deleter(const type_info&) const _NOEXCEPT;
3512 #endif
3513
3514 private:
3515     virtual void __on_zero_shared() _NOEXCEPT;
3516     virtual void __on_zero_shared_weak() _NOEXCEPT;
3517 };
3518
3519 #ifndef _LIBCPP_NO_RTTI
3520
3521 template <class _Tp, class _Dp, class _Alloc>
3522 const void*
3523 __shared_ptr_pointer<_Tp, _Dp, _Alloc>::__get_deleter(const type_info& __t) const _NOEXCEPT
3524 {
3525     return __t == typeid(_Dp) ? _VSTD::addressof(__data_.first().second()) : nullptr;
3526 }
3527
3528 #endif  // _LIBCPP_NO_RTTI
3529
3530 template <class _Tp, class _Dp, class _Alloc>
3531 void
3532 __shared_ptr_pointer<_Tp, _Dp, _Alloc>::__on_zero_shared() _NOEXCEPT
3533 {
3534     __data_.first().second()(__data_.first().first());
3535     __data_.first().second().~_Dp();
3536 }
3537
3538 template <class _Tp, class _Dp, class _Alloc>
3539 void
3540 __shared_ptr_pointer<_Tp, _Dp, _Alloc>::__on_zero_shared_weak() _NOEXCEPT
3541 {
3542     typedef typename __allocator_traits_rebind<_Alloc, __shared_ptr_pointer>::type _Al;
3543     typedef allocator_traits<_Al> _ATraits;
3544     typedef pointer_traits<typename _ATraits::pointer> _PTraits;
3545
3546     _Al __a(__data_.second());
3547     __data_.second().~_Alloc();
3548     __a.deallocate(_PTraits::pointer_to(*this), 1);
3549 }
3550
3551 template <class _Tp, class _Alloc>
3552 class __shared_ptr_emplace
3553     : public __shared_weak_count
3554 {
3555     __compressed_pair<_Alloc, _Tp> __data_;
3556 public:
3557 #ifndef _LIBCPP_HAS_NO_VARIADICS
3558
3559     _LIBCPP_INLINE_VISIBILITY
3560     __shared_ptr_emplace(_Alloc __a)
3561         :  __data_(_VSTD::move(__a)) {}
3562
3563     template <class ..._Args>
3564         _LIBCPP_INLINE_VISIBILITY
3565         __shared_ptr_emplace(_Alloc __a, _Args&& ...__args)
3566             :  __data_(piecewise_construct, _VSTD::forward_as_tuple(__a),
3567                    _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)) {}
3568
3569 #else  // _LIBCPP_HAS_NO_VARIADICS
3570
3571     _LIBCPP_INLINE_VISIBILITY
3572     __shared_ptr_emplace(_Alloc __a)
3573         :  __data_(__a) {}
3574
3575     template <class _A0>
3576         _LIBCPP_INLINE_VISIBILITY
3577         __shared_ptr_emplace(_Alloc __a, _A0& __a0)
3578             :  __data_(__a, _Tp(__a0)) {}
3579
3580     template <class _A0, class _A1>
3581         _LIBCPP_INLINE_VISIBILITY
3582         __shared_ptr_emplace(_Alloc __a, _A0& __a0, _A1& __a1)
3583             :  __data_(__a, _Tp(__a0, __a1)) {}
3584
3585     template <class _A0, class _A1, class _A2>
3586         _LIBCPP_INLINE_VISIBILITY
3587         __shared_ptr_emplace(_Alloc __a, _A0& __a0, _A1& __a1, _A2& __a2)
3588             :  __data_(__a, _Tp(__a0, __a1, __a2)) {}
3589
3590 #endif  // _LIBCPP_HAS_NO_VARIADICS
3591
3592 private:
3593     virtual void __on_zero_shared() _NOEXCEPT;
3594     virtual void __on_zero_shared_weak() _NOEXCEPT;
3595 public:
3596     _LIBCPP_INLINE_VISIBILITY
3597     _Tp* get() _NOEXCEPT {return &__data_.second();}
3598 };
3599
3600 template <class _Tp, class _Alloc>
3601 void
3602 __shared_ptr_emplace<_Tp, _Alloc>::__on_zero_shared() _NOEXCEPT
3603 {
3604     __data_.second().~_Tp();
3605 }
3606
3607 template <class _Tp, class _Alloc>
3608 void
3609 __shared_ptr_emplace<_Tp, _Alloc>::__on_zero_shared_weak() _NOEXCEPT
3610 {
3611     typedef typename __allocator_traits_rebind<_Alloc, __shared_ptr_emplace>::type _Al;
3612     typedef allocator_traits<_Al> _ATraits;
3613     typedef pointer_traits<typename _ATraits::pointer> _PTraits;
3614     _Al __a(__data_.first());
3615     __data_.first().~_Alloc();
3616     __a.deallocate(_PTraits::pointer_to(*this), 1);
3617 }
3618
3619 struct __shared_ptr_dummy_rebind_allocator_type;
3620 template <>
3621 class _LIBCPP_TEMPLATE_VIS allocator<__shared_ptr_dummy_rebind_allocator_type>
3622 {
3623 public:
3624     template <class _Other>
3625     struct rebind
3626     {
3627         typedef allocator<_Other> other;
3628     };
3629 };
3630
3631 template<class _Tp> class _LIBCPP_TEMPLATE_VIS enable_shared_from_this;
3632
3633 template<class _Tp>
3634 class _LIBCPP_TEMPLATE_VIS shared_ptr
3635 {
3636 public:
3637     typedef _Tp element_type;
3638
3639 #if _LIBCPP_STD_VER > 14
3640     typedef weak_ptr<_Tp> weak_type;
3641 #endif
3642 private:
3643     element_type*      __ptr_;
3644     __shared_weak_count* __cntrl_;
3645
3646     struct __nat {int __for_bool_;};
3647 public:
3648     _LIBCPP_INLINE_VISIBILITY
3649     _LIBCPP_CONSTEXPR shared_ptr() _NOEXCEPT;
3650     _LIBCPP_INLINE_VISIBILITY
3651     _LIBCPP_CONSTEXPR shared_ptr(nullptr_t) _NOEXCEPT;
3652     template<class _Yp>
3653         explicit shared_ptr(_Yp* __p,
3654                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3655     template<class _Yp, class _Dp>
3656         shared_ptr(_Yp* __p, _Dp __d,
3657                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3658     template<class _Yp, class _Dp, class _Alloc>
3659         shared_ptr(_Yp* __p, _Dp __d, _Alloc __a,
3660                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3661     template <class _Dp> shared_ptr(nullptr_t __p, _Dp __d);
3662     template <class _Dp, class _Alloc> shared_ptr(nullptr_t __p, _Dp __d, _Alloc __a);
3663     template<class _Yp> _LIBCPP_INLINE_VISIBILITY shared_ptr(const shared_ptr<_Yp>& __r, element_type* __p) _NOEXCEPT;
3664     _LIBCPP_INLINE_VISIBILITY
3665     shared_ptr(const shared_ptr& __r) _NOEXCEPT;
3666     template<class _Yp>
3667         _LIBCPP_INLINE_VISIBILITY
3668         shared_ptr(const shared_ptr<_Yp>& __r,
3669                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat())
3670                        _NOEXCEPT;
3671 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3672     _LIBCPP_INLINE_VISIBILITY
3673     shared_ptr(shared_ptr&& __r) _NOEXCEPT;
3674     template<class _Yp> _LIBCPP_INLINE_VISIBILITY  shared_ptr(shared_ptr<_Yp>&& __r,
3675                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat())
3676                        _NOEXCEPT;
3677 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3678     template<class _Yp> explicit shared_ptr(const weak_ptr<_Yp>& __r,
3679                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type= __nat());
3680 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR)
3681 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3682     template<class _Yp>
3683         shared_ptr(auto_ptr<_Yp>&& __r,
3684                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3685 #else
3686     template<class _Yp>
3687         shared_ptr(auto_ptr<_Yp> __r,
3688                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3689 #endif
3690 #endif
3691 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3692     template <class _Yp, class _Dp>
3693         shared_ptr(unique_ptr<_Yp, _Dp>&&,
3694                    typename enable_if
3695                    <
3696                        !is_lvalue_reference<_Dp>::value &&
3697                        !is_array<_Yp>::value &&
3698                        is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3699                        __nat
3700                    >::type = __nat());
3701     template <class _Yp, class _Dp>
3702         shared_ptr(unique_ptr<_Yp, _Dp>&&,
3703                    typename enable_if
3704                    <
3705                        is_lvalue_reference<_Dp>::value &&
3706                        !is_array<_Yp>::value &&
3707                        is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3708                        __nat
3709                    >::type = __nat());
3710 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3711     template <class _Yp, class _Dp>
3712         shared_ptr(unique_ptr<_Yp, _Dp>,
3713                    typename enable_if
3714                    <
3715                        !is_lvalue_reference<_Dp>::value &&
3716                        !is_array<_Yp>::value &&
3717                        is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3718                        __nat
3719                    >::type = __nat());
3720     template <class _Yp, class _Dp>
3721         shared_ptr(unique_ptr<_Yp, _Dp>,
3722                    typename enable_if
3723                    <
3724                        is_lvalue_reference<_Dp>::value &&
3725                        !is_array<_Yp>::value &&
3726                        is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3727                        __nat
3728                    >::type = __nat());
3729 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3730
3731     ~shared_ptr();
3732
3733     _LIBCPP_INLINE_VISIBILITY
3734     shared_ptr& operator=(const shared_ptr& __r) _NOEXCEPT;
3735     template<class _Yp>
3736         typename enable_if
3737         <
3738             is_convertible<_Yp*, element_type*>::value,
3739             shared_ptr&
3740         >::type
3741         _LIBCPP_INLINE_VISIBILITY
3742         operator=(const shared_ptr<_Yp>& __r) _NOEXCEPT;
3743 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3744     _LIBCPP_INLINE_VISIBILITY
3745     shared_ptr& operator=(shared_ptr&& __r) _NOEXCEPT;
3746     template<class _Yp>
3747         typename enable_if
3748         <
3749             is_convertible<_Yp*, element_type*>::value,
3750             shared_ptr<_Tp>&
3751         >::type
3752         _LIBCPP_INLINE_VISIBILITY
3753         operator=(shared_ptr<_Yp>&& __r);
3754 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR)
3755     template<class _Yp>
3756         _LIBCPP_INLINE_VISIBILITY
3757         typename enable_if
3758         <
3759             !is_array<_Yp>::value &&
3760             is_convertible<_Yp*, element_type*>::value,
3761             shared_ptr
3762         >::type&
3763         operator=(auto_ptr<_Yp>&& __r);
3764 #endif
3765 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3766 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR)
3767     template<class _Yp>
3768         _LIBCPP_INLINE_VISIBILITY
3769         typename enable_if
3770         <
3771             !is_array<_Yp>::value &&
3772             is_convertible<_Yp*, element_type*>::value,
3773             shared_ptr&
3774         >::type
3775         operator=(auto_ptr<_Yp> __r);
3776 #endif
3777 #endif
3778     template <class _Yp, class _Dp>
3779         typename enable_if
3780         <
3781             !is_array<_Yp>::value &&
3782             is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3783             shared_ptr&
3784         >::type
3785 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3786         _LIBCPP_INLINE_VISIBILITY
3787         operator=(unique_ptr<_Yp, _Dp>&& __r);
3788 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3789         _LIBCPP_INLINE_VISIBILITY
3790         operator=(unique_ptr<_Yp, _Dp> __r);
3791 #endif
3792
3793     _LIBCPP_INLINE_VISIBILITY
3794     void swap(shared_ptr& __r) _NOEXCEPT;
3795     _LIBCPP_INLINE_VISIBILITY
3796     void reset() _NOEXCEPT;
3797     template<class _Yp>
3798         typename enable_if
3799         <
3800             is_convertible<_Yp*, element_type*>::value,
3801             void
3802         >::type
3803         _LIBCPP_INLINE_VISIBILITY
3804         reset(_Yp* __p);
3805     template<class _Yp, class _Dp>
3806         typename enable_if
3807         <
3808             is_convertible<_Yp*, element_type*>::value,
3809             void
3810         >::type
3811         _LIBCPP_INLINE_VISIBILITY
3812         reset(_Yp* __p, _Dp __d);
3813     template<class _Yp, class _Dp, class _Alloc>
3814         typename enable_if
3815         <
3816             is_convertible<_Yp*, element_type*>::value,
3817             void
3818         >::type
3819         _LIBCPP_INLINE_VISIBILITY
3820         reset(_Yp* __p, _Dp __d, _Alloc __a);
3821
3822     _LIBCPP_INLINE_VISIBILITY
3823     element_type* get() const _NOEXCEPT {return __ptr_;}
3824     _LIBCPP_INLINE_VISIBILITY
3825     typename add_lvalue_reference<element_type>::type operator*() const _NOEXCEPT
3826         {return *__ptr_;}
3827     _LIBCPP_INLINE_VISIBILITY
3828     element_type* operator->() const _NOEXCEPT {return __ptr_;}
3829     _LIBCPP_INLINE_VISIBILITY
3830     long use_count() const _NOEXCEPT {return __cntrl_ ? __cntrl_->use_count() : 0;}
3831     _LIBCPP_INLINE_VISIBILITY
3832     bool unique() const _NOEXCEPT {return use_count() == 1;}
3833     _LIBCPP_INLINE_VISIBILITY
3834     _LIBCPP_EXPLICIT operator bool() const _NOEXCEPT {return get() != 0;}
3835     template <class _Up>
3836         _LIBCPP_INLINE_VISIBILITY
3837         bool owner_before(shared_ptr<_Up> const& __p) const _NOEXCEPT
3838         {return __cntrl_ < __p.__cntrl_;}
3839     template <class _Up>
3840         _LIBCPP_INLINE_VISIBILITY
3841         bool owner_before(weak_ptr<_Up> const& __p) const _NOEXCEPT
3842         {return __cntrl_ < __p.__cntrl_;}
3843     _LIBCPP_INLINE_VISIBILITY
3844     bool
3845     __owner_equivalent(const shared_ptr& __p) const
3846         {return __cntrl_ == __p.__cntrl_;}
3847
3848 #ifndef _LIBCPP_NO_RTTI
3849     template <class _Dp>
3850         _LIBCPP_INLINE_VISIBILITY
3851         _Dp* __get_deleter() const _NOEXCEPT
3852             {return static_cast<_Dp*>(__cntrl_
3853                     ? const_cast<void *>(__cntrl_->__get_deleter(typeid(_Dp)))
3854                       : nullptr);}
3855 #endif  // _LIBCPP_NO_RTTI
3856
3857 #ifndef _LIBCPP_HAS_NO_VARIADICS
3858
3859     template<class ..._Args>
3860         static
3861         shared_ptr<_Tp>
3862         make_shared(_Args&& ...__args);
3863
3864     template<class _Alloc, class ..._Args>
3865         static
3866         shared_ptr<_Tp>
3867         allocate_shared(const _Alloc& __a, _Args&& ...__args);
3868
3869 #else  // _LIBCPP_HAS_NO_VARIADICS
3870
3871     static shared_ptr<_Tp> make_shared();
3872
3873     template<class _A0>
3874         static shared_ptr<_Tp> make_shared(_A0&);
3875
3876     template<class _A0, class _A1>
3877         static shared_ptr<_Tp> make_shared(_A0&, _A1&);
3878
3879     template<class _A0, class _A1, class _A2>
3880         static shared_ptr<_Tp> make_shared(_A0&, _A1&, _A2&);
3881
3882     template<class _Alloc>
3883         static shared_ptr<_Tp>
3884         allocate_shared(const _Alloc& __a);
3885
3886     template<class _Alloc, class _A0>
3887         static shared_ptr<_Tp>
3888         allocate_shared(const _Alloc& __a, _A0& __a0);
3889
3890     template<class _Alloc, class _A0, class _A1>
3891         static shared_ptr<_Tp>
3892         allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1);
3893
3894     template<class _Alloc, class _A0, class _A1, class _A2>
3895         static shared_ptr<_Tp>
3896         allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2);
3897
3898 #endif  // _LIBCPP_HAS_NO_VARIADICS
3899
3900 private:
3901     template <class _Yp, bool = is_function<_Yp>::value>
3902         struct __shared_ptr_default_allocator
3903         {
3904             typedef allocator<_Yp> type;
3905         };
3906
3907     template <class _Yp>
3908         struct __shared_ptr_default_allocator<_Yp, true>
3909         {
3910             typedef allocator<__shared_ptr_dummy_rebind_allocator_type> type;
3911         };
3912
3913     template <class _Yp, class _OrigPtr>
3914         _LIBCPP_INLINE_VISIBILITY
3915         typename enable_if<is_convertible<_OrigPtr*,
3916                                           const enable_shared_from_this<_Yp>*
3917         >::value,
3918             void>::type
3919         __enable_weak_this(const enable_shared_from_this<_Yp>* __e,
3920                            _OrigPtr* __ptr) _NOEXCEPT
3921         {
3922             typedef typename remove_cv<_Yp>::type _RawYp;
3923             if (__e && __e->__weak_this_.expired())
3924             {
3925                 __e->__weak_this_ = shared_ptr<_RawYp>(*this,
3926                     const_cast<_RawYp*>(static_cast<const _Yp*>(__ptr)));
3927             }
3928         }
3929
3930     _LIBCPP_INLINE_VISIBILITY void __enable_weak_this(...) _NOEXCEPT {}
3931
3932     template <class _Up> friend class _LIBCPP_TEMPLATE_VIS shared_ptr;
3933     template <class _Up> friend class _LIBCPP_TEMPLATE_VIS weak_ptr;
3934 };
3935
3936
3937 template<class _Tp>
3938 inline
3939 _LIBCPP_CONSTEXPR
3940 shared_ptr<_Tp>::shared_ptr() _NOEXCEPT
3941     : __ptr_(0),
3942       __cntrl_(0)
3943 {
3944 }
3945
3946 template<class _Tp>
3947 inline
3948 _LIBCPP_CONSTEXPR
3949 shared_ptr<_Tp>::shared_ptr(nullptr_t) _NOEXCEPT
3950     : __ptr_(0),
3951       __cntrl_(0)
3952 {
3953 }
3954
3955 template<class _Tp>
3956 template<class _Yp>
3957 shared_ptr<_Tp>::shared_ptr(_Yp* __p,
3958                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
3959     : __ptr_(__p)
3960 {
3961     unique_ptr<_Yp> __hold(__p);
3962     typedef typename __shared_ptr_default_allocator<_Yp>::type _AllocT;
3963     typedef __shared_ptr_pointer<_Yp*, default_delete<_Yp>, _AllocT > _CntrlBlk;
3964     __cntrl_ = new _CntrlBlk(__p, default_delete<_Yp>(), _AllocT());
3965     __hold.release();
3966     __enable_weak_this(__p, __p);
3967 }
3968
3969 template<class _Tp>
3970 template<class _Yp, class _Dp>
3971 shared_ptr<_Tp>::shared_ptr(_Yp* __p, _Dp __d,
3972                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
3973     : __ptr_(__p)
3974 {
3975 #ifndef _LIBCPP_NO_EXCEPTIONS
3976     try
3977     {
3978 #endif  // _LIBCPP_NO_EXCEPTIONS
3979         typedef typename __shared_ptr_default_allocator<_Yp>::type _AllocT;
3980         typedef __shared_ptr_pointer<_Yp*, _Dp, _AllocT > _CntrlBlk;
3981         __cntrl_ = new _CntrlBlk(__p, __d, _AllocT());
3982         __enable_weak_this(__p, __p);
3983 #ifndef _LIBCPP_NO_EXCEPTIONS
3984     }
3985     catch (...)
3986     {
3987         __d(__p);
3988         throw;
3989     }
3990 #endif  // _LIBCPP_NO_EXCEPTIONS
3991 }
3992
3993 template<class _Tp>
3994 template<class _Dp>
3995 shared_ptr<_Tp>::shared_ptr(nullptr_t __p, _Dp __d)
3996     : __ptr_(0)
3997 {
3998 #ifndef _LIBCPP_NO_EXCEPTIONS
3999     try
4000     {
4001 #endif  // _LIBCPP_NO_EXCEPTIONS
4002         typedef typename __shared_ptr_default_allocator<_Tp>::type _AllocT;
4003         typedef __shared_ptr_pointer<nullptr_t, _Dp, _AllocT > _CntrlBlk;
4004         __cntrl_ = new _CntrlBlk(__p, __d, _AllocT());
4005 #ifndef _LIBCPP_NO_EXCEPTIONS
4006     }
4007     catch (...)
4008     {
4009         __d(__p);
4010         throw;
4011     }
4012 #endif  // _LIBCPP_NO_EXCEPTIONS
4013 }
4014
4015 template<class _Tp>
4016 template<class _Yp, class _Dp, class _Alloc>
4017 shared_ptr<_Tp>::shared_ptr(_Yp* __p, _Dp __d, _Alloc __a,
4018                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
4019     : __ptr_(__p)
4020 {
4021 #ifndef _LIBCPP_NO_EXCEPTIONS
4022     try
4023     {
4024 #endif  // _LIBCPP_NO_EXCEPTIONS
4025         typedef __shared_ptr_pointer<_Yp*, _Dp, _Alloc> _CntrlBlk;
4026         typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _A2;
4027         typedef __allocator_destructor<_A2> _D2;
4028         _A2 __a2(__a);
4029         unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4030         ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4031             _CntrlBlk(__p, __d, __a);
4032         __cntrl_ = _VSTD::addressof(*__hold2.release());
4033         __enable_weak_this(__p, __p);
4034 #ifndef _LIBCPP_NO_EXCEPTIONS
4035     }
4036     catch (...)
4037     {
4038         __d(__p);
4039         throw;
4040     }
4041 #endif  // _LIBCPP_NO_EXCEPTIONS
4042 }
4043
4044 template<class _Tp>
4045 template<class _Dp, class _Alloc>
4046 shared_ptr<_Tp>::shared_ptr(nullptr_t __p, _Dp __d, _Alloc __a)
4047     : __ptr_(0)
4048 {
4049 #ifndef _LIBCPP_NO_EXCEPTIONS
4050     try
4051     {
4052 #endif  // _LIBCPP_NO_EXCEPTIONS
4053         typedef __shared_ptr_pointer<nullptr_t, _Dp, _Alloc> _CntrlBlk;
4054         typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _A2;
4055         typedef __allocator_destructor<_A2> _D2;
4056         _A2 __a2(__a);
4057         unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4058         ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4059             _CntrlBlk(__p, __d, __a);
4060         __cntrl_ = _VSTD::addressof(*__hold2.release());
4061 #ifndef _LIBCPP_NO_EXCEPTIONS
4062     }
4063     catch (...)
4064     {
4065         __d(__p);
4066         throw;
4067     }
4068 #endif  // _LIBCPP_NO_EXCEPTIONS
4069 }
4070
4071 template<class _Tp>
4072 template<class _Yp>
4073 inline
4074 shared_ptr<_Tp>::shared_ptr(const shared_ptr<_Yp>& __r, element_type *__p) _NOEXCEPT
4075     : __ptr_(__p),
4076       __cntrl_(__r.__cntrl_)
4077 {
4078     if (__cntrl_)
4079         __cntrl_->__add_shared();
4080 }
4081
4082 template<class _Tp>
4083 inline
4084 shared_ptr<_Tp>::shared_ptr(const shared_ptr& __r) _NOEXCEPT
4085     : __ptr_(__r.__ptr_),
4086       __cntrl_(__r.__cntrl_)
4087 {
4088     if (__cntrl_)
4089         __cntrl_->__add_shared();
4090 }
4091
4092 template<class _Tp>
4093 template<class _Yp>
4094 inline
4095 shared_ptr<_Tp>::shared_ptr(const shared_ptr<_Yp>& __r,
4096                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
4097          _NOEXCEPT
4098     : __ptr_(__r.__ptr_),
4099       __cntrl_(__r.__cntrl_)
4100 {
4101     if (__cntrl_)
4102         __cntrl_->__add_shared();
4103 }
4104
4105 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4106
4107 template<class _Tp>
4108 inline
4109 shared_ptr<_Tp>::shared_ptr(shared_ptr&& __r) _NOEXCEPT
4110     : __ptr_(__r.__ptr_),
4111       __cntrl_(__r.__cntrl_)
4112 {
4113     __r.__ptr_ = 0;
4114     __r.__cntrl_ = 0;
4115 }
4116
4117 template<class _Tp>
4118 template<class _Yp>
4119 inline
4120 shared_ptr<_Tp>::shared_ptr(shared_ptr<_Yp>&& __r,
4121                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
4122          _NOEXCEPT
4123     : __ptr_(__r.__ptr_),
4124       __cntrl_(__r.__cntrl_)
4125 {
4126     __r.__ptr_ = 0;
4127     __r.__cntrl_ = 0;
4128 }
4129
4130 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4131
4132 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR)
4133 template<class _Tp>
4134 template<class _Yp>
4135 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4136 shared_ptr<_Tp>::shared_ptr(auto_ptr<_Yp>&& __r,
4137 #else
4138 shared_ptr<_Tp>::shared_ptr(auto_ptr<_Yp> __r,
4139 #endif
4140                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
4141     : __ptr_(__r.get())
4142 {
4143     typedef __shared_ptr_pointer<_Yp*, default_delete<_Yp>, allocator<_Yp> > _CntrlBlk;
4144     __cntrl_ = new _CntrlBlk(__r.get(), default_delete<_Yp>(), allocator<_Yp>());
4145     __enable_weak_this(__r.get(), __r.get());
4146     __r.release();
4147 }
4148 #endif
4149
4150 template<class _Tp>
4151 template <class _Yp, class _Dp>
4152 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4153 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp>&& __r,
4154 #else
4155 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp> __r,
4156 #endif
4157                             typename enable_if
4158                             <
4159                                 !is_lvalue_reference<_Dp>::value &&
4160                                 !is_array<_Yp>::value &&
4161                                 is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
4162                                 __nat
4163                             >::type)
4164     : __ptr_(__r.get())
4165 {
4166 #if _LIBCPP_STD_VER > 11
4167     if (__ptr_ == nullptr)
4168         __cntrl_ = nullptr;
4169     else
4170 #endif
4171     {
4172         typedef typename __shared_ptr_default_allocator<_Yp>::type _AllocT;
4173         typedef __shared_ptr_pointer<_Yp*, _Dp, _AllocT > _CntrlBlk;
4174         __cntrl_ = new _CntrlBlk(__r.get(), __r.get_deleter(), _AllocT());
4175         __enable_weak_this(__r.get(), __r.get());
4176     }
4177     __r.release();
4178 }
4179
4180 template<class _Tp>
4181 template <class _Yp, class _Dp>
4182 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4183 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp>&& __r,
4184 #else
4185 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp> __r,
4186 #endif
4187                             typename enable_if
4188                             <
4189                                 is_lvalue_reference<_Dp>::value &&
4190                                 !is_array<_Yp>::value &&
4191                                 is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
4192                                 __nat
4193                             >::type)
4194     : __ptr_(__r.get())
4195 {
4196 #if _LIBCPP_STD_VER > 11
4197     if (__ptr_ == nullptr)
4198         __cntrl_ = nullptr;
4199     else
4200 #endif
4201     {
4202         typedef typename __shared_ptr_default_allocator<_Yp>::type _AllocT;
4203         typedef __shared_ptr_pointer<_Yp*,
4204                                      reference_wrapper<typename remove_reference<_Dp>::type>,
4205                                      _AllocT > _CntrlBlk;
4206         __cntrl_ = new _CntrlBlk(__r.get(), ref(__r.get_deleter()), _AllocT());
4207         __enable_weak_this(__r.get(), __r.get());
4208     }
4209     __r.release();
4210 }
4211
4212 #ifndef _LIBCPP_HAS_NO_VARIADICS
4213
4214 template<class _Tp>
4215 template<class ..._Args>
4216 shared_ptr<_Tp>
4217 shared_ptr<_Tp>::make_shared(_Args&& ...__args)
4218 {
4219     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4220     typedef allocator<_CntrlBlk> _A2;
4221     typedef __allocator_destructor<_A2> _D2;
4222     _A2 __a2;
4223     unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4224     ::new(__hold2.get()) _CntrlBlk(__a2, _VSTD::forward<_Args>(__args)...);
4225     shared_ptr<_Tp> __r;
4226     __r.__ptr_ = __hold2.get()->get();
4227     __r.__cntrl_ = __hold2.release();
4228     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4229     return __r;
4230 }
4231
4232 template<class _Tp>
4233 template<class _Alloc, class ..._Args>
4234 shared_ptr<_Tp>
4235 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _Args&& ...__args)
4236 {
4237     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4238     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _A2;
4239     typedef __allocator_destructor<_A2> _D2;
4240     _A2 __a2(__a);
4241     unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4242     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4243         _CntrlBlk(__a, _VSTD::forward<_Args>(__args)...);
4244     shared_ptr<_Tp> __r;
4245     __r.__ptr_ = __hold2.get()->get();
4246     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4247     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4248     return __r;
4249 }
4250
4251 #else  // _LIBCPP_HAS_NO_VARIADICS
4252
4253 template<class _Tp>
4254 shared_ptr<_Tp>
4255 shared_ptr<_Tp>::make_shared()
4256 {
4257     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4258     typedef allocator<_CntrlBlk> _Alloc2;
4259     typedef __allocator_destructor<_Alloc2> _D2;
4260     _Alloc2 __alloc2;
4261     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4262     ::new(__hold2.get()) _CntrlBlk(__alloc2);
4263     shared_ptr<_Tp> __r;
4264     __r.__ptr_ = __hold2.get()->get();
4265     __r.__cntrl_ = __hold2.release();
4266     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4267     return __r;
4268 }
4269
4270 template<class _Tp>
4271 template<class _A0>
4272 shared_ptr<_Tp>
4273 shared_ptr<_Tp>::make_shared(_A0& __a0)
4274 {
4275     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4276     typedef allocator<_CntrlBlk> _Alloc2;
4277     typedef __allocator_destructor<_Alloc2> _D2;
4278     _Alloc2 __alloc2;
4279     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4280     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0);
4281     shared_ptr<_Tp> __r;
4282     __r.__ptr_ = __hold2.get()->get();
4283     __r.__cntrl_ = __hold2.release();
4284     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4285     return __r;
4286 }
4287
4288 template<class _Tp>
4289 template<class _A0, class _A1>
4290 shared_ptr<_Tp>
4291 shared_ptr<_Tp>::make_shared(_A0& __a0, _A1& __a1)
4292 {
4293     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4294     typedef allocator<_CntrlBlk> _Alloc2;
4295     typedef __allocator_destructor<_Alloc2> _D2;
4296     _Alloc2 __alloc2;
4297     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4298     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0, __a1);
4299     shared_ptr<_Tp> __r;
4300     __r.__ptr_ = __hold2.get()->get();
4301     __r.__cntrl_ = __hold2.release();
4302     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4303     return __r;
4304 }
4305
4306 template<class _Tp>
4307 template<class _A0, class _A1, class _A2>
4308 shared_ptr<_Tp>
4309 shared_ptr<_Tp>::make_shared(_A0& __a0, _A1& __a1, _A2& __a2)
4310 {
4311     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4312     typedef allocator<_CntrlBlk> _Alloc2;
4313     typedef __allocator_destructor<_Alloc2> _D2;
4314     _Alloc2 __alloc2;
4315     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4316     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0, __a1, __a2);
4317     shared_ptr<_Tp> __r;
4318     __r.__ptr_ = __hold2.get()->get();
4319     __r.__cntrl_ = __hold2.release();
4320     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4321     return __r;
4322 }
4323
4324 template<class _Tp>
4325 template<class _Alloc>
4326 shared_ptr<_Tp>
4327 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a)
4328 {
4329     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4330     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _Alloc2;
4331     typedef __allocator_destructor<_Alloc2> _D2;
4332     _Alloc2 __alloc2(__a);
4333     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4334     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4335         _CntrlBlk(__a);
4336     shared_ptr<_Tp> __r;
4337     __r.__ptr_ = __hold2.get()->get();
4338     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4339     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4340     return __r;
4341 }
4342
4343 template<class _Tp>
4344 template<class _Alloc, class _A0>
4345 shared_ptr<_Tp>
4346 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0)
4347 {
4348     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4349     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _Alloc2;
4350     typedef __allocator_destructor<_Alloc2> _D2;
4351     _Alloc2 __alloc2(__a);
4352     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4353     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4354         _CntrlBlk(__a, __a0);
4355     shared_ptr<_Tp> __r;
4356     __r.__ptr_ = __hold2.get()->get();
4357     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4358     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4359     return __r;
4360 }
4361
4362 template<class _Tp>
4363 template<class _Alloc, class _A0, class _A1>
4364 shared_ptr<_Tp>
4365 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1)
4366 {
4367     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4368     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _Alloc2;
4369     typedef __allocator_destructor<_Alloc2> _D2;
4370     _Alloc2 __alloc2(__a);
4371     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4372     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4373         _CntrlBlk(__a, __a0, __a1);
4374     shared_ptr<_Tp> __r;
4375     __r.__ptr_ = __hold2.get()->get();
4376     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4377     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4378     return __r;
4379 }
4380
4381 template<class _Tp>
4382 template<class _Alloc, class _A0, class _A1, class _A2>
4383 shared_ptr<_Tp>
4384 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2)
4385 {
4386     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4387     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _Alloc2;
4388     typedef __allocator_destructor<_Alloc2> _D2;
4389     _Alloc2 __alloc2(__a);
4390     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4391     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4392         _CntrlBlk(__a, __a0, __a1, __a2);
4393     shared_ptr<_Tp> __r;
4394     __r.__ptr_ = __hold2.get()->get();
4395     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4396     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4397     return __r;
4398 }
4399
4400 #endif  // _LIBCPP_HAS_NO_VARIADICS
4401
4402 template<class _Tp>
4403 shared_ptr<_Tp>::~shared_ptr()
4404 {
4405     if (__cntrl_)
4406         __cntrl_->__release_shared();
4407 }
4408
4409 template<class _Tp>
4410 inline
4411 shared_ptr<_Tp>&
4412 shared_ptr<_Tp>::operator=(const shared_ptr& __r) _NOEXCEPT
4413 {
4414     shared_ptr(__r).swap(*this);
4415     return *this;
4416 }
4417
4418 template<class _Tp>
4419 template<class _Yp>
4420 inline
4421 typename enable_if
4422 <
4423     is_convertible<_Yp*, typename shared_ptr<_Tp>::element_type*>::value,
4424     shared_ptr<_Tp>&
4425 >::type
4426 shared_ptr<_Tp>::operator=(const shared_ptr<_Yp>& __r) _NOEXCEPT
4427 {
4428     shared_ptr(__r).swap(*this);
4429     return *this;
4430 }
4431
4432 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4433
4434 template<class _Tp>
4435 inline
4436 shared_ptr<_Tp>&
4437 shared_ptr<_Tp>::operator=(shared_ptr&& __r) _NOEXCEPT
4438 {
4439     shared_ptr(_VSTD::move(__r)).swap(*this);
4440     return *this;
4441 }
4442
4443 template<class _Tp>
4444 template<class _Yp>
4445 inline
4446 typename enable_if
4447 <
4448     is_convertible<_Yp*, typename shared_ptr<_Tp>::element_type*>::value,
4449     shared_ptr<_Tp>&
4450 >::type
4451 shared_ptr<_Tp>::operator=(shared_ptr<_Yp>&& __r)
4452 {
4453     shared_ptr(_VSTD::move(__r)).swap(*this);
4454     return *this;
4455 }
4456
4457 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR)
4458 template<class _Tp>
4459 template<class _Yp>
4460 inline
4461 typename enable_if
4462 <
4463     !is_array<_Yp>::value &&
4464     is_convertible<_Yp*, typename shared_ptr<_Tp>::element_type*>::value,
4465     shared_ptr<_Tp>
4466 >::type&
4467 shared_ptr<_Tp>::operator=(auto_ptr<_Yp>&& __r)
4468 {
4469     shared_ptr(_VSTD::move(__r)).swap(*this);
4470     return *this;
4471 }
4472 #endif
4473
4474 template<class _Tp>
4475 template <class _Yp, class _Dp>
4476 inline
4477 typename enable_if
4478 <
4479     !is_array<_Yp>::value &&
4480     is_convertible<typename unique_ptr<_Yp, _Dp>::pointer,
4481                    typename shared_ptr<_Tp>::element_type*>::value,
4482     shared_ptr<_Tp>&
4483 >::type
4484 shared_ptr<_Tp>::operator=(unique_ptr<_Yp, _Dp>&& __r)
4485 {
4486     shared_ptr(_VSTD::move(__r)).swap(*this);
4487     return *this;
4488 }
4489
4490 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4491
4492 #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR)
4493 template<class _Tp>
4494 template<class _Yp>
4495 inline _LIBCPP_INLINE_VISIBILITY
4496 typename enable_if
4497 <
4498     !is_array<_Yp>::value &&
4499     is_convertible<_Yp*, typename shared_ptr<_Tp>::element_type*>::value,
4500     shared_ptr<_Tp>&
4501 >::type
4502 shared_ptr<_Tp>::operator=(auto_ptr<_Yp> __r)
4503 {
4504     shared_ptr(__r).swap(*this);
4505     return *this;
4506 }
4507 #endif
4508
4509 template<class _Tp>
4510 template <class _Yp, class _Dp>
4511 inline _LIBCPP_INLINE_VISIBILITY
4512 typename enable_if
4513 <
4514     !is_array<_Yp>::value &&
4515     is_convertible<typename unique_ptr<_Yp, _Dp>::pointer,
4516                    typename shared_ptr<_Tp>::element_type*>::value,
4517     shared_ptr<_Tp>&
4518 >::type
4519 shared_ptr<_Tp>::operator=(unique_ptr<_Yp, _Dp> __r)
4520 {
4521     shared_ptr(_VSTD::move(__r)).swap(*this);
4522     return *this;
4523 }
4524
4525 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4526
4527 template<class _Tp>
4528 inline
4529 void
4530 shared_ptr<_Tp>::swap(shared_ptr& __r) _NOEXCEPT
4531 {
4532     _VSTD::swap(__ptr_, __r.__ptr_);
4533     _VSTD::swap(__cntrl_, __r.__cntrl_);
4534 }
4535
4536 template<class _Tp>
4537 inline
4538 void
4539 shared_ptr<_Tp>::reset() _NOEXCEPT
4540 {
4541     shared_ptr().swap(*this);
4542 }
4543
4544 template<class _Tp>
4545 template<class _Yp>
4546 inline
4547 typename enable_if
4548 <
4549     is_convertible<_Yp*, typename shared_ptr<_Tp>::element_type*>::value,
4550     void
4551 >::type
4552 shared_ptr<_Tp>::reset(_Yp* __p)
4553 {
4554     shared_ptr(__p).swap(*this);
4555 }
4556
4557 template<class _Tp>
4558 template<class _Yp, class _Dp>
4559 inline
4560 typename enable_if
4561 <
4562     is_convertible<_Yp*, typename shared_ptr<_Tp>::element_type*>::value,
4563     void
4564 >::type
4565 shared_ptr<_Tp>::reset(_Yp* __p, _Dp __d)
4566 {
4567     shared_ptr(__p, __d).swap(*this);
4568 }
4569
4570 template<class _Tp>
4571 template<class _Yp, class _Dp, class _Alloc>
4572 inline
4573 typename enable_if
4574 <
4575     is_convertible<_Yp*, typename shared_ptr<_Tp>::element_type*>::value,
4576     void
4577 >::type
4578 shared_ptr<_Tp>::reset(_Yp* __p, _Dp __d, _Alloc __a)
4579 {
4580     shared_ptr(__p, __d, __a).swap(*this);
4581 }
4582
4583 #ifndef _LIBCPP_HAS_NO_VARIADICS
4584
4585 template<class _Tp, class ..._Args>
4586 inline _LIBCPP_INLINE_VISIBILITY
4587 typename enable_if
4588 <
4589     !is_array<_Tp>::value,
4590     shared_ptr<_Tp>
4591 >::type
4592 make_shared(_Args&& ...__args)
4593 {
4594     return shared_ptr<_Tp>::make_shared(_VSTD::forward<_Args>(__args)...);
4595 }
4596
4597 template<class _Tp, class _Alloc, class ..._Args>
4598 inline _LIBCPP_INLINE_VISIBILITY
4599 typename enable_if
4600 <
4601     !is_array<_Tp>::value,
4602     shared_ptr<_Tp>
4603 >::type
4604 allocate_shared(const _Alloc& __a, _Args&& ...__args)
4605 {
4606     return shared_ptr<_Tp>::allocate_shared(__a, _VSTD::forward<_Args>(__args)...);
4607 }
4608
4609 #else  // _LIBCPP_HAS_NO_VARIADICS
4610
4611 template<class _Tp>
4612 inline _LIBCPP_INLINE_VISIBILITY
4613 shared_ptr<_Tp>
4614 make_shared()
4615 {
4616     return shared_ptr<_Tp>::make_shared();
4617 }
4618
4619 template<class _Tp, class _A0>
4620 inline _LIBCPP_INLINE_VISIBILITY
4621 shared_ptr<_Tp>
4622 make_shared(_A0& __a0)
4623 {
4624     return shared_ptr<_Tp>::make_shared(__a0);
4625 }
4626
4627 template<class _Tp, class _A0, class _A1>
4628 inline _LIBCPP_INLINE_VISIBILITY
4629 shared_ptr<_Tp>
4630 make_shared(_A0& __a0, _A1& __a1)
4631 {
4632     return shared_ptr<_Tp>::make_shared(__a0, __a1);
4633 }
4634
4635 template<class _Tp, class _A0, class _A1, class _A2>
4636 inline _LIBCPP_INLINE_VISIBILITY
4637 shared_ptr<_Tp>
4638 make_shared(_A0& __a0, _A1& __a1, _A2& __a2)
4639 {
4640     return shared_ptr<_Tp>::make_shared(__a0, __a1, __a2);
4641 }
4642
4643 template<class _Tp, class _Alloc>
4644 inline _LIBCPP_INLINE_VISIBILITY
4645 shared_ptr<_Tp>
4646 allocate_shared(const _Alloc& __a)
4647 {
4648     return shared_ptr<_Tp>::allocate_shared(__a);
4649 }
4650
4651 template<class _Tp, class _Alloc, class _A0>
4652 inline _LIBCPP_INLINE_VISIBILITY
4653 shared_ptr<_Tp>
4654 allocate_shared(const _Alloc& __a, _A0& __a0)
4655 {
4656     return shared_ptr<_Tp>::allocate_shared(__a, __a0);
4657 }
4658
4659 template<class _Tp, class _Alloc, class _A0, class _A1>
4660 inline _LIBCPP_INLINE_VISIBILITY
4661 shared_ptr<_Tp>
4662 allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1)
4663 {
4664     return shared_ptr<_Tp>::allocate_shared(__a, __a0, __a1);
4665 }
4666
4667 template<class _Tp, class _Alloc, class _A0, class _A1, class _A2>
4668 inline _LIBCPP_INLINE_VISIBILITY
4669 shared_ptr<_Tp>
4670 allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2)
4671 {
4672     return shared_ptr<_Tp>::allocate_shared(__a, __a0, __a1, __a2);
4673 }
4674
4675 #endif  // _LIBCPP_HAS_NO_VARIADICS
4676
4677 template<class _Tp, class _Up>
4678 inline _LIBCPP_INLINE_VISIBILITY
4679 bool
4680 operator==(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4681 {
4682     return __x.get() == __y.get();
4683 }
4684
4685 template<class _Tp, class _Up>
4686 inline _LIBCPP_INLINE_VISIBILITY
4687 bool
4688 operator!=(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4689 {
4690     return !(__x == __y);
4691 }
4692
4693 template<class _Tp, class _Up>
4694 inline _LIBCPP_INLINE_VISIBILITY
4695 bool
4696 operator<(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4697 {
4698     typedef typename common_type<_Tp*, _Up*>::type _Vp;
4699     return less<_Vp>()(__x.get(), __y.get());
4700 }
4701
4702 template<class _Tp, class _Up>
4703 inline _LIBCPP_INLINE_VISIBILITY
4704 bool
4705 operator>(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4706 {
4707     return __y < __x;
4708 }
4709
4710 template<class _Tp, class _Up>
4711 inline _LIBCPP_INLINE_VISIBILITY
4712 bool
4713 operator<=(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4714 {
4715     return !(__y < __x);
4716 }
4717
4718 template<class _Tp, class _Up>
4719 inline _LIBCPP_INLINE_VISIBILITY
4720 bool
4721 operator>=(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4722 {
4723     return !(__x < __y);
4724 }
4725
4726 template<class _Tp>
4727 inline _LIBCPP_INLINE_VISIBILITY
4728 bool
4729 operator==(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4730 {
4731     return !__x;
4732 }
4733
4734 template<class _Tp>
4735 inline _LIBCPP_INLINE_VISIBILITY
4736 bool
4737 operator==(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4738 {
4739     return !__x;
4740 }
4741
4742 template<class _Tp>
4743 inline _LIBCPP_INLINE_VISIBILITY
4744 bool
4745 operator!=(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4746 {
4747     return static_cast<bool>(__x);
4748 }
4749
4750 template<class _Tp>
4751 inline _LIBCPP_INLINE_VISIBILITY
4752 bool
4753 operator!=(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4754 {
4755     return static_cast<bool>(__x);
4756 }
4757
4758 template<class _Tp>
4759 inline _LIBCPP_INLINE_VISIBILITY
4760 bool
4761 operator<(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4762 {
4763     return less<_Tp*>()(__x.get(), nullptr);
4764 }
4765
4766 template<class _Tp>
4767 inline _LIBCPP_INLINE_VISIBILITY
4768 bool
4769 operator<(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4770 {
4771     return less<_Tp*>()(nullptr, __x.get());
4772 }
4773
4774 template<class _Tp>
4775 inline _LIBCPP_INLINE_VISIBILITY
4776 bool
4777 operator>(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4778 {
4779     return nullptr < __x;
4780 }
4781
4782 template<class _Tp>
4783 inline _LIBCPP_INLINE_VISIBILITY
4784 bool
4785 operator>(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4786 {
4787     return __x < nullptr;
4788 }
4789
4790 template<class _Tp>
4791 inline _LIBCPP_INLINE_VISIBILITY
4792 bool
4793 operator<=(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4794 {
4795     return !(nullptr < __x);
4796 }
4797
4798 template<class _Tp>
4799 inline _LIBCPP_INLINE_VISIBILITY
4800 bool
4801 operator<=(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4802 {
4803     return !(__x < nullptr);
4804 }
4805
4806 template<class _Tp>
4807 inline _LIBCPP_INLINE_VISIBILITY
4808 bool
4809 operator>=(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4810 {
4811     return !(__x < nullptr);
4812 }
4813
4814 template<class _Tp>
4815 inline _LIBCPP_INLINE_VISIBILITY
4816 bool
4817 operator>=(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4818 {
4819     return !(nullptr < __x);
4820 }
4821
4822 template<class _Tp>
4823 inline _LIBCPP_INLINE_VISIBILITY
4824 void
4825 swap(shared_ptr<_Tp>& __x, shared_ptr<_Tp>& __y) _NOEXCEPT
4826 {
4827     __x.swap(__y);
4828 }
4829
4830 template<class _Tp, class _Up>
4831 inline _LIBCPP_INLINE_VISIBILITY
4832 typename enable_if
4833 <
4834     !is_array<_Tp>::value && !is_array<_Up>::value,
4835     shared_ptr<_Tp>
4836 >::type
4837 static_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
4838 {
4839     return shared_ptr<_Tp>(__r, static_cast<_Tp*>(__r.get()));
4840 }
4841
4842 template<class _Tp, class _Up>
4843 inline _LIBCPP_INLINE_VISIBILITY
4844 typename enable_if
4845 <
4846     !is_array<_Tp>::value && !is_array<_Up>::value,
4847     shared_ptr<_Tp>
4848 >::type
4849 dynamic_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
4850 {
4851     _Tp* __p = dynamic_cast<_Tp*>(__r.get());
4852     return __p ? shared_ptr<_Tp>(__r, __p) : shared_ptr<_Tp>();
4853 }
4854
4855 template<class _Tp, class _Up>
4856 typename enable_if
4857 <
4858     is_array<_Tp>::value == is_array<_Up>::value,
4859     shared_ptr<_Tp>
4860 >::type
4861 const_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
4862 {
4863     typedef typename remove_extent<_Tp>::type _RTp;
4864     return shared_ptr<_Tp>(__r, const_cast<_RTp*>(__r.get()));
4865 }
4866
4867 #ifndef _LIBCPP_NO_RTTI
4868
4869 template<class _Dp, class _Tp>
4870 inline _LIBCPP_INLINE_VISIBILITY
4871 _Dp*
4872 get_deleter(const shared_ptr<_Tp>& __p) _NOEXCEPT
4873 {
4874     return __p.template __get_deleter<_Dp>();
4875 }
4876
4877 #endif  // _LIBCPP_NO_RTTI
4878
4879 template<class _Tp>
4880 class _LIBCPP_TEMPLATE_VIS weak_ptr
4881 {
4882 public:
4883     typedef _Tp element_type;
4884 private:
4885     element_type*        __ptr_;
4886     __shared_weak_count* __cntrl_;
4887
4888 public:
4889     _LIBCPP_INLINE_VISIBILITY
4890     _LIBCPP_CONSTEXPR weak_ptr() _NOEXCEPT;
4891     template<class _Yp> _LIBCPP_INLINE_VISIBILITY weak_ptr(shared_ptr<_Yp> const& __r,
4892                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
4893                         _NOEXCEPT;
4894     _LIBCPP_INLINE_VISIBILITY
4895     weak_ptr(weak_ptr const& __r) _NOEXCEPT;
4896     template<class _Yp> _LIBCPP_INLINE_VISIBILITY weak_ptr(weak_ptr<_Yp> const& __r,
4897                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
4898                          _NOEXCEPT;
4899
4900 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4901     _LIBCPP_INLINE_VISIBILITY
4902     weak_ptr(weak_ptr&& __r) _NOEXCEPT;
4903     template<class _Yp> _LIBCPP_INLINE_VISIBILITY weak_ptr(weak_ptr<_Yp>&& __r,
4904                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
4905                          _NOEXCEPT;
4906 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4907     ~weak_ptr();
4908
4909     _LIBCPP_INLINE_VISIBILITY
4910     weak_ptr& operator=(weak_ptr const& __r) _NOEXCEPT;
4911     template<class _Yp>
4912         typename enable_if
4913         <
4914             is_convertible<_Yp*, element_type*>::value,
4915             weak_ptr&
4916         >::type
4917         _LIBCPP_INLINE_VISIBILITY
4918         operator=(weak_ptr<_Yp> const& __r) _NOEXCEPT;
4919
4920 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4921
4922     _LIBCPP_INLINE_VISIBILITY
4923     weak_ptr& operator=(weak_ptr&& __r) _NOEXCEPT;
4924     template<class _Yp>
4925         typename enable_if
4926         <
4927             is_convertible<_Yp*, element_type*>::value,
4928             weak_ptr&
4929         >::type
4930         _LIBCPP_INLINE_VISIBILITY
4931         operator=(weak_ptr<_Yp>&& __r) _NOEXCEPT;
4932
4933 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4934
4935     template<class _Yp>
4936         typename enable_if
4937         <
4938             is_convertible<_Yp*, element_type*>::value,
4939             weak_ptr&
4940         >::type
4941         _LIBCPP_INLINE_VISIBILITY
4942         operator=(shared_ptr<_Yp> const& __r) _NOEXCEPT;
4943
4944     _LIBCPP_INLINE_VISIBILITY
4945     void swap(weak_ptr& __r) _NOEXCEPT;
4946     _LIBCPP_INLINE_VISIBILITY
4947     void reset() _NOEXCEPT;
4948
4949     _LIBCPP_INLINE_VISIBILITY
4950     long use_count() const _NOEXCEPT
4951         {return __cntrl_ ? __cntrl_->use_count() : 0;}
4952     _LIBCPP_INLINE_VISIBILITY
4953     bool expired() const _NOEXCEPT
4954         {return __cntrl_ == 0 || __cntrl_->use_count() == 0;}
4955     shared_ptr<_Tp> lock() const _NOEXCEPT;
4956     template<class _Up>
4957         _LIBCPP_INLINE_VISIBILITY
4958         bool owner_before(const shared_ptr<_Up>& __r) const _NOEXCEPT
4959         {return __cntrl_ < __r.__cntrl_;}
4960     template<class _Up>
4961         _LIBCPP_INLINE_VISIBILITY
4962         bool owner_before(const weak_ptr<_Up>& __r) const _NOEXCEPT
4963         {return __cntrl_ < __r.__cntrl_;}
4964
4965     template <class _Up> friend class _LIBCPP_TEMPLATE_VIS weak_ptr;
4966     template <class _Up> friend class _LIBCPP_TEMPLATE_VIS shared_ptr;
4967 };
4968
4969 template<class _Tp>
4970 inline
4971 _LIBCPP_CONSTEXPR
4972 weak_ptr<_Tp>::weak_ptr() _NOEXCEPT
4973     : __ptr_(0),
4974       __cntrl_(0)
4975 {
4976 }
4977
4978 template<class _Tp>
4979 inline
4980 weak_ptr<_Tp>::weak_ptr(weak_ptr const& __r) _NOEXCEPT
4981     : __ptr_(__r.__ptr_),
4982       __cntrl_(__r.__cntrl_)
4983 {
4984     if (__cntrl_)
4985         __cntrl_->__add_weak();
4986 }
4987
4988 template<class _Tp>
4989 template<class _Yp>
4990 inline
4991 weak_ptr<_Tp>::weak_ptr(shared_ptr<_Yp> const& __r,
4992                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
4993                          _NOEXCEPT
4994     : __ptr_(__r.__ptr_),
4995       __cntrl_(__r.__cntrl_)
4996 {
4997     if (__cntrl_)
4998         __cntrl_->__add_weak();
4999 }
5000
5001 template<class _Tp>
5002 template<class _Yp>
5003 inline
5004 weak_ptr<_Tp>::weak_ptr(weak_ptr<_Yp> const& __r,
5005                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
5006          _NOEXCEPT
5007     : __ptr_(__r.__ptr_),
5008       __cntrl_(__r.__cntrl_)
5009 {
5010     if (__cntrl_)
5011         __cntrl_->__add_weak();
5012 }
5013
5014 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
5015
5016 template<class _Tp>
5017 inline
5018 weak_ptr<_Tp>::weak_ptr(weak_ptr&& __r) _NOEXCEPT
5019     : __ptr_(__r.__ptr_),
5020       __cntrl_(__r.__cntrl_)
5021 {
5022     __r.__ptr_ = 0;
5023     __r.__cntrl_ = 0;
5024 }
5025
5026 template<class _Tp>
5027 template<class _Yp>
5028 inline
5029 weak_ptr<_Tp>::weak_ptr(weak_ptr<_Yp>&& __r,
5030                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
5031          _NOEXCEPT
5032     : __ptr_(__r.__ptr_),
5033       __cntrl_(__r.__cntrl_)
5034 {
5035     __r.__ptr_ = 0;
5036     __r.__cntrl_ = 0;
5037 }
5038
5039 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
5040
5041 template<class _Tp>
5042 weak_ptr<_Tp>::~weak_ptr()
5043 {
5044     if (__cntrl_)
5045         __cntrl_->__release_weak();
5046 }
5047
5048 template<class _Tp>
5049 inline
5050 weak_ptr<_Tp>&
5051 weak_ptr<_Tp>::operator=(weak_ptr const& __r) _NOEXCEPT
5052 {
5053     weak_ptr(__r).swap(*this);
5054     return *this;
5055 }
5056
5057 template<class _Tp>
5058 template<class _Yp>
5059 inline
5060 typename enable_if
5061 <
5062     is_convertible<_Yp*, _Tp*>::value,
5063     weak_ptr<_Tp>&
5064 >::type
5065 weak_ptr<_Tp>::operator=(weak_ptr<_Yp> const& __r) _NOEXCEPT
5066 {
5067     weak_ptr(__r).swap(*this);
5068     return *this;
5069 }
5070
5071 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
5072
5073 template<class _Tp>
5074 inline
5075 weak_ptr<_Tp>&
5076 weak_ptr<_Tp>::operator=(weak_ptr&& __r) _NOEXCEPT
5077 {
5078     weak_ptr(_VSTD::move(__r)).swap(*this);
5079     return *this;
5080 }
5081
5082 template<class _Tp>
5083 template<class _Yp>
5084 inline
5085 typename enable_if
5086 <
5087     is_convertible<_Yp*, _Tp*>::value,
5088     weak_ptr<_Tp>&
5089 >::type
5090 weak_ptr<_Tp>::operator=(weak_ptr<_Yp>&& __r) _NOEXCEPT
5091 {
5092     weak_ptr(_VSTD::move(__r)).swap(*this);
5093     return *this;
5094 }
5095
5096 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
5097
5098 template<class _Tp>
5099 template<class _Yp>
5100 inline
5101 typename enable_if
5102 <
5103     is_convertible<_Yp*, _Tp*>::value,
5104     weak_ptr<_Tp>&
5105 >::type
5106 weak_ptr<_Tp>::operator=(shared_ptr<_Yp> const& __r) _NOEXCEPT
5107 {
5108     weak_ptr(__r).swap(*this);
5109     return *this;
5110 }
5111
5112 template<class _Tp>
5113 inline
5114 void
5115 weak_ptr<_Tp>::swap(weak_ptr& __r) _NOEXCEPT
5116 {
5117     _VSTD::swap(__ptr_, __r.__ptr_);
5118     _VSTD::swap(__cntrl_, __r.__cntrl_);
5119 }
5120
5121 template<class _Tp>
5122 inline _LIBCPP_INLINE_VISIBILITY
5123 void
5124 swap(weak_ptr<_Tp>& __x, weak_ptr<_Tp>& __y) _NOEXCEPT
5125 {
5126     __x.swap(__y);
5127 }
5128
5129 template<class _Tp>
5130 inline
5131 void
5132 weak_ptr<_Tp>::reset() _NOEXCEPT
5133 {
5134     weak_ptr().swap(*this);
5135 }
5136
5137 template<class _Tp>
5138 template<class _Yp>
5139 shared_ptr<_Tp>::shared_ptr(const weak_ptr<_Yp>& __r,
5140                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
5141     : __ptr_(__r.__ptr_),
5142       __cntrl_(__r.__cntrl_ ? __r.__cntrl_->lock() : __r.__cntrl_)
5143 {
5144     if (__cntrl_ == 0)
5145         __throw_bad_weak_ptr();
5146 }
5147
5148 template<class _Tp>
5149 shared_ptr<_Tp>
5150 weak_ptr<_Tp>::lock() const _NOEXCEPT
5151 {
5152     shared_ptr<_Tp> __r;
5153     __r.__cntrl_ = __cntrl_ ? __cntrl_->lock() : __cntrl_;
5154     if (__r.__cntrl_)
5155         __r.__ptr_ = __ptr_;
5156     return __r;
5157 }
5158
5159 #if _LIBCPP_STD_VER > 14
5160 template <class _Tp = void> struct owner_less;
5161 #else
5162 template <class _Tp> struct owner_less;
5163 #endif
5164
5165 template <class _Tp>
5166 struct _LIBCPP_TEMPLATE_VIS owner_less<shared_ptr<_Tp> >
5167     : binary_function<shared_ptr<_Tp>, shared_ptr<_Tp>, bool>
5168 {
5169     typedef bool result_type;
5170     _LIBCPP_INLINE_VISIBILITY
5171     bool operator()(shared_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const _NOEXCEPT
5172         {return __x.owner_before(__y);}
5173     _LIBCPP_INLINE_VISIBILITY
5174     bool operator()(shared_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const _NOEXCEPT
5175         {return __x.owner_before(__y);}
5176     _LIBCPP_INLINE_VISIBILITY
5177     bool operator()(  weak_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const _NOEXCEPT
5178         {return __x.owner_before(__y);}
5179 };
5180
5181 template <class _Tp>
5182 struct _LIBCPP_TEMPLATE_VIS owner_less<weak_ptr<_Tp> >
5183     : binary_function<weak_ptr<_Tp>, weak_ptr<_Tp>, bool>
5184 {
5185     typedef bool result_type;
5186     _LIBCPP_INLINE_VISIBILITY
5187     bool operator()(  weak_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const _NOEXCEPT
5188         {return __x.owner_before(__y);}
5189     _LIBCPP_INLINE_VISIBILITY
5190     bool operator()(shared_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const _NOEXCEPT
5191         {return __x.owner_before(__y);}
5192     _LIBCPP_INLINE_VISIBILITY
5193     bool operator()(  weak_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const _NOEXCEPT
5194         {return __x.owner_before(__y);}
5195 };
5196
5197 #if _LIBCPP_STD_VER > 14
5198 template <>
5199 struct _LIBCPP_TEMPLATE_VIS owner_less<void>
5200 {
5201     template <class _Tp, class _Up>
5202     _LIBCPP_INLINE_VISIBILITY
5203     bool operator()( shared_ptr<_Tp> const& __x, shared_ptr<_Up> const& __y) const _NOEXCEPT
5204         {return __x.owner_before(__y);}
5205     template <class _Tp, class _Up>
5206     _LIBCPP_INLINE_VISIBILITY
5207     bool operator()( shared_ptr<_Tp> const& __x,   weak_ptr<_Up> const& __y) const _NOEXCEPT
5208         {return __x.owner_before(__y);}
5209     template <class _Tp, class _Up>
5210     _LIBCPP_INLINE_VISIBILITY
5211     bool operator()(   weak_ptr<_Tp> const& __x, shared_ptr<_Up> const& __y) const _NOEXCEPT
5212         {return __x.owner_before(__y);}
5213     template <class _Tp, class _Up>
5214     _LIBCPP_INLINE_VISIBILITY
5215     bool operator()(   weak_ptr<_Tp> const& __x,   weak_ptr<_Up> const& __y) const _NOEXCEPT
5216         {return __x.owner_before(__y);}
5217     typedef void is_transparent;
5218 };
5219 #endif
5220
5221 template<class _Tp>
5222 class _LIBCPP_TEMPLATE_VIS enable_shared_from_this
5223 {
5224     mutable weak_ptr<_Tp> __weak_this_;
5225 protected:
5226     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
5227     enable_shared_from_this() _NOEXCEPT {}
5228     _LIBCPP_INLINE_VISIBILITY
5229     enable_shared_from_this(enable_shared_from_this const&) _NOEXCEPT {}
5230     _LIBCPP_INLINE_VISIBILITY
5231     enable_shared_from_this& operator=(enable_shared_from_this const&) _NOEXCEPT
5232         {return *this;}
5233     _LIBCPP_INLINE_VISIBILITY
5234     ~enable_shared_from_this() {}
5235 public:
5236     _LIBCPP_INLINE_VISIBILITY
5237     shared_ptr<_Tp> shared_from_this()
5238         {return shared_ptr<_Tp>(__weak_this_);}
5239     _LIBCPP_INLINE_VISIBILITY
5240     shared_ptr<_Tp const> shared_from_this() const
5241         {return shared_ptr<const _Tp>(__weak_this_);}
5242
5243 #if _LIBCPP_STD_VER > 14
5244     _LIBCPP_INLINE_VISIBILITY
5245     weak_ptr<_Tp> weak_from_this() _NOEXCEPT
5246        { return __weak_this_; }
5247
5248     _LIBCPP_INLINE_VISIBILITY
5249     weak_ptr<const _Tp> weak_from_this() const _NOEXCEPT
5250         { return __weak_this_; }
5251 #endif // _LIBCPP_STD_VER > 14
5252
5253     template <class _Up> friend class shared_ptr;
5254 };
5255
5256 template <class _Tp>
5257 struct _LIBCPP_TEMPLATE_VIS hash<shared_ptr<_Tp> >
5258 {
5259     typedef shared_ptr<_Tp>      argument_type;
5260     typedef size_t               result_type;
5261
5262     _LIBCPP_INLINE_VISIBILITY
5263     result_type operator()(const argument_type& __ptr) const _NOEXCEPT
5264     {
5265         return hash<_Tp*>()(__ptr.get());
5266     }
5267 };
5268
5269 template<class _CharT, class _Traits, class _Yp>
5270 inline _LIBCPP_INLINE_VISIBILITY
5271 basic_ostream<_CharT, _Traits>&
5272 operator<<(basic_ostream<_CharT, _Traits>& __os, shared_ptr<_Yp> const& __p);
5273
5274
5275 #if !defined(_LIBCPP_HAS_NO_ATOMIC_HEADER)
5276
5277 class _LIBCPP_TYPE_VIS __sp_mut
5278 {
5279     void* __lx;
5280 public:
5281     void lock() _NOEXCEPT;
5282     void unlock() _NOEXCEPT;
5283
5284 private:
5285     _LIBCPP_CONSTEXPR __sp_mut(void*) _NOEXCEPT;
5286     __sp_mut(const __sp_mut&);
5287     __sp_mut& operator=(const __sp_mut&);
5288
5289     friend _LIBCPP_FUNC_VIS __sp_mut& __get_sp_mut(const void*);
5290 };
5291
5292 _LIBCPP_FUNC_VIS _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5293 __sp_mut& __get_sp_mut(const void*);
5294
5295 template <class _Tp>
5296 inline _LIBCPP_INLINE_VISIBILITY
5297 bool
5298 atomic_is_lock_free(const shared_ptr<_Tp>*)
5299 {
5300     return false;
5301 }
5302
5303 template <class _Tp>
5304 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5305 shared_ptr<_Tp>
5306 atomic_load(const shared_ptr<_Tp>* __p)
5307 {
5308     __sp_mut& __m = __get_sp_mut(__p);
5309     __m.lock();
5310     shared_ptr<_Tp> __q = *__p;
5311     __m.unlock();
5312     return __q;
5313 }
5314
5315 template <class _Tp>
5316 inline _LIBCPP_INLINE_VISIBILITY
5317 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5318 shared_ptr<_Tp>
5319 atomic_load_explicit(const shared_ptr<_Tp>* __p, memory_order)
5320 {
5321     return atomic_load(__p);
5322 }
5323
5324 template <class _Tp>
5325 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5326 void
5327 atomic_store(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r)
5328 {
5329     __sp_mut& __m = __get_sp_mut(__p);
5330     __m.lock();
5331     __p->swap(__r);
5332     __m.unlock();
5333 }
5334
5335 template <class _Tp>
5336 inline _LIBCPP_INLINE_VISIBILITY
5337 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5338 void
5339 atomic_store_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r, memory_order)
5340 {
5341     atomic_store(__p, __r);
5342 }
5343
5344 template <class _Tp>
5345 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5346 shared_ptr<_Tp>
5347 atomic_exchange(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r)
5348 {
5349     __sp_mut& __m = __get_sp_mut(__p);
5350     __m.lock();
5351     __p->swap(__r);
5352     __m.unlock();
5353     return __r;
5354 }
5355
5356 template <class _Tp>
5357 inline _LIBCPP_INLINE_VISIBILITY
5358 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5359 shared_ptr<_Tp>
5360 atomic_exchange_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r, memory_order)
5361 {
5362     return atomic_exchange(__p, __r);
5363 }
5364
5365 template <class _Tp>
5366 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5367 bool
5368 atomic_compare_exchange_strong(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v, shared_ptr<_Tp> __w)
5369 {
5370     shared_ptr<_Tp> __temp;
5371     __sp_mut& __m = __get_sp_mut(__p);
5372     __m.lock();
5373     if (__p->__owner_equivalent(*__v))
5374     {
5375         _VSTD::swap(__temp, *__p);
5376         *__p = __w;
5377         __m.unlock();
5378         return true;
5379     }
5380     _VSTD::swap(__temp, *__v);
5381     *__v = *__p;
5382     __m.unlock();
5383     return false;
5384 }
5385
5386 template <class _Tp>
5387 inline _LIBCPP_INLINE_VISIBILITY
5388 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5389 bool
5390 atomic_compare_exchange_weak(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v, shared_ptr<_Tp> __w)
5391 {
5392     return atomic_compare_exchange_strong(__p, __v, __w);
5393 }
5394
5395 template <class _Tp>
5396 inline _LIBCPP_INLINE_VISIBILITY
5397 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5398 bool
5399 atomic_compare_exchange_strong_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v,
5400                                         shared_ptr<_Tp> __w, memory_order, memory_order)
5401 {
5402     return atomic_compare_exchange_strong(__p, __v, __w);
5403 }
5404
5405 template <class _Tp>
5406 inline _LIBCPP_INLINE_VISIBILITY
5407 _LIBCPP_AVAILABILITY_ATOMIC_SHARED_PTR
5408 bool
5409 atomic_compare_exchange_weak_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v,
5410                                       shared_ptr<_Tp> __w, memory_order, memory_order)
5411 {
5412     return atomic_compare_exchange_weak(__p, __v, __w);
5413 }
5414
5415 #endif  // !defined(_LIBCPP_HAS_NO_ATOMIC_HEADER)
5416
5417 //enum class
5418 #if defined(_LIBCPP_ABI_POINTER_SAFETY_ENUM_TYPE)
5419 # ifndef _LIBCPP_CXX03_LANG
5420 enum class pointer_safety : unsigned char {
5421   relaxed,
5422   preferred,
5423   strict
5424 };
5425 # endif
5426 #else
5427 struct _LIBCPP_TYPE_VIS pointer_safety
5428 {
5429     enum __lx
5430     {
5431         relaxed,
5432         preferred,
5433         strict
5434     };
5435
5436     __lx __v_;
5437
5438     _LIBCPP_INLINE_VISIBILITY
5439     pointer_safety() : __v_() {}
5440
5441     _LIBCPP_INLINE_VISIBILITY
5442     pointer_safety(__lx __v) : __v_(__v) {}
5443     _LIBCPP_INLINE_VISIBILITY
5444     operator int() const {return __v_;}
5445 };
5446 #endif
5447
5448 #if !defined(_LIBCPP_ABI_POINTER_SAFETY_ENUM_TYPE) && \
5449     defined(_LIBCPP_BUILDING_MEMORY)
5450 _LIBCPP_FUNC_VIS pointer_safety get_pointer_safety() _NOEXCEPT;
5451 #else
5452 // This function is only offered in C++03 under ABI v1.
5453 # if !defined(_LIBCPP_ABI_POINTER_SAFETY_ENUM_TYPE) || !defined(_LIBCPP_CXX03_LANG)
5454 inline _LIBCPP_INLINE_VISIBILITY
5455 pointer_safety get_pointer_safety() _NOEXCEPT {
5456   return pointer_safety::relaxed;
5457 }
5458 # endif
5459 #endif
5460
5461
5462 _LIBCPP_FUNC_VIS void declare_reachable(void* __p);
5463 _LIBCPP_FUNC_VIS void declare_no_pointers(char* __p, size_t __n);
5464 _LIBCPP_FUNC_VIS void undeclare_no_pointers(char* __p, size_t __n);
5465 _LIBCPP_FUNC_VIS void* __undeclare_reachable(void* __p);
5466
5467 template <class _Tp>
5468 inline _LIBCPP_INLINE_VISIBILITY
5469 _Tp*
5470 undeclare_reachable(_Tp* __p)
5471 {
5472     return static_cast<_Tp*>(__undeclare_reachable(__p));
5473 }
5474
5475 _LIBCPP_FUNC_VIS void* align(size_t __align, size_t __sz, void*& __ptr, size_t& __space);
5476
5477 // --- Helper for container swap --
5478 template <typename _Alloc>
5479 inline _LIBCPP_INLINE_VISIBILITY
5480 void __swap_allocator(_Alloc & __a1, _Alloc & __a2)
5481 #if _LIBCPP_STD_VER >= 14
5482     _NOEXCEPT
5483 #else
5484     _NOEXCEPT_(__is_nothrow_swappable<_Alloc>::value)
5485 #endif
5486 {
5487     __swap_allocator(__a1, __a2,
5488       integral_constant<bool, _VSTD::allocator_traits<_Alloc>::propagate_on_container_swap::value>());
5489 }
5490
5491 template <typename _Alloc>
5492 _LIBCPP_INLINE_VISIBILITY
5493 void __swap_allocator(_Alloc & __a1, _Alloc & __a2, true_type)
5494 #if _LIBCPP_STD_VER >= 14
5495     _NOEXCEPT
5496 #else
5497     _NOEXCEPT_(__is_nothrow_swappable<_Alloc>::value)
5498 #endif
5499 {
5500     using _VSTD::swap;
5501     swap(__a1, __a2);
5502 }
5503
5504 template <typename _Alloc>
5505 inline _LIBCPP_INLINE_VISIBILITY
5506 void __swap_allocator(_Alloc &, _Alloc &, false_type) _NOEXCEPT {}
5507
5508 template <typename _Alloc, typename _Traits=allocator_traits<_Alloc> >
5509 struct __noexcept_move_assign_container : public integral_constant<bool,
5510     _Traits::propagate_on_container_move_assignment::value
5511 #if _LIBCPP_STD_VER > 14
5512         || _Traits::is_always_equal::value
5513 #else
5514         && is_nothrow_move_assignable<_Alloc>::value
5515 #endif
5516     > {};
5517
5518
5519 #ifndef _LIBCPP_HAS_NO_VARIADICS
5520 template <class _Tp, class _Alloc>
5521 struct __temp_value {
5522     typedef allocator_traits<_Alloc> _Traits;
5523
5524     typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __v;
5525     _Alloc &__a;
5526
5527     _Tp *__addr() { return reinterpret_cast<_Tp *>(addressof(__v)); }
5528     _Tp &   get() { return *__addr(); }
5529
5530     template<class... _Args>
5531     __temp_value(_Alloc &__alloc, _Args&& ... __args) : __a(__alloc)
5532     { _Traits::construct(__a, __addr(), _VSTD::forward<_Args>(__args)...); }
5533
5534     ~__temp_value() { _Traits::destroy(__a, __addr()); }
5535     };
5536 #endif
5537
5538 _LIBCPP_END_NAMESPACE_STD
5539
5540 _LIBCPP_POP_MACROS
5541
5542 #endif  // _LIBCPP_MEMORY