contrib/libc++/include/memory

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