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