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