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