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