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