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