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