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*)&(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_VISIBLE 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_VISIBLE 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 _; char __;};
 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 _; char __;};
 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 _; char __;};
 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_VISIBLE 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_VISIBLE 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 _; char __;};
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 _; char __;};
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 _; char __;};
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 _; char __;};
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 _; char __;};
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 _; char __;};
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 _; char __;};
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 _; char __;};
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_VISIBLE 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                 construct(__a, _VSTD::__to_raw_pointer(--__end2), _VSTD::move_if_noexcept(*--__end1));
1575         }
1576
1577     template <class _Tp>
1578         _LIBCPP_INLINE_VISIBILITY
1579         static
1580         typename enable_if
1581         <
1582             (is_same<allocator_type, allocator<_Tp> >::value
1583                 || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
1584              is_trivially_move_constructible<_Tp>::value,
1585             void
1586         >::type
1587         __construct_backward(allocator_type& __a, _Tp* __begin1, _Tp* __end1, _Tp*& __end2)
1588         {
1589             ptrdiff_t _Np = __end1 - __begin1;
1590             __end2 -= _Np;
1591             _VSTD::memcpy(__end2, __begin1, _Np * sizeof(_Tp));
1592         }
1593
1594 private:
1595
1596     _LIBCPP_INLINE_VISIBILITY
1597     static pointer allocate(allocator_type& __a, size_type __n,
1598         const_void_pointer __hint, true_type)
1599         {return __a.allocate(__n, __hint);}
1600     _LIBCPP_INLINE_VISIBILITY
1601     static pointer allocate(allocator_type& __a, size_type __n,
1602         const_void_pointer, false_type)
1603         {return __a.allocate(__n);}
1604
1605 #ifndef _LIBCPP_HAS_NO_VARIADICS
1606     template <class _Tp, class... _Args>
1607         _LIBCPP_INLINE_VISIBILITY
1608         static void __construct(true_type, allocator_type& __a, _Tp* __p, _Args&&... __args)
1609             {__a.construct(__p, _VSTD::forward<_Args>(__args)...);}
1610     template <class _Tp, class... _Args>
1611         _LIBCPP_INLINE_VISIBILITY
1612         static void __construct(false_type, allocator_type&, _Tp* __p, _Args&&... __args)
1613             {
1614                 ::new ((void*)__p) _Tp(_VSTD::forward<_Args>(__args)...);
1615             }
1616 #endif  // _LIBCPP_HAS_NO_VARIADICS
1617
1618     template <class _Tp>
1619         _LIBCPP_INLINE_VISIBILITY
1620         static void __destroy(true_type, allocator_type& __a, _Tp* __p)
1621             {__a.destroy(__p);}
1622     template <class _Tp>
1623         _LIBCPP_INLINE_VISIBILITY
1624         static void __destroy(false_type, allocator_type&, _Tp* __p)
1625             {
1626                 __p->~_Tp();
1627             }
1628
1629     _LIBCPP_INLINE_VISIBILITY
1630     static size_type __max_size(true_type, const allocator_type& __a)
1631             {return __a.max_size();}
1632     _LIBCPP_INLINE_VISIBILITY
1633     static size_type __max_size(false_type, const allocator_type&)
1634             {return numeric_limits<size_type>::max();}
1635
1636     _LIBCPP_INLINE_VISIBILITY
1637     static allocator_type
1638         select_on_container_copy_construction(true_type, const allocator_type& __a)
1639             {return __a.select_on_container_copy_construction();}
1640     _LIBCPP_INLINE_VISIBILITY
1641     static allocator_type
1642         select_on_container_copy_construction(false_type, const allocator_type& __a)
1643             {return __a;}
1644 };
1645
1646 // allocator
1647
1648 template <class _Tp>
1649 class _LIBCPP_VISIBLE allocator
1650 {
1651 public:
1652     typedef size_t            size_type;
1653     typedef ptrdiff_t         difference_type;
1654     typedef _Tp*              pointer;
1655     typedef const _Tp*        const_pointer;
1656     typedef _Tp&              reference;
1657     typedef const _Tp&        const_reference;
1658     typedef _Tp               value_type;
1659
1660     typedef true_type propagate_on_container_move_assignment;
1661
1662     template <class _Up> struct rebind {typedef allocator<_Up> other;};
1663
1664     _LIBCPP_INLINE_VISIBILITY allocator() _NOEXCEPT {}
1665     template <class _Up> _LIBCPP_INLINE_VISIBILITY allocator(const allocator<_Up>&) _NOEXCEPT {}
1666     _LIBCPP_INLINE_VISIBILITY pointer address(reference __x) const _NOEXCEPT
1667         {return _VSTD::addressof(__x);}
1668     _LIBCPP_INLINE_VISIBILITY const_pointer address(const_reference __x) const _NOEXCEPT
1669         {return _VSTD::addressof(__x);}
1670     _LIBCPP_INLINE_VISIBILITY pointer allocate(size_type __n, allocator<void>::const_pointer = 0)
1671         {return static_cast<pointer>(::operator new(__n * sizeof(_Tp)));}
1672     _LIBCPP_INLINE_VISIBILITY void deallocate(pointer __p, size_type) _NOEXCEPT
1673         {::operator delete((void*)__p);}
1674     _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT
1675         {return size_type(~0) / sizeof(_Tp);}
1676 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1677     template <class _Up, class... _Args>
1678         _LIBCPP_INLINE_VISIBILITY
1679         void
1680         construct(_Up* __p, _Args&&... __args)
1681         {
1682             ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
1683         }
1684 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1685         _LIBCPP_INLINE_VISIBILITY
1686         void
1687         construct(pointer __p)
1688         {
1689             ::new((void*)__p) _Tp();
1690         }
1691 # if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1692
1693     template <class _A0>
1694         _LIBCPP_INLINE_VISIBILITY
1695         void
1696         construct(pointer __p, _A0& __a0)
1697         {
1698             ::new((void*)__p) _Tp(__a0);
1699         }
1700     template <class _A0>
1701         _LIBCPP_INLINE_VISIBILITY
1702         void
1703         construct(pointer __p, const _A0& __a0)
1704         {
1705             ::new((void*)__p) _Tp(__a0);
1706         }
1707 # endif  // defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1708     template <class _A0, class _A1>
1709         _LIBCPP_INLINE_VISIBILITY
1710         void
1711         construct(pointer __p, _A0& __a0, _A1& __a1)
1712         {
1713             ::new((void*)__p) _Tp(__a0, __a1);
1714         }
1715     template <class _A0, class _A1>
1716         _LIBCPP_INLINE_VISIBILITY
1717         void
1718         construct(pointer __p, const _A0& __a0, _A1& __a1)
1719         {
1720             ::new((void*)__p) _Tp(__a0, __a1);
1721         }
1722     template <class _A0, class _A1>
1723         _LIBCPP_INLINE_VISIBILITY
1724         void
1725         construct(pointer __p, _A0& __a0, const _A1& __a1)
1726         {
1727             ::new((void*)__p) _Tp(__a0, __a1);
1728         }
1729     template <class _A0, class _A1>
1730         _LIBCPP_INLINE_VISIBILITY
1731         void
1732         construct(pointer __p, const _A0& __a0, const _A1& __a1)
1733         {
1734             ::new((void*)__p) _Tp(__a0, __a1);
1735         }
1736 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1737     _LIBCPP_INLINE_VISIBILITY void destroy(pointer __p) {__p->~_Tp();}
1738 };
1739
1740 template <class _Tp>
1741 class _LIBCPP_VISIBLE allocator<const _Tp>
1742 {
1743 public:
1744     typedef size_t            size_type;
1745     typedef ptrdiff_t         difference_type;
1746     typedef const _Tp*        pointer;
1747     typedef const _Tp*        const_pointer;
1748     typedef const _Tp&        reference;
1749     typedef const _Tp&        const_reference;
1750     typedef _Tp               value_type;
1751
1752     typedef true_type propagate_on_container_move_assignment;
1753
1754     template <class _Up> struct rebind {typedef allocator<_Up> other;};
1755
1756     _LIBCPP_INLINE_VISIBILITY allocator() _NOEXCEPT {}
1757     template <class _Up> _LIBCPP_INLINE_VISIBILITY allocator(const allocator<_Up>&) _NOEXCEPT {}
1758     _LIBCPP_INLINE_VISIBILITY const_pointer address(const_reference __x) const _NOEXCEPT
1759         {return _VSTD::addressof(__x);}
1760     _LIBCPP_INLINE_VISIBILITY pointer allocate(size_type __n, allocator<void>::const_pointer = 0)
1761         {return static_cast<pointer>(::operator new(__n * sizeof(_Tp)));}
1762     _LIBCPP_INLINE_VISIBILITY void deallocate(pointer __p, size_type) _NOEXCEPT
1763         {::operator delete((void*)__p);}
1764     _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT
1765         {return size_type(~0) / sizeof(_Tp);}
1766 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1767     template <class _Up, class... _Args>
1768         _LIBCPP_INLINE_VISIBILITY
1769         void
1770         construct(_Up* __p, _Args&&... __args)
1771         {
1772             ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
1773         }
1774 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1775         _LIBCPP_INLINE_VISIBILITY
1776         void
1777         construct(pointer __p)
1778         {
1779             ::new((void*)__p) _Tp();
1780         }
1781 # if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1782
1783     template <class _A0>
1784         _LIBCPP_INLINE_VISIBILITY
1785         void
1786         construct(pointer __p, _A0& __a0)
1787         {
1788             ::new((void*)__p) _Tp(__a0);
1789         }
1790     template <class _A0>
1791         _LIBCPP_INLINE_VISIBILITY
1792         void
1793         construct(pointer __p, const _A0& __a0)
1794         {
1795             ::new((void*)__p) _Tp(__a0);
1796         }
1797 # endif  // defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1798     template <class _A0, class _A1>
1799         _LIBCPP_INLINE_VISIBILITY
1800         void
1801         construct(pointer __p, _A0& __a0, _A1& __a1)
1802         {
1803             ::new((void*)__p) _Tp(__a0, __a1);
1804         }
1805     template <class _A0, class _A1>
1806         _LIBCPP_INLINE_VISIBILITY
1807         void
1808         construct(pointer __p, const _A0& __a0, _A1& __a1)
1809         {
1810             ::new((void*)__p) _Tp(__a0, __a1);
1811         }
1812     template <class _A0, class _A1>
1813         _LIBCPP_INLINE_VISIBILITY
1814         void
1815         construct(pointer __p, _A0& __a0, const _A1& __a1)
1816         {
1817             ::new((void*)__p) _Tp(__a0, __a1);
1818         }
1819     template <class _A0, class _A1>
1820         _LIBCPP_INLINE_VISIBILITY
1821         void
1822         construct(pointer __p, const _A0& __a0, const _A1& __a1)
1823         {
1824             ::new((void*)__p) _Tp(__a0, __a1);
1825         }
1826 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1827     _LIBCPP_INLINE_VISIBILITY void destroy(pointer __p) {__p->~_Tp();}
1828 };
1829
1830 template <class _Tp, class _Up>
1831 inline _LIBCPP_INLINE_VISIBILITY
1832 bool operator==(const allocator<_Tp>&, const allocator<_Up>&) _NOEXCEPT {return true;}
1833
1834 template <class _Tp, class _Up>
1835 inline _LIBCPP_INLINE_VISIBILITY
1836 bool operator!=(const allocator<_Tp>&, const allocator<_Up>&) _NOEXCEPT {return false;}
1837
1838 template <class _OutputIterator, class _Tp>
1839 class _LIBCPP_VISIBLE raw_storage_iterator
1840     : public iterator<output_iterator_tag,
1841                       _Tp,                                         // purposefully not C++03
1842                       ptrdiff_t,                                   // purposefully not C++03
1843                       _Tp*,                                        // purposefully not C++03
1844                       raw_storage_iterator<_OutputIterator, _Tp>&> // purposefully not C++03
1845 {
1846 private:
1847     _OutputIterator __x_;
1848 public:
1849     _LIBCPP_INLINE_VISIBILITY explicit raw_storage_iterator(_OutputIterator __x) : __x_(__x) {}
1850     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator*() {return *this;}
1851     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator=(const _Tp& __element)
1852         {::new(&*__x_) _Tp(__element); return *this;}
1853     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator++() {++__x_; return *this;}
1854     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator  operator++(int)
1855         {raw_storage_iterator __t(*this); ++__x_; return __t;}
1856 };
1857
1858 template <class _Tp>
1859 pair<_Tp*, ptrdiff_t>
1860 get_temporary_buffer(ptrdiff_t __n) _NOEXCEPT
1861 {
1862     pair<_Tp*, ptrdiff_t> __r(0, 0);
1863     const ptrdiff_t __m = (~ptrdiff_t(0) ^
1864                            ptrdiff_t(ptrdiff_t(1) << (sizeof(ptrdiff_t) * __CHAR_BIT__ - 1)))
1865                            / sizeof(_Tp);
1866     if (__n > __m)
1867         __n = __m;
1868     while (__n > 0)
1869     {
1870         __r.first = static_cast<_Tp*>(::operator new(__n * sizeof(_Tp), nothrow));
1871         if (__r.first)
1872         {
1873             __r.second = __n;
1874             break;
1875         }
1876         __n /= 2;
1877     }
1878     return __r;
1879 }
1880
1881 template <class _Tp>
1882 inline _LIBCPP_INLINE_VISIBILITY
1883 void return_temporary_buffer(_Tp* __p) _NOEXCEPT {::operator delete(__p);}
1884
1885 template <class _Tp>
1886 struct auto_ptr_ref
1887 {
1888     _Tp* __ptr_;
1889 };
1890
1891 template<class _Tp>
1892 class _LIBCPP_VISIBLE auto_ptr
1893 {
1894 private:
1895     _Tp* __ptr_;
1896 public:
1897     typedef _Tp element_type;
1898
1899     _LIBCPP_INLINE_VISIBILITY explicit auto_ptr(_Tp* __p = 0) throw() : __ptr_(__p) {}
1900     _LIBCPP_INLINE_VISIBILITY auto_ptr(auto_ptr& __p) throw() : __ptr_(__p.release()) {}
1901     template<class _Up> _LIBCPP_INLINE_VISIBILITY auto_ptr(auto_ptr<_Up>& __p) throw()
1902         : __ptr_(__p.release()) {}
1903     _LIBCPP_INLINE_VISIBILITY auto_ptr& operator=(auto_ptr& __p) throw()
1904         {reset(__p.release()); return *this;}
1905     template<class _Up> _LIBCPP_INLINE_VISIBILITY auto_ptr& operator=(auto_ptr<_Up>& __p) throw()
1906         {reset(__p.release()); return *this;}
1907     _LIBCPP_INLINE_VISIBILITY auto_ptr& operator=(auto_ptr_ref<_Tp> __p) throw()
1908         {reset(__p.__ptr_); return *this;}
1909     _LIBCPP_INLINE_VISIBILITY ~auto_ptr() throw() {delete __ptr_;}
1910
1911     _LIBCPP_INLINE_VISIBILITY _Tp& operator*() const throw()
1912         {return *__ptr_;}
1913     _LIBCPP_INLINE_VISIBILITY _Tp* operator->() const throw() {return __ptr_;}
1914     _LIBCPP_INLINE_VISIBILITY _Tp* get() const throw() {return __ptr_;}
1915     _LIBCPP_INLINE_VISIBILITY _Tp* release() throw()
1916     {
1917         _Tp* __t = __ptr_;
1918         __ptr_ = 0;
1919         return __t;
1920     }
1921     _LIBCPP_INLINE_VISIBILITY void reset(_Tp* __p = 0) throw()
1922     {
1923         if (__ptr_ != __p)
1924             delete __ptr_;
1925         __ptr_ = __p;
1926     }
1927
1928     _LIBCPP_INLINE_VISIBILITY auto_ptr(auto_ptr_ref<_Tp> __p) throw() : __ptr_(__p.__ptr_) {}
1929     template<class _Up> _LIBCPP_INLINE_VISIBILITY operator auto_ptr_ref<_Up>() throw()
1930         {auto_ptr_ref<_Up> __t; __t.__ptr_ = release(); return __t;}
1931     template<class _Up> _LIBCPP_INLINE_VISIBILITY operator auto_ptr<_Up>() throw()
1932         {return auto_ptr<_Up>(release());}
1933 };
1934
1935 template <>
1936 class _LIBCPP_VISIBLE auto_ptr<void>
1937 {
1938 public:
1939     typedef void element_type;
1940 };
1941
1942 template <class _T1, class _T2, bool = is_same<typename remove_cv<_T1>::type,
1943                                                      typename remove_cv<_T2>::type>::value,
1944                                 bool = is_empty<_T1>::value
1945 #if __has_feature(is_final)
1946                                        && !__is_final(_T1)
1947 #endif
1948                                 ,
1949                                 bool = is_empty<_T2>::value
1950 #if __has_feature(is_final)
1951                                        && !__is_final(_T2)
1952 #endif
1953          >
1954 struct __libcpp_compressed_pair_switch;
1955
1956 template <class _T1, class _T2, bool IsSame>
1957 struct __libcpp_compressed_pair_switch<_T1, _T2, IsSame, false, false> {enum {value = 0};};
1958
1959 template <class _T1, class _T2, bool IsSame>
1960 struct __libcpp_compressed_pair_switch<_T1, _T2, IsSame, true, false>  {enum {value = 1};};
1961
1962 template <class _T1, class _T2, bool IsSame>
1963 struct __libcpp_compressed_pair_switch<_T1, _T2, IsSame, false, true>  {enum {value = 2};};
1964
1965 template <class _T1, class _T2>
1966 struct __libcpp_compressed_pair_switch<_T1, _T2, false, true, true>    {enum {value = 3};};
1967
1968 template <class _T1, class _T2>
1969 struct __libcpp_compressed_pair_switch<_T1, _T2, true, true, true>     {enum {value = 1};};
1970
1971 template <class _T1, class _T2, unsigned = __libcpp_compressed_pair_switch<_T1, _T2>::value>
1972 class __libcpp_compressed_pair_imp;
1973
1974 template <class _T1, class _T2>
1975 class __libcpp_compressed_pair_imp<_T1, _T2, 0>
1976 {
1977 private:
1978     _T1 __first_;
1979     _T2 __second_;
1980 public:
1981     typedef _T1 _T1_param;
1982     typedef _T2 _T2_param;
1983
1984     typedef typename remove_reference<_T1>::type& _T1_reference;
1985     typedef typename remove_reference<_T2>::type& _T2_reference;
1986
1987     typedef const typename remove_reference<_T1>::type& _T1_const_reference;
1988     typedef const typename remove_reference<_T2>::type& _T2_const_reference;
1989
1990     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp() {}
1991     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T1_param __t1)
1992         : __first_(_VSTD::forward<_T1_param>(__t1)) {}
1993     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T2_param __t2)
1994         : __second_(_VSTD::forward<_T2_param>(__t2)) {}
1995     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp(_T1_param __t1, _T2_param __t2)
1996         : __first_(_VSTD::forward<_T1_param>(__t1)), __second_(_VSTD::forward<_T2_param>(__t2)) {}
1997
1998 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
1999
2000     _LIBCPP_INLINE_VISIBILITY
2001     __libcpp_compressed_pair_imp(const __libcpp_compressed_pair_imp& __p)
2002         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
2003                    is_nothrow_copy_constructible<_T2>::value)
2004         : __first_(__p.first()),
2005           __second_(__p.second()) {}
2006
2007     _LIBCPP_INLINE_VISIBILITY
2008     __libcpp_compressed_pair_imp& operator=(const __libcpp_compressed_pair_imp& __p)
2009         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
2010                    is_nothrow_copy_assignable<_T2>::value)
2011         {
2012             __first_ = __p.first();
2013             __second_ = __p.second();
2014             return *this;
2015         }
2016
2017 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2018
2019     _LIBCPP_INLINE_VISIBILITY
2020     __libcpp_compressed_pair_imp(__libcpp_compressed_pair_imp&& __p)
2021         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2022                    is_nothrow_move_constructible<_T2>::value)
2023         : __first_(_VSTD::forward<_T1>(__p.first())),
2024           __second_(_VSTD::forward<_T2>(__p.second())) {}
2025
2026     _LIBCPP_INLINE_VISIBILITY
2027     __libcpp_compressed_pair_imp& operator=(__libcpp_compressed_pair_imp&& __p)
2028         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
2029                    is_nothrow_move_assignable<_T2>::value)
2030         {
2031             __first_ = _VSTD::forward<_T1>(__p.first());
2032             __second_ = _VSTD::forward<_T2>(__p.second());
2033             return *this;
2034         }
2035
2036 #ifndef _LIBCPP_HAS_NO_VARIADICS
2037
2038     template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2>
2039         _LIBCPP_INLINE_VISIBILITY
2040         __libcpp_compressed_pair_imp(piecewise_construct_t __pc,
2041                                      tuple<_Args1...> __first_args,
2042                                      tuple<_Args2...> __second_args,
2043                                      __tuple_indices<_I1...>,
2044                                      __tuple_indices<_I2...>)
2045             : __first_(_VSTD::forward<_Args1>(get<_I1>(__first_args))...),
2046               __second_(_VSTD::forward<_Args2>(get<_I2>(__second_args))...)
2047             {}
2048
2049 #endif  // _LIBCPP_HAS_NO_VARIADICS
2050
2051 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2052
2053 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2054
2055     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return __first_;}
2056     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return __first_;}
2057
2058     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return __second_;}
2059     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return __second_;}
2060
2061     _LIBCPP_INLINE_VISIBILITY void swap(__libcpp_compressed_pair_imp& __x)
2062         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2063                    __is_nothrow_swappable<_T1>::value)
2064     {
2065         using _VSTD::swap;
2066         swap(__first_, __x.__first_);
2067         swap(__second_, __x.__second_);
2068     }
2069 };
2070
2071 template <class _T1, class _T2>
2072 class __libcpp_compressed_pair_imp<_T1, _T2, 1>
2073     : private _T1
2074 {
2075 private:
2076     _T2 __second_;
2077 public:
2078     typedef _T1 _T1_param;
2079     typedef _T2 _T2_param;
2080
2081     typedef _T1&                                        _T1_reference;
2082     typedef typename remove_reference<_T2>::type& _T2_reference;
2083
2084     typedef const _T1&                                        _T1_const_reference;
2085     typedef const typename remove_reference<_T2>::type& _T2_const_reference;
2086
2087     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp() {}
2088     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T1_param __t1)
2089         : _T1(_VSTD::forward<_T1_param>(__t1)) {}
2090     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T2_param __t2)
2091         : __second_(_VSTD::forward<_T2_param>(__t2)) {}
2092     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp(_T1_param __t1, _T2_param __t2)
2093         : _T1(_VSTD::forward<_T1_param>(__t1)), __second_(_VSTD::forward<_T2_param>(__t2)) {}
2094
2095 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2096
2097     _LIBCPP_INLINE_VISIBILITY
2098     __libcpp_compressed_pair_imp(const __libcpp_compressed_pair_imp& __p)
2099         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
2100                    is_nothrow_copy_constructible<_T2>::value)
2101         : _T1(__p.first()), __second_(__p.second()) {}
2102
2103     _LIBCPP_INLINE_VISIBILITY
2104     __libcpp_compressed_pair_imp& operator=(const __libcpp_compressed_pair_imp& __p)
2105         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
2106                    is_nothrow_copy_assignable<_T2>::value)
2107         {
2108             _T1::operator=(__p.first());
2109             __second_ = __p.second();
2110             return *this;
2111         }
2112
2113 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2114
2115     _LIBCPP_INLINE_VISIBILITY
2116     __libcpp_compressed_pair_imp(__libcpp_compressed_pair_imp&& __p)
2117         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2118                    is_nothrow_move_constructible<_T2>::value)
2119         : _T1(_VSTD::move(__p.first())), __second_(_VSTD::forward<_T2>(__p.second())) {}
2120
2121     _LIBCPP_INLINE_VISIBILITY
2122     __libcpp_compressed_pair_imp& operator=(__libcpp_compressed_pair_imp&& __p)
2123         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
2124                    is_nothrow_move_assignable<_T2>::value)
2125         {
2126             _T1::operator=(_VSTD::move(__p.first()));
2127             __second_ = _VSTD::forward<_T2>(__p.second());
2128             return *this;
2129         }
2130
2131 #ifndef _LIBCPP_HAS_NO_VARIADICS
2132
2133     template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2>
2134         _LIBCPP_INLINE_VISIBILITY
2135         __libcpp_compressed_pair_imp(piecewise_construct_t __pc,
2136                                      tuple<_Args1...> __first_args,
2137                                      tuple<_Args2...> __second_args,
2138                                      __tuple_indices<_I1...>,
2139                                      __tuple_indices<_I2...>)
2140             : _T1(_VSTD::forward<_Args1>(get<_I1>(__first_args))...),
2141               __second_(_VSTD::forward<_Args2>(get<_I2>(__second_args))...)
2142             {}
2143
2144 #endif  // _LIBCPP_HAS_NO_VARIADICS
2145
2146 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2147
2148 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2149
2150     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return *this;}
2151     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return *this;}
2152
2153     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return __second_;}
2154     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return __second_;}
2155
2156     _LIBCPP_INLINE_VISIBILITY void swap(__libcpp_compressed_pair_imp& __x)
2157         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2158                    __is_nothrow_swappable<_T1>::value)
2159     {
2160         using _VSTD::swap;
2161         swap(__second_, __x.__second_);
2162     }
2163 };
2164
2165 template <class _T1, class _T2>
2166 class __libcpp_compressed_pair_imp<_T1, _T2, 2>
2167     : private _T2
2168 {
2169 private:
2170     _T1 __first_;
2171 public:
2172     typedef _T1 _T1_param;
2173     typedef _T2 _T2_param;
2174
2175     typedef typename remove_reference<_T1>::type& _T1_reference;
2176     typedef _T2&                                        _T2_reference;
2177
2178     typedef const typename remove_reference<_T1>::type& _T1_const_reference;
2179     typedef const _T2&                                        _T2_const_reference;
2180
2181     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp() {}
2182     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T1_param __t1)
2183         : __first_(_VSTD::forward<_T1_param>(__t1)) {}
2184     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T2_param __t2)
2185         : _T2(_VSTD::forward<_T2_param>(__t2)) {}
2186     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp(_T1_param __t1, _T2_param __t2)
2187         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2188                    is_nothrow_move_constructible<_T2>::value)
2189         : _T2(_VSTD::forward<_T2_param>(__t2)), __first_(_VSTD::forward<_T1_param>(__t1)) {}
2190
2191 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2192
2193     _LIBCPP_INLINE_VISIBILITY
2194     __libcpp_compressed_pair_imp(const __libcpp_compressed_pair_imp& __p)
2195         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
2196                    is_nothrow_copy_constructible<_T2>::value)
2197         : _T2(__p.second()), __first_(__p.first()) {}
2198
2199     _LIBCPP_INLINE_VISIBILITY
2200     __libcpp_compressed_pair_imp& operator=(const __libcpp_compressed_pair_imp& __p)
2201         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
2202                    is_nothrow_copy_assignable<_T2>::value)
2203         {
2204             _T2::operator=(__p.second());
2205             __first_ = __p.first();
2206             return *this;
2207         }
2208
2209 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2210
2211     _LIBCPP_INLINE_VISIBILITY
2212     __libcpp_compressed_pair_imp(__libcpp_compressed_pair_imp&& __p)
2213         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2214                    is_nothrow_move_constructible<_T2>::value)
2215         : _T2(_VSTD::forward<_T2>(__p.second())), __first_(_VSTD::move(__p.first())) {}
2216
2217     _LIBCPP_INLINE_VISIBILITY
2218     __libcpp_compressed_pair_imp& operator=(__libcpp_compressed_pair_imp&& __p)
2219         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
2220                    is_nothrow_move_assignable<_T2>::value)
2221         {
2222             _T2::operator=(_VSTD::forward<_T2>(__p.second()));
2223             __first_ = _VSTD::move(__p.first());
2224             return *this;
2225         }
2226
2227 #ifndef _LIBCPP_HAS_NO_VARIADICS
2228
2229     template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2>
2230         _LIBCPP_INLINE_VISIBILITY
2231         __libcpp_compressed_pair_imp(piecewise_construct_t __pc,
2232                                      tuple<_Args1...> __first_args,
2233                                      tuple<_Args2...> __second_args,
2234                                      __tuple_indices<_I1...>,
2235                                      __tuple_indices<_I2...>)
2236             : _T2(_VSTD::forward<_Args2>(get<_I2>(__second_args))...),
2237               __first_(_VSTD::forward<_Args1>(get<_I1>(__first_args))...)
2238
2239             {}
2240
2241 #endif  // _LIBCPP_HAS_NO_VARIADICS
2242
2243 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2244
2245 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2246
2247     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return __first_;}
2248     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return __first_;}
2249
2250     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return *this;}
2251     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return *this;}
2252
2253     _LIBCPP_INLINE_VISIBILITY void swap(__libcpp_compressed_pair_imp& __x)
2254         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2255                    __is_nothrow_swappable<_T1>::value)
2256     {
2257         using _VSTD::swap;
2258         swap(__first_, __x.__first_);
2259     }
2260 };
2261
2262 template <class _T1, class _T2>
2263 class __libcpp_compressed_pair_imp<_T1, _T2, 3>
2264     : private _T1,
2265       private _T2
2266 {
2267 public:
2268     typedef _T1 _T1_param;
2269     typedef _T2 _T2_param;
2270
2271     typedef _T1& _T1_reference;
2272     typedef _T2& _T2_reference;
2273
2274     typedef const _T1& _T1_const_reference;
2275     typedef const _T2& _T2_const_reference;
2276
2277     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp() {}
2278     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T1_param __t1)
2279         : _T1(_VSTD::forward<_T1_param>(__t1)) {}
2280     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T2_param __t2)
2281         : _T2(_VSTD::forward<_T2_param>(__t2)) {}
2282     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp(_T1_param __t1, _T2_param __t2)
2283         : _T1(_VSTD::forward<_T1_param>(__t1)), _T2(_VSTD::forward<_T2_param>(__t2)) {}
2284
2285 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2286
2287     _LIBCPP_INLINE_VISIBILITY
2288     __libcpp_compressed_pair_imp(const __libcpp_compressed_pair_imp& __p)
2289         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
2290                    is_nothrow_copy_constructible<_T2>::value)
2291         : _T1(__p.first()), _T2(__p.second()) {}
2292
2293     _LIBCPP_INLINE_VISIBILITY
2294     __libcpp_compressed_pair_imp& operator=(const __libcpp_compressed_pair_imp& __p)
2295         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
2296                    is_nothrow_copy_assignable<_T2>::value)
2297         {
2298             _T1::operator=(__p.first());
2299             _T2::operator=(__p.second());
2300             return *this;
2301         }
2302
2303 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2304
2305     _LIBCPP_INLINE_VISIBILITY
2306     __libcpp_compressed_pair_imp(__libcpp_compressed_pair_imp&& __p)
2307         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2308                    is_nothrow_move_constructible<_T2>::value)
2309         : _T1(_VSTD::move(__p.first())), _T2(_VSTD::move(__p.second())) {}
2310
2311     _LIBCPP_INLINE_VISIBILITY
2312     __libcpp_compressed_pair_imp& operator=(__libcpp_compressed_pair_imp&& __p)
2313         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
2314                    is_nothrow_move_assignable<_T2>::value)
2315         {
2316             _T1::operator=(_VSTD::move(__p.first()));
2317             _T2::operator=(_VSTD::move(__p.second()));
2318             return *this;
2319         }
2320
2321 #ifndef _LIBCPP_HAS_NO_VARIADICS
2322
2323     template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2>
2324         _LIBCPP_INLINE_VISIBILITY
2325         __libcpp_compressed_pair_imp(piecewise_construct_t __pc,
2326                                      tuple<_Args1...> __first_args,
2327                                      tuple<_Args2...> __second_args,
2328                                      __tuple_indices<_I1...>,
2329                                      __tuple_indices<_I2...>)
2330             : _T1(_VSTD::forward<_Args1>(get<_I1>(__first_args))...),
2331               _T2(_VSTD::forward<_Args2>(get<_I2>(__second_args))...)
2332             {}
2333
2334 #endif  // _LIBCPP_HAS_NO_VARIADICS
2335
2336 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2337
2338 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2339
2340     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return *this;}
2341     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return *this;}
2342
2343     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return *this;}
2344     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return *this;}
2345
2346     _LIBCPP_INLINE_VISIBILITY void swap(__libcpp_compressed_pair_imp&)
2347         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2348                    __is_nothrow_swappable<_T1>::value)
2349     {
2350     }
2351 };
2352
2353 template <class _T1, class _T2>
2354 class __compressed_pair
2355     : private __libcpp_compressed_pair_imp<_T1, _T2>
2356 {
2357     typedef __libcpp_compressed_pair_imp<_T1, _T2> base;
2358 public:
2359     typedef typename base::_T1_param _T1_param;
2360     typedef typename base::_T2_param _T2_param;
2361
2362     typedef typename base::_T1_reference _T1_reference;
2363     typedef typename base::_T2_reference _T2_reference;
2364
2365     typedef typename base::_T1_const_reference _T1_const_reference;
2366     typedef typename base::_T2_const_reference _T2_const_reference;
2367
2368     _LIBCPP_INLINE_VISIBILITY __compressed_pair() {}
2369     _LIBCPP_INLINE_VISIBILITY explicit __compressed_pair(_T1_param __t1)
2370         : base(_VSTD::forward<_T1_param>(__t1)) {}
2371     _LIBCPP_INLINE_VISIBILITY explicit __compressed_pair(_T2_param __t2)
2372         : base(_VSTD::forward<_T2_param>(__t2)) {}
2373     _LIBCPP_INLINE_VISIBILITY __compressed_pair(_T1_param __t1, _T2_param __t2)
2374         : base(_VSTD::forward<_T1_param>(__t1), _VSTD::forward<_T2_param>(__t2)) {}
2375
2376 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2377
2378     _LIBCPP_INLINE_VISIBILITY
2379     __compressed_pair(const __compressed_pair& __p)
2380         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
2381                    is_nothrow_copy_constructible<_T2>::value)
2382         : base(__p) {}
2383
2384     _LIBCPP_INLINE_VISIBILITY
2385     __compressed_pair& operator=(const __compressed_pair& __p)
2386         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
2387                    is_nothrow_copy_assignable<_T2>::value)
2388         {
2389             base::operator=(__p);
2390             return *this;
2391         }
2392
2393 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2394     _LIBCPP_INLINE_VISIBILITY
2395     __compressed_pair(__compressed_pair&& __p)
2396         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2397                    is_nothrow_move_constructible<_T2>::value)
2398         : base(_VSTD::move(__p)) {}
2399
2400     _LIBCPP_INLINE_VISIBILITY
2401     __compressed_pair& operator=(__compressed_pair&& __p)
2402         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
2403                    is_nothrow_move_assignable<_T2>::value)
2404         {
2405             base::operator=(_VSTD::move(__p));
2406             return *this;
2407         }
2408
2409 #ifndef _LIBCPP_HAS_NO_VARIADICS
2410
2411     template <class... _Args1, class... _Args2>
2412         _LIBCPP_INLINE_VISIBILITY
2413         __compressed_pair(piecewise_construct_t __pc, tuple<_Args1...> __first_args,
2414                                                       tuple<_Args2...> __second_args)
2415             : base(__pc, _VSTD::move(__first_args), _VSTD::move(__second_args),
2416                    typename __make_tuple_indices<sizeof...(_Args1)>::type(),
2417                    typename __make_tuple_indices<sizeof...(_Args2) >::type())
2418             {}
2419
2420 #endif  // _LIBCPP_HAS_NO_VARIADICS
2421
2422 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2423
2424 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2425
2426     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return base::first();}
2427     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return base::first();}
2428
2429     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return base::second();}
2430     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return base::second();}
2431
2432     _LIBCPP_INLINE_VISIBILITY void swap(__compressed_pair& __x)
2433         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2434                    __is_nothrow_swappable<_T1>::value)
2435         {base::swap(__x);}
2436 };
2437
2438 template <class _T1, class _T2>
2439 inline _LIBCPP_INLINE_VISIBILITY
2440 void
2441 swap(__compressed_pair<_T1, _T2>& __x, __compressed_pair<_T1, _T2>& __y)
2442         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2443                    __is_nothrow_swappable<_T1>::value)
2444     {__x.swap(__y);}
2445
2446 // __same_or_less_cv_qualified
2447
2448 template <class _Ptr1, class _Ptr2,
2449           bool = is_same<typename remove_cv<typename pointer_traits<_Ptr1>::element_type>::type,
2450                          typename remove_cv<typename pointer_traits<_Ptr2>::element_type>::type
2451                         >::value
2452          >
2453 struct __same_or_less_cv_qualified_imp
2454     : is_convertible<_Ptr1, _Ptr2> {};
2455
2456 template <class _Ptr1, class _Ptr2>
2457 struct __same_or_less_cv_qualified_imp<_Ptr1, _Ptr2, false>
2458     : false_type {};
2459
2460 template <class _Ptr1, class _Ptr2, bool = is_scalar<_Ptr1>::value &&
2461                                          !is_pointer<_Ptr1>::value>
2462 struct __same_or_less_cv_qualified
2463     : __same_or_less_cv_qualified_imp<_Ptr1, _Ptr2> {};
2464
2465 template <class _Ptr1, class _Ptr2>
2466 struct __same_or_less_cv_qualified<_Ptr1, _Ptr2, true>
2467     : false_type {};
2468
2469 // default_delete
2470
2471 template <class _Tp>
2472 struct _LIBCPP_VISIBLE default_delete
2473 {
2474 #ifndef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2475     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR default_delete() _NOEXCEPT = default;
2476 #else
2477     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR default_delete() _NOEXCEPT {}
2478 #endif
2479     template <class _Up>
2480         _LIBCPP_INLINE_VISIBILITY default_delete(const default_delete<_Up>&,
2481              typename enable_if<is_convertible<_Up*, _Tp*>::value>::type* = 0) _NOEXCEPT {}
2482     _LIBCPP_INLINE_VISIBILITY void operator() (_Tp* __ptr) const _NOEXCEPT
2483         {
2484             static_assert(sizeof(_Tp) > 0, "default_delete can not delete incomplete type");
2485             delete __ptr;
2486         }
2487 };
2488
2489 template <class _Tp>
2490 struct _LIBCPP_VISIBLE default_delete<_Tp[]>
2491 {
2492 public:
2493 #ifndef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2494     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR default_delete() _NOEXCEPT = default;
2495 #else
2496     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR default_delete() _NOEXCEPT {}
2497 #endif
2498     template <class _Up>
2499         _LIBCPP_INLINE_VISIBILITY default_delete(const default_delete<_Up[]>&,
2500              typename enable_if<__same_or_less_cv_qualified<_Up*, _Tp*>::value>::type* = 0) _NOEXCEPT {}
2501     template <class _Up>
2502         _LIBCPP_INLINE_VISIBILITY
2503         void operator() (_Up* __ptr,
2504                          typename enable_if<__same_or_less_cv_qualified<_Up*, _Tp*>::value>::type* = 0) const _NOEXCEPT
2505         {
2506             static_assert(sizeof(_Tp) > 0, "default_delete can not delete incomplete type");
2507             delete [] __ptr;
2508         }
2509 };
2510
2511 template <class _Tp, class _Dp = default_delete<_Tp> >
2512 class _LIBCPP_VISIBLE unique_ptr
2513 {
2514 public:
2515     typedef _Tp element_type;
2516     typedef _Dp deleter_type;
2517     typedef typename __pointer_type<_Tp, deleter_type>::type pointer;
2518 private:
2519     __compressed_pair<pointer, deleter_type> __ptr_;
2520
2521 #ifdef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2522     unique_ptr(unique_ptr&);
2523     template <class _Up, class _Ep>
2524         unique_ptr(unique_ptr<_Up, _Ep>&);
2525     unique_ptr& operator=(unique_ptr&);
2526     template <class _Up, class _Ep>
2527         unique_ptr& operator=(unique_ptr<_Up, _Ep>&);
2528 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2529
2530     struct __nat {int __for_bool_;};
2531
2532     typedef       typename remove_reference<deleter_type>::type& _Dp_reference;
2533     typedef const typename remove_reference<deleter_type>::type& _Dp_const_reference;
2534 public:
2535     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unique_ptr() _NOEXCEPT
2536         : __ptr_(pointer())
2537         {
2538             static_assert(!is_pointer<deleter_type>::value,
2539                 "unique_ptr constructed with null function pointer deleter");
2540         }
2541     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unique_ptr(nullptr_t) _NOEXCEPT
2542         : __ptr_(pointer())
2543         {
2544             static_assert(!is_pointer<deleter_type>::value,
2545                 "unique_ptr constructed with null function pointer deleter");
2546         }
2547     _LIBCPP_INLINE_VISIBILITY explicit unique_ptr(pointer __p) _NOEXCEPT
2548         : __ptr_(_VSTD::move(__p))
2549         {
2550             static_assert(!is_pointer<deleter_type>::value,
2551                 "unique_ptr constructed with null function pointer deleter");
2552         }
2553
2554 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2555     _LIBCPP_INLINE_VISIBILITY unique_ptr(pointer __p, typename conditional<
2556                                         is_reference<deleter_type>::value,
2557                                         deleter_type,
2558                                         typename add_lvalue_reference<const deleter_type>::type>::type __d)
2559              _NOEXCEPT
2560         : __ptr_(__p, __d) {}
2561
2562     _LIBCPP_INLINE_VISIBILITY unique_ptr(pointer __p, typename remove_reference<deleter_type>::type&& __d)
2563              _NOEXCEPT
2564         : __ptr_(__p, _VSTD::move(__d))
2565         {
2566             static_assert(!is_reference<deleter_type>::value, "rvalue deleter bound to reference");
2567         }
2568     _LIBCPP_INLINE_VISIBILITY unique_ptr(unique_ptr&& __u) _NOEXCEPT
2569         : __ptr_(__u.release(), _VSTD::forward<deleter_type>(__u.get_deleter())) {}
2570     template <class _Up, class _Ep>
2571         _LIBCPP_INLINE_VISIBILITY
2572         unique_ptr(unique_ptr<_Up, _Ep>&& __u,
2573                    typename enable_if
2574                       <
2575                         !is_array<_Up>::value &&
2576                          is_convertible<typename unique_ptr<_Up, _Ep>::pointer, pointer>::value &&
2577                          is_convertible<_Ep, deleter_type>::value &&
2578                          (
2579                             !is_reference<deleter_type>::value ||
2580                             is_same<deleter_type, _Ep>::value
2581                          ),
2582                          __nat
2583                       >::type = __nat()) _NOEXCEPT
2584             : __ptr_(__u.release(), _VSTD::forward<_Ep>(__u.get_deleter())) {}
2585
2586     template <class _Up>
2587         _LIBCPP_INLINE_VISIBILITY unique_ptr(auto_ptr<_Up>&& __p,
2588                 typename enable_if<
2589                                       is_convertible<_Up*, _Tp*>::value &&
2590                                       is_same<_Dp, default_delete<_Tp> >::value,
2591                                       __nat
2592                                   >::type = __nat()) _NOEXCEPT
2593             : __ptr_(__p.release())
2594             {
2595             }
2596
2597         _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(unique_ptr&& __u) _NOEXCEPT
2598             {
2599                 reset(__u.release());
2600                 __ptr_.second() = _VSTD::forward<deleter_type>(__u.get_deleter());
2601                 return *this;
2602             }
2603
2604         template <class _Up, class _Ep>
2605             _LIBCPP_INLINE_VISIBILITY
2606             typename enable_if
2607             <
2608                 !is_array<_Up>::value &&
2609                 is_convertible<typename unique_ptr<_Up, _Ep>::pointer, pointer>::value &&
2610                 is_assignable<deleter_type&, _Ep&&>::value,
2611                 unique_ptr&
2612             >::type
2613             operator=(unique_ptr<_Up, _Ep>&& __u) _NOEXCEPT
2614             {
2615                 reset(__u.release());
2616                 __ptr_.second() = _VSTD::forward<_Ep>(__u.get_deleter());
2617                 return *this;
2618             }
2619 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2620
2621     _LIBCPP_INLINE_VISIBILITY operator __rv<unique_ptr>()
2622     {
2623         return __rv<unique_ptr>(*this);
2624     }
2625
2626     _LIBCPP_INLINE_VISIBILITY unique_ptr(__rv<unique_ptr> __u)
2627         : __ptr_(__u->release(), _VSTD::forward<deleter_type>(__u->get_deleter())) {}
2628
2629     template <class _Up, class _Ep>
2630     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(unique_ptr<_Up, _Ep> __u)
2631     {
2632         reset(__u.release());
2633         __ptr_.second() = _VSTD::forward<deleter_type>(__u.get_deleter());
2634         return *this;
2635     }
2636
2637     _LIBCPP_INLINE_VISIBILITY unique_ptr(pointer __p, deleter_type __d)
2638         : __ptr_(_VSTD::move(__p), _VSTD::move(__d)) {}
2639
2640     template <class _Up>
2641         _LIBCPP_INLINE_VISIBILITY
2642                 typename enable_if<
2643                                       is_convertible<_Up*, _Tp*>::value &&
2644                                       is_same<_Dp, default_delete<_Tp> >::value,
2645                                       unique_ptr&
2646                                   >::type
2647         operator=(auto_ptr<_Up> __p)
2648             {reset(__p.release()); return *this;}
2649
2650 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2651     _LIBCPP_INLINE_VISIBILITY ~unique_ptr() {reset();}
2652
2653     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(nullptr_t) _NOEXCEPT
2654     {
2655         reset();
2656         return *this;
2657     }
2658
2659     _LIBCPP_INLINE_VISIBILITY typename add_lvalue_reference<_Tp>::type operator*() const
2660         {return *__ptr_.first();}
2661     _LIBCPP_INLINE_VISIBILITY pointer operator->() const _NOEXCEPT {return __ptr_.first();}
2662     _LIBCPP_INLINE_VISIBILITY pointer get() const _NOEXCEPT {return __ptr_.first();}
2663     _LIBCPP_INLINE_VISIBILITY       _Dp_reference get_deleter() _NOEXCEPT
2664         {return __ptr_.second();}
2665     _LIBCPP_INLINE_VISIBILITY _Dp_const_reference get_deleter() const _NOEXCEPT
2666         {return __ptr_.second();}
2667     _LIBCPP_INLINE_VISIBILITY
2668         _LIBCPP_EXPLICIT operator bool() const _NOEXCEPT
2669         {return __ptr_.first() != nullptr;}
2670
2671     _LIBCPP_INLINE_VISIBILITY pointer release() _NOEXCEPT
2672     {
2673         pointer __t = __ptr_.first();
2674         __ptr_.first() = pointer();
2675         return __t;
2676     }
2677
2678     _LIBCPP_INLINE_VISIBILITY void reset(pointer __p = pointer()) _NOEXCEPT
2679     {
2680         pointer __tmp = __ptr_.first();
2681         __ptr_.first() = __p;
2682         if (__tmp)
2683             __ptr_.second()(__tmp);
2684     }
2685
2686     _LIBCPP_INLINE_VISIBILITY void swap(unique_ptr& __u) _NOEXCEPT
2687         {__ptr_.swap(__u.__ptr_);}
2688 };
2689
2690 template <class _Tp, class _Dp>
2691 class _LIBCPP_VISIBLE unique_ptr<_Tp[], _Dp>
2692 {
2693 public:
2694     typedef _Tp element_type;
2695     typedef _Dp deleter_type;
2696     typedef typename __pointer_type<_Tp, deleter_type>::type pointer;
2697 private:
2698     __compressed_pair<pointer, deleter_type> __ptr_;
2699
2700 #ifdef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2701     unique_ptr(unique_ptr&);
2702     template <class _Up>
2703         unique_ptr(unique_ptr<_Up>&);
2704     unique_ptr& operator=(unique_ptr&);
2705     template <class _Up>
2706         unique_ptr& operator=(unique_ptr<_Up>&);
2707 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2708
2709     struct __nat {int __for_bool_;};
2710
2711     typedef       typename remove_reference<deleter_type>::type& _Dp_reference;
2712     typedef const typename remove_reference<deleter_type>::type& _Dp_const_reference;
2713 public:
2714     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unique_ptr() _NOEXCEPT
2715         : __ptr_(pointer())
2716         {
2717             static_assert(!is_pointer<deleter_type>::value,
2718                 "unique_ptr constructed with null function pointer deleter");
2719         }
2720     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unique_ptr(nullptr_t) _NOEXCEPT
2721         : __ptr_(pointer())
2722         {
2723             static_assert(!is_pointer<deleter_type>::value,
2724                 "unique_ptr constructed with null function pointer deleter");
2725         }
2726 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2727     template <class _Pp,
2728               class = typename enable_if<__same_or_less_cv_qualified<_Pp, pointer>::value>::type
2729              >
2730     _LIBCPP_INLINE_VISIBILITY explicit unique_ptr(_Pp __p) _NOEXCEPT
2731         : __ptr_(__p)
2732         {
2733             static_assert(!is_pointer<deleter_type>::value,
2734                 "unique_ptr constructed with null function pointer deleter");
2735         }
2736
2737     template <class _Pp,
2738               class = typename enable_if<__same_or_less_cv_qualified<_Pp, pointer>::value>::type
2739              >
2740     _LIBCPP_INLINE_VISIBILITY unique_ptr(_Pp __p, typename conditional<
2741                                        is_reference<deleter_type>::value,
2742                                        deleter_type,
2743                                        typename add_lvalue_reference<const deleter_type>::type>::type __d)
2744              _NOEXCEPT
2745         : __ptr_(__p, __d) {}
2746
2747     _LIBCPP_INLINE_VISIBILITY unique_ptr(nullptr_t, typename conditional<
2748                                        is_reference<deleter_type>::value,
2749                                        deleter_type,
2750                                        typename add_lvalue_reference<const deleter_type>::type>::type __d)
2751              _NOEXCEPT
2752         : __ptr_(pointer(), __d) {}
2753
2754     template <class _Pp,
2755               class = typename enable_if<__same_or_less_cv_qualified<_Pp, pointer>::value>::type
2756              >
2757     _LIBCPP_INLINE_VISIBILITY unique_ptr(_Pp __p, typename remove_reference<deleter_type>::type&& __d)
2758              _NOEXCEPT
2759         : __ptr_(__p, _VSTD::move(__d))
2760         {
2761             static_assert(!is_reference<deleter_type>::value, "rvalue deleter bound to reference");
2762         }
2763
2764     _LIBCPP_INLINE_VISIBILITY unique_ptr(nullptr_t, typename remove_reference<deleter_type>::type&& __d)
2765              _NOEXCEPT
2766         : __ptr_(pointer(), _VSTD::move(__d))
2767         {
2768             static_assert(!is_reference<deleter_type>::value, "rvalue deleter bound to reference");
2769         }
2770
2771     _LIBCPP_INLINE_VISIBILITY unique_ptr(unique_ptr&& __u) _NOEXCEPT
2772         : __ptr_(__u.release(), _VSTD::forward<deleter_type>(__u.get_deleter())) {}
2773
2774     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(unique_ptr&& __u) _NOEXCEPT
2775         {
2776             reset(__u.release());
2777             __ptr_.second() = _VSTD::forward<deleter_type>(__u.get_deleter());
2778             return *this;
2779         }
2780
2781     template <class _Up, class _Ep>
2782         _LIBCPP_INLINE_VISIBILITY
2783         unique_ptr(unique_ptr<_Up, _Ep>&& __u,
2784                    typename enable_if
2785                             <
2786                                 is_array<_Up>::value &&
2787                                 __same_or_less_cv_qualified<typename unique_ptr<_Up, _Ep>::pointer, pointer>::value
2788                                 && is_convertible<_Ep, deleter_type>::value &&
2789                                 (
2790                                     !is_reference<deleter_type>::value ||
2791                                     is_same<deleter_type, _Ep>::value
2792                                 ),
2793                                 __nat
2794                             >::type = __nat()
2795                   ) _NOEXCEPT
2796         : __ptr_(__u.release(), _VSTD::forward<deleter_type>(__u.get_deleter())) {}
2797
2798
2799         template <class _Up, class _Ep>
2800             _LIBCPP_INLINE_VISIBILITY
2801             typename enable_if
2802             <
2803                 is_array<_Up>::value &&
2804                 __same_or_less_cv_qualified<typename unique_ptr<_Up, _Ep>::pointer, pointer>::value &&
2805                 is_assignable<deleter_type&, _Ep&&>::value,
2806                 unique_ptr&
2807             >::type
2808             operator=(unique_ptr<_Up, _Ep>&& __u) _NOEXCEPT
2809             {
2810                 reset(__u.release());
2811                 __ptr_.second() = _VSTD::forward<_Ep>(__u.get_deleter());
2812                 return *this;
2813             }
2814 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2815
2816     _LIBCPP_INLINE_VISIBILITY explicit unique_ptr(pointer __p)
2817         : __ptr_(__p)
2818         {
2819             static_assert(!is_pointer<deleter_type>::value,
2820                 "unique_ptr constructed with null function pointer deleter");
2821         }
2822
2823     _LIBCPP_INLINE_VISIBILITY unique_ptr(pointer __p, deleter_type __d)
2824         : __ptr_(__p, _VSTD::forward<deleter_type>(__d)) {}
2825
2826     _LIBCPP_INLINE_VISIBILITY unique_ptr(nullptr_t, deleter_type __d)
2827         : __ptr_(pointer(), _VSTD::forward<deleter_type>(__d)) {}
2828
2829     _LIBCPP_INLINE_VISIBILITY operator __rv<unique_ptr>()
2830     {
2831         return __rv<unique_ptr>(*this);
2832     }
2833
2834     _LIBCPP_INLINE_VISIBILITY unique_ptr(__rv<unique_ptr> __u)
2835         : __ptr_(__u->release(), _VSTD::forward<deleter_type>(__u->get_deleter())) {}
2836
2837     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(__rv<unique_ptr> __u)
2838     {
2839         reset(__u->release());
2840         __ptr_.second() = _VSTD::forward<deleter_type>(__u->get_deleter());
2841         return *this;
2842     }
2843
2844 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2845     _LIBCPP_INLINE_VISIBILITY ~unique_ptr() {reset();}
2846
2847     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(nullptr_t) _NOEXCEPT
2848     {
2849         reset();
2850         return *this;
2851     }
2852
2853     _LIBCPP_INLINE_VISIBILITY typename add_lvalue_reference<_Tp>::type operator[](size_t __i) const
2854         {return __ptr_.first()[__i];}
2855     _LIBCPP_INLINE_VISIBILITY pointer get() const _NOEXCEPT {return __ptr_.first();}
2856     _LIBCPP_INLINE_VISIBILITY       _Dp_reference get_deleter() _NOEXCEPT
2857         {return __ptr_.second();}
2858     _LIBCPP_INLINE_VISIBILITY _Dp_const_reference get_deleter() const _NOEXCEPT
2859         {return __ptr_.second();}
2860     _LIBCPP_INLINE_VISIBILITY
2861         _LIBCPP_EXPLICIT operator bool() const _NOEXCEPT
2862         {return __ptr_.first() != nullptr;}
2863
2864     _LIBCPP_INLINE_VISIBILITY pointer release() _NOEXCEPT
2865     {
2866         pointer __t = __ptr_.first();
2867         __ptr_.first() = pointer();
2868         return __t;
2869     }
2870
2871 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2872     template <class _Pp,
2873               class = typename enable_if<__same_or_less_cv_qualified<_Pp, pointer>::value>::type
2874              >
2875     _LIBCPP_INLINE_VISIBILITY void reset(_Pp __p) _NOEXCEPT
2876     {
2877         pointer __tmp = __ptr_.first();
2878         __ptr_.first() = __p;
2879         if (__tmp)
2880             __ptr_.second()(__tmp);
2881     }
2882     _LIBCPP_INLINE_VISIBILITY void reset(nullptr_t) _NOEXCEPT
2883     {
2884         pointer __tmp = __ptr_.first();
2885         __ptr_.first() = nullptr;
2886         if (__tmp)
2887             __ptr_.second()(__tmp);
2888     }
2889     _LIBCPP_INLINE_VISIBILITY void reset() _NOEXCEPT
2890     {
2891         pointer __tmp = __ptr_.first();
2892         __ptr_.first() = nullptr;
2893         if (__tmp)
2894             __ptr_.second()(__tmp);
2895     }
2896 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2897     _LIBCPP_INLINE_VISIBILITY void reset(pointer __p = pointer())
2898     {
2899         pointer __tmp = __ptr_.first();
2900         __ptr_.first() = __p;
2901         if (__tmp)
2902             __ptr_.second()(__tmp);
2903     }
2904 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2905
2906     _LIBCPP_INLINE_VISIBILITY void swap(unique_ptr& __u) {__ptr_.swap(__u.__ptr_);}
2907 private:
2908
2909 #ifdef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2910     template <class _Up>
2911         explicit unique_ptr(_Up);
2912     template <class _Up>
2913         unique_ptr(_Up __u,
2914                    typename conditional<
2915                                        is_reference<deleter_type>::value,
2916                                        deleter_type,
2917                                        typename add_lvalue_reference<const deleter_type>::type>::type,
2918                    typename enable_if
2919                       <
2920                          is_convertible<_Up, pointer>::value,
2921                          __nat
2922                       >::type = __nat());
2923 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2924 };
2925
2926 template <class _Tp, class _Dp>
2927 inline _LIBCPP_INLINE_VISIBILITY
2928 void
2929 swap(unique_ptr<_Tp, _Dp>& __x, unique_ptr<_Tp, _Dp>& __y) _NOEXCEPT {__x.swap(__y);}
2930
2931 template <class _T1, class _D1, class _T2, class _D2>
2932 inline _LIBCPP_INLINE_VISIBILITY
2933 bool
2934 operator==(const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return __x.get() == __y.get();}
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 == __y);}
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)
2945 {
2946     typedef typename unique_ptr<_T1, _D1>::pointer _P1;
2947     typedef typename unique_ptr<_T2, _D2>::pointer _P2;
2948     typedef typename common_type<_P1, _P2>::type _V;
2949     return less<_V>()(__x.get(), __y.get());
2950 }
2951
2952 template <class _T1, class _D1, class _T2, class _D2>
2953 inline _LIBCPP_INLINE_VISIBILITY
2954 bool
2955 operator> (const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return __y < __x;}
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 !(__x < __y);}
2966
2967 template <class _T1, class _D1>
2968 inline _LIBCPP_INLINE_VISIBILITY
2969 bool
2970 operator==(const unique_ptr<_T1, _D1>& __x, nullptr_t) _NOEXCEPT
2971 {
2972     return !__x;
2973 }
2974
2975 template <class _T1, class _D1>
2976 inline _LIBCPP_INLINE_VISIBILITY
2977 bool
2978 operator==(nullptr_t, const unique_ptr<_T1, _D1>& __x) _NOEXCEPT
2979 {
2980     return !__x;
2981 }
2982
2983 template <class _T1, class _D1>
2984 inline _LIBCPP_INLINE_VISIBILITY
2985 bool
2986 operator!=(const unique_ptr<_T1, _D1>& __x, nullptr_t) _NOEXCEPT
2987 {
2988     return static_cast<bool>(__x);
2989 }
2990
2991 template <class _T1, class _D1>
2992 inline _LIBCPP_INLINE_VISIBILITY
2993 bool
2994 operator!=(nullptr_t, const unique_ptr<_T1, _D1>& __x) _NOEXCEPT
2995 {
2996     return static_cast<bool>(__x);
2997 }
2998
2999 template <class _T1, class _D1>
3000 inline _LIBCPP_INLINE_VISIBILITY
3001 bool
3002 operator<(const unique_ptr<_T1, _D1>& __x, nullptr_t)
3003 {
3004     typedef typename unique_ptr<_T1, _D1>::pointer _P1;
3005     return less<_P1>()(__x.get(), nullptr);
3006 }
3007
3008 template <class _T1, class _D1>
3009 inline _LIBCPP_INLINE_VISIBILITY
3010 bool
3011 operator<(nullptr_t, const unique_ptr<_T1, _D1>& __x)
3012 {
3013     typedef typename unique_ptr<_T1, _D1>::pointer _P1;
3014     return less<_P1>()(nullptr, __x.get());
3015 }
3016
3017 template <class _T1, class _D1>
3018 inline _LIBCPP_INLINE_VISIBILITY
3019 bool
3020 operator>(const unique_ptr<_T1, _D1>& __x, nullptr_t)
3021 {
3022     return nullptr < __x;
3023 }
3024
3025 template <class _T1, class _D1>
3026 inline _LIBCPP_INLINE_VISIBILITY
3027 bool
3028 operator>(nullptr_t, const unique_ptr<_T1, _D1>& __x)
3029 {
3030     return __x < nullptr;
3031 }
3032
3033 template <class _T1, class _D1>
3034 inline _LIBCPP_INLINE_VISIBILITY
3035 bool
3036 operator<=(const unique_ptr<_T1, _D1>& __x, nullptr_t)
3037 {
3038     return !(nullptr < __x);
3039 }
3040
3041 template <class _T1, class _D1>
3042 inline _LIBCPP_INLINE_VISIBILITY
3043 bool
3044 operator<=(nullptr_t, const unique_ptr<_T1, _D1>& __x)
3045 {
3046     return !(__x < nullptr);
3047 }
3048
3049 template <class _T1, class _D1>
3050 inline _LIBCPP_INLINE_VISIBILITY
3051 bool
3052 operator>=(const unique_ptr<_T1, _D1>& __x, nullptr_t)
3053 {
3054     return !(__x < nullptr);
3055 }
3056
3057 template <class _T1, class _D1>
3058 inline _LIBCPP_INLINE_VISIBILITY
3059 bool
3060 operator>=(nullptr_t, const unique_ptr<_T1, _D1>& __x)
3061 {
3062     return !(nullptr < __x);
3063 }
3064
3065 #ifdef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3066
3067 template <class _Tp, class _Dp>
3068 inline _LIBCPP_INLINE_VISIBILITY
3069 unique_ptr<_Tp, _Dp>
3070 move(unique_ptr<_Tp, _Dp>& __t)
3071 {
3072     return unique_ptr<_Tp, _Dp>(__rv<unique_ptr<_Tp, _Dp> >(__t));
3073 }
3074
3075 #endif
3076
3077 template <class _Tp> struct hash;
3078
3079 // We use murmur2 when size_t is 32 bits, and cityhash64 when size_t
3080 // is 64 bits.  This is because cityhash64 uses 64bit x 64bit
3081 // multiplication, which can be very slow on 32-bit systems.
3082 template <class _Size, size_t = sizeof(_Size)*__CHAR_BIT__>
3083 struct __murmur2_or_cityhash;
3084
3085 template <class _Size>
3086 struct __murmur2_or_cityhash<_Size, 32>
3087 {
3088     _Size operator()(const void* __key, _Size __len);
3089 };
3090
3091 // murmur2
3092 template <class _Size>
3093 _Size
3094 __murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len)
3095 {
3096     const _Size __m = 0x5bd1e995;
3097     const _Size __r = 24;
3098     _Size __h = __len;
3099     const unsigned char* __data = static_cast<const unsigned char*>(__key);
3100     for (; __len >= 4; __data += 4, __len -= 4)
3101     {
3102         _Size __k = *(const _Size*)__data;
3103         __k *= __m;
3104         __k ^= __k >> __r;
3105         __k *= __m;
3106         __h *= __m;
3107         __h ^= __k;
3108     }
3109     switch (__len)
3110     {
3111     case 3:
3112         __h ^= __data[2] << 16;
3113     case 2:
3114         __h ^= __data[1] << 8;
3115     case 1:
3116         __h ^= __data[0];
3117         __h *= __m;
3118     }
3119     __h ^= __h >> 13;
3120     __h *= __m;
3121     __h ^= __h >> 15;
3122     return __h;
3123 }
3124
3125 template <class _Size>
3126 struct __murmur2_or_cityhash<_Size, 64>
3127 {
3128     _Size operator()(const void* __key, _Size __len);
3129
3130  private:
3131   // Some primes between 2^63 and 2^64.
3132   static const _Size __k0 = 0xc3a5c85c97cb3127ULL;
3133   static const _Size __k1 = 0xb492b66fbe98f273ULL;
3134   static const _Size __k2 = 0x9ae16a3b2f90404fULL;
3135   static const _Size __k3 = 0xc949d7c7509e6557ULL;
3136
3137   static _Size __rotate(_Size __val, int __shift) {
3138     return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift)));
3139   }
3140
3141   static _Size __rotate_by_at_least_1(_Size __val, int __shift) {
3142     return (__val >> __shift) | (__val << (64 - __shift));
3143   }
3144
3145   static _Size __shift_mix(_Size __val) {
3146     return __val ^ (__val >> 47);
3147   }
3148
3149   static _Size __hash_len_16(_Size __u, _Size __v) {
3150     const _Size __mul = 0x9ddfea08eb382d69ULL;
3151     _Size __a = (__u ^ __v) * __mul;
3152     __a ^= (__a >> 47);
3153     _Size __b = (__v ^ __a) * __mul;
3154     __b ^= (__b >> 47);
3155     __b *= __mul;
3156     return __b;
3157   }
3158
3159   static _Size __hash_len_0_to_16(const char* __s, _Size __len) {
3160     if (__len > 8) {
3161       const _Size __a = *(const _Size*)__s;
3162       const _Size __b = *(const _Size*)(__s + __len - 8);
3163       return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b;
3164     }
3165     if (__len >= 4) {
3166       const uint32_t __a = *(const uint32_t*)(__s);
3167       const uint32_t __b = *(const uint32_t*)(__s + __len - 4);
3168       return __hash_len_16(__len + (__a << 3), __b);
3169     }
3170     if (__len > 0) {
3171       const unsigned char __a = __s[0];
3172       const unsigned char __b = __s[__len >> 1];
3173       const unsigned char __c = __s[__len - 1];
3174       const uint32_t __y = static_cast<uint32_t>(__a) +
3175                            (static_cast<uint32_t>(__b) << 8);
3176       const uint32_t __z = __len + (static_cast<uint32_t>(__c) << 2);
3177       return __shift_mix(__y * __k2 ^ __z * __k3) * __k2;
3178     }
3179     return __k2;
3180   }
3181
3182   static _Size __hash_len_17_to_32(const char *__s, _Size __len) {
3183     const _Size __a = *(const _Size*)(__s) * __k1;
3184     const _Size __b = *(const _Size*)(__s + 8);
3185     const _Size __c = *(const _Size*)(__s + __len - 8) * __k2;
3186     const _Size __d = *(const _Size*)(__s + __len - 16) * __k0;
3187     return __hash_len_16(__rotate(__a - __b, 43) + __rotate(__c, 30) + __d,
3188                          __a + __rotate(__b ^ __k3, 20) - __c + __len);
3189   }
3190
3191   // Return a 16-byte hash for 48 bytes.  Quick and dirty.
3192   // Callers do best to use "random-looking" values for a and b.
3193   static pair<_Size, _Size> __weak_hash_len_32_with_seeds(
3194       _Size __w, _Size __x, _Size __y, _Size __z, _Size __a, _Size __b) {
3195     __a += __w;
3196     __b = __rotate(__b + __a + __z, 21);
3197     const _Size __c = __a;
3198     __a += __x;
3199     __a += __y;
3200     __b += __rotate(__a, 44);
3201     return pair<_Size, _Size>(__a + __z, __b + __c);
3202   }
3203
3204   // Return a 16-byte hash for s[0] ... s[31], a, and b.  Quick and dirty.
3205   static pair<_Size, _Size> __weak_hash_len_32_with_seeds(
3206       const char* __s, _Size __a, _Size __b) {
3207     return __weak_hash_len_32_with_seeds(*(const _Size*)(__s),
3208                                          *(const _Size*)(__s + 8),
3209                                          *(const _Size*)(__s + 16),
3210                                          *(const _Size*)(__s + 24),
3211                                          __a,
3212                                          __b);
3213   }
3214
3215   // Return an 8-byte hash for 33 to 64 bytes.
3216   static _Size __hash_len_33_to_64(const char *__s, size_t __len) {
3217     _Size __z = *(const _Size*)(__s + 24);
3218     _Size __a = *(const _Size*)(__s) +
3219                 (__len + *(const _Size*)(__s + __len - 16)) * __k0;
3220     _Size __b = __rotate(__a + __z, 52);
3221     _Size __c = __rotate(__a, 37);
3222     __a += *(const _Size*)(__s + 8);
3223     __c += __rotate(__a, 7);
3224     __a += *(const _Size*)(__s + 16);
3225     _Size __vf = __a + __z;
3226     _Size __vs = __b + __rotate(__a, 31) + __c;
3227     __a = *(const _Size*)(__s + 16) + *(const _Size*)(__s + __len - 32);
3228     __z += *(const _Size*)(__s + __len - 8);
3229     __b = __rotate(__a + __z, 52);
3230     __c = __rotate(__a, 37);
3231     __a += *(const _Size*)(__s + __len - 24);
3232     __c += __rotate(__a, 7);
3233     __a += *(const _Size*)(__s + __len - 16);
3234     _Size __wf = __a + __z;
3235     _Size __ws = __b + __rotate(__a, 31) + __c;
3236     _Size __r = __shift_mix((__vf + __ws) * __k2 + (__wf + __vs) * __k0);
3237     return __shift_mix(__r * __k0 + __vs) * __k2;
3238   }
3239 };
3240
3241 // cityhash64
3242 template <class _Size>
3243 _Size
3244 __murmur2_or_cityhash<_Size, 64>::operator()(const void* __key, _Size __len)
3245 {
3246   const char* __s = static_cast<const char*>(__key);
3247   if (__len <= 32) {
3248     if (__len <= 16) {
3249       return __hash_len_0_to_16(__s, __len);
3250     } else {
3251       return __hash_len_17_to_32(__s, __len);
3252     }
3253   } else if (__len <= 64) {
3254     return __hash_len_33_to_64(__s, __len);
3255   }
3256
3257   // For strings over 64 bytes we hash the end first, and then as we
3258   // loop we keep 56 bytes of state: v, w, x, y, and z.
3259   _Size __x = *(const _Size*)(__s + __len - 40);
3260   _Size __y = *(const _Size*)(__s + __len - 16) +
3261               *(const _Size*)(__s + __len - 56);
3262   _Size __z = __hash_len_16(*(const _Size*)(__s + __len - 48) + __len,
3263                           *(const _Size*)(__s + __len - 24));
3264   pair<_Size, _Size> __v = __weak_hash_len_32_with_seeds(__s + __len - 64, __len, __z);
3265   pair<_Size, _Size> __w = __weak_hash_len_32_with_seeds(__s + __len - 32, __y + __k1, __x);
3266   __x = __x * __k1 + *(const _Size*)(__s);
3267
3268   // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
3269   __len = (__len - 1) & ~static_cast<_Size>(63);
3270   do {
3271     __x = __rotate(__x + __y + __v.first + *(const _Size*)(__s + 8), 37) * __k1;
3272     __y = __rotate(__y + __v.second + *(const _Size*)(__s + 48), 42) * __k1;
3273     __x ^= __w.second;
3274     __y += __v.first + *(const _Size*)(__s + 40);
3275     __z = __rotate(__z + __w.first, 33) * __k1;
3276     __v = __weak_hash_len_32_with_seeds(__s, __v.second * __k1, __x + __w.first);
3277     __w = __weak_hash_len_32_with_seeds(__s + 32, __z + __w.second,
3278                                         __y + *(const _Size*)(__s + 16));
3279     std::swap(__z, __x);
3280     __s += 64;
3281     __len -= 64;
3282   } while (__len != 0);
3283   return __hash_len_16(
3284       __hash_len_16(__v.first, __w.first) + __shift_mix(__y) * __k1 + __z,
3285       __hash_len_16(__v.second, __w.second) + __x);
3286 }
3287
3288 template <class _Tp, size_t = sizeof(_Tp) / sizeof(size_t)>
3289 struct __scalar_hash;
3290
3291 template <class _Tp>
3292 struct __scalar_hash<_Tp, 0>
3293     : public unary_function<_Tp, size_t>
3294 {
3295     _LIBCPP_INLINE_VISIBILITY
3296     size_t operator()(_Tp __v) const _NOEXCEPT
3297     {
3298         union
3299         {
3300             _Tp    __t;
3301             size_t __a;
3302         } __u;
3303         __u.__a = 0;
3304         __u.__t = __v;
3305         return __u.__a;
3306     }
3307 };
3308
3309 template <class _Tp>
3310 struct __scalar_hash<_Tp, 1>
3311     : public unary_function<_Tp, size_t>
3312 {
3313     _LIBCPP_INLINE_VISIBILITY
3314     size_t operator()(_Tp __v) const _NOEXCEPT
3315     {
3316         union
3317         {
3318             _Tp    __t;
3319             size_t __a;
3320         } __u;
3321         __u.__t = __v;
3322         return __u.__a;
3323     }
3324 };
3325
3326 template <class _Tp>
3327 struct __scalar_hash<_Tp, 2>
3328     : public unary_function<_Tp, size_t>
3329 {
3330     _LIBCPP_INLINE_VISIBILITY
3331     size_t operator()(_Tp __v) const _NOEXCEPT
3332     {
3333         union
3334         {
3335             _Tp __t;
3336             struct
3337             {
3338                 size_t __a;
3339                 size_t __b;
3340             };
3341         } __u;
3342         __u.__t = __v;
3343         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
3344     }
3345 };
3346
3347 template <class _Tp>
3348 struct __scalar_hash<_Tp, 3>
3349     : public unary_function<_Tp, size_t>
3350 {
3351     _LIBCPP_INLINE_VISIBILITY
3352     size_t operator()(_Tp __v) const _NOEXCEPT
3353     {
3354         union
3355         {
3356             _Tp __t;
3357             struct
3358             {
3359                 size_t __a;
3360                 size_t __b;
3361                 size_t __c;
3362             };
3363         } __u;
3364         __u.__t = __v;
3365         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
3366     }
3367 };
3368
3369 template <class _Tp>
3370 struct __scalar_hash<_Tp, 4>
3371     : public unary_function<_Tp, size_t>
3372 {
3373     _LIBCPP_INLINE_VISIBILITY
3374     size_t operator()(_Tp __v) const _NOEXCEPT
3375     {
3376         union
3377         {
3378             _Tp __t;
3379             struct
3380             {
3381                 size_t __a;
3382                 size_t __b;
3383                 size_t __c;
3384                 size_t __d;
3385             };
3386         } __u;
3387         __u.__t = __v;
3388         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
3389     }
3390 };
3391
3392 template<class _Tp>
3393 struct _LIBCPP_VISIBLE hash<_Tp*>
3394     : public unary_function<_Tp*, size_t>
3395 {
3396     _LIBCPP_INLINE_VISIBILITY
3397     size_t operator()(_Tp* __v) const _NOEXCEPT
3398     {
3399         union
3400         {
3401             _Tp* __t;
3402             size_t __a;
3403         } __u;
3404         __u.__t = __v;
3405         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
3406     }
3407 };
3408
3409 template <class _Tp, class _Dp>
3410 struct _LIBCPP_VISIBLE hash<unique_ptr<_Tp, _Dp> >
3411 {
3412     typedef unique_ptr<_Tp, _Dp> argument_type;
3413     typedef size_t               result_type;
3414     _LIBCPP_INLINE_VISIBILITY
3415     result_type operator()(const argument_type& __ptr) const _NOEXCEPT
3416     {
3417         typedef typename argument_type::pointer pointer;
3418         return hash<pointer>()(__ptr.get());
3419     }
3420 };
3421
3422 struct __destruct_n
3423 {
3424 private:
3425     size_t size;
3426
3427     template <class _Tp>
3428     _LIBCPP_INLINE_VISIBILITY void __process(_Tp* __p, false_type) _NOEXCEPT
3429         {for (size_t __i = 0; __i < size; ++__i, ++__p) __p->~_Tp();}
3430
3431     template <class _Tp>
3432     _LIBCPP_INLINE_VISIBILITY void __process(_Tp*, true_type) _NOEXCEPT
3433         {}
3434
3435     _LIBCPP_INLINE_VISIBILITY void __incr(false_type) _NOEXCEPT
3436         {++size;}
3437     _LIBCPP_INLINE_VISIBILITY void __incr(true_type) _NOEXCEPT
3438         {}
3439
3440     _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, false_type) _NOEXCEPT
3441         {size = __s;}
3442     _LIBCPP_INLINE_VISIBILITY void __set(size_t, true_type) _NOEXCEPT
3443         {}
3444 public:
3445     _LIBCPP_INLINE_VISIBILITY explicit __destruct_n(size_t __s) _NOEXCEPT
3446         : size(__s) {}
3447
3448     template <class _Tp>
3449     _LIBCPP_INLINE_VISIBILITY void __incr(_Tp*) _NOEXCEPT
3450         {__incr(integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
3451
3452     template <class _Tp>
3453     _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, _Tp*) _NOEXCEPT
3454         {__set(__s, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
3455
3456     template <class _Tp>
3457     _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) _NOEXCEPT
3458         {__process(__p, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
3459 };
3460
3461 template <class _Alloc>
3462 class __allocator_destructor
3463 {
3464     typedef allocator_traits<_Alloc> __alloc_traits;
3465 public:
3466     typedef typename __alloc_traits::pointer pointer;
3467     typedef typename __alloc_traits::size_type size_type;
3468 private:
3469     _Alloc& __alloc_;
3470     size_type __s_;
3471 public:
3472     _LIBCPP_INLINE_VISIBILITY __allocator_destructor(_Alloc& __a, size_type __s)
3473              _NOEXCEPT
3474         : __alloc_(__a), __s_(__s) {}
3475     _LIBCPP_INLINE_VISIBILITY
3476     void operator()(pointer __p) _NOEXCEPT
3477         {__alloc_traits::deallocate(__alloc_, __p, __s_);}
3478 };
3479
3480 template <class _InputIterator, class _ForwardIterator>
3481 _ForwardIterator
3482 uninitialized_copy(_InputIterator __f, _InputIterator __l, _ForwardIterator __r)
3483 {
3484     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3485 #ifndef _LIBCPP_NO_EXCEPTIONS
3486     _ForwardIterator __s = __r;
3487     try
3488     {
3489 #endif
3490         for (; __f != __l; ++__f, ++__r)
3491             ::new(&*__r) value_type(*__f);
3492 #ifndef _LIBCPP_NO_EXCEPTIONS
3493     }
3494     catch (...)
3495     {
3496         for (; __s != __r; ++__s)
3497             __s->~value_type();
3498         throw;
3499     }
3500 #endif
3501     return __r;
3502 }
3503
3504 template <class _InputIterator, class _Size, class _ForwardIterator>
3505 _ForwardIterator
3506 uninitialized_copy_n(_InputIterator __f, _Size __n, _ForwardIterator __r)
3507 {
3508     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3509 #ifndef _LIBCPP_NO_EXCEPTIONS
3510     _ForwardIterator __s = __r;
3511     try
3512     {
3513 #endif
3514         for (; __n > 0; ++__f, ++__r, --__n)
3515             ::new(&*__r) value_type(*__f);
3516 #ifndef _LIBCPP_NO_EXCEPTIONS
3517     }
3518     catch (...)
3519     {
3520         for (; __s != __r; ++__s)
3521             __s->~value_type();
3522         throw;
3523     }
3524 #endif
3525     return __r;
3526 }
3527
3528 template <class _ForwardIterator, class _Tp>
3529 void
3530 uninitialized_fill(_ForwardIterator __f, _ForwardIterator __l, const _Tp& __x)
3531 {
3532     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3533 #ifndef _LIBCPP_NO_EXCEPTIONS
3534     _ForwardIterator __s = __f;
3535     try
3536     {
3537 #endif
3538         for (; __f != __l; ++__f)
3539             ::new(&*__f) value_type(__x);
3540 #ifndef _LIBCPP_NO_EXCEPTIONS
3541     }
3542     catch (...)
3543     {
3544         for (; __s != __f; ++__s)
3545             __s->~value_type();
3546         throw;
3547     }
3548 #endif
3549 }
3550
3551 template <class _ForwardIterator, class _Size, class _Tp>
3552 _ForwardIterator
3553 uninitialized_fill_n(_ForwardIterator __f, _Size __n, const _Tp& __x)
3554 {
3555     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
3556 #ifndef _LIBCPP_NO_EXCEPTIONS
3557     _ForwardIterator __s = __f;
3558     try
3559     {
3560 #endif
3561         for (; __n > 0; ++__f, --__n)
3562             ::new(&*__f) value_type(__x);
3563 #ifndef _LIBCPP_NO_EXCEPTIONS
3564     }
3565     catch (...)
3566     {
3567         for (; __s != __f; ++__s)
3568             __s->~value_type();
3569         throw;
3570     }
3571 #endif
3572     return __f;
3573 }
3574
3575 class _LIBCPP_EXCEPTION_ABI bad_weak_ptr
3576     : public std::exception
3577 {
3578 public:
3579     virtual ~bad_weak_ptr() _NOEXCEPT;
3580     virtual const char* what() const  _NOEXCEPT;
3581 };
3582
3583 template<class _Tp> class _LIBCPP_VISIBLE weak_ptr;
3584
3585 class __shared_count
3586 {
3587     __shared_count(const __shared_count&);
3588     __shared_count& operator=(const __shared_count&);
3589
3590 protected:
3591     long __shared_owners_;
3592     virtual ~__shared_count();
3593 private:
3594     virtual void __on_zero_shared() _NOEXCEPT = 0;
3595
3596 public:
3597     _LIBCPP_INLINE_VISIBILITY
3598     explicit __shared_count(long __refs = 0) _NOEXCEPT
3599         : __shared_owners_(__refs) {}
3600
3601     void __add_shared() _NOEXCEPT;
3602     bool __release_shared() _NOEXCEPT;
3603     _LIBCPP_INLINE_VISIBILITY
3604     long use_count() const _NOEXCEPT {return __shared_owners_ + 1;}
3605 };
3606
3607 class __shared_weak_count
3608     : private __shared_count
3609 {
3610     long __shared_weak_owners_;
3611
3612 public:
3613     _LIBCPP_INLINE_VISIBILITY
3614     explicit __shared_weak_count(long __refs = 0) _NOEXCEPT
3615         : __shared_count(__refs),
3616           __shared_weak_owners_(__refs) {}
3617 protected:
3618     virtual ~__shared_weak_count();
3619
3620 public:
3621     void __add_shared() _NOEXCEPT;
3622     void __add_weak() _NOEXCEPT;
3623     void __release_shared() _NOEXCEPT;
3624     void __release_weak() _NOEXCEPT;
3625     _LIBCPP_INLINE_VISIBILITY
3626     long use_count() const _NOEXCEPT {return __shared_count::use_count();}
3627     __shared_weak_count* lock() _NOEXCEPT;
3628
3629     // purposefully not protected with #ifndef _LIBCPP_NO_RTTI because doing so
3630     //  breaks ABI for those clients who need to compile their projects with
3631     //    -fno-rtti and yet link against a libc++.dylib compiled without -fno-rtti.
3632     virtual const void* __get_deleter(const type_info&) const _NOEXCEPT;
3633 private:
3634     virtual void __on_zero_shared_weak() _NOEXCEPT = 0;
3635 };
3636
3637 template <class _Tp, class _Dp, class _Alloc>
3638 class __shared_ptr_pointer
3639     : public __shared_weak_count
3640 {
3641     __compressed_pair<__compressed_pair<_Tp, _Dp>, _Alloc> __data_;
3642 public:
3643     _LIBCPP_INLINE_VISIBILITY
3644     __shared_ptr_pointer(_Tp __p, _Dp __d, _Alloc __a)
3645         :  __data_(__compressed_pair<_Tp, _Dp>(__p, _VSTD::move(__d)), _VSTD::move(__a)) {}
3646
3647 #ifndef _LIBCPP_NO_RTTI
3648     virtual const void* __get_deleter(const type_info&) const _NOEXCEPT;
3649 #endif
3650
3651 private:
3652     virtual void __on_zero_shared() _NOEXCEPT;
3653     virtual void __on_zero_shared_weak() _NOEXCEPT;
3654 };
3655
3656 #ifndef _LIBCPP_NO_RTTI
3657
3658 template <class _Tp, class _Dp, class _Alloc>
3659 const void*
3660 __shared_ptr_pointer<_Tp, _Dp, _Alloc>::__get_deleter(const type_info& __t) const _NOEXCEPT
3661 {
3662     return __t == typeid(_Dp) ? &__data_.first().second() : 0;
3663 }
3664
3665 #endif  // _LIBCPP_NO_RTTI
3666
3667 template <class _Tp, class _Dp, class _Alloc>
3668 void
3669 __shared_ptr_pointer<_Tp, _Dp, _Alloc>::__on_zero_shared() _NOEXCEPT
3670 {
3671     __data_.first().second()(__data_.first().first());
3672     __data_.first().second().~_Dp();
3673 }
3674
3675 template <class _Tp, class _Dp, class _Alloc>
3676 void
3677 __shared_ptr_pointer<_Tp, _Dp, _Alloc>::__on_zero_shared_weak() _NOEXCEPT
3678 {
3679     typename _Alloc::template rebind<__shared_ptr_pointer>::other __a(__data_.second());
3680     __data_.second().~_Alloc();
3681     __a.deallocate(this, 1);
3682 }
3683
3684 template <class _Tp, class _Alloc>
3685 class __shared_ptr_emplace
3686     : public __shared_weak_count
3687 {
3688     __compressed_pair<_Alloc, _Tp> __data_;
3689 public:
3690 #ifndef _LIBCPP_HAS_NO_VARIADICS
3691
3692     _LIBCPP_INLINE_VISIBILITY
3693     __shared_ptr_emplace(_Alloc __a)
3694         :  __data_(_VSTD::move(__a)) {}
3695
3696     template <class ..._Args>
3697         _LIBCPP_INLINE_VISIBILITY
3698         __shared_ptr_emplace(_Alloc __a, _Args&& ...__args)
3699             :  __data_(piecewise_construct, _VSTD::forward_as_tuple(__a),
3700                    _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)) {}
3701
3702 #else  // _LIBCPP_HAS_NO_VARIADICS
3703
3704     _LIBCPP_INLINE_VISIBILITY
3705     __shared_ptr_emplace(_Alloc __a)
3706         :  __data_(__a) {}
3707
3708     template <class _A0>
3709         _LIBCPP_INLINE_VISIBILITY
3710         __shared_ptr_emplace(_Alloc __a, _A0& __a0)
3711             :  __data_(__a, _Tp(__a0)) {}
3712
3713     template <class _A0, class _A1>
3714         _LIBCPP_INLINE_VISIBILITY
3715         __shared_ptr_emplace(_Alloc __a, _A0& __a0, _A1& __a1)
3716             :  __data_(__a, _Tp(__a0, __a1)) {}
3717
3718     template <class _A0, class _A1, class _A2>
3719         _LIBCPP_INLINE_VISIBILITY
3720         __shared_ptr_emplace(_Alloc __a, _A0& __a0, _A1& __a1, _A2& __a2)
3721             :  __data_(__a, _Tp(__a0, __a1, __a2)) {}
3722
3723 #endif  // _LIBCPP_HAS_NO_VARIADICS
3724
3725 private:
3726     virtual void __on_zero_shared() _NOEXCEPT;
3727     virtual void __on_zero_shared_weak() _NOEXCEPT;
3728 public:
3729     _LIBCPP_INLINE_VISIBILITY
3730     _Tp* get() _NOEXCEPT {return &__data_.second();}
3731 };
3732
3733 template <class _Tp, class _Alloc>
3734 void
3735 __shared_ptr_emplace<_Tp, _Alloc>::__on_zero_shared() _NOEXCEPT
3736 {
3737     __data_.second().~_Tp();
3738 }
3739
3740 template <class _Tp, class _Alloc>
3741 void
3742 __shared_ptr_emplace<_Tp, _Alloc>::__on_zero_shared_weak() _NOEXCEPT
3743 {
3744     typename _Alloc::template rebind<__shared_ptr_emplace>::other __a(__data_.first());
3745     __data_.first().~_Alloc();
3746     __a.deallocate(this, 1);
3747 }
3748
3749 template<class _Tp> class _LIBCPP_VISIBLE enable_shared_from_this;
3750
3751 template<class _Tp>
3752 class _LIBCPP_VISIBLE shared_ptr
3753 {
3754 public:
3755     typedef _Tp element_type;
3756 private:
3757     element_type*      __ptr_;
3758     __shared_weak_count* __cntrl_;
3759
3760     struct __nat {int __for_bool_;};
3761 public:
3762     _LIBCPP_CONSTEXPR shared_ptr() _NOEXCEPT;
3763     _LIBCPP_CONSTEXPR shared_ptr(nullptr_t) _NOEXCEPT;
3764     template<class _Yp,
3765              class = typename enable_if
3766                      <
3767                         is_convertible<_Yp*, element_type*>::value
3768                      >::type
3769             >
3770         explicit shared_ptr(_Yp* __p);
3771     template<class _Yp, class _Dp,
3772              class = typename enable_if
3773                      <
3774                         is_convertible<_Yp*, element_type*>::value
3775                      >::type
3776             >
3777         shared_ptr(_Yp* __p, _Dp __d);
3778     template<class _Yp, class _Dp, class _Alloc,
3779              class = typename enable_if
3780                      <
3781                         is_convertible<_Yp*, element_type*>::value
3782                      >::type
3783             >
3784         shared_ptr(_Yp* __p, _Dp __d, _Alloc __a);
3785     template <class _Dp> shared_ptr(nullptr_t __p, _Dp __d);
3786     template <class _Dp, class _Alloc> shared_ptr(nullptr_t __p, _Dp __d, _Alloc __a);
3787     template<class _Yp> shared_ptr(const shared_ptr<_Yp>& __r, element_type* __p) _NOEXCEPT;
3788     shared_ptr(const shared_ptr& __r) _NOEXCEPT;
3789     template<class _Yp>
3790         shared_ptr(const shared_ptr<_Yp>& __r,
3791                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type = __nat())
3792                        _NOEXCEPT;
3793 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3794     shared_ptr(shared_ptr&& __r) _NOEXCEPT;
3795     template<class _Yp> shared_ptr(shared_ptr<_Yp>&& __r,
3796                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type = __nat())
3797                        _NOEXCEPT;
3798 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3799     template<class _Yp> explicit shared_ptr(const weak_ptr<_Yp>& __r,
3800                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type= __nat());
3801 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3802     template<class _Yp,
3803              class = typename enable_if
3804                      <
3805                         is_convertible<_Yp*, element_type*>::value
3806                      >::type
3807             >
3808         shared_ptr(auto_ptr<_Yp>&& __r);
3809 #else
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 #endif
3818 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3819     template <class _Yp, class _Dp,
3820                  class = typename enable_if
3821                  <
3822                     !is_array<_Yp>::value &&
3823                     is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value
3824                  >::type
3825              >
3826        shared_ptr(unique_ptr<_Yp, _Dp>&&,
3827        typename enable_if<!is_lvalue_reference<_Dp>::value, __nat>::type = __nat());
3828     template <class _Yp, class _Dp,
3829                  class = typename enable_if
3830                  <
3831                     !is_array<_Yp>::value &&
3832                     is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value
3833                  >::type
3834              >
3835        shared_ptr(unique_ptr<_Yp, _Dp>&&,
3836        typename enable_if<is_lvalue_reference<_Dp>::value, __nat>::type = __nat());
3837 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3838     template <class _Yp, class _Dp,
3839                  class = typename enable_if
3840                  <
3841                     !is_array<_Yp>::value &&
3842                     is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value
3843                  >::type
3844              > shared_ptr(unique_ptr<_Yp, _Dp>,
3845        typename enable_if<!is_lvalue_reference<_Dp>::value, __nat>::type = __nat());
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              >
3853        shared_ptr(unique_ptr<_Yp, _Dp>,
3854        typename enable_if<is_lvalue_reference<_Dp>::value, __nat>::type = __nat());
3855 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3856
3857     ~shared_ptr();
3858
3859     shared_ptr& operator=(const shared_ptr& __r) _NOEXCEPT;
3860     template<class _Yp>
3861         typename enable_if
3862         <
3863             is_convertible<_Yp*, element_type*>::value,
3864             shared_ptr&
3865         >::type
3866         operator=(const shared_ptr<_Yp>& __r) _NOEXCEPT;
3867 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3868     shared_ptr& operator=(shared_ptr&& __r) _NOEXCEPT;
3869     template<class _Yp>
3870         typename enable_if
3871         <
3872             is_convertible<_Yp*, element_type*>::value,
3873             shared_ptr<_Tp>&
3874         >::type
3875         operator=(shared_ptr<_Yp>&& __r);
3876     template<class _Yp>
3877         typename enable_if
3878         <
3879             !is_array<_Yp>::value &&
3880             is_convertible<_Yp*, element_type*>::value,
3881             shared_ptr&
3882         >::type
3883         operator=(auto_ptr<_Yp>&& __r);
3884 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3885     template<class _Yp>
3886         typename enable_if
3887         <
3888             !is_array<_Yp>::value &&
3889             is_convertible<_Yp*, element_type*>::value,
3890             shared_ptr&
3891         >::type
3892         operator=(auto_ptr<_Yp> __r);
3893 #endif
3894     template <class _Yp, class _Dp>
3895         typename enable_if
3896         <
3897             !is_array<_Yp>::value &&
3898             is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, element_type*>::value,
3899             shared_ptr&
3900         >::type
3901 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3902         operator=(unique_ptr<_Yp, _Dp>&& __r);
3903 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3904         operator=(unique_ptr<_Yp, _Dp> __r);
3905 #endif
3906
3907     void swap(shared_ptr& __r) _NOEXCEPT;
3908     void reset() _NOEXCEPT;
3909     template<class _Yp>
3910         typename enable_if
3911         <
3912             is_convertible<_Yp*, element_type*>::value,
3913             void
3914         >::type
3915         reset(_Yp* __p);
3916     template<class _Yp, class _Dp>
3917         typename enable_if
3918         <
3919             is_convertible<_Yp*, element_type*>::value,
3920             void
3921         >::type
3922         reset(_Yp* __p, _Dp __d);
3923     template<class _Yp, class _Dp, class _Alloc>
3924         typename enable_if
3925         <
3926             is_convertible<_Yp*, element_type*>::value,
3927             void
3928         >::type
3929         reset(_Yp* __p, _Dp __d, _Alloc __a);
3930
3931     _LIBCPP_INLINE_VISIBILITY
3932     element_type* get() const _NOEXCEPT {return __ptr_;}
3933     _LIBCPP_INLINE_VISIBILITY
3934     typename add_lvalue_reference<element_type>::type operator*() const _NOEXCEPT
3935         {return *__ptr_;}
3936     _LIBCPP_INLINE_VISIBILITY
3937     element_type* operator->() const _NOEXCEPT {return __ptr_;}
3938     _LIBCPP_INLINE_VISIBILITY
3939     long use_count() const _NOEXCEPT {return __cntrl_ ? __cntrl_->use_count() : 0;}
3940     _LIBCPP_INLINE_VISIBILITY
3941     bool unique() const _NOEXCEPT {return use_count() == 1;}
3942     _LIBCPP_INLINE_VISIBILITY
3943     _LIBCPP_EXPLICIT operator bool() const _NOEXCEPT {return get() != 0;}
3944     template <class _Up>
3945         _LIBCPP_INLINE_VISIBILITY
3946         bool owner_before(shared_ptr<_Up> const& __p) const
3947         {return __cntrl_ < __p.__cntrl_;}
3948     template <class _Up>
3949         _LIBCPP_INLINE_VISIBILITY
3950         bool owner_before(weak_ptr<_Up> const& __p) const
3951         {return __cntrl_ < __p.__cntrl_;}
3952     _LIBCPP_INLINE_VISIBILITY
3953     bool
3954     __owner_equivalent(const shared_ptr& __p) const
3955         {return __cntrl_ == __p.__cntrl_;}
3956
3957 #ifndef _LIBCPP_NO_RTTI
3958     template <class _Dp>
3959         _LIBCPP_INLINE_VISIBILITY
3960         _Dp* __get_deleter() const _NOEXCEPT
3961             {return (_Dp*)(__cntrl_ ? __cntrl_->__get_deleter(typeid(_Dp)) : 0);}
3962 #endif  // _LIBCPP_NO_RTTI
3963
3964 #ifndef _LIBCPP_HAS_NO_VARIADICS
3965
3966     template<class ..._Args>
3967         static
3968         shared_ptr<_Tp>
3969         make_shared(_Args&& ...__args);
3970
3971     template<class _Alloc, class ..._Args>
3972         static
3973         shared_ptr<_Tp>
3974         allocate_shared(const _Alloc& __a, _Args&& ...__args);
3975
3976 #else  // _LIBCPP_HAS_NO_VARIADICS
3977
3978     static shared_ptr<_Tp> make_shared();
3979
3980     template<class _A0>
3981         static shared_ptr<_Tp> make_shared(_A0&);
3982
3983     template<class _A0, class _A1>
3984         static shared_ptr<_Tp> make_shared(_A0&, _A1&);
3985
3986     template<class _A0, class _A1, class _A2>
3987         static shared_ptr<_Tp> make_shared(_A0&, _A1&, _A2&);
3988
3989     template<class _Alloc>
3990         static shared_ptr<_Tp>
3991         allocate_shared(const _Alloc& __a);
3992
3993     template<class _Alloc, class _A0>
3994         static shared_ptr<_Tp>
3995         allocate_shared(const _Alloc& __a, _A0& __a0);
3996
3997     template<class _Alloc, class _A0, class _A1>
3998         static shared_ptr<_Tp>
3999         allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1);
4000
4001     template<class _Alloc, class _A0, class _A1, class _A2>
4002         static shared_ptr<_Tp>
4003         allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2);
4004
4005 #endif  // _LIBCPP_HAS_NO_VARIADICS
4006
4007 private:
4008
4009     template <class _Yp>
4010         _LIBCPP_INLINE_VISIBILITY
4011         void
4012         __enable_weak_this(const enable_shared_from_this<_Yp>* __e) _NOEXCEPT
4013         {
4014             if (__e)
4015                 __e->__weak_this_ = *this;
4016         }
4017
4018     _LIBCPP_INLINE_VISIBILITY
4019     void __enable_weak_this(const void*) _NOEXCEPT {}
4020
4021     template <class _Up> friend class _LIBCPP_VISIBLE shared_ptr;
4022     template <class _Up> friend class _LIBCPP_VISIBLE weak_ptr;
4023 };
4024
4025 template<class _Tp>
4026 inline _LIBCPP_INLINE_VISIBILITY
4027 _LIBCPP_CONSTEXPR
4028 shared_ptr<_Tp>::shared_ptr() _NOEXCEPT
4029     : __ptr_(0),
4030       __cntrl_(0)
4031 {
4032 }
4033
4034 template<class _Tp>
4035 inline _LIBCPP_INLINE_VISIBILITY
4036 _LIBCPP_CONSTEXPR
4037 shared_ptr<_Tp>::shared_ptr(nullptr_t) _NOEXCEPT
4038     : __ptr_(0),
4039       __cntrl_(0)
4040 {
4041 }
4042
4043 template<class _Tp>
4044 template<class _Yp, class>
4045 shared_ptr<_Tp>::shared_ptr(_Yp* __p)
4046     : __ptr_(__p)
4047 {
4048     unique_ptr<_Yp> __hold(__p);
4049     typedef __shared_ptr_pointer<_Yp*, default_delete<_Yp>, allocator<_Yp> > _CntrlBlk;
4050     __cntrl_ = new _CntrlBlk(__p, default_delete<_Yp>(), allocator<_Yp>());
4051     __hold.release();
4052     __enable_weak_this(__p);
4053 }
4054
4055 template<class _Tp>
4056 template<class _Yp, class _Dp, class>
4057 shared_ptr<_Tp>::shared_ptr(_Yp* __p, _Dp __d)
4058     : __ptr_(__p)
4059 {
4060 #ifndef _LIBCPP_NO_EXCEPTIONS
4061     try
4062     {
4063 #endif  // _LIBCPP_NO_EXCEPTIONS
4064         typedef __shared_ptr_pointer<_Yp*, _Dp, allocator<_Yp> > _CntrlBlk;
4065         __cntrl_ = new _CntrlBlk(__p, __d, allocator<_Yp>());
4066         __enable_weak_this(__p);
4067 #ifndef _LIBCPP_NO_EXCEPTIONS
4068     }
4069     catch (...)
4070     {
4071         __d(__p);
4072         throw;
4073     }
4074 #endif  // _LIBCPP_NO_EXCEPTIONS
4075 }
4076
4077 template<class _Tp>
4078 template<class _Dp>
4079 shared_ptr<_Tp>::shared_ptr(nullptr_t __p, _Dp __d)
4080     : __ptr_(0)
4081 {
4082 #ifndef _LIBCPP_NO_EXCEPTIONS
4083     try
4084     {
4085 #endif  // _LIBCPP_NO_EXCEPTIONS
4086         typedef __shared_ptr_pointer<nullptr_t, _Dp, allocator<_Tp> > _CntrlBlk;
4087         __cntrl_ = new _CntrlBlk(__p, __d, allocator<_Tp>());
4088 #ifndef _LIBCPP_NO_EXCEPTIONS
4089     }
4090     catch (...)
4091     {
4092         __d(__p);
4093         throw;
4094     }
4095 #endif  // _LIBCPP_NO_EXCEPTIONS
4096 }
4097
4098 template<class _Tp>
4099 template<class _Yp, class _Dp, class _Alloc, class>
4100 shared_ptr<_Tp>::shared_ptr(_Yp* __p, _Dp __d, _Alloc __a)
4101     : __ptr_(__p)
4102 {
4103 #ifndef _LIBCPP_NO_EXCEPTIONS
4104     try
4105     {
4106 #endif  // _LIBCPP_NO_EXCEPTIONS
4107         typedef __shared_ptr_pointer<_Yp*, _Dp, _Alloc> _CntrlBlk;
4108         typedef typename _Alloc::template rebind<_CntrlBlk>::other _A2;
4109         typedef __allocator_destructor<_A2> _D2;
4110         _A2 __a2(__a);
4111         unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4112         ::new(__hold2.get()) _CntrlBlk(__p, __d, __a);
4113         __cntrl_ = __hold2.release();
4114         __enable_weak_this(__p);
4115 #ifndef _LIBCPP_NO_EXCEPTIONS
4116     }
4117     catch (...)
4118     {
4119         __d(__p);
4120         throw;
4121     }
4122 #endif  // _LIBCPP_NO_EXCEPTIONS
4123 }
4124
4125 template<class _Tp>
4126 template<class _Dp, class _Alloc>
4127 shared_ptr<_Tp>::shared_ptr(nullptr_t __p, _Dp __d, _Alloc __a)
4128     : __ptr_(0)
4129 {
4130 #ifndef _LIBCPP_NO_EXCEPTIONS
4131     try
4132     {
4133 #endif  // _LIBCPP_NO_EXCEPTIONS
4134         typedef __shared_ptr_pointer<nullptr_t, _Dp, _Alloc> _CntrlBlk;
4135         typedef typename _Alloc::template rebind<_CntrlBlk>::other _A2;
4136         typedef __allocator_destructor<_A2> _D2;
4137         _A2 __a2(__a);
4138         unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4139         ::new(__hold2.get()) _CntrlBlk(__p, __d, __a);
4140         __cntrl_ = __hold2.release();
4141 #ifndef _LIBCPP_NO_EXCEPTIONS
4142     }
4143     catch (...)
4144     {
4145         __d(__p);
4146         throw;
4147     }
4148 #endif  // _LIBCPP_NO_EXCEPTIONS
4149 }
4150
4151 template<class _Tp>
4152 template<class _Yp>
4153 inline _LIBCPP_INLINE_VISIBILITY
4154 shared_ptr<_Tp>::shared_ptr(const shared_ptr<_Yp>& __r, element_type *__p) _NOEXCEPT
4155     : __ptr_(__p),
4156       __cntrl_(__r.__cntrl_)
4157 {
4158     if (__cntrl_)
4159         __cntrl_->__add_shared();
4160 }
4161
4162 template<class _Tp>
4163 inline _LIBCPP_INLINE_VISIBILITY
4164 shared_ptr<_Tp>::shared_ptr(const shared_ptr& __r) _NOEXCEPT
4165     : __ptr_(__r.__ptr_),
4166       __cntrl_(__r.__cntrl_)
4167 {
4168     if (__cntrl_)
4169         __cntrl_->__add_shared();
4170 }
4171
4172 template<class _Tp>
4173 template<class _Yp>
4174 inline _LIBCPP_INLINE_VISIBILITY
4175 shared_ptr<_Tp>::shared_ptr(const shared_ptr<_Yp>& __r,
4176                             typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type)
4177          _NOEXCEPT
4178     : __ptr_(__r.__ptr_),
4179       __cntrl_(__r.__cntrl_)
4180 {
4181     if (__cntrl_)
4182         __cntrl_->__add_shared();
4183 }
4184
4185 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4186
4187 template<class _Tp>
4188 inline _LIBCPP_INLINE_VISIBILITY
4189 shared_ptr<_Tp>::shared_ptr(shared_ptr&& __r) _NOEXCEPT
4190     : __ptr_(__r.__ptr_),
4191       __cntrl_(__r.__cntrl_)
4192 {
4193     __r.__ptr_ = 0;
4194     __r.__cntrl_ = 0;
4195 }
4196
4197 template<class _Tp>
4198 template<class _Yp>
4199 inline _LIBCPP_INLINE_VISIBILITY
4200 shared_ptr<_Tp>::shared_ptr(shared_ptr<_Yp>&& __r,
4201                             typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type)
4202          _NOEXCEPT
4203     : __ptr_(__r.__ptr_),
4204       __cntrl_(__r.__cntrl_)
4205 {
4206     __r.__ptr_ = 0;
4207     __r.__cntrl_ = 0;
4208 }
4209
4210 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4211
4212 template<class _Tp>
4213 template<class _Yp, class>
4214 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4215 shared_ptr<_Tp>::shared_ptr(auto_ptr<_Yp>&& __r)
4216 #else
4217 shared_ptr<_Tp>::shared_ptr(auto_ptr<_Yp> __r)
4218 #endif
4219     : __ptr_(__r.get())
4220 {
4221     typedef __shared_ptr_pointer<_Yp*, default_delete<_Yp>, allocator<_Yp> > _CntrlBlk;
4222     __cntrl_ = new _CntrlBlk(__r.get(), default_delete<_Yp>(), allocator<_Yp>());
4223     __enable_weak_this(__r.get());
4224     __r.release();
4225 }
4226
4227 template<class _Tp>
4228 template <class _Yp, class _Dp, class>
4229 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4230 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp>&& __r,
4231 #else
4232 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp> __r,
4233 #endif
4234            typename enable_if<!is_lvalue_reference<_Dp>::value, __nat>::type)
4235     : __ptr_(__r.get())
4236 {
4237     typedef __shared_ptr_pointer<_Yp*, _Dp, allocator<_Yp> > _CntrlBlk;
4238     __cntrl_ = new _CntrlBlk(__r.get(), __r.get_deleter(), allocator<_Yp>());
4239     __enable_weak_this(__r.get());
4240     __r.release();
4241 }
4242
4243 template<class _Tp>
4244 template <class _Yp, class _Dp, class>
4245 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4246 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp>&& __r,
4247 #else
4248 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp> __r,
4249 #endif
4250            typename enable_if<is_lvalue_reference<_Dp>::value, __nat>::type)
4251     : __ptr_(__r.get())
4252 {
4253     typedef __shared_ptr_pointer<_Yp*,
4254                                  reference_wrapper<typename remove_reference<_Dp>::type>,
4255                                  allocator<_Yp> > _CntrlBlk;
4256     __cntrl_ = new _CntrlBlk(__r.get(), ref(__r.get_deleter()), allocator<_Yp>());
4257     __enable_weak_this(__r.get());
4258     __r.release();
4259 }
4260
4261 #ifndef _LIBCPP_HAS_NO_VARIADICS
4262
4263 template<class _Tp>
4264 template<class ..._Args>
4265 shared_ptr<_Tp>
4266 shared_ptr<_Tp>::make_shared(_Args&& ...__args)
4267 {
4268     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4269     typedef allocator<_CntrlBlk> _A2;
4270     typedef __allocator_destructor<_A2> _D2;
4271     _A2 __a2;
4272     unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4273     ::new(__hold2.get()) _CntrlBlk(__a2, _VSTD::forward<_Args>(__args)...);
4274     shared_ptr<_Tp> __r;
4275     __r.__ptr_ = __hold2.get()->get();
4276     __r.__cntrl_ = __hold2.release();
4277     __r.__enable_weak_this(__r.__ptr_);
4278     return __r;
4279 }
4280
4281 template<class _Tp>
4282 template<class _Alloc, class ..._Args>
4283 shared_ptr<_Tp>
4284 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _Args&& ...__args)
4285 {
4286     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4287     typedef typename _Alloc::template rebind<_CntrlBlk>::other _A2;
4288     typedef __allocator_destructor<_A2> _D2;
4289     _A2 __a2(__a);
4290     unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
4291     ::new(__hold2.get()) _CntrlBlk(__a, _VSTD::forward<_Args>(__args)...);
4292     shared_ptr<_Tp> __r;
4293     __r.__ptr_ = __hold2.get()->get();
4294     __r.__cntrl_ = __hold2.release();
4295     __r.__enable_weak_this(__r.__ptr_);
4296     return __r;
4297 }
4298
4299 #else  // _LIBCPP_HAS_NO_VARIADICS
4300
4301 template<class _Tp>
4302 shared_ptr<_Tp>
4303 shared_ptr<_Tp>::make_shared()
4304 {
4305     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4306     typedef allocator<_CntrlBlk> _Alloc2;
4307     typedef __allocator_destructor<_Alloc2> _D2;
4308     _Alloc2 __alloc2;
4309     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4310     ::new(__hold2.get()) _CntrlBlk(__alloc2);
4311     shared_ptr<_Tp> __r;
4312     __r.__ptr_ = __hold2.get()->get();
4313     __r.__cntrl_ = __hold2.release();
4314     __r.__enable_weak_this(__r.__ptr_);
4315     return __r;
4316 }
4317
4318 template<class _Tp>
4319 template<class _A0>
4320 shared_ptr<_Tp>
4321 shared_ptr<_Tp>::make_shared(_A0& __a0)
4322 {
4323     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4324     typedef allocator<_CntrlBlk> _Alloc2;
4325     typedef __allocator_destructor<_Alloc2> _D2;
4326     _Alloc2 __alloc2;
4327     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4328     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0);
4329     shared_ptr<_Tp> __r;
4330     __r.__ptr_ = __hold2.get()->get();
4331     __r.__cntrl_ = __hold2.release();
4332     __r.__enable_weak_this(__r.__ptr_);
4333     return __r;
4334 }
4335
4336 template<class _Tp>
4337 template<class _A0, class _A1>
4338 shared_ptr<_Tp>
4339 shared_ptr<_Tp>::make_shared(_A0& __a0, _A1& __a1)
4340 {
4341     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4342     typedef allocator<_CntrlBlk> _Alloc2;
4343     typedef __allocator_destructor<_Alloc2> _D2;
4344     _Alloc2 __alloc2;
4345     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4346     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0, __a1);
4347     shared_ptr<_Tp> __r;
4348     __r.__ptr_ = __hold2.get()->get();
4349     __r.__cntrl_ = __hold2.release();
4350     __r.__enable_weak_this(__r.__ptr_);
4351     return __r;
4352 }
4353
4354 template<class _Tp>
4355 template<class _A0, class _A1, class _A2>
4356 shared_ptr<_Tp>
4357 shared_ptr<_Tp>::make_shared(_A0& __a0, _A1& __a1, _A2& __a2)
4358 {
4359     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
4360     typedef allocator<_CntrlBlk> _Alloc2;
4361     typedef __allocator_destructor<_Alloc2> _D2;
4362     _Alloc2 __alloc2;
4363     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4364     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0, __a1, __a2);
4365     shared_ptr<_Tp> __r;
4366     __r.__ptr_ = __hold2.get()->get();
4367     __r.__cntrl_ = __hold2.release();
4368     __r.__enable_weak_this(__r.__ptr_);
4369     return __r;
4370 }
4371
4372 template<class _Tp>
4373 template<class _Alloc>
4374 shared_ptr<_Tp>
4375 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a)
4376 {
4377     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4378     typedef typename _Alloc::template rebind<_CntrlBlk>::other _Alloc2;
4379     typedef __allocator_destructor<_Alloc2> _D2;
4380     _Alloc2 __alloc2(__a);
4381     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4382     ::new(__hold2.get()) _CntrlBlk(__a);
4383     shared_ptr<_Tp> __r;
4384     __r.__ptr_ = __hold2.get()->get();
4385     __r.__cntrl_ = __hold2.release();
4386     __r.__enable_weak_this(__r.__ptr_);
4387     return __r;
4388 }
4389
4390 template<class _Tp>
4391 template<class _Alloc, class _A0>
4392 shared_ptr<_Tp>
4393 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0)
4394 {
4395     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4396     typedef typename _Alloc::template rebind<_CntrlBlk>::other _Alloc2;
4397     typedef __allocator_destructor<_Alloc2> _D2;
4398     _Alloc2 __alloc2(__a);
4399     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4400     ::new(__hold2.get()) _CntrlBlk(__a, __a0);
4401     shared_ptr<_Tp> __r;
4402     __r.__ptr_ = __hold2.get()->get();
4403     __r.__cntrl_ = __hold2.release();
4404     __r.__enable_weak_this(__r.__ptr_);
4405     return __r;
4406 }
4407
4408 template<class _Tp>
4409 template<class _Alloc, class _A0, class _A1>
4410 shared_ptr<_Tp>
4411 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1)
4412 {
4413     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4414     typedef typename _Alloc::template rebind<_CntrlBlk>::other _Alloc2;
4415     typedef __allocator_destructor<_Alloc2> _D2;
4416     _Alloc2 __alloc2(__a);
4417     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4418     ::new(__hold2.get()) _CntrlBlk(__a, __a0, __a1);
4419     shared_ptr<_Tp> __r;
4420     __r.__ptr_ = __hold2.get()->get();
4421     __r.__cntrl_ = __hold2.release();
4422     __r.__enable_weak_this(__r.__ptr_);
4423     return __r;
4424 }
4425
4426 template<class _Tp>
4427 template<class _Alloc, class _A0, class _A1, class _A2>
4428 shared_ptr<_Tp>
4429 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2)
4430 {
4431     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
4432     typedef typename _Alloc::template rebind<_CntrlBlk>::other _Alloc2;
4433     typedef __allocator_destructor<_Alloc2> _D2;
4434     _Alloc2 __alloc2(__a);
4435     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
4436     ::new(__hold2.get()) _CntrlBlk(__a, __a0, __a1, __a2);
4437     shared_ptr<_Tp> __r;
4438     __r.__ptr_ = __hold2.get()->get();
4439     __r.__cntrl_ = __hold2.release();
4440     __r.__enable_weak_this(__r.__ptr_);
4441     return __r;
4442 }
4443
4444 #endif  // _LIBCPP_HAS_NO_VARIADICS
4445
4446 template<class _Tp>
4447 shared_ptr<_Tp>::~shared_ptr()
4448 {
4449     if (__cntrl_)
4450         __cntrl_->__release_shared();
4451 }
4452
4453 template<class _Tp>
4454 inline _LIBCPP_INLINE_VISIBILITY
4455 shared_ptr<_Tp>&
4456 shared_ptr<_Tp>::operator=(const shared_ptr& __r) _NOEXCEPT
4457 {
4458     shared_ptr(__r).swap(*this);
4459     return *this;
4460 }
4461
4462 template<class _Tp>
4463 template<class _Yp>
4464 inline _LIBCPP_INLINE_VISIBILITY
4465 typename enable_if
4466 <
4467     is_convertible<_Yp*, _Tp*>::value,
4468     shared_ptr<_Tp>&
4469 >::type
4470 shared_ptr<_Tp>::operator=(const shared_ptr<_Yp>& __r) _NOEXCEPT
4471 {
4472     shared_ptr(__r).swap(*this);
4473     return *this;
4474 }
4475
4476 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4477
4478 template<class _Tp>
4479 inline _LIBCPP_INLINE_VISIBILITY
4480 shared_ptr<_Tp>&
4481 shared_ptr<_Tp>::operator=(shared_ptr&& __r) _NOEXCEPT
4482 {
4483     shared_ptr(_VSTD::move(__r)).swap(*this);
4484     return *this;
4485 }
4486
4487 template<class _Tp>
4488 template<class _Yp>
4489 inline _LIBCPP_INLINE_VISIBILITY
4490 typename enable_if
4491 <
4492     is_convertible<_Yp*, _Tp*>::value,
4493     shared_ptr<_Tp>&
4494 >::type
4495 shared_ptr<_Tp>::operator=(shared_ptr<_Yp>&& __r)
4496 {
4497     shared_ptr(_VSTD::move(__r)).swap(*this);
4498     return *this;
4499 }
4500
4501 template<class _Tp>
4502 template<class _Yp>
4503 inline _LIBCPP_INLINE_VISIBILITY
4504 typename enable_if
4505 <
4506     !is_array<_Yp>::value &&
4507     is_convertible<_Yp*, _Tp*>::value,
4508     shared_ptr<_Tp>&
4509 >::type
4510 shared_ptr<_Tp>::operator=(auto_ptr<_Yp>&& __r)
4511 {
4512     shared_ptr(_VSTD::move(__r)).swap(*this);
4513     return *this;
4514 }
4515
4516 template<class _Tp>
4517 template <class _Yp, class _Dp>
4518 inline _LIBCPP_INLINE_VISIBILITY
4519 typename enable_if
4520 <
4521     !is_array<_Yp>::value &&
4522     is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, _Tp*>::value,
4523     shared_ptr<_Tp>&
4524 >::type
4525 shared_ptr<_Tp>::operator=(unique_ptr<_Yp, _Dp>&& __r)
4526 {
4527     shared_ptr(_VSTD::move(__r)).swap(*this);
4528     return *this;
4529 }
4530
4531 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4532
4533 template<class _Tp>
4534 template<class _Yp>
4535 inline _LIBCPP_INLINE_VISIBILITY
4536 typename enable_if
4537 <
4538     !is_array<_Yp>::value &&
4539     is_convertible<_Yp*, _Tp*>::value,
4540     shared_ptr<_Tp>&
4541 >::type
4542 shared_ptr<_Tp>::operator=(auto_ptr<_Yp> __r)
4543 {
4544     shared_ptr(__r).swap(*this);
4545     return *this;
4546 }
4547
4548 template<class _Tp>
4549 template <class _Yp, class _Dp>
4550 inline _LIBCPP_INLINE_VISIBILITY
4551 typename enable_if
4552 <
4553     !is_array<_Yp>::value &&
4554     is_convertible<typename unique_ptr<_Yp, _Dp>::pointer, _Tp*>::value,
4555     shared_ptr<_Tp>&
4556 >::type
4557 shared_ptr<_Tp>::operator=(unique_ptr<_Yp, _Dp> __r)
4558 {
4559     shared_ptr(_VSTD::move(__r)).swap(*this);
4560     return *this;
4561 }
4562
4563 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4564
4565 template<class _Tp>
4566 inline _LIBCPP_INLINE_VISIBILITY
4567 void
4568 shared_ptr<_Tp>::swap(shared_ptr& __r) _NOEXCEPT
4569 {
4570     _VSTD::swap(__ptr_, __r.__ptr_);
4571     _VSTD::swap(__cntrl_, __r.__cntrl_);
4572 }
4573
4574 template<class _Tp>
4575 inline _LIBCPP_INLINE_VISIBILITY
4576 void
4577 shared_ptr<_Tp>::reset() _NOEXCEPT
4578 {
4579     shared_ptr().swap(*this);
4580 }
4581
4582 template<class _Tp>
4583 template<class _Yp>
4584 inline _LIBCPP_INLINE_VISIBILITY
4585 typename enable_if
4586 <
4587     is_convertible<_Yp*, _Tp*>::value,
4588     void
4589 >::type
4590 shared_ptr<_Tp>::reset(_Yp* __p)
4591 {
4592     shared_ptr(__p).swap(*this);
4593 }
4594
4595 template<class _Tp>
4596 template<class _Yp, class _Dp>
4597 inline _LIBCPP_INLINE_VISIBILITY
4598 typename enable_if
4599 <
4600     is_convertible<_Yp*, _Tp*>::value,
4601     void
4602 >::type
4603 shared_ptr<_Tp>::reset(_Yp* __p, _Dp __d)
4604 {
4605     shared_ptr(__p, __d).swap(*this);
4606 }
4607
4608 template<class _Tp>
4609 template<class _Yp, class _Dp, class _Alloc>
4610 inline _LIBCPP_INLINE_VISIBILITY
4611 typename enable_if
4612 <
4613     is_convertible<_Yp*, _Tp*>::value,
4614     void
4615 >::type
4616 shared_ptr<_Tp>::reset(_Yp* __p, _Dp __d, _Alloc __a)
4617 {
4618     shared_ptr(__p, __d, __a).swap(*this);
4619 }
4620
4621 #ifndef _LIBCPP_HAS_NO_VARIADICS
4622
4623 template<class _Tp, class ..._Args>
4624 inline _LIBCPP_INLINE_VISIBILITY
4625 typename enable_if
4626 <
4627     !is_array<_Tp>::value,
4628     shared_ptr<_Tp>
4629 >::type
4630 make_shared(_Args&& ...__args)
4631 {
4632     return shared_ptr<_Tp>::make_shared(_VSTD::forward<_Args>(__args)...);
4633 }
4634
4635 template<class _Tp, class _Alloc, class ..._Args>
4636 inline _LIBCPP_INLINE_VISIBILITY
4637 typename enable_if
4638 <
4639     !is_array<_Tp>::value,
4640     shared_ptr<_Tp>
4641 >::type
4642 allocate_shared(const _Alloc& __a, _Args&& ...__args)
4643 {
4644     return shared_ptr<_Tp>::allocate_shared(__a, _VSTD::forward<_Args>(__args)...);
4645 }
4646
4647 #else  // _LIBCPP_HAS_NO_VARIADICS
4648
4649 template<class _Tp>
4650 inline _LIBCPP_INLINE_VISIBILITY
4651 shared_ptr<_Tp>
4652 make_shared()
4653 {
4654     return shared_ptr<_Tp>::make_shared();
4655 }
4656
4657 template<class _Tp, class _A0>
4658 inline _LIBCPP_INLINE_VISIBILITY
4659 shared_ptr<_Tp>
4660 make_shared(_A0& __a0)
4661 {
4662     return shared_ptr<_Tp>::make_shared(__a0);
4663 }
4664
4665 template<class _Tp, class _A0, class _A1>
4666 inline _LIBCPP_INLINE_VISIBILITY
4667 shared_ptr<_Tp>
4668 make_shared(_A0& __a0, _A1& __a1)
4669 {
4670     return shared_ptr<_Tp>::make_shared(__a0, __a1);
4671 }
4672
4673 template<class _Tp, class _A0, class _A1, class _A2>
4674 inline _LIBCPP_INLINE_VISIBILITY
4675 shared_ptr<_Tp>
4676 make_shared(_A0& __a0, _A1& __a1, _A2& __a2)
4677 {
4678     return shared_ptr<_Tp>::make_shared(__a0, __a1, __a2);
4679 }
4680
4681 template<class _Tp, class _Alloc>
4682 inline _LIBCPP_INLINE_VISIBILITY
4683 shared_ptr<_Tp>
4684 allocate_shared(const _Alloc& __a)
4685 {
4686     return shared_ptr<_Tp>::allocate_shared(__a);
4687 }
4688
4689 template<class _Tp, class _Alloc, class _A0>
4690 inline _LIBCPP_INLINE_VISIBILITY
4691 shared_ptr<_Tp>
4692 allocate_shared(const _Alloc& __a, _A0& __a0)
4693 {
4694     return shared_ptr<_Tp>::allocate_shared(__a, __a0);
4695 }
4696
4697 template<class _Tp, class _Alloc, class _A0, class _A1>
4698 inline _LIBCPP_INLINE_VISIBILITY
4699 shared_ptr<_Tp>
4700 allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1)
4701 {
4702     return shared_ptr<_Tp>::allocate_shared(__a, __a0, __a1);
4703 }
4704
4705 template<class _Tp, class _Alloc, class _A0, class _A1, class _A2>
4706 inline _LIBCPP_INLINE_VISIBILITY
4707 shared_ptr<_Tp>
4708 allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2)
4709 {
4710     return shared_ptr<_Tp>::allocate_shared(__a, __a0, __a1, __a2);
4711 }
4712
4713 #endif  // _LIBCPP_HAS_NO_VARIADICS
4714
4715 template<class _Tp, class _Up>
4716 inline _LIBCPP_INLINE_VISIBILITY
4717 bool
4718 operator==(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4719 {
4720     return __x.get() == __y.get();
4721 }
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 == __y);
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     typedef typename common_type<_Tp*, _Up*>::type _V;
4737     return less<_V>()(__x.get(), __y.get());
4738 }
4739
4740 template<class _Tp, class _Up>
4741 inline _LIBCPP_INLINE_VISIBILITY
4742 bool
4743 operator>(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
4744 {
4745     return __y < __x;
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 !(__x < __y);
4762 }
4763
4764 template<class _Tp>
4765 inline _LIBCPP_INLINE_VISIBILITY
4766 bool
4767 operator==(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4768 {
4769     return !__x;
4770 }
4771
4772 template<class _Tp>
4773 inline _LIBCPP_INLINE_VISIBILITY
4774 bool
4775 operator==(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4776 {
4777     return !__x;
4778 }
4779
4780 template<class _Tp>
4781 inline _LIBCPP_INLINE_VISIBILITY
4782 bool
4783 operator!=(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4784 {
4785     return static_cast<bool>(__x);
4786 }
4787
4788 template<class _Tp>
4789 inline _LIBCPP_INLINE_VISIBILITY
4790 bool
4791 operator!=(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4792 {
4793     return static_cast<bool>(__x);
4794 }
4795
4796 template<class _Tp>
4797 inline _LIBCPP_INLINE_VISIBILITY
4798 bool
4799 operator<(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4800 {
4801     return less<_Tp*>()(__x.get(), nullptr);
4802 }
4803
4804 template<class _Tp>
4805 inline _LIBCPP_INLINE_VISIBILITY
4806 bool
4807 operator<(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4808 {
4809     return less<_Tp*>()(nullptr, __x.get());
4810 }
4811
4812 template<class _Tp>
4813 inline _LIBCPP_INLINE_VISIBILITY
4814 bool
4815 operator>(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4816 {
4817     return nullptr < __x;
4818 }
4819
4820 template<class _Tp>
4821 inline _LIBCPP_INLINE_VISIBILITY
4822 bool
4823 operator>(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4824 {
4825     return __x < nullptr;
4826 }
4827
4828 template<class _Tp>
4829 inline _LIBCPP_INLINE_VISIBILITY
4830 bool
4831 operator<=(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4832 {
4833     return !(nullptr < __x);
4834 }
4835
4836 template<class _Tp>
4837 inline _LIBCPP_INLINE_VISIBILITY
4838 bool
4839 operator<=(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4840 {
4841     return !(__x < nullptr);
4842 }
4843
4844 template<class _Tp>
4845 inline _LIBCPP_INLINE_VISIBILITY
4846 bool
4847 operator>=(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
4848 {
4849     return !(__x < nullptr);
4850 }
4851
4852 template<class _Tp>
4853 inline _LIBCPP_INLINE_VISIBILITY
4854 bool
4855 operator>=(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
4856 {
4857     return !(nullptr < __x);
4858 }
4859
4860 template<class _Tp>
4861 inline _LIBCPP_INLINE_VISIBILITY
4862 void
4863 swap(shared_ptr<_Tp>& __x, shared_ptr<_Tp>& __y) _NOEXCEPT
4864 {
4865     __x.swap(__y);
4866 }
4867
4868 template<class _Tp, class _Up>
4869 inline _LIBCPP_INLINE_VISIBILITY
4870 typename enable_if
4871 <
4872     !is_array<_Tp>::value && !is_array<_Up>::value,
4873     shared_ptr<_Tp>
4874 >::type
4875 static_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
4876 {
4877     return shared_ptr<_Tp>(__r, static_cast<_Tp*>(__r.get()));
4878 }
4879
4880 template<class _Tp, class _Up>
4881 inline _LIBCPP_INLINE_VISIBILITY
4882 typename enable_if
4883 <
4884     !is_array<_Tp>::value && !is_array<_Up>::value,
4885     shared_ptr<_Tp>
4886 >::type
4887 dynamic_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
4888 {
4889     _Tp* __p = dynamic_cast<_Tp*>(__r.get());
4890     return __p ? shared_ptr<_Tp>(__r, __p) : shared_ptr<_Tp>();
4891 }
4892
4893 template<class _Tp, class _Up>
4894 typename enable_if
4895 <
4896     is_array<_Tp>::value == is_array<_Up>::value,
4897     shared_ptr<_Tp>
4898 >::type
4899 const_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
4900 {
4901     typedef typename remove_extent<_Tp>::type _RTp;
4902     return shared_ptr<_Tp>(__r, const_cast<_RTp*>(__r.get()));
4903 }
4904
4905 #ifndef _LIBCPP_NO_RTTI
4906
4907 template<class _Dp, class _Tp>
4908 inline _LIBCPP_INLINE_VISIBILITY
4909 _Dp*
4910 get_deleter(const shared_ptr<_Tp>& __p) _NOEXCEPT
4911 {
4912     return __p.template __get_deleter<_Dp>();
4913 }
4914
4915 #endif  // _LIBCPP_NO_RTTI
4916
4917 template<class _Tp>
4918 class _LIBCPP_VISIBLE weak_ptr
4919 {
4920 public:
4921     typedef _Tp element_type;
4922 private:
4923     element_type*        __ptr_;
4924     __shared_weak_count* __cntrl_;
4925
4926 public:
4927     _LIBCPP_CONSTEXPR weak_ptr() _NOEXCEPT;
4928     template<class _Yp> weak_ptr(shared_ptr<_Yp> const& __r,
4929                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
4930                         _NOEXCEPT;
4931     weak_ptr(weak_ptr const& __r) _NOEXCEPT;
4932     template<class _Yp> weak_ptr(weak_ptr<_Yp> const& __r,
4933                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
4934                          _NOEXCEPT;
4935
4936 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4937     weak_ptr(weak_ptr&& __r) _NOEXCEPT;
4938     template<class _Yp> weak_ptr(weak_ptr<_Yp>&& __r,
4939                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
4940                          _NOEXCEPT;
4941 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4942     ~weak_ptr();
4943
4944     weak_ptr& operator=(weak_ptr const& __r) _NOEXCEPT;
4945     template<class _Yp>
4946         typename enable_if
4947         <
4948             is_convertible<_Yp*, element_type*>::value,
4949             weak_ptr&
4950         >::type
4951         operator=(weak_ptr<_Yp> const& __r) _NOEXCEPT;
4952
4953 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
4954
4955     weak_ptr& operator=(weak_ptr&& __r) _NOEXCEPT;
4956     template<class _Yp>
4957         typename enable_if
4958         <
4959             is_convertible<_Yp*, element_type*>::value,
4960             weak_ptr&
4961         >::type
4962         operator=(weak_ptr<_Yp>&& __r) _NOEXCEPT;
4963
4964 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
4965
4966     template<class _Yp>
4967         typename enable_if
4968         <
4969             is_convertible<_Yp*, element_type*>::value,
4970             weak_ptr&
4971         >::type
4972         operator=(shared_ptr<_Yp> const& __r) _NOEXCEPT;
4973
4974     void swap(weak_ptr& __r) _NOEXCEPT;
4975     void reset() _NOEXCEPT;
4976
4977     _LIBCPP_INLINE_VISIBILITY
4978     long use_count() const _NOEXCEPT
4979         {return __cntrl_ ? __cntrl_->use_count() : 0;}
4980     _LIBCPP_INLINE_VISIBILITY
4981     bool expired() const _NOEXCEPT
4982         {return __cntrl_ == 0 || __cntrl_->use_count() == 0;}
4983     shared_ptr<_Tp> lock() const _NOEXCEPT;
4984     template<class _Up>
4985         _LIBCPP_INLINE_VISIBILITY
4986         bool owner_before(const shared_ptr<_Up>& __r) const
4987         {return __cntrl_ < __r.__cntrl_;}
4988     template<class _Up>
4989         _LIBCPP_INLINE_VISIBILITY
4990         bool owner_before(const weak_ptr<_Up>& __r) const
4991         {return __cntrl_ < __r.__cntrl_;}
4992
4993     template <class _Up> friend class _LIBCPP_VISIBLE weak_ptr;
4994     template <class _Up> friend class _LIBCPP_VISIBLE shared_ptr;
4995 };
4996
4997 template<class _Tp>
4998 inline _LIBCPP_INLINE_VISIBILITY
4999 _LIBCPP_CONSTEXPR
5000 weak_ptr<_Tp>::weak_ptr() _NOEXCEPT
5001     : __ptr_(0),
5002       __cntrl_(0)
5003 {
5004 }
5005
5006 template<class _Tp>
5007 inline _LIBCPP_INLINE_VISIBILITY
5008 weak_ptr<_Tp>::weak_ptr(weak_ptr const& __r) _NOEXCEPT
5009     : __ptr_(__r.__ptr_),
5010       __cntrl_(__r.__cntrl_)
5011 {
5012     if (__cntrl_)
5013         __cntrl_->__add_weak();
5014 }
5015
5016 template<class _Tp>
5017 template<class _Yp>
5018 inline _LIBCPP_INLINE_VISIBILITY
5019 weak_ptr<_Tp>::weak_ptr(shared_ptr<_Yp> const& __r,
5020                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
5021                          _NOEXCEPT
5022     : __ptr_(__r.__ptr_),
5023       __cntrl_(__r.__cntrl_)
5024 {
5025     if (__cntrl_)
5026         __cntrl_->__add_weak();
5027 }
5028
5029 template<class _Tp>
5030 template<class _Yp>
5031 inline _LIBCPP_INLINE_VISIBILITY
5032 weak_ptr<_Tp>::weak_ptr(weak_ptr<_Yp> const& __r,
5033                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
5034          _NOEXCEPT
5035     : __ptr_(__r.__ptr_),
5036       __cntrl_(__r.__cntrl_)
5037 {
5038     if (__cntrl_)
5039         __cntrl_->__add_weak();
5040 }
5041
5042 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
5043
5044 template<class _Tp>
5045 inline _LIBCPP_INLINE_VISIBILITY
5046 weak_ptr<_Tp>::weak_ptr(weak_ptr&& __r) _NOEXCEPT
5047     : __ptr_(__r.__ptr_),
5048       __cntrl_(__r.__cntrl_)
5049 {
5050     __r.__ptr_ = 0;
5051     __r.__cntrl_ = 0;
5052 }
5053
5054 template<class _Tp>
5055 template<class _Yp>
5056 inline _LIBCPP_INLINE_VISIBILITY
5057 weak_ptr<_Tp>::weak_ptr(weak_ptr<_Yp>&& __r,
5058                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
5059          _NOEXCEPT
5060     : __ptr_(__r.__ptr_),
5061       __cntrl_(__r.__cntrl_)
5062 {
5063     __r.__ptr_ = 0;
5064     __r.__cntrl_ = 0;
5065 }
5066
5067 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
5068
5069 template<class _Tp>
5070 weak_ptr<_Tp>::~weak_ptr()
5071 {
5072     if (__cntrl_)
5073         __cntrl_->__release_weak();
5074 }
5075
5076 template<class _Tp>
5077 inline _LIBCPP_INLINE_VISIBILITY
5078 weak_ptr<_Tp>&
5079 weak_ptr<_Tp>::operator=(weak_ptr const& __r) _NOEXCEPT
5080 {
5081     weak_ptr(__r).swap(*this);
5082     return *this;
5083 }
5084
5085 template<class _Tp>
5086 template<class _Yp>
5087 inline _LIBCPP_INLINE_VISIBILITY
5088 typename enable_if
5089 <
5090     is_convertible<_Yp*, _Tp*>::value,
5091     weak_ptr<_Tp>&
5092 >::type
5093 weak_ptr<_Tp>::operator=(weak_ptr<_Yp> const& __r) _NOEXCEPT
5094 {
5095     weak_ptr(__r).swap(*this);
5096     return *this;
5097 }
5098
5099 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
5100
5101 template<class _Tp>
5102 inline _LIBCPP_INLINE_VISIBILITY
5103 weak_ptr<_Tp>&
5104 weak_ptr<_Tp>::operator=(weak_ptr&& __r) _NOEXCEPT
5105 {
5106     weak_ptr(_VSTD::move(__r)).swap(*this);
5107     return *this;
5108 }
5109
5110 template<class _Tp>
5111 template<class _Yp>
5112 inline _LIBCPP_INLINE_VISIBILITY
5113 typename enable_if
5114 <
5115     is_convertible<_Yp*, _Tp*>::value,
5116     weak_ptr<_Tp>&
5117 >::type
5118 weak_ptr<_Tp>::operator=(weak_ptr<_Yp>&& __r) _NOEXCEPT
5119 {
5120     weak_ptr(_VSTD::move(__r)).swap(*this);
5121     return *this;
5122 }
5123
5124 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
5125
5126 template<class _Tp>
5127 template<class _Yp>
5128 inline _LIBCPP_INLINE_VISIBILITY
5129 typename enable_if
5130 <
5131     is_convertible<_Yp*, _Tp*>::value,
5132     weak_ptr<_Tp>&
5133 >::type
5134 weak_ptr<_Tp>::operator=(shared_ptr<_Yp> const& __r) _NOEXCEPT
5135 {
5136     weak_ptr(__r).swap(*this);
5137     return *this;
5138 }
5139
5140 template<class _Tp>
5141 inline _LIBCPP_INLINE_VISIBILITY
5142 void
5143 weak_ptr<_Tp>::swap(weak_ptr& __r) _NOEXCEPT
5144 {
5145     _VSTD::swap(__ptr_, __r.__ptr_);
5146     _VSTD::swap(__cntrl_, __r.__cntrl_);
5147 }
5148
5149 template<class _Tp>
5150 inline _LIBCPP_INLINE_VISIBILITY
5151 void
5152 swap(weak_ptr<_Tp>& __x, weak_ptr<_Tp>& __y) _NOEXCEPT
5153 {
5154     __x.swap(__y);
5155 }
5156
5157 template<class _Tp>
5158 inline _LIBCPP_INLINE_VISIBILITY
5159 void
5160 weak_ptr<_Tp>::reset() _NOEXCEPT
5161 {
5162     weak_ptr().swap(*this);
5163 }
5164
5165 template<class _Tp>
5166 template<class _Yp>
5167 shared_ptr<_Tp>::shared_ptr(const weak_ptr<_Yp>& __r,
5168                             typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type)
5169     : __ptr_(__r.__ptr_),
5170       __cntrl_(__r.__cntrl_ ? __r.__cntrl_->lock() : __r.__cntrl_)
5171 {
5172     if (__cntrl_ == 0)
5173 #ifndef _LIBCPP_NO_EXCEPTIONS
5174         throw bad_weak_ptr();
5175 #else
5176         assert(!"bad_weak_ptr");
5177 #endif
5178 }
5179
5180 template<class _Tp>
5181 shared_ptr<_Tp>
5182 weak_ptr<_Tp>::lock() const _NOEXCEPT
5183 {
5184     shared_ptr<_Tp> __r;
5185     __r.__cntrl_ = __cntrl_ ? __cntrl_->lock() : __cntrl_;
5186     if (__r.__cntrl_)
5187         __r.__ptr_ = __ptr_;
5188     return __r;
5189 }
5190
5191 template <class _Tp> struct owner_less;
5192
5193 template <class _Tp>
5194 struct _LIBCPP_VISIBLE owner_less<shared_ptr<_Tp> >
5195     : binary_function<shared_ptr<_Tp>, shared_ptr<_Tp>, bool>
5196 {
5197     typedef bool result_type;
5198     _LIBCPP_INLINE_VISIBILITY
5199     bool operator()(shared_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const
5200         {return __x.owner_before(__y);}
5201     _LIBCPP_INLINE_VISIBILITY
5202     bool operator()(shared_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const
5203         {return __x.owner_before(__y);}
5204     _LIBCPP_INLINE_VISIBILITY
5205     bool operator()(  weak_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const
5206         {return __x.owner_before(__y);}
5207 };
5208
5209 template <class _Tp>
5210 struct _LIBCPP_VISIBLE owner_less<weak_ptr<_Tp> >
5211     : binary_function<weak_ptr<_Tp>, weak_ptr<_Tp>, bool>
5212 {
5213     typedef bool result_type;
5214     _LIBCPP_INLINE_VISIBILITY
5215     bool operator()(  weak_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const
5216         {return __x.owner_before(__y);}
5217     _LIBCPP_INLINE_VISIBILITY
5218     bool operator()(shared_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const
5219         {return __x.owner_before(__y);}
5220     _LIBCPP_INLINE_VISIBILITY
5221     bool operator()(  weak_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const
5222         {return __x.owner_before(__y);}
5223 };
5224
5225 template<class _Tp>
5226 class _LIBCPP_VISIBLE enable_shared_from_this
5227 {
5228     mutable weak_ptr<_Tp> __weak_this_;
5229 protected:
5230     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
5231     enable_shared_from_this() _NOEXCEPT {}
5232     _LIBCPP_INLINE_VISIBILITY
5233     enable_shared_from_this(enable_shared_from_this const&) _NOEXCEPT {}
5234     _LIBCPP_INLINE_VISIBILITY
5235     enable_shared_from_this& operator=(enable_shared_from_this const&) _NOEXCEPT
5236         {return *this;}
5237     _LIBCPP_INLINE_VISIBILITY
5238     ~enable_shared_from_this() {}
5239 public:
5240     _LIBCPP_INLINE_VISIBILITY
5241     shared_ptr<_Tp> shared_from_this()
5242         {return shared_ptr<_Tp>(__weak_this_);}
5243     _LIBCPP_INLINE_VISIBILITY
5244     shared_ptr<_Tp const> shared_from_this() const
5245         {return shared_ptr<const _Tp>(__weak_this_);}
5246
5247     template <class _Up> friend class shared_ptr;
5248 };
5249
5250 template <class _Tp>
5251 struct _LIBCPP_VISIBLE hash<shared_ptr<_Tp> >
5252 {
5253     typedef shared_ptr<_Tp>      argument_type;
5254     typedef size_t               result_type;
5255     _LIBCPP_INLINE_VISIBILITY
5256     result_type operator()(const argument_type& __ptr) const _NOEXCEPT
5257     {
5258         return hash<_Tp*>()(__ptr.get());
5259     }
5260 };
5261
5262 template<class _CharT, class _Traits, class _Yp>
5263 inline _LIBCPP_INLINE_VISIBILITY
5264 basic_ostream<_CharT, _Traits>&
5265 operator<<(basic_ostream<_CharT, _Traits>& __os, shared_ptr<_Yp> const& __p);
5266
5267 #if __has_feature(cxx_atomic)
5268
5269 class __sp_mut
5270 {
5271     void* _;
5272 public:
5273     void lock() _NOEXCEPT;
5274     void unlock() _NOEXCEPT;
5275
5276 private:
5277     _LIBCPP_CONSTEXPR __sp_mut(void*) _NOEXCEPT;
5278     __sp_mut(const __sp_mut&);
5279     __sp_mut& operator=(const __sp_mut&);
5280
5281     friend _LIBCPP_VISIBLE __sp_mut& __get_sp_mut(const void*);
5282 };
5283
5284 _LIBCPP_VISIBLE __sp_mut& __get_sp_mut(const void*);
5285
5286 template <class _Tp>
5287 inline _LIBCPP_INLINE_VISIBILITY
5288 bool
5289 atomic_is_lock_free(const shared_ptr<_Tp>*)
5290 {
5291     return false;
5292 }
5293
5294 template <class _Tp>
5295 shared_ptr<_Tp>
5296 atomic_load(const shared_ptr<_Tp>* __p)
5297 {
5298     __sp_mut& __m = __get_sp_mut(__p);
5299     __m.lock();
5300     shared_ptr<_Tp> __q = *__p;
5301     __m.unlock();
5302     return __q;
5303 }
5304
5305 template <class _Tp>
5306 inline _LIBCPP_INLINE_VISIBILITY
5307 shared_ptr<_Tp>
5308 atomic_load_explicit(const shared_ptr<_Tp>* __p, memory_order)
5309 {
5310     return atomic_load(__p);
5311 }
5312
5313 template <class _Tp>
5314 void
5315 atomic_store(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r)
5316 {
5317     __sp_mut& __m = __get_sp_mut(__p);
5318     __m.lock();
5319     __p->swap(__r);
5320     __m.unlock();
5321 }
5322
5323 template <class _Tp>
5324 inline _LIBCPP_INLINE_VISIBILITY
5325 void
5326 atomic_store_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r, memory_order)
5327 {
5328     atomic_store(__p, __r);
5329 }
5330
5331 template <class _Tp>
5332 shared_ptr<_Tp>
5333 atomic_exchange(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r)
5334 {
5335     __sp_mut& __m = __get_sp_mut(__p);
5336     __m.lock();
5337     __p->swap(__r);
5338     __m.unlock();
5339     return __r;
5340 }
5341
5342 template <class _Tp>
5343 inline _LIBCPP_INLINE_VISIBILITY
5344 shared_ptr<_Tp>
5345 atomic_exchange_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp> __r, memory_order)
5346 {
5347     return atomic_exchange(__p, __r);
5348 }
5349
5350 template <class _Tp>
5351 bool
5352 atomic_compare_exchange_strong(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v, shared_ptr<_Tp> __w)
5353 {
5354     __sp_mut& __m = __get_sp_mut(__p);
5355     __m.lock();
5356     if (__p->__owner_equivalent(*__v))
5357     {
5358         *__p = __w;
5359         __m.unlock();
5360         return true;
5361     }
5362     *__v = *__p;
5363     __m.unlock();
5364     return false;
5365 }
5366
5367 template <class _Tp>
5368 inline _LIBCPP_INLINE_VISIBILITY
5369 bool
5370 atomic_compare_exchange_weak(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v, shared_ptr<_Tp> __w)
5371 {
5372     return atomic_compare_exchange_strong(__p, __v, __w);
5373 }
5374
5375 template <class _Tp>
5376 inline _LIBCPP_INLINE_VISIBILITY
5377 bool
5378 atomic_compare_exchange_strong_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v,
5379                                         shared_ptr<_Tp> __w, memory_order, memory_order)
5380 {
5381     return atomic_compare_exchange_strong(__p, __v, __w);
5382 }
5383
5384 template <class _Tp>
5385 inline _LIBCPP_INLINE_VISIBILITY
5386 bool
5387 atomic_compare_exchange_weak_explicit(shared_ptr<_Tp>* __p, shared_ptr<_Tp>* __v,
5388                                       shared_ptr<_Tp> __w, memory_order, memory_order)
5389 {
5390     return atomic_compare_exchange_weak(__p, __v, __w);
5391 }
5392
5393 #endif  // __has_feature(cxx_atomic)
5394
5395 //enum class
5396 struct _LIBCPP_VISIBLE pointer_safety
5397 {
5398     enum _
5399     {
5400         relaxed,
5401         preferred,
5402         strict
5403     };
5404
5405     _ __v_;
5406
5407     _LIBCPP_INLINE_VISIBILITY
5408     pointer_safety(_ __v) : __v_(__v) {}
5409     _LIBCPP_INLINE_VISIBILITY
5410     operator int() const {return __v_;}
5411 };
5412
5413 void declare_reachable(void* __p);
5414 void declare_no_pointers(char* __p, size_t __n);
5415 void undeclare_no_pointers(char* __p, size_t __n);
5416 pointer_safety get_pointer_safety() _NOEXCEPT;
5417 void* __undeclare_reachable(void* __p);
5418
5419 template <class _Tp>
5420 inline _LIBCPP_INLINE_VISIBILITY
5421 _Tp*
5422 undeclare_reachable(_Tp* __p)
5423 {
5424     return static_cast<_Tp*>(__undeclare_reachable(__p));
5425 }
5426
5427 void* align(size_t __align, size_t __sz, void*& __ptr, size_t& __space);
5428
5429 _LIBCPP_END_NAMESPACE_STD
5430
5431 #endif  // _LIBCPP_MEMORY