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 #if _LIBCPP_STD_VER > 14
3888     typedef weak_ptr<_Tp> weak_type;
3889 #endif
3890 private:
3891     element_type*      __ptr_;
3892     __shared_weak_count* __cntrl_;
3893
3894     struct __nat {int __for_bool_;};
3895 public:
3896     _LIBCPP_INLINE_VISIBILITY
3897     _LIBCPP_CONSTEXPR shared_ptr() _NOEXCEPT;
3898     _LIBCPP_INLINE_VISIBILITY
3899     _LIBCPP_CONSTEXPR shared_ptr(nullptr_t) _NOEXCEPT;
3900     template<class _Yp>
3901         explicit shared_ptr(_Yp* __p,
3902                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3903     template<class _Yp, class _Dp>
3904         shared_ptr(_Yp* __p, _Dp __d,
3905                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3906     template<class _Yp, class _Dp, class _Alloc>
3907         shared_ptr(_Yp* __p, _Dp __d, _Alloc __a,
3908                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3909     template <class _Dp> shared_ptr(nullptr_t __p, _Dp __d);
3910     template <class _Dp, class _Alloc> shared_ptr(nullptr_t __p, _Dp __d, _Alloc __a);
3911     template<class _Yp> _LIBCPP_INLINE_VISIBILITY shared_ptr(const shared_ptr<_Yp>& __r, element_type* __p) _NOEXCEPT;
3912     _LIBCPP_INLINE_VISIBILITY
3913     shared_ptr(const shared_ptr& __r) _NOEXCEPT;
3914     template<class _Yp>
3915         _LIBCPP_INLINE_VISIBILITY
3916         shared_ptr(const shared_ptr<_Yp>& __r,
3917                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type = __nat())
3918                        _NOEXCEPT;
3919 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3920     _LIBCPP_INLINE_VISIBILITY
3921     shared_ptr(shared_ptr&& __r) _NOEXCEPT;
3922     template<class _Yp> _LIBCPP_INLINE_VISIBILITY  shared_ptr(shared_ptr<_Yp>&& __r,
3923                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type = __nat())
3924                        _NOEXCEPT;
3925 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3926     template<class _Yp> explicit shared_ptr(const weak_ptr<_Yp>& __r,
3927                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type= __nat());
3928 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3929     template<class _Yp>
3930         shared_ptr(auto_ptr<_Yp>&& __r,
3931                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3932 #else
3933     template<class _Yp>
3934         shared_ptr(auto_ptr<_Yp> __r,
3935                    typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type = __nat());
3936 #endif
3937 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3938     template <class _Yp, class _Dp>
3939         shared_ptr(unique_ptr<_Yp, _Dp>&&,
3940                    typename enable_if
3941                    <
3942                        !is_lvalue_reference<_Dp>::value &&
3943                        !is_array<_Yp>::value &&
3944                        is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3945                        __nat
3946                    >::type = __nat());
3947     template <class _Yp, class _Dp>
3948         shared_ptr(unique_ptr<_Yp, _Dp>&&,
3949                    typename enable_if
3950                    <
3951                        is_lvalue_reference<_Dp>::value &&
3952                        !is_array<_Yp>::value &&
3953                        is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3954                        __nat
3955                    >::type = __nat());
3956 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3957     template <class _Yp, class _Dp>
3958         shared_ptr(unique_ptr<_Yp, _Dp>,
3959                    typename enable_if
3960                    <
3961                        !is_lvalue_reference<_Dp>::value &&
3962                        !is_array<_Yp>::value &&
3963                        is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3964                        __nat
3965                    >::type = __nat());
3966     template <class _Yp, class _Dp>
3967         shared_ptr(unique_ptr<_Yp, _Dp>,
3968                    typename enable_if
3969                    <
3970                        is_lvalue_reference<_Dp>::value &&
3971                        !is_array<_Yp>::value &&
3972                        is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3973                        __nat
3974                    >::type = __nat());
3975 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3976
3977     ~shared_ptr();
3978
3979     _LIBCPP_INLINE_VISIBILITY
3980     shared_ptr& operator=(const shared_ptr& __r) _NOEXCEPT;
3981     template<class _Yp>
3982         typename enable_if
3983         <
3984             is_convertible<_Yp*, element_type*>::value,
3985             shared_ptr&
3986         >::type
3987         _LIBCPP_INLINE_VISIBILITY
3988         operator=(const shared_ptr<_Yp>& __r) _NOEXCEPT;
3989 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3990     _LIBCPP_INLINE_VISIBILITY
3991     shared_ptr& operator=(shared_ptr&& __r) _NOEXCEPT;
3992     template<class _Yp>
3993         typename enable_if
3994         <
3995             is_convertible<_Yp*, element_type*>::value,
3996             shared_ptr<_Tp>&
3997         >::type
3998         _LIBCPP_INLINE_VISIBILITY
3999         operator=(shared_ptr<_Yp>&& __r);
4000     template<class _Yp>
4001         _LIBCPP_INLINE_VISIBILITY
4002         typename enable_if
4003         <
4004             !is_array<_Yp>::value &&
4005             is_convertible<_Yp*, element_type*>::value,
4006             shared_ptr
4007         >::type&
4008         operator=(auto_ptr<_Yp>&& __r);
4009 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4010     template<class _Yp>
4011         _LIBCPP_INLINE_VISIBILITY
4012         typename enable_if
4013         <
4014             !is_array<_Yp>::value &&
4015             is_convertible<_Yp*, element_type*>::value,
4016             shared_ptr&
4017         >::type
4018         operator=(auto_ptr<_Yp> __r);
4019 #endif
4020     template <class _Yp, class _Dp>
4021         typename enable_if
4022         <
4023             !is_array<_Yp>::value &&
4024             is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
4025             shared_ptr&
4026         >::type
4027 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4028         _LIBCPP_INLINE_VISIBILITY
4029         operator=(unique_ptr<_Yp, _Dp>&& __r);
4030 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4031         _LIBCPP_INLINE_VISIBILITY
4032         operator=(unique_ptr<_Yp, _Dp> __r);
4033 #endif
4034
4035     _LIBCPP_INLINE_VISIBILITY
4036     void swap(shared_ptr& __r) _NOEXCEPT;
4037     _LIBCPP_INLINE_VISIBILITY
4038     void reset() _NOEXCEPT;
4039     template<class _Yp>
4040         typename enable_if
4041         <
4042             is_convertible<_Yp*, element_type*>::value,
4043             void
4044         >::type
4045         _LIBCPP_INLINE_VISIBILITY
4046         reset(_Yp* __p);
4047     template<class _Yp, class _Dp>
4048         typename enable_if
4049         <
4050             is_convertible<_Yp*, element_type*>::value,
4051             void
4052         >::type
4053         _LIBCPP_INLINE_VISIBILITY
4054         reset(_Yp* __p, _Dp __d);
4055     template<class _Yp, class _Dp, class _Alloc>
4056         typename enable_if
4057         <
4058             is_convertible<_Yp*, element_type*>::value,
4059             void
4060         >::type
4061         _LIBCPP_INLINE_VISIBILITY
4062         reset(_Yp* __p, _Dp __d, _Alloc __a);
4063
4064     _LIBCPP_INLINE_VISIBILITY
4065     element_type* get() const _NOEXCEPT {return __ptr_;}
4066     _LIBCPP_INLINE_VISIBILITY
4067     typename add_lvalue_reference<element_type>::type operator*() const _NOEXCEPT
4068         {return *__ptr_;}
4069     _LIBCPP_INLINE_VISIBILITY
4070     element_type* operator->() const _NOEXCEPT {return __ptr_;}
4071     _LIBCPP_INLINE_VISIBILITY
4072     long use_count() const _NOEXCEPT {return __cntrl_ ? __cntrl_->use_count() : 0;}
4073     _LIBCPP_INLINE_VISIBILITY
4074     bool unique() const _NOEXCEPT {return use_count() == 1;}
4075     _LIBCPP_INLINE_VISIBILITY
4076     _LIBCPP_EXPLICIT operator bool() const _NOEXCEPT {return get() != 0;}
4077     template <class _Up>
4078         _LIBCPP_INLINE_VISIBILITY
4079         bool owner_before(shared_ptr<_Up> const& __p) const
4080         {return __cntrl_ < __p.__cntrl_;}
4081     template <class _Up>
4082         _LIBCPP_INLINE_VISIBILITY
4083         bool owner_before(weak_ptr<_Up> const& __p) const
4084         {return __cntrl_ < __p.__cntrl_;}
4085     _LIBCPP_INLINE_VISIBILITY
4086     bool
4087     __owner_equivalent(const shared_ptr& __p) const
4088         {return __cntrl_ == __p.__cntrl_;}
4089
4090 #ifndef _LIBCPP_NO_RTTI
4091     template <class _Dp>
4092         _LIBCPP_INLINE_VISIBILITY
4093         _Dp* __get_deleter() const _NOEXCEPT
4094             {return (_Dp*)(__cntrl_ ? __cntrl_->__get_deleter(typeid(_Dp)) : 0);}
4095 #endif  // _LIBCPP_NO_RTTI
4096
4097 #ifndef _LIBCPP_HAS_NO_VARIADICS
4098
4099     template<class ..._Args>
4100         static
4101         shared_ptr<_Tp>
4102         make_shared(_Args&& ...__args);
4103
4104     template<class _Alloc, class ..._Args>
4105         static
4106         shared_ptr<_Tp>
4107         allocate_shared(const _Alloc& __a, _Args&& ...__args);
4108
4109 #else  // _LIBCPP_HAS_NO_VARIADICS
4110
4111     static shared_ptr<_Tp> make_shared();
4112
4113     template<class _A0>
4114         static shared_ptr<_Tp> make_shared(_A0&);
4115
4116     template<class _A0, class _A1>
4117         static shared_ptr<_Tp> make_shared(_A0&, _A1&);
4118
4119     template<class _A0, class _A1, class _A2>
4120         static shared_ptr<_Tp> make_shared(_A0&, _A1&, _A2&);
4121
4122     template<class _Alloc>
4123         static shared_ptr<_Tp>
4124         allocate_shared(const _Alloc& __a);
4125
4126     template<class _Alloc, class _A0>
4127         static shared_ptr<_Tp>
4128         allocate_shared(const _Alloc& __a, _A0& __a0);
4129
4130     template<class _Alloc, class _A0, class _A1>
4131         static shared_ptr<_Tp>
4132         allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1);
4133
4134     template<class _Alloc, class _A0, class _A1, class _A2>
4135         static shared_ptr<_Tp>
4136         allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2);
4137
4138 #endif  // _LIBCPP_HAS_NO_VARIADICS
4139
4140 private:
4141
4142     template <class _Yp, class _OrigPtr>
4143         _LIBCPP_INLINE_VISIBILITY
4144         void
4145         __enable_weak_this(const enable_shared_from_this<_Yp>* __e,
4146                            _OrigPtr* __ptr) _NOEXCEPT
4147         {
4148             typedef typename remove_cv<_Yp>::type _RawYp;
4149             if (__e && __e->__weak_this_.expired())
4150             {
4151                 __e->__weak_this_ = shared_ptr<_RawYp>(*this,
4152                     const_cast<_RawYp*>(static_cast<const _Yp*>(__ptr)));
4153             }
4154         }
4155
4156     _LIBCPP_INLINE_VISIBILITY
4157     void __enable_weak_this(const volatile void*, const volatile void*) _NOEXCEPT {}
4158
4159     template <class _Up> friend class _LIBCPP_TEMPLATE_VIS shared_ptr;
4160     template <class _Up> friend class _LIBCPP_TEMPLATE_VIS weak_ptr;
4161 };
4162
4163 template<class _Tp>
4164 inline
4165 _LIBCPP_CONSTEXPR
4166 shared_ptr<_Tp>::shared_ptr() _NOEXCEPT
4167     : __ptr_(0),
4168       __cntrl_(0)
4169 {
4170 }
4171
4172 template<class _Tp>
4173 inline
4174 _LIBCPP_CONSTEXPR
4175 shared_ptr<_Tp>::shared_ptr(nullptr_t) _NOEXCEPT
4176     : __ptr_(0),
4177       __cntrl_(0)
4178 {
4179 }
4180
4181 template<class _Tp>
4182 template<class _Yp>
4183 shared_ptr<_Tp>::shared_ptr(_Yp* __p,
4184                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
4185     : __ptr_(__p)
4186 {
4187     unique_ptr<_Yp> __hold(__p);
4188     typedef __shared_ptr_pointer<_Yp*, default_delete<_Yp>, allocator<_Yp> > _CntrlBlk;
4189     __cntrl_ = new _CntrlBlk(__p, default_delete<_Yp>(), allocator<_Yp>());
4190     __hold.release();
4191     __enable_weak_this(__p, __p);
4192 }
4193
4194 template<class _Tp>
4195 template<class _Yp, class _Dp>
4196 shared_ptr<_Tp>::shared_ptr(_Yp* __p, _Dp __d,
4197                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
4198     : __ptr_(__p)
4199 {
4200 #ifndef _LIBCPP_NO_EXCEPTIONS
4201     try
4202     {
4203 #endif  // _LIBCPP_NO_EXCEPTIONS
4204         typedef __shared_ptr_pointer<_Yp*, _Dp, allocator<_Yp> > _CntrlBlk;
4205         __cntrl_ = new _CntrlBlk(__p, __d, allocator<_Yp>());
4206         __enable_weak_this(__p, __p);
4207 #ifndef _LIBCPP_NO_EXCEPTIONS
4208     }
4209     catch (...)
4210     {
4211         __d(__p);
4212         throw;
4213     }
4214 #endif  // _LIBCPP_NO_EXCEPTIONS
4215 }
4216
4217 template<class _Tp>
4218 template<class _Dp>
4219 shared_ptr<_Tp>::shared_ptr(nullptr_t __p, _Dp __d)
4220     : __ptr_(0)
4221 {
4222 #ifndef _LIBCPP_NO_EXCEPTIONS
4223     try
4224     {
4225 #endif  // _LIBCPP_NO_EXCEPTIONS
4226         typedef __shared_ptr_pointer<nullptr_t, _Dp, allocator<_Tp> > _CntrlBlk;
4227         __cntrl_ = new _CntrlBlk(__p, __d, allocator<_Tp>());
4228 #ifndef _LIBCPP_NO_EXCEPTIONS
4229     }
4230     catch (...)
4231     {
4232         __d(__p);
4233         throw;
4234     }
4235 #endif  // _LIBCPP_NO_EXCEPTIONS
4236 }
4237
4238 template<class _Tp>
4239 template<class _Yp, class _Dp, class _Alloc>
4240 shared_ptr<_Tp>::shared_ptr(_Yp* __p, _Dp __d, _Alloc __a,
4241                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
4242     : __ptr_(__p)
4243 {
4244 #ifndef _LIBCPP_NO_EXCEPTIONS
4245     try
4246     {
4247 #endif  // _LIBCPP_NO_EXCEPTIONS
4248         typedef __shared_ptr_pointer<_Yp*, _Dp, _Alloc> _CntrlBlk;
4249         typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _A2;
4250         typedef __allocator_destructor<_A2> _D2;
4251         _A2 __a2(__a);
4252         unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4253         ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4254             _CntrlBlk(__p, __d, __a);
4255         __cntrl_ = _VSTD::addressof(*__hold2.release());
4256         __enable_weak_this(__p, __p);
4257 #ifndef _LIBCPP_NO_EXCEPTIONS
4258     }
4259     catch (...)
4260     {
4261         __d(__p);
4262         throw;
4263     }
4264 #endif  // _LIBCPP_NO_EXCEPTIONS
4265 }
4266
4267 template<class _Tp>
4268 template<class _Dp, class _Alloc>
4269 shared_ptr<_Tp>::shared_ptr(nullptr_t __p, _Dp __d, _Alloc __a)
4270     : __ptr_(0)
4271 {
4272 #ifndef _LIBCPP_NO_EXCEPTIONS
4273     try
4274     {
4275 #endif  // _LIBCPP_NO_EXCEPTIONS
4276         typedef __shared_ptr_pointer<nullptr_t, _Dp, _Alloc> _CntrlBlk;
4277         typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _A2;
4278         typedef __allocator_destructor<_A2> _D2;
4279         _A2 __a2(__a);
4280         unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4281         ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4282             _CntrlBlk(__p, __d, __a);
4283         __cntrl_ = _VSTD::addressof(*__hold2.release());
4284 #ifndef _LIBCPP_NO_EXCEPTIONS
4285     }
4286     catch (...)
4287     {
4288         __d(__p);
4289         throw;
4290     }
4291 #endif  // _LIBCPP_NO_EXCEPTIONS
4292 }
4293
4294 template<class _Tp>
4295 template<class _Yp>
4296 inline
4297 shared_ptr<_Tp>::shared_ptr(const shared_ptr<_Yp>& __r, element_type *__p) _NOEXCEPT
4298     : __ptr_(__p),
4299       __cntrl_(__r.__cntrl_)
4300 {
4301     if (__cntrl_)
4302         __cntrl_->__add_shared();
4303 }
4304
4305 template<class _Tp>
4306 inline
4307 shared_ptr<_Tp>::shared_ptr(const shared_ptr& __r) _NOEXCEPT
4308     : __ptr_(__r.__ptr_),
4309       __cntrl_(__r.__cntrl_)
4310 {
4311     if (__cntrl_)
4312         __cntrl_->__add_shared();
4313 }
4314
4315 template<class _Tp>
4316 template<class _Yp>
4317 inline
4318 shared_ptr<_Tp>::shared_ptr(const shared_ptr<_Yp>& __r,
4319                             typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type)
4320          _NOEXCEPT
4321     : __ptr_(__r.__ptr_),
4322       __cntrl_(__r.__cntrl_)
4323 {
4324     if (__cntrl_)
4325         __cntrl_->__add_shared();
4326 }
4327
4328 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4329
4330 template<class _Tp>
4331 inline
4332 shared_ptr<_Tp>::shared_ptr(shared_ptr&& __r) _NOEXCEPT
4333     : __ptr_(__r.__ptr_),
4334       __cntrl_(__r.__cntrl_)
4335 {
4336     __r.__ptr_ = 0;
4337     __r.__cntrl_ = 0;
4338 }
4339
4340 template<class _Tp>
4341 template<class _Yp>
4342 inline
4343 shared_ptr<_Tp>::shared_ptr(shared_ptr<_Yp>&& __r,
4344                             typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type)
4345          _NOEXCEPT
4346     : __ptr_(__r.__ptr_),
4347       __cntrl_(__r.__cntrl_)
4348 {
4349     __r.__ptr_ = 0;
4350     __r.__cntrl_ = 0;
4351 }
4352
4353 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4354
4355 template<class _Tp>
4356 template<class _Yp>
4357 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4358 shared_ptr<_Tp>::shared_ptr(auto_ptr<_Yp>&& __r,
4359 #else
4360 shared_ptr<_Tp>::shared_ptr(auto_ptr<_Yp> __r,
4361 #endif
4362                             typename enable_if<is_convertible<_Yp*, element_type*>::value, __nat>::type)
4363     : __ptr_(__r.get())
4364 {
4365     typedef __shared_ptr_pointer<_Yp*, default_delete<_Yp>, allocator<_Yp> > _CntrlBlk;
4366     __cntrl_ = new _CntrlBlk(__r.get(), default_delete<_Yp>(), allocator<_Yp>());
4367     __enable_weak_this(__r.get(), __r.get());
4368     __r.release();
4369 }
4370
4371 template<class _Tp>
4372 template <class _Yp, class _Dp>
4373 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4374 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp>&& __r,
4375 #else
4376 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp> __r,
4377 #endif
4378                             typename enable_if
4379                             <
4380                                 !is_lvalue_reference<_Dp>::value &&
4381                                 !is_array<_Yp>::value &&
4382                                 is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
4383                                 __nat
4384                             >::type)
4385     : __ptr_(__r.get())
4386 {
4387 #if _LIBCPP_STD_VER > 11
4388     if (__ptr_ == nullptr)
4389         __cntrl_ = nullptr;
4390     else
4391 #endif
4392     {
4393         typedef __shared_ptr_pointer<_Yp*, _Dp, allocator<_Yp> > _CntrlBlk;
4394         __cntrl_ = new _CntrlBlk(__r.get(), __r.get_deleter(), allocator<_Yp>());
4395         __enable_weak_this(__r.get(), __r.get());
4396     }
4397     __r.release();
4398 }
4399
4400 template<class _Tp>
4401 template <class _Yp, class _Dp>
4402 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4403 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp>&& __r,
4404 #else
4405 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp> __r,
4406 #endif
4407                             typename enable_if
4408                             <
4409                                 is_lvalue_reference<_Dp>::value &&
4410                                 !is_array<_Yp>::value &&
4411                                 is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
4412                                 __nat
4413                             >::type)
4414     : __ptr_(__r.get())
4415 {
4416 #if _LIBCPP_STD_VER > 11
4417     if (__ptr_ == nullptr)
4418         __cntrl_ = nullptr;
4419     else
4420 #endif
4421     {
4422         typedef __shared_ptr_pointer<_Yp*,
4423                                      reference_wrapper<typename remove_reference<_Dp>::type>,
4424                                      allocator<_Yp> > _CntrlBlk;
4425         __cntrl_ = new _CntrlBlk(__r.get(), ref(__r.get_deleter()), allocator<_Yp>());
4426         __enable_weak_this(__r.get(), __r.get());
4427     }
4428     __r.release();
4429 }
4430
4431 #ifndef _LIBCPP_HAS_NO_VARIADICS
4432
4433 template<class _Tp>
4434 template<class ..._Args>
4435 shared_ptr<_Tp>
4436 shared_ptr<_Tp>::make_shared(_Args&& ...__args)
4437 {
4438     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4439     typedef allocator<_CntrlBlk> _A2;
4440     typedef __allocator_destructor<_A2> _D2;
4441     _A2 __a2;
4442     unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4443     ::new(__hold2.get()) _CntrlBlk(__a2, _VSTD::forward<_Args>(__args)...);
4444     shared_ptr<_Tp> __r;
4445     __r.__ptr_ = __hold2.get()->get();
4446     __r.__cntrl_ = __hold2.release();
4447     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4448     return __r;
4449 }
4450
4451 template<class _Tp>
4452 template<class _Alloc, class ..._Args>
4453 shared_ptr<_Tp>
4454 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _Args&& ...__args)
4455 {
4456     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4457     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _A2;
4458     typedef __allocator_destructor<_A2> _D2;
4459     _A2 __a2(__a);
4460     unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4461     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4462         _CntrlBlk(__a, _VSTD::forward<_Args>(__args)...);
4463     shared_ptr<_Tp> __r;
4464     __r.__ptr_ = __hold2.get()->get();
4465     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4466     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4467     return __r;
4468 }
4469
4470 #else  // _LIBCPP_HAS_NO_VARIADICS
4471
4472 template<class _Tp>
4473 shared_ptr<_Tp>
4474 shared_ptr<_Tp>::make_shared()
4475 {
4476     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4477     typedef allocator<_CntrlBlk> _Alloc2;
4478     typedef __allocator_destructor<_Alloc2> _D2;
4479     _Alloc2 __alloc2;
4480     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4481     ::new(__hold2.get()) _CntrlBlk(__alloc2);
4482     shared_ptr<_Tp> __r;
4483     __r.__ptr_ = __hold2.get()->get();
4484     __r.__cntrl_ = __hold2.release();
4485     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4486     return __r;
4487 }
4488
4489 template<class _Tp>
4490 template<class _A0>
4491 shared_ptr<_Tp>
4492 shared_ptr<_Tp>::make_shared(_A0& __a0)
4493 {
4494     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4495     typedef allocator<_CntrlBlk> _Alloc2;
4496     typedef __allocator_destructor<_Alloc2> _D2;
4497     _Alloc2 __alloc2;
4498     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4499     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0);
4500     shared_ptr<_Tp> __r;
4501     __r.__ptr_ = __hold2.get()->get();
4502     __r.__cntrl_ = __hold2.release();
4503     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4504     return __r;
4505 }
4506
4507 template<class _Tp>
4508 template<class _A0, class _A1>
4509 shared_ptr<_Tp>
4510 shared_ptr<_Tp>::make_shared(_A0& __a0, _A1& __a1)
4511 {
4512     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4513     typedef allocator<_CntrlBlk> _Alloc2;
4514     typedef __allocator_destructor<_Alloc2> _D2;
4515     _Alloc2 __alloc2;
4516     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4517     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0, __a1);
4518     shared_ptr<_Tp> __r;
4519     __r.__ptr_ = __hold2.get()->get();
4520     __r.__cntrl_ = __hold2.release();
4521     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4522     return __r;
4523 }
4524
4525 template<class _Tp>
4526 template<class _A0, class _A1, class _A2>
4527 shared_ptr<_Tp>
4528 shared_ptr<_Tp>::make_shared(_A0& __a0, _A1& __a1, _A2& __a2)
4529 {
4530     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4531     typedef allocator<_CntrlBlk> _Alloc2;
4532     typedef __allocator_destructor<_Alloc2> _D2;
4533     _Alloc2 __alloc2;
4534     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4535     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0, __a1, __a2);
4536     shared_ptr<_Tp> __r;
4537     __r.__ptr_ = __hold2.get()->get();
4538     __r.__cntrl_ = __hold2.release();
4539     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4540     return __r;
4541 }
4542
4543 template<class _Tp>
4544 template<class _Alloc>
4545 shared_ptr<_Tp>
4546 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a)
4547 {
4548     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4549     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _Alloc2;
4550     typedef __allocator_destructor<_Alloc2> _D2;
4551     _Alloc2 __alloc2(__a);
4552     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4553     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4554         _CntrlBlk(__a);
4555     shared_ptr<_Tp> __r;
4556     __r.__ptr_ = __hold2.get()->get();
4557     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4558     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4559     return __r;
4560 }
4561
4562 template<class _Tp>
4563 template<class _Alloc, class _A0>
4564 shared_ptr<_Tp>
4565 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0)
4566 {
4567     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4568     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _Alloc2;
4569     typedef __allocator_destructor<_Alloc2> _D2;
4570     _Alloc2 __alloc2(__a);
4571     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4572     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4573         _CntrlBlk(__a, __a0);
4574     shared_ptr<_Tp> __r;
4575     __r.__ptr_ = __hold2.get()->get();
4576     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4577     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4578     return __r;
4579 }
4580
4581 template<class _Tp>
4582 template<class _Alloc, class _A0, class _A1>
4583 shared_ptr<_Tp>
4584 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1)
4585 {
4586     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4587     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _Alloc2;
4588     typedef __allocator_destructor<_Alloc2> _D2;
4589     _Alloc2 __alloc2(__a);
4590     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4591     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4592         _CntrlBlk(__a, __a0, __a1);
4593     shared_ptr<_Tp> __r;
4594     __r.__ptr_ = __hold2.get()->get();
4595     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4596     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4597     return __r;
4598 }
4599
4600 template<class _Tp>
4601 template<class _Alloc, class _A0, class _A1, class _A2>
4602 shared_ptr<_Tp>
4603 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2)
4604 {
4605     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4606     typedef typename __allocator_traits_rebind<_Alloc, _CntrlBlk>::type _Alloc2;
4607     typedef __allocator_destructor<_Alloc2> _D2;
4608     _Alloc2 __alloc2(__a);
4609     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4610     ::new(static_cast<void*>(_VSTD::addressof(*__hold2.get())))
4611         _CntrlBlk(__a, __a0, __a1, __a2);
4612     shared_ptr<_Tp> __r;
4613     __r.__ptr_ = __hold2.get()->get();
4614     __r.__cntrl_ = _VSTD::addressof(*__hold2.release());
4615     __r.__enable_weak_this(__r.__ptr_, __r.__ptr_);
4616     return __r;
4617 }
4618
4619 #endif  // _LIBCPP_HAS_NO_VARIADICS
4620
4621 template<class _Tp>
4622 shared_ptr<_Tp>::~shared_ptr()
4623 {
4624     if (__cntrl_)
4625         __cntrl_->__release_shared();
4626 }
4627
4628 template<class _Tp>
4629 inline
4630 shared_ptr<_Tp>&
4631 shared_ptr<_Tp>::operator=(const shared_ptr& __r) _NOEXCEPT
4632 {
4633     shared_ptr(__r).swap(*this);
4634     return *this;
4635 }
4636
4637 template<class _Tp>
4638 template<class _Yp>
4639 inline
4640 typename enable_if
4641 <
4642     is_convertible<_Yp*, _Tp*>::value,
4643     shared_ptr<_Tp>&
4644 >::type
4645 shared_ptr<_Tp>::operator=(const shared_ptr<_Yp>& __r) _NOEXCEPT
4646 {
4647     shared_ptr(__r).swap(*this);
4648     return *this;
4649 }
4650
4651 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4652
4653 template<class _Tp>
4654 inline
4655 shared_ptr<_Tp>&
4656 shared_ptr<_Tp>::operator=(shared_ptr&& __r) _NOEXCEPT
4657 {
4658     shared_ptr(_VSTD::move(__r)).swap(*this);
4659     return *this;
4660 }
4661
4662 template<class _Tp>
4663 template<class _Yp>
4664 inline
4665 typename enable_if
4666 <
4667     is_convertible<_Yp*, _Tp*>::value,
4668     shared_ptr<_Tp>&
4669 >::type
4670 shared_ptr<_Tp>::operator=(shared_ptr<_Yp>&& __r)
4671 {
4672     shared_ptr(_VSTD::move(__r)).swap(*this);
4673     return *this;
4674 }
4675
4676 template<class _Tp>
4677 template<class _Yp>
4678 inline
4679 typename enable_if
4680 <
4681     !is_array<_Yp>::value &&
4682     is_convertible<_Yp*, _Tp*>::value,
4683     shared_ptr<_Tp>
4684 >::type&
4685 shared_ptr<_Tp>::operator=(auto_ptr<_Yp>&& __r)
4686 {
4687     shared_ptr(_VSTD::move(__r)).swap(*this);
4688     return *this;
4689 }
4690
4691 template<class _Tp>
4692 template <class _Yp, class _Dp>
4693 inline
4694 typename enable_if
4695 <
4696     !is_array<_Yp>::value &&
4697     is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, _Tp*>::value,
4698     shared_ptr<_Tp>&
4699 >::type
4700 shared_ptr<_Tp>::operator=(unique_ptr<_Yp, _Dp>&& __r)
4701 {
4702     shared_ptr(_VSTD::move(__r)).swap(*this);
4703     return *this;
4704 }
4705
4706 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4707
4708 template<class _Tp>
4709 template<class _Yp>
4710 inline _LIBCPP_INLINE_VISIBILITY
4711 typename enable_if
4712 <
4713     !is_array<_Yp>::value &&
4714     is_convertible<_Yp*, _Tp*>::value,
4715     shared_ptr<_Tp>&
4716 >::type
4717 shared_ptr<_Tp>::operator=(auto_ptr<_Yp> __r)
4718 {
4719     shared_ptr(__r).swap(*this);
4720     return *this;
4721 }
4722
4723 template<class _Tp>
4724 template <class _Yp, class _Dp>
4725 inline _LIBCPP_INLINE_VISIBILITY
4726 typename enable_if
4727 <
4728     !is_array<_Yp>::value &&
4729     is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, _Tp*>::value,
4730     shared_ptr<_Tp>&
4731 >::type
4732 shared_ptr<_Tp>::operator=(unique_ptr<_Yp, _Dp> __r)
4733 {
4734     shared_ptr(_VSTD::move(__r)).swap(*this);
4735     return *this;
4736 }
4737
4738 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4739
4740 template<class _Tp>
4741 inline
4742 void
4743 shared_ptr<_Tp>::swap(shared_ptr& __r) _NOEXCEPT
4744 {
4745     _VSTD::swap(__ptr_, __r.__ptr_);
4746     _VSTD::swap(__cntrl_, __r.__cntrl_);
4747 }
4748
4749 template<class _Tp>
4750 inline
4751 void
4752 shared_ptr<_Tp>::reset() _NOEXCEPT
4753 {
4754     shared_ptr().swap(*this);
4755 }
4756
4757 template<class _Tp>
4758 template<class _Yp>
4759 inline
4760 typename enable_if
4761 <
4762     is_convertible<_Yp*, _Tp*>::value,
4763     void
4764 >::type
4765 shared_ptr<_Tp>::reset(_Yp* __p)
4766 {
4767     shared_ptr(__p).swap(*this);
4768 }
4769
4770 template<class _Tp>
4771 template<class _Yp, class _Dp>
4772 inline
4773 typename enable_if
4774 <
4775     is_convertible<_Yp*, _Tp*>::value,
4776     void
4777 >::type
4778 shared_ptr<_Tp>::reset(_Yp* __p, _Dp __d)
4779 {
4780     shared_ptr(__p, __d).swap(*this);
4781 }
4782
4783 template<class _Tp>
4784 template<class _Yp, class _Dp, class _Alloc>
4785 inline
4786 typename enable_if
4787 <
4788     is_convertible<_Yp*, _Tp*>::value,
4789     void
4790 >::type
4791 shared_ptr<_Tp>::reset(_Yp* __p, _Dp __d, _Alloc __a)
4792 {
4793     shared_ptr(__p, __d, __a).swap(*this);
4794 }
4795
4796 #ifndef _LIBCPP_HAS_NO_VARIADICS
4797
4798 template<class _Tp, class ..._Args>
4799 inline _LIBCPP_INLINE_VISIBILITY
4800 typename enable_if
4801 <
4802     !is_array<_Tp>::value,
4803     shared_ptr<_Tp>
4804 >::type
4805 make_shared(_Args&& ...__args)
4806 {
4807     return shared_ptr<_Tp>::make_shared(_VSTD::forward<_Args>(__args)...);
4808 }
4809
4810 template<class _Tp, class _Alloc, class ..._Args>
4811 inline _LIBCPP_INLINE_VISIBILITY
4812 typename enable_if
4813 <
4814     !is_array<_Tp>::value,
4815     shared_ptr<_Tp>
4816 >::type
4817 allocate_shared(const _Alloc& __a, _Args&& ...__args)
4818 {
4819     return shared_ptr<_Tp>::allocate_shared(__a, _VSTD::forward<_Args>(__args)...);
4820 }
4821
4822 #else  // _LIBCPP_HAS_NO_VARIADICS
4823
4824 template<class _Tp>
4825 inline _LIBCPP_INLINE_VISIBILITY
4826 shared_ptr<_Tp>
4827 make_shared()
4828 {
4829     return shared_ptr<_Tp>::make_shared();
4830 }
4831
4832 template<class _Tp, class _A0>
4833 inline _LIBCPP_INLINE_VISIBILITY
4834 shared_ptr<_Tp>
4835 make_shared(_A0& __a0)
4836 {
4837     return shared_ptr<_Tp>::make_shared(__a0);
4838 }
4839
4840 template<class _Tp, class _A0, class _A1>
4841 inline _LIBCPP_INLINE_VISIBILITY
4842 shared_ptr<_Tp>
4843 make_shared(_A0& __a0, _A1& __a1)
4844 {
4845     return shared_ptr<_Tp>::make_shared(__a0, __a1);
4846 }
4847
4848 template<class _Tp, class _A0, class _A1, class _A2>
4849 inline _LIBCPP_INLINE_VISIBILITY
4850 shared_ptr<_Tp>
4851 make_shared(_A0& __a0, _A1& __a1, _A2& __a2)
4852 {
4853     return shared_ptr<_Tp>::make_shared(__a0, __a1, __a2);
4854 }
4855
4856 template<class _Tp, class _Alloc>
4857 inline _LIBCPP_INLINE_VISIBILITY
4858 shared_ptr<_Tp>
4859 allocate_shared(const _Alloc& __a)
4860 {
4861     return shared_ptr<_Tp>::allocate_shared(__a);
4862 }
4863
4864 template<class _Tp, class _Alloc, class _A0>
4865 inline _LIBCPP_INLINE_VISIBILITY
4866 shared_ptr<_Tp>
4867 allocate_shared(const _Alloc& __a, _A0& __a0)
4868 {
4869     return shared_ptr<_Tp>::allocate_shared(__a, __a0);
4870 }
4871
4872 template<class _Tp, class _Alloc, class _A0, class _A1>
4873 inline _LIBCPP_INLINE_VISIBILITY
4874 shared_ptr<_Tp>
4875 allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1)
4876 {
4877     return shared_ptr<_Tp>::allocate_shared(__a, __a0, __a1);
4878 }
4879
4880 template<class _Tp, class _Alloc, class _A0, class _A1, class _A2>
4881 inline _LIBCPP_INLINE_VISIBILITY
4882 shared_ptr<_Tp>
4883 allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2)
4884 {
4885     return shared_ptr<_Tp>::allocate_shared(__a, __a0, __a1, __a2);
4886 }
4887
4888 #endif  // _LIBCPP_HAS_NO_VARIADICS
4889
4890 template<class _Tp, class _Up>
4891 inline _LIBCPP_INLINE_VISIBILITY
4892 bool
4893 operator==(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4894 {
4895     return __x.get() == __y.get();
4896 }
4897
4898 template<class _Tp, class _Up>
4899 inline _LIBCPP_INLINE_VISIBILITY
4900 bool
4901 operator!=(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4902 {
4903     return !(__x == __y);
4904 }
4905
4906 template<class _Tp, class _Up>
4907 inline _LIBCPP_INLINE_VISIBILITY
4908 bool
4909 operator<(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4910 {
4911     typedef typename common_type<_Tp*, _Up*>::type _Vp;
4912     return less<_Vp>()(__x.get(), __y.get());
4913 }
4914
4915 template<class _Tp, class _Up>
4916 inline _LIBCPP_INLINE_VISIBILITY
4917 bool
4918 operator>(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4919 {
4920     return __y < __x;
4921 }
4922
4923 template<class _Tp, class _Up>
4924 inline _LIBCPP_INLINE_VISIBILITY
4925 bool
4926 operator<=(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4927 {
4928     return !(__y < __x);
4929 }
4930
4931 template<class _Tp, class _Up>
4932 inline _LIBCPP_INLINE_VISIBILITY
4933 bool
4934 operator>=(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4935 {
4936     return !(__x < __y);
4937 }
4938
4939 template<class _Tp>
4940 inline _LIBCPP_INLINE_VISIBILITY
4941 bool
4942 operator==(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4943 {
4944     return !__x;
4945 }
4946
4947 template<class _Tp>
4948 inline _LIBCPP_INLINE_VISIBILITY
4949 bool
4950 operator==(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4951 {
4952     return !__x;
4953 }
4954
4955 template<class _Tp>
4956 inline _LIBCPP_INLINE_VISIBILITY
4957 bool
4958 operator!=(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4959 {
4960     return static_cast<bool>(__x);
4961 }
4962
4963 template<class _Tp>
4964 inline _LIBCPP_INLINE_VISIBILITY
4965 bool
4966 operator!=(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4967 {
4968     return static_cast<bool>(__x);
4969 }
4970
4971 template<class _Tp>
4972 inline _LIBCPP_INLINE_VISIBILITY
4973 bool
4974 operator<(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4975 {
4976     return less<_Tp*>()(__x.get(), nullptr);
4977 }
4978
4979 template<class _Tp>
4980 inline _LIBCPP_INLINE_VISIBILITY
4981 bool
4982 operator<(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4983 {
4984     return less<_Tp*>()(nullptr, __x.get());
4985 }
4986
4987 template<class _Tp>
4988 inline _LIBCPP_INLINE_VISIBILITY
4989 bool
4990 operator>(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4991 {
4992     return nullptr < __x;
4993 }
4994
4995 template<class _Tp>
4996 inline _LIBCPP_INLINE_VISIBILITY
4997 bool
4998 operator>(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4999 {
5000     return __x < nullptr;
5001 }
5002
5003 template<class _Tp>
5004 inline _LIBCPP_INLINE_VISIBILITY
5005 bool
5006 operator<=(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
5007 {
5008     return !(nullptr < __x);
5009 }
5010
5011 template<class _Tp>
5012 inline _LIBCPP_INLINE_VISIBILITY
5013 bool
5014 operator<=(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
5015 {
5016     return !(__x < nullptr);
5017 }
5018
5019 template<class _Tp>
5020 inline _LIBCPP_INLINE_VISIBILITY
5021 bool
5022 operator>=(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
5023 {
5024     return !(__x < nullptr);
5025 }
5026
5027 template<class _Tp>
5028 inline _LIBCPP_INLINE_VISIBILITY
5029 bool
5030 operator>=(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
5031 {
5032     return !(nullptr < __x);
5033 }
5034
5035 template<class _Tp>
5036 inline _LIBCPP_INLINE_VISIBILITY
5037 void
5038 swap(shared_ptr<_Tp>& __x, shared_ptr<_Tp>& __y) _NOEXCEPT
5039 {
5040     __x.swap(__y);
5041 }
5042
5043 template<class _Tp, class _Up>
5044 inline _LIBCPP_INLINE_VISIBILITY
5045 typename enable_if
5046 <
5047     !is_array<_Tp>::value && !is_array<_Up>::value,
5048     shared_ptr<_Tp>
5049 >::type
5050 static_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
5051 {
5052     return shared_ptr<_Tp>(__r, static_cast<_Tp*>(__r.get()));
5053 }
5054
5055 template<class _Tp, class _Up>
5056 inline _LIBCPP_INLINE_VISIBILITY
5057 typename enable_if
5058 <
5059     !is_array<_Tp>::value && !is_array<_Up>::value,
5060     shared_ptr<_Tp>
5061 >::type
5062 dynamic_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
5063 {
5064     _Tp* __p = dynamic_cast<_Tp*>(__r.get());
5065     return __p ? shared_ptr<_Tp>(__r, __p) : shared_ptr<_Tp>();
5066 }
5067
5068 template<class _Tp, class _Up>
5069 typename enable_if
5070 <
5071     is_array<_Tp>::value == is_array<_Up>::value,
5072     shared_ptr<_Tp>
5073 >::type
5074 const_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
5075 {
5076     typedef typename remove_extent<_Tp>::type _RTp;
5077     return shared_ptr<_Tp>(__r, const_cast<_RTp*>(__r.get()));
5078 }
5079
5080 #ifndef _LIBCPP_NO_RTTI
5081
5082 template<class _Dp, class _Tp>
5083 inline _LIBCPP_INLINE_VISIBILITY
5084 _Dp*
5085 get_deleter(const shared_ptr<_Tp>& __p) _NOEXCEPT
5086 {
5087     return __p.template __get_deleter<_Dp>();
5088 }
5089
5090 #endif  // _LIBCPP_NO_RTTI
5091
5092 template<class _Tp>
5093 class _LIBCPP_TEMPLATE_VIS weak_ptr
5094 {
5095 public:
5096     typedef _Tp element_type;
5097 private:
5098     element_type*        __ptr_;
5099     __shared_weak_count* __cntrl_;
5100
5101 public:
5102     _LIBCPP_INLINE_VISIBILITY
5103     _LIBCPP_CONSTEXPR weak_ptr() _NOEXCEPT;
5104     template<class _Yp> _LIBCPP_INLINE_VISIBILITY weak_ptr(shared_ptr<_Yp> const& __r,
5105                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
5106                         _NOEXCEPT;
5107     _LIBCPP_INLINE_VISIBILITY
5108     weak_ptr(weak_ptr const& __r) _NOEXCEPT;
5109     template<class _Yp> _LIBCPP_INLINE_VISIBILITY weak_ptr(weak_ptr<_Yp> const& __r,
5110                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
5111                          _NOEXCEPT;
5112
5113 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
5114     _LIBCPP_INLINE_VISIBILITY
5115     weak_ptr(weak_ptr&& __r) _NOEXCEPT;
5116     template<class _Yp> _LIBCPP_INLINE_VISIBILITY weak_ptr(weak_ptr<_Yp>&& __r,
5117                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
5118                          _NOEXCEPT;
5119 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
5120     ~weak_ptr();
5121
5122     _LIBCPP_INLINE_VISIBILITY
5123     weak_ptr& operator=(weak_ptr const& __r) _NOEXCEPT;
5124     template<class _Yp>
5125         typename enable_if
5126         <
5127             is_convertible<_Yp*, element_type*>::value,
5128             weak_ptr&
5129         >::type
5130         _LIBCPP_INLINE_VISIBILITY
5131         operator=(weak_ptr<_Yp> const& __r) _NOEXCEPT;
5132
5133 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
5134
5135     _LIBCPP_INLINE_VISIBILITY
5136     weak_ptr& operator=(weak_ptr&& __r) _NOEXCEPT;
5137     template<class _Yp>
5138         typename enable_if
5139         <
5140             is_convertible<_Yp*, element_type*>::value,
5141             weak_ptr&
5142         >::type
5143         _LIBCPP_INLINE_VISIBILITY
5144         operator=(weak_ptr<_Yp>&& __r) _NOEXCEPT;
5145
5146 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
5147
5148     template<class _Yp>
5149         typename enable_if
5150         <
5151             is_convertible<_Yp*, element_type*>::value,
5152             weak_ptr&
5153         >::type
5154         _LIBCPP_INLINE_VISIBILITY
5155         operator=(shared_ptr<_Yp> const& __r) _NOEXCEPT;
5156
5157     _LIBCPP_INLINE_VISIBILITY
5158     void swap(weak_ptr& __r) _NOEXCEPT;
5159     _LIBCPP_INLINE_VISIBILITY
5160     void reset() _NOEXCEPT;
5161
5162     _LIBCPP_INLINE_VISIBILITY
5163     long use_count() const _NOEXCEPT
5164         {return __cntrl_ ? __cntrl_->use_count() : 0;}
5165     _LIBCPP_INLINE_VISIBILITY
5166     bool expired() const _NOEXCEPT
5167         {return __cntrl_ == 0 || __cntrl_->use_count() == 0;}
5168     shared_ptr<_Tp> lock() const _NOEXCEPT;
5169     template<class _Up>
5170         _LIBCPP_INLINE_VISIBILITY
5171         bool owner_before(const shared_ptr<_Up>& __r) const
5172         {return __cntrl_ < __r.__cntrl_;}
5173     template<class _Up>
5174         _LIBCPP_INLINE_VISIBILITY
5175         bool owner_before(const weak_ptr<_Up>& __r) const
5176         {return __cntrl_ < __r.__cntrl_;}
5177
5178     template <class _Up> friend class _LIBCPP_TEMPLATE_VIS weak_ptr;
5179     template <class _Up> friend class _LIBCPP_TEMPLATE_VIS shared_ptr;
5180 };
5181
5182 template<class _Tp>
5183 inline
5184 _LIBCPP_CONSTEXPR
5185 weak_ptr<_Tp>::weak_ptr() _NOEXCEPT
5186     : __ptr_(0),
5187       __cntrl_(0)
5188 {
5189 }
5190
5191 template<class _Tp>
5192 inline
5193 weak_ptr<_Tp>::weak_ptr(weak_ptr const& __r) _NOEXCEPT
5194     : __ptr_(__r.__ptr_),
5195       __cntrl_(__r.__cntrl_)
5196 {
5197     if (__cntrl_)
5198         __cntrl_->__add_weak();
5199 }
5200
5201 template<class _Tp>
5202 template<class _Yp>
5203 inline
5204 weak_ptr<_Tp>::weak_ptr(shared_ptr<_Yp> const& __r,
5205                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
5206                          _NOEXCEPT
5207     : __ptr_(__r.__ptr_),
5208       __cntrl_(__r.__cntrl_)
5209 {
5210     if (__cntrl_)
5211         __cntrl_->__add_weak();
5212 }
5213
5214 template<class _Tp>
5215 template<class _Yp>
5216 inline
5217 weak_ptr<_Tp>::weak_ptr(weak_ptr<_Yp> const& __r,
5218                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
5219          _NOEXCEPT
5220     : __ptr_(__r.__ptr_),
5221       __cntrl_(__r.__cntrl_)
5222 {
5223     if (__cntrl_)
5224         __cntrl_->__add_weak();
5225 }
5226
5227 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
5228
5229 template<class _Tp>
5230 inline
5231 weak_ptr<_Tp>::weak_ptr(weak_ptr&& __r) _NOEXCEPT
5232     : __ptr_(__r.__ptr_),
5233       __cntrl_(__r.__cntrl_)
5234 {
5235     __r.__ptr_ = 0;
5236     __r.__cntrl_ = 0;
5237 }
5238
5239 template<class _Tp>
5240 template<class _Yp>
5241 inline
5242 weak_ptr<_Tp>::weak_ptr(weak_ptr<_Yp>&& __r,
5243                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
5244          _NOEXCEPT
5245     : __ptr_(__r.__ptr_),
5246       __cntrl_(__r.__cntrl_)
5247 {
5248     __r.__ptr_ = 0;
5249     __r.__cntrl_ = 0;
5250 }
5251
5252 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
5253
5254 template<class _Tp>
5255 weak_ptr<_Tp>::~weak_ptr()
5256 {
5257     if (__cntrl_)
5258         __cntrl_->__release_weak();
5259 }
5260
5261 template<class _Tp>
5262 inline
5263 weak_ptr<_Tp>&
5264 weak_ptr<_Tp>::operator=(weak_ptr const& __r) _NOEXCEPT
5265 {
5266     weak_ptr(__r).swap(*this);
5267     return *this;
5268 }
5269
5270 template<class _Tp>
5271 template<class _Yp>
5272 inline
5273 typename enable_if
5274 <
5275     is_convertible<_Yp*, _Tp*>::value,
5276     weak_ptr<_Tp>&
5277 >::type
5278 weak_ptr<_Tp>::operator=(weak_ptr<_Yp> const& __r) _NOEXCEPT
5279 {
5280     weak_ptr(__r).swap(*this);
5281     return *this;
5282 }
5283
5284 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
5285
5286 template<class _Tp>
5287 inline
5288 weak_ptr<_Tp>&
5289 weak_ptr<_Tp>::operator=(weak_ptr&& __r) _NOEXCEPT
5290 {
5291     weak_ptr(_VSTD::move(__r)).swap(*this);
5292     return *this;
5293 }
5294
5295 template<class _Tp>
5296 template<class _Yp>
5297 inline
5298 typename enable_if
5299 <
5300     is_convertible<_Yp*, _Tp*>::value,
5301     weak_ptr<_Tp>&
5302 >::type
5303 weak_ptr<_Tp>::operator=(weak_ptr<_Yp>&& __r) _NOEXCEPT
5304 {
5305     weak_ptr(_VSTD::move(__r)).swap(*this);
5306     return *this;
5307 }
5308
5309 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
5310
5311 template<class _Tp>
5312 template<class _Yp>
5313 inline
5314 typename enable_if
5315 <
5316     is_convertible<_Yp*, _Tp*>::value,
5317     weak_ptr<_Tp>&
5318 >::type
5319 weak_ptr<_Tp>::operator=(shared_ptr<_Yp> const& __r) _NOEXCEPT
5320 {
5321     weak_ptr(__r).swap(*this);
5322     return *this;
5323 }
5324
5325 template<class _Tp>
5326 inline
5327 void
5328 weak_ptr<_Tp>::swap(weak_ptr& __r) _NOEXCEPT
5329 {
5330     _VSTD::swap(__ptr_, __r.__ptr_);
5331     _VSTD::swap(__cntrl_, __r.__cntrl_);
5332 }
5333
5334 template<class _Tp>
5335 inline _LIBCPP_INLINE_VISIBILITY
5336 void
5337 swap(weak_ptr<_Tp>& __x, weak_ptr<_Tp>& __y) _NOEXCEPT
5338 {
5339     __x.swap(__y);
5340 }
5341
5342 template<class _Tp>
5343 inline
5344 void
5345 weak_ptr<_Tp>::reset() _NOEXCEPT
5346 {
5347     weak_ptr().swap(*this);
5348 }
5349
5350 template<class _Tp>
5351 template<class _Yp>
5352 shared_ptr<_Tp>::shared_ptr(const weak_ptr<_Yp>& __r,
5353                             typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type)
5354     : __ptr_(__r.__ptr_),
5355       __cntrl_(__r.__cntrl_ ? __r.__cntrl_->lock() : __r.__cntrl_)
5356 {
5357     if (__cntrl_ == 0)
5358         __throw_bad_weak_ptr();
5359 }
5360
5361 template<class _Tp>
5362 shared_ptr<_Tp>
5363 weak_ptr<_Tp>::lock() const _NOEXCEPT
5364 {
5365     shared_ptr<_Tp> __r;
5366     __r.__cntrl_ = __cntrl_ ? __cntrl_->lock() : __cntrl_;
5367     if (__r.__cntrl_)
5368         __r.__ptr_ = __ptr_;
5369     return __r;
5370 }
5371
5372 #if _LIBCPP_STD_VER > 14
5373 template <class _Tp = void> struct owner_less;
5374 #else
5375 template <class _Tp> struct owner_less;
5376 #endif
5377
5378 template <class _Tp>
5379 struct _LIBCPP_TEMPLATE_VIS owner_less<shared_ptr<_Tp> >
5380     : binary_function<shared_ptr<_Tp>, shared_ptr<_Tp>, bool>
5381 {
5382     typedef bool result_type;
5383     _LIBCPP_INLINE_VISIBILITY
5384     bool operator()(shared_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const
5385         {return __x.owner_before(__y);}
5386     _LIBCPP_INLINE_VISIBILITY
5387     bool operator()(shared_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const
5388         {return __x.owner_before(__y);}
5389     _LIBCPP_INLINE_VISIBILITY
5390     bool operator()(  weak_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const
5391         {return __x.owner_before(__y);}
5392 };
5393
5394 template <class _Tp>
5395 struct _LIBCPP_TEMPLATE_VIS owner_less<weak_ptr<_Tp> >
5396     : binary_function<weak_ptr<_Tp>, weak_ptr<_Tp>, bool>
5397 {
5398     typedef bool result_type;
5399     _LIBCPP_INLINE_VISIBILITY
5400     bool operator()(  weak_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const
5401         {return __x.owner_before(__y);}
5402     _LIBCPP_INLINE_VISIBILITY
5403     bool operator()(shared_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const
5404         {return __x.owner_before(__y);}
5405     _LIBCPP_INLINE_VISIBILITY
5406     bool operator()(  weak_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const
5407         {return __x.owner_before(__y);}
5408 };
5409
5410 #if _LIBCPP_STD_VER > 14
5411 template <>
5412 struct _LIBCPP_TEMPLATE_VIS owner_less<void>
5413 {
5414     template <class _Tp, class _Up>
5415     _LIBCPP_INLINE_VISIBILITY
5416     bool operator()( shared_ptr<_Tp> const& __x, shared_ptr<_Up> const& __y) const
5417         {return __x.owner_before(__y);}
5418     template <class _Tp, class _Up>
5419     _LIBCPP_INLINE_VISIBILITY
5420     bool operator()( shared_ptr<_Tp> const& __x,  weak_ptr<_Up> const& __y) const
5421         {return __x.owner_before(__y);}
5422     template <class _Tp, class _Up>
5423     _LIBCPP_INLINE_VISIBILITY
5424     bool operator()(   weak_ptr<_Tp> const& __x, shared_ptr<_Up> const& __y) const
5425         {return __x.owner_before(__y);}
5426     template <class _Tp, class _Up>
5427     _LIBCPP_INLINE_VISIBILITY
5428     bool operator()(   weak_ptr<_Tp> const& __x,   weak_ptr<_Up> const& __y) const
5429         {return __x.owner_before(__y);}
5430     typedef void is_transparent;
5431 };
5432 #endif
5433
5434 template<class _Tp>
5435 class _LIBCPP_TEMPLATE_VIS enable_shared_from_this
5436 {
5437     mutable weak_ptr<_Tp> __weak_this_;
5438 protected:
5439     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
5440     enable_shared_from_this() _NOEXCEPT {}
5441     _LIBCPP_INLINE_VISIBILITY
5442     enable_shared_from_this(enable_shared_from_this const&) _NOEXCEPT {}
5443     _LIBCPP_INLINE_VISIBILITY
5444     enable_shared_from_this& operator=(enable_shared_from_this const&) _NOEXCEPT
5445         {return *this;}
5446     _LIBCPP_INLINE_VISIBILITY
5447     ~enable_shared_from_this() {}
5448 public:
5449     _LIBCPP_INLINE_VISIBILITY
5450     shared_ptr<_Tp> shared_from_this()
5451         {return shared_ptr<_Tp>(__weak_this_);}
5452     _LIBCPP_INLINE_VISIBILITY
5453     shared_ptr<_Tp const> shared_from_this() const
5454         {return shared_ptr<const _Tp>(__weak_this_);}
5455
5456 #if _LIBCPP_STD_VER > 14
5457     _LIBCPP_INLINE_VISIBILITY
5458     weak_ptr<_Tp> weak_from_this() _NOEXCEPT
5459        { return __weak_this_; }
5460
5461     _LIBCPP_INLINE_VISIBILITY
5462     weak_ptr<const _Tp> weak_from_this() const _NOEXCEPT
5463         { return __weak_this_; }
5464 #endif // _LIBCPP_STD_VER > 14
5465
5466     template <class _Up> friend class shared_ptr;
5467 };
5468
5469 template <class _Tp>
5470 struct _LIBCPP_TEMPLATE_VIS hash<shared_ptr<_Tp> >
5471 {
5472     typedef shared_ptr<_Tp>      argument_type;
5473     typedef size_t               result_type;
5474     _LIBCPP_INLINE_VISIBILITY
5475     result_type operator()(const argument_type& __ptr) const _NOEXCEPT
5476     {
5477         return hash<_Tp*>()(__ptr.get());
5478     }
5479 };
5480
5481 template<class _CharT, class _Traits, class _Yp>
5482 inline _LIBCPP_INLINE_VISIBILITY
5483 basic_ostream<_CharT, _Traits>&
5484 operator<<(basic_ostream<_CharT, _Traits>& __os, shared_ptr<_Yp> const& __p);
5485
5486
5487 #if !defined(_LIBCPP_HAS_NO_ATOMIC_HEADER)
5488
5489 class _LIBCPP_TYPE_VIS __sp_mut
5490 {
5491     void* __lx;
5492 public:
5493     void lock() _NOEXCEPT;
5494     void unlock() _NOEXCEPT;
5495
5496 private:
5497     _LIBCPP_CONSTEXPR __sp_mut(void*) _NOEXCEPT;
5498     __sp_mut(const __sp_mut&);
5499     __sp_mut& operator=(const __sp_mut&);
5500
5501     friend _LIBCPP_FUNC_VIS __sp_mut& __get_sp_mut(const void*);
5502 };
5503
5504 _LIBCPP_FUNC_VIS __sp_mut& __get_sp_mut(const void*);
5505
5506 template <class _Tp>
5507 inline _LIBCPP_INLINE_VISIBILITY
5508 bool
5509 atomic_is_lock_free(const shared_ptr<_Tp>*)
5510 {
5511     return false;
5512 }
5513
5514 template <class _Tp>
5515 shared_ptr<_Tp>
5516 atomic_load(const shared_ptr<_Tp>* __p)
5517 {
5518     __sp_mut& __m = __get_sp_mut(__p);
5519     __m.lock();
5520     shared_ptr<_Tp> __q = *__p;
5521     __m.unlock();
5522     return __q;
5523 }
5524
5525 template <class _Tp>
5526 inline _LIBCPP_INLINE_VISIBILITY
5527 shared_ptr<_Tp>
5528 atomic_load_explicit(const shared_ptr<_Tp>* __p, memory_order)
5529 {
5530     return atomic_load(__p);
5531 }
5532
5533 template <class _Tp>
5534 void
5535 atomic_store(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r)
5536 {
5537     __sp_mut& __m = __get_sp_mut(__p);
5538     __m.lock();
5539     __p->swap(__r);
5540     __m.unlock();
5541 }
5542
5543 template <class _Tp>
5544 inline _LIBCPP_INLINE_VISIBILITY
5545 void
5546 atomic_store_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r, memory_order)
5547 {
5548     atomic_store(__p, __r);
5549 }
5550
5551 template <class _Tp>
5552 shared_ptr<_Tp>
5553 atomic_exchange(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r)
5554 {
5555     __sp_mut& __m = __get_sp_mut(__p);
5556     __m.lock();
5557     __p->swap(__r);
5558     __m.unlock();
5559     return __r;
5560 }
5561
5562 template <class _Tp>
5563 inline _LIBCPP_INLINE_VISIBILITY
5564 shared_ptr<_Tp>
5565 atomic_exchange_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r, memory_order)
5566 {
5567     return atomic_exchange(__p, __r);
5568 }
5569
5570 template <class _Tp>
5571 bool
5572 atomic_compare_exchange_strong(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v, shared_ptr<_Tp> __w)
5573 {
5574     shared_ptr<_Tp> __temp;
5575     __sp_mut& __m = __get_sp_mut(__p);
5576     __m.lock();
5577     if (__p->__owner_equivalent(*__v))
5578     {
5579         _VSTD::swap(__temp, *__p);
5580         *__p = __w;
5581         __m.unlock();
5582         return true;
5583     }
5584     _VSTD::swap(__temp, *__v);
5585     *__v = *__p;
5586     __m.unlock();
5587     return false;
5588 }
5589
5590 template <class _Tp>
5591 inline _LIBCPP_INLINE_VISIBILITY
5592 bool
5593 atomic_compare_exchange_weak(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v, shared_ptr<_Tp> __w)
5594 {
5595     return atomic_compare_exchange_strong(__p, __v, __w);
5596 }
5597
5598 template <class _Tp>
5599 inline _LIBCPP_INLINE_VISIBILITY
5600 bool
5601 atomic_compare_exchange_strong_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v,
5602                                         shared_ptr<_Tp> __w, memory_order, memory_order)
5603 {
5604     return atomic_compare_exchange_strong(__p, __v, __w);
5605 }
5606
5607 template <class _Tp>
5608 inline _LIBCPP_INLINE_VISIBILITY
5609 bool
5610 atomic_compare_exchange_weak_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v,
5611                                       shared_ptr<_Tp> __w, memory_order, memory_order)
5612 {
5613     return atomic_compare_exchange_weak(__p, __v, __w);
5614 }
5615
5616 #endif  // !defined(_LIBCPP_HAS_NO_ATOMIC_HEADER)
5617
5618 //enum class
5619 #if defined(_LIBCPP_ABI_POINTER_SAFETY_ENUM_TYPE)
5620 # ifndef _LIBCPP_CXX03_LANG
5621 enum class pointer_safety : unsigned char {
5622   relaxed,
5623   preferred,
5624   strict
5625 };
5626 # endif
5627 #else
5628 struct _LIBCPP_TYPE_VIS pointer_safety
5629 {
5630     enum __lx
5631     {
5632         relaxed,
5633         preferred,
5634         strict
5635     };
5636
5637     __lx __v_;
5638
5639     _LIBCPP_INLINE_VISIBILITY
5640     pointer_safety() : __v_() {}
5641
5642     _LIBCPP_INLINE_VISIBILITY
5643     pointer_safety(__lx __v) : __v_(__v) {}
5644     _LIBCPP_INLINE_VISIBILITY
5645     operator int() const {return __v_;}
5646 };
5647 #endif
5648
5649 #if !defined(_LIBCPP_ABI_POINTER_SAFETY_ENUM_TYPE) && \
5650     defined(_LIBCPP_BUILDING_MEMORY)
5651 _LIBCPP_FUNC_VIS pointer_safety get_pointer_safety() _NOEXCEPT;
5652 #else
5653 // This function is only offered in C++03 under ABI v1.
5654 # if !defined(_LIBCPP_ABI_POINTER_SAFETY_ENUM_TYPE) || !defined(_LIBCPP_CXX03_LANG)
5655 inline _LIBCPP_INLINE_VISIBILITY
5656 pointer_safety get_pointer_safety() _NOEXCEPT {
5657   return pointer_safety::relaxed;
5658 }
5659 # endif
5660 #endif
5661
5662
5663 _LIBCPP_FUNC_VIS void declare_reachable(void* __p);
5664 _LIBCPP_FUNC_VIS void declare_no_pointers(char* __p, size_t __n);
5665 _LIBCPP_FUNC_VIS void undeclare_no_pointers(char* __p, size_t __n);
5666 _LIBCPP_FUNC_VIS void* __undeclare_reachable(void* __p);
5667
5668 template <class _Tp>
5669 inline _LIBCPP_INLINE_VISIBILITY
5670 _Tp*
5671 undeclare_reachable(_Tp* __p)
5672 {
5673     return static_cast<_Tp*>(__undeclare_reachable(__p));
5674 }
5675
5676 _LIBCPP_FUNC_VIS void* align(size_t __align, size_t __sz, void*& __ptr, size_t& __space);
5677
5678 // --- Helper for container swap --
5679 template <typename _Alloc>
5680 inline _LIBCPP_INLINE_VISIBILITY
5681 void __swap_allocator(_Alloc & __a1, _Alloc & __a2)
5682 #if _LIBCPP_STD_VER >= 14
5683     _NOEXCEPT
5684 #else
5685     _NOEXCEPT_(__is_nothrow_swappable<_Alloc>::value)
5686 #endif
5687 {
5688     __swap_allocator(__a1, __a2,
5689       integral_constant<bool, _VSTD::allocator_traits<_Alloc>::propagate_on_container_swap::value>());
5690 }
5691
5692 template <typename _Alloc>
5693 _LIBCPP_INLINE_VISIBILITY
5694 void __swap_allocator(_Alloc & __a1, _Alloc & __a2, true_type)
5695 #if _LIBCPP_STD_VER >= 14
5696     _NOEXCEPT
5697 #else
5698     _NOEXCEPT_(__is_nothrow_swappable<_Alloc>::value)
5699 #endif
5700 {
5701     using _VSTD::swap;
5702     swap(__a1, __a2);
5703 }
5704
5705 template <typename _Alloc>
5706 inline _LIBCPP_INLINE_VISIBILITY
5707 void __swap_allocator(_Alloc &, _Alloc &, false_type) _NOEXCEPT {}
5708
5709 template <typename _Alloc, typename _Traits=allocator_traits<_Alloc> >
5710 struct __noexcept_move_assign_container : public integral_constant<bool,
5711     _Traits::propagate_on_container_move_assignment::value
5712 #if _LIBCPP_STD_VER > 14
5713         || _Traits::is_always_equal::value
5714 #else
5715         && is_nothrow_move_assignable<_Alloc>::value
5716 #endif
5717     > {};
5718
5719
5720 #ifndef _LIBCPP_HAS_NO_VARIADICS
5721 template <class _Tp, class _Alloc>
5722 struct __temp_value {
5723     typedef allocator_traits<_Alloc> _Traits;
5724
5725     typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __v;
5726     _Alloc &__a;
5727
5728     _Tp *__addr() { return reinterpret_cast<_Tp *>(addressof(__v)); }
5729     _Tp &   get() { return *__addr(); }
5730
5731     template<class... _Args>
5732     __temp_value(_Alloc &__alloc, _Args&& ... __args) : __a(__alloc)
5733     { _Traits::construct(__a, __addr(), _VSTD::forward<_Args>(__args)...); }
5734
5735     ~__temp_value() { _Traits::destroy(__a, __addr()); }
5736     };
5737 #endif
5738
5739 _LIBCPP_END_NAMESPACE_STD
5740
5741 #endif  // _LIBCPP_MEMORY