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 #if defined(_LIBCPP_NO_EXCEPTIONS)
 600     #include <cassert>
 601 #endif
 602
 603 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 604 #pragma GCC system_header
 605 #endif
 606
 607 _LIBCPP_BEGIN_NAMESPACE_STD
 608
 609 // allocator_arg_t
 610
 611 struct _LIBCPP_VISIBLE allocator_arg_t { };
 612
 613 extern const allocator_arg_t allocator_arg;
 614
 615 // addressof
 616
 617 template <class _Tp>
 618 inline _LIBCPP_INLINE_VISIBILITY
 619 _Tp*
 620 addressof(_Tp& __x) _NOEXCEPT
 621 {
 622     return (_Tp*)&(char&)__x;
 623 }
 624
 625 #if defined(_LIBCPP_HAS_OBJC_ARC) && !defined(_LIBCPP_PREDEFINED_OBJC_ARC_ADDRESSOF)
 626 // Objective-C++ Automatic Reference Counting uses qualified pointers
 627 // that require special addressof() signatures. When
 628 // _LIBCPP_PREDEFINED_OBJC_ARC_ADDRESSOF is defined, the compiler
 629 // itself is providing these definitions. Otherwise, we provide them.
 630 template <class _Tp>
 631 inline _LIBCPP_INLINE_VISIBILITY
 632 __strong _Tp*
 633 addressof(__strong _Tp& __x) _NOEXCEPT
 634 {
 635   return &__x;
 636 }
 637
 638 #ifdef _LIBCPP_HAS_OBJC_ARC_WEAK
 639 template <class _Tp>
 640 inline _LIBCPP_INLINE_VISIBILITY
 641 __weak _Tp*
 642 addressof(__weak _Tp& __x) _NOEXCEPT
 643 {
 644   return &__x;
 645 }
 646 #endif
 647
 648 template <class _Tp>
 649 inline _LIBCPP_INLINE_VISIBILITY
 650 __autoreleasing _Tp*
 651 addressof(__autoreleasing _Tp& __x) _NOEXCEPT
 652 {
 653   return &__x;
 654 }
 655
 656 template <class _Tp>
 657 inline _LIBCPP_INLINE_VISIBILITY
 658 __unsafe_unretained _Tp*
 659 addressof(__unsafe_unretained _Tp& __x) _NOEXCEPT
 660 {
 661   return &__x;
 662 }
 663 #endif
 664
 665 template <class _Tp> class allocator;
 666
 667 template <>
 668 class _LIBCPP_VISIBLE allocator<void>
 669 {
 670 public:
 671     typedef void*             pointer;
 672     typedef const void*       const_pointer;
 673     typedef void              value_type;
 674
 675     template <class _Up> struct rebind {typedef allocator<_Up> other;};
 676 };
 677
 678 // pointer_traits
 679
 680 template <class _Tp>
 681 struct __has_element_type
 682 {
 683 private:
 684     struct __two {char _; char __;};
 685     template <class _Up> static __two __test(...);
 686     template <class _Up> static char __test(typename _Up::element_type* = 0);
 687 public:
 688     static const bool value = sizeof(__test<_Tp>(0)) == 1;
 689 };
 690
 691 template <class _Ptr, bool = __has_element_type<_Ptr>::value>
 692 struct __pointer_traits_element_type;
 693
 694 template <class _Ptr>
 695 struct __pointer_traits_element_type<_Ptr, true>
 696 {
 697     typedef typename _Ptr::element_type type;
 698 };
 699
 700 #ifndef _LIBCPP_HAS_NO_VARIADICS
 701
 702 template <template <class, class...> class _Sp, class _Tp, class ..._Args>
 703 struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, true>
 704 {
 705     typedef typename _Sp<_Tp, _Args...>::element_type type;
 706 };
 707
 708 template <template <class, class...> class _Sp, class _Tp, class ..._Args>
 709 struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, false>
 710 {
 711     typedef _Tp type;
 712 };
 713
 714 #else  // _LIBCPP_HAS_NO_VARIADICS
 715
 716 template <template <class> class _Sp, class _Tp>
 717 struct __pointer_traits_element_type<_Sp<_Tp>, true>
 718 {
 719     typedef typename _Sp<_Tp>::element_type type;
 720 };
 721
 722 template <template <class> class _Sp, class _Tp>
 723 struct __pointer_traits_element_type<_Sp<_Tp>, false>
 724 {
 725     typedef _Tp type;
 726 };
 727
 728 template <template <class, class> class _Sp, class _Tp, class _A0>
 729 struct __pointer_traits_element_type<_Sp<_Tp, _A0>, true>
 730 {
 731     typedef typename _Sp<_Tp, _A0>::element_type type;
 732 };
 733
 734 template <template <class, class> class _Sp, class _Tp, class _A0>
 735 struct __pointer_traits_element_type<_Sp<_Tp, _A0>, false>
 736 {
 737     typedef _Tp type;
 738 };
 739
 740 template <template <class, class, class> class _Sp, class _Tp, class _A0, class _A1>
 741 struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1>, true>
 742 {
 743     typedef typename _Sp<_Tp, _A0, _A1>::element_type type;
 744 };
 745
 746 template <template <class, class, class> class _Sp, class _Tp, class _A0, class _A1>
 747 struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1>, false>
 748 {
 749     typedef _Tp type;
 750 };
 751
 752 template <template <class, class, class, class> class _Sp, class _Tp, class _A0,
 753                                                            class _A1, class _A2>
 754 struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1, _A2>, true>
 755 {
 756     typedef typename _Sp<_Tp, _A0, _A1, _A2>::element_type type;
 757 };
 758
 759 template <template <class, class, class, class> class _Sp, class _Tp, class _A0,
 760                                                            class _A1, class _A2>
 761 struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1, _A2>, false>
 762 {
 763     typedef _Tp type;
 764 };
 765
 766 #endif  // _LIBCPP_HAS_NO_VARIADICS
 767
 768 template <class _Tp>
 769 struct __has_difference_type
 770 {
 771 private:
 772     struct __two {char _; char __;};
 773     template <class _Up> static __two __test(...);
 774     template <class _Up> static char __test(typename _Up::difference_type* = 0);
 775 public:
 776     static const bool value = sizeof(__test<_Tp>(0)) == 1;
 777 };
 778
 779 template <class _Ptr, bool = __has_difference_type<_Ptr>::value>
 780 struct __pointer_traits_difference_type
 781 {
 782     typedef ptrdiff_t type;
 783 };
 784
 785 template <class _Ptr>
 786 struct __pointer_traits_difference_type<_Ptr, true>
 787 {
 788     typedef typename _Ptr::difference_type type;
 789 };
 790
 791 template <class _Tp, class _Up>
 792 struct __has_rebind
 793 {
 794 private:
 795     struct __two {char _; char __;};
 796     template <class _Xp> static __two __test(...);
 797     template <class _Xp> static char __test(typename _Xp::template rebind<_Up>* = 0);
 798 public:
 799     static const bool value = sizeof(__test<_Tp>(0)) == 1;
 800 };
 801
 802 template <class _Tp, class _Up, bool = __has_rebind<_Tp, _Up>::value>
 803 struct __pointer_traits_rebind
 804 {
 805 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 806     typedef typename _Tp::template rebind<_Up> type;
 807 #else
 808     typedef typename _Tp::template rebind<_Up>::other type;
 809 #endif
 810 };
 811
 812 #ifndef _LIBCPP_HAS_NO_VARIADICS
 813
 814 template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>
 815 struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, true>
 816 {
 817 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 818     typedef typename _Sp<_Tp, _Args...>::template rebind<_Up> type;
 819 #else
 820     typedef typename _Sp<_Tp, _Args...>::template rebind<_Up>::other type;
 821 #endif
 822 };
 823
 824 template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>
 825 struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, false>
 826 {
 827     typedef _Sp<_Up, _Args...> type;
 828 };
 829
 830 #else  // _LIBCPP_HAS_NO_VARIADICS
 831
 832 template <template <class> class _Sp, class _Tp, class _Up>
 833 struct __pointer_traits_rebind<_Sp<_Tp>, _Up, true>
 834 {
 835 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 836     typedef typename _Sp<_Tp>::template rebind<_Up> type;
 837 #else
 838     typedef typename _Sp<_Tp>::template rebind<_Up>::other type;
 839 #endif
 840 };
 841
 842 template <template <class> class _Sp, class _Tp, class _Up>
 843 struct __pointer_traits_rebind<_Sp<_Tp>, _Up, false>
 844 {
 845     typedef _Sp<_Up> type;
 846 };
 847
 848 template <template <class, class> class _Sp, class _Tp, class _A0, class _Up>
 849 struct __pointer_traits_rebind<_Sp<_Tp, _A0>, _Up, true>
 850 {
 851 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 852     typedef typename _Sp<_Tp, _A0>::template rebind<_Up> type;
 853 #else
 854     typedef typename _Sp<_Tp, _A0>::template rebind<_Up>::other type;
 855 #endif
 856 };
 857
 858 template <template <class, class> class _Sp, class _Tp, class _A0, class _Up>
 859 struct __pointer_traits_rebind<_Sp<_Tp, _A0>, _Up, false>
 860 {
 861     typedef _Sp<_Up, _A0> type;
 862 };
 863
 864 template <template <class, class, class> class _Sp, class _Tp, class _A0,
 865                                          class _A1, class _Up>
 866 struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1>, _Up, true>
 867 {
 868 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 869     typedef typename _Sp<_Tp, _A0, _A1>::template rebind<_Up> type;
 870 #else
 871     typedef typename _Sp<_Tp, _A0, _A1>::template rebind<_Up>::other type;
 872 #endif
 873 };
 874
 875 template <template <class, class, class> class _Sp, class _Tp, class _A0,
 876                                          class _A1, class _Up>
 877 struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1>, _Up, false>
 878 {
 879     typedef _Sp<_Up, _A0, _A1> type;
 880 };
 881
 882 template <template <class, class, class, class> class _Sp, class _Tp, class _A0,
 883                                                 class _A1, class _A2, class _Up>
 884 struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1, _A2>, _Up, true>
 885 {
 886 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 887     typedef typename _Sp<_Tp, _A0, _A1, _A2>::template rebind<_Up> type;
 888 #else
 889     typedef typename _Sp<_Tp, _A0, _A1, _A2>::template rebind<_Up>::other type;
 890 #endif
 891 };
 892
 893 template <template <class, class, class, class> class _Sp, class _Tp, class _A0,
 894                                                 class _A1, class _A2, class _Up>
 895 struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1, _A2>, _Up, false>
 896 {
 897     typedef _Sp<_Up, _A0, _A1, _A2> type;
 898 };
 899
 900 #endif  // _LIBCPP_HAS_NO_VARIADICS
 901
 902 template <class _Ptr>
 903 struct _LIBCPP_VISIBLE pointer_traits
 904 {
 905     typedef _Ptr                                                     pointer;
 906     typedef typename __pointer_traits_element_type<pointer>::type    element_type;
 907     typedef typename __pointer_traits_difference_type<pointer>::type difference_type;
 908
 909 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 910     template <class _Up> using rebind = typename __pointer_traits_rebind<pointer, _Up>::type;
 911 #else
 912     template <class _Up> struct rebind
 913         {typedef typename __pointer_traits_rebind<pointer, _Up>::type other;};
 914 #endif  // _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 915
 916 private:
 917     struct __nat {};
 918 public:
 919     _LIBCPP_INLINE_VISIBILITY
 920     static pointer pointer_to(typename conditional<is_void<element_type>::value,
 921                                            __nat, element_type>::type& __r)
 922         {return pointer::pointer_to(__r);}
 923 };
 924
 925 template <class _Tp>
 926 struct _LIBCPP_VISIBLE pointer_traits<_Tp*>
 927 {
 928     typedef _Tp*      pointer;
 929     typedef _Tp       element_type;
 930     typedef ptrdiff_t difference_type;
 931
 932 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 933     template <class _Up> using rebind = _Up*;
 934 #else
 935     template <class _Up> struct rebind {typedef _Up* other;};
 936 #endif
 937
 938 private:
 939     struct __nat {};
 940 public:
 941     _LIBCPP_INLINE_VISIBILITY
 942     static pointer pointer_to(typename conditional<is_void<element_type>::value,
 943                                       __nat, element_type>::type& __r) _NOEXCEPT
 944         {return _VSTD::addressof(__r);}
 945 };
 946
 947 // allocator_traits
 948
 949 namespace __has_pointer_type_imp
 950 {
 951     template <class _Up> static __two test(...);
 952     template <class _Up> static char test(typename _Up::pointer* = 0);
 953 }
 954
 955 template <class _Tp>
 956 struct __has_pointer_type
 957     : public integral_constant<bool, sizeof(__has_pointer_type_imp::test<_Tp>(0)) == 1>
 958 {
 959 };
 960
 961 namespace __pointer_type_imp
 962 {
 963
 964 template <class _Tp, class _Dp, bool = __has_pointer_type<_Dp>::value>
 965 struct __pointer_type
 966 {
 967     typedef typename _Dp::pointer type;
 968 };
 969
 970 template <class _Tp, class _Dp>
 971 struct __pointer_type<_Tp, _Dp, false>
 972 {
 973     typedef _Tp* type;
 974 };
 975
 976 }  // __pointer_type_imp
 977
 978 template <class _Tp, class _Dp>
 979 struct __pointer_type
 980 {
 981     typedef typename __pointer_type_imp::__pointer_type<_Tp, typename remove_reference<_Dp>::type>::type type;
 982 };
 983
 984 template <class _Tp>
 985 struct __has_const_pointer
 986 {
 987 private:
 988     struct __two {char _; char __;};
 989     template <class _Up> static __two __test(...);
 990     template <class _Up> static char __test(typename _Up::const_pointer* = 0);
 991 public:
 992     static const bool value = sizeof(__test<_Tp>(0)) == 1;
 993 };
 994
 995 template <class _Tp, class _Ptr, class _Alloc, bool = __has_const_pointer<_Alloc>::value>
 996 struct __const_pointer
 997 {
 998     typedef typename _Alloc::const_pointer type;
 999 };
1000
1001 template <class _Tp, class _Ptr, class _Alloc>
1002 struct __const_pointer<_Tp, _Ptr, _Alloc, false>
1003 {
1004 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1005     typedef typename pointer_traits<_Ptr>::template rebind<const _Tp> type;
1006 #else
1007     typedef typename pointer_traits<_Ptr>::template rebind<const _Tp>::other type;
1008 #endif
1009 };
1010
1011 template <class _Tp>
1012 struct __has_void_pointer
1013 {
1014 private:
1015     struct __two {char _; char __;};
1016     template <class _Up> static __two __test(...);
1017     template <class _Up> static char __test(typename _Up::void_pointer* = 0);
1018 public:
1019     static const bool value = sizeof(__test<_Tp>(0)) == 1;
1020 };
1021
1022 template <class _Ptr, class _Alloc, bool = __has_void_pointer<_Alloc>::value>
1023 struct __void_pointer
1024 {
1025     typedef typename _Alloc::void_pointer type;
1026 };
1027
1028 template <class _Ptr, class _Alloc>
1029 struct __void_pointer<_Ptr, _Alloc, false>
1030 {
1031 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1032     typedef typename pointer_traits<_Ptr>::template rebind<void> type;
1033 #else
1034     typedef typename pointer_traits<_Ptr>::template rebind<void>::other type;
1035 #endif
1036 };
1037
1038 template <class _Tp>
1039 struct __has_const_void_pointer
1040 {
1041 private:
1042     struct __two {char _; char __;};
1043     template <class _Up> static __two __test(...);
1044     template <class _Up> static char __test(typename _Up::const_void_pointer* = 0);
1045 public:
1046     static const bool value = sizeof(__test<_Tp>(0)) == 1;
1047 };
1048
1049 template <class _Ptr, class _Alloc, bool = __has_const_void_pointer<_Alloc>::value>
1050 struct __const_void_pointer
1051 {
1052     typedef typename _Alloc::const_void_pointer type;
1053 };
1054
1055 template <class _Ptr, class _Alloc>
1056 struct __const_void_pointer<_Ptr, _Alloc, false>
1057 {
1058 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1059     typedef typename pointer_traits<_Ptr>::template rebind<const void> type;
1060 #else
1061     typedef typename pointer_traits<_Ptr>::template rebind<const void>::other type;
1062 #endif
1063 };
1064
1065 template <class _T>
1066 inline _LIBCPP_INLINE_VISIBILITY
1067 _T*
1068 __to_raw_pointer(_T* __p) _NOEXCEPT
1069 {
1070     return __p;
1071 }
1072
1073 template <class _Pointer>
1074 inline _LIBCPP_INLINE_VISIBILITY
1075 typename pointer_traits<_Pointer>::element_type*
1076 __to_raw_pointer(_Pointer __p) _NOEXCEPT
1077 {
1078     return _VSTD::__to_raw_pointer(__p.operator->());
1079 }
1080
1081 template <class _Tp>
1082 struct __has_size_type
1083 {
1084 private:
1085     struct __two {char _; char __;};
1086     template <class _Up> static __two __test(...);
1087     template <class _Up> static char __test(typename _Up::size_type* = 0);
1088 public:
1089     static const bool value = sizeof(__test<_Tp>(0)) == 1;
1090 };
1091
1092 template <class _Alloc, class _DiffType, bool = __has_size_type<_Alloc>::value>
1093 struct __size_type
1094 {
1095     typedef typename make_unsigned<_DiffType>::type type;
1096 };
1097
1098 template <class _Alloc, class _DiffType>
1099 struct __size_type<_Alloc, _DiffType, true>
1100 {
1101     typedef typename _Alloc::size_type type;
1102 };
1103
1104 template <class _Tp>
1105 struct __has_propagate_on_container_copy_assignment
1106 {
1107 private:
1108     struct __two {char _; char __;};
1109     template <class _Up> static __two __test(...);
1110     template <class _Up> static char __test(typename _Up::propagate_on_container_copy_assignment* = 0);
1111 public:
1112     static const bool value = sizeof(__test<_Tp>(0)) == 1;
1113 };
1114
1115 template <class _Alloc, bool = __has_propagate_on_container_copy_assignment<_Alloc>::value>
1116 struct __propagate_on_container_copy_assignment
1117 {
1118     typedef false_type type;
1119 };
1120
1121 template <class _Alloc>
1122 struct __propagate_on_container_copy_assignment<_Alloc, true>
1123 {
1124     typedef typename _Alloc::propagate_on_container_copy_assignment type;
1125 };
1126
1127 template <class _Tp>
1128 struct __has_propagate_on_container_move_assignment
1129 {
1130 private:
1131     struct __two {char _; char __;};
1132     template <class _Up> static __two __test(...);
1133     template <class _Up> static char __test(typename _Up::propagate_on_container_move_assignment* = 0);
1134 public:
1135     static const bool value = sizeof(__test<_Tp>(0)) == 1;
1136 };
1137
1138 template <class _Alloc, bool = __has_propagate_on_container_move_assignment<_Alloc>::value>
1139 struct __propagate_on_container_move_assignment
1140 {
1141     typedef false_type type;
1142 };
1143
1144 template <class _Alloc>
1145 struct __propagate_on_container_move_assignment<_Alloc, true>
1146 {
1147     typedef typename _Alloc::propagate_on_container_move_assignment type;
1148 };
1149
1150 template <class _Tp>
1151 struct __has_propagate_on_container_swap
1152 {
1153 private:
1154     struct __two {char _; char __;};
1155     template <class _Up> static __two __test(...);
1156     template <class _Up> static char __test(typename _Up::propagate_on_container_swap* = 0);
1157 public:
1158     static const bool value = sizeof(__test<_Tp>(0)) == 1;
1159 };
1160
1161 template <class _Alloc, bool = __has_propagate_on_container_swap<_Alloc>::value>
1162 struct __propagate_on_container_swap
1163 {
1164     typedef false_type type;
1165 };
1166
1167 template <class _Alloc>
1168 struct __propagate_on_container_swap<_Alloc, true>
1169 {
1170     typedef typename _Alloc::propagate_on_container_swap type;
1171 };
1172
1173 template <class _Tp, class _Up, bool = __has_rebind<_Tp, _Up>::value>
1174 struct __has_rebind_other
1175 {
1176 private:
1177     struct __two {char _; char __;};
1178     template <class _Xp> static __two __test(...);
1179     template <class _Xp> static char __test(typename _Xp::template rebind<_Up>::other* = 0);
1180 public:
1181     static const bool value = sizeof(__test<_Tp>(0)) == 1;
1182 };
1183
1184 template <class _Tp, class _Up>
1185 struct __has_rebind_other<_Tp, _Up, false>
1186 {
1187     static const bool value = false;
1188 };
1189
1190 template <class _Tp, class _Up, bool = __has_rebind_other<_Tp, _Up>::value>
1191 struct __allocator_traits_rebind
1192 {
1193     typedef typename _Tp::template rebind<_Up>::other type;
1194 };
1195
1196 #ifndef _LIBCPP_HAS_NO_VARIADICS
1197
1198 template <template <class, class...> class _Alloc, class _Tp, class ..._Args, class _Up>
1199 struct __allocator_traits_rebind<_Alloc<_Tp, _Args...>, _Up, true>
1200 {
1201     typedef typename _Alloc<_Tp, _Args...>::template rebind<_Up>::other type;
1202 };
1203
1204 template <template <class, class...> class _Alloc, class _Tp, class ..._Args, class _Up>
1205 struct __allocator_traits_rebind<_Alloc<_Tp, _Args...>, _Up, false>
1206 {
1207     typedef _Alloc<_Up, _Args...> type;
1208 };
1209
1210 #else  // _LIBCPP_HAS_NO_VARIADICS
1211
1212 template <template <class> class _Alloc, class _Tp, class _Up>
1213 struct __allocator_traits_rebind<_Alloc<_Tp>, _Up, true>
1214 {
1215     typedef typename _Alloc<_Tp>::template rebind<_Up>::other type;
1216 };
1217
1218 template <template <class> class _Alloc, class _Tp, class _Up>
1219 struct __allocator_traits_rebind<_Alloc<_Tp>, _Up, false>
1220 {
1221     typedef _Alloc<_Up> type;
1222 };
1223
1224 template <template <class, class> class _Alloc, class _Tp, class _A0, class _Up>
1225 struct __allocator_traits_rebind<_Alloc<_Tp, _A0>, _Up, true>
1226 {
1227     typedef typename _Alloc<_Tp, _A0>::template rebind<_Up>::other type;
1228 };
1229
1230 template <template <class, class> class _Alloc, class _Tp, class _A0, class _Up>
1231 struct __allocator_traits_rebind<_Alloc<_Tp, _A0>, _Up, false>
1232 {
1233     typedef _Alloc<_Up, _A0> type;
1234 };
1235
1236 template <template <class, class, class> class _Alloc, class _Tp, class _A0,
1237                                          class _A1, class _Up>
1238 struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1>, _Up, true>
1239 {
1240     typedef typename _Alloc<_Tp, _A0, _A1>::template rebind<_Up>::other type;
1241 };
1242
1243 template <template <class, class, class> class _Alloc, class _Tp, class _A0,
1244                                          class _A1, class _Up>
1245 struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1>, _Up, false>
1246 {
1247     typedef _Alloc<_Up, _A0, _A1> type;
1248 };
1249
1250 template <template <class, class, class, class> class _Alloc, class _Tp, class _A0,
1251                                                 class _A1, class _A2, class _Up>
1252 struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1, _A2>, _Up, true>
1253 {
1254     typedef typename _Alloc<_Tp, _A0, _A1, _A2>::template rebind<_Up>::other type;
1255 };
1256
1257 template <template <class, class, class, class> class _Alloc, class _Tp, class _A0,
1258                                                 class _A1, class _A2, class _Up>
1259 struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1, _A2>, _Up, false>
1260 {
1261     typedef _Alloc<_Up, _A0, _A1, _A2> type;
1262 };
1263
1264 #endif  // _LIBCPP_HAS_NO_VARIADICS
1265
1266 #ifndef _LIBCPP_HAS_NO_ADVANCED_SFINAE
1267
1268 template <class _Alloc, class _SizeType, class _ConstVoidPtr>
1269 auto
1270 __has_allocate_hint_test(_Alloc&& __a, _SizeType&& __sz, _ConstVoidPtr&& __p)
1271     -> decltype(__a.allocate(__sz, __p), true_type());
1272
1273 template <class _Alloc, class _SizeType, class _ConstVoidPtr>
1274 auto
1275 __has_allocate_hint_test(const _Alloc& __a, _SizeType&& __sz, _ConstVoidPtr&& __p)
1276     -> false_type;
1277
1278 template <class _Alloc, class _SizeType, class _ConstVoidPtr>
1279 struct __has_allocate_hint
1280     : integral_constant<bool,
1281         is_same<
1282             decltype(__has_allocate_hint_test(declval<_Alloc>(),
1283                                           declval<_SizeType>(),
1284                                           declval<_ConstVoidPtr>())),
1285             true_type>::value>
1286 {
1287 };
1288
1289 #else  // _LIBCPP_HAS_NO_ADVANCED_SFINAE
1290
1291 template <class _Alloc, class _SizeType, class _ConstVoidPtr>
1292 struct __has_allocate_hint
1293     : true_type
1294 {
1295 };
1296
1297 #endif  // _LIBCPP_HAS_NO_ADVANCED_SFINAE
1298
1299 #if !defined(_LIBCPP_HAS_NO_ADVANCED_SFINAE) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1300
1301 template <class _Alloc, class _Tp, class ..._Args>
1302 decltype(_VSTD::declval<_Alloc>().construct(_VSTD::declval<_Tp*>(),
1303                                            _VSTD::declval<_Args>()...),
1304                                            true_type())
1305 __has_construct_test(_Alloc&& __a, _Tp* __p, _Args&& ...__args);
1306
1307 template <class _Alloc, class _Pointer, class ..._Args>
1308 false_type
1309 __has_construct_test(const _Alloc& __a, _Pointer&& __p, _Args&& ...__args);
1310
1311 template <class _Alloc, class _Pointer, class ..._Args>
1312 struct __has_construct
1313     : integral_constant<bool,
1314         is_same<
1315             decltype(__has_construct_test(declval<_Alloc>(),
1316                                           declval<_Pointer>(),
1317                                           declval<_Args>()...)),
1318             true_type>::value>
1319 {
1320 };
1321
1322 template <class _Alloc, class _Pointer>
1323 auto
1324 __has_destroy_test(_Alloc&& __a, _Pointer&& __p)
1325     -> decltype(__a.destroy(__p), true_type());
1326
1327 template <class _Alloc, class _Pointer>
1328 auto
1329 __has_destroy_test(const _Alloc& __a, _Pointer&& __p)
1330     -> false_type;
1331
1332 template <class _Alloc, class _Pointer>
1333 struct __has_destroy
1334     : integral_constant<bool,
1335         is_same<
1336             decltype(__has_destroy_test(declval<_Alloc>(),
1337                                         declval<_Pointer>())),
1338             true_type>::value>
1339 {
1340 };
1341
1342 template <class _Alloc>
1343 auto
1344 __has_max_size_test(_Alloc&& __a)
1345     -> decltype(__a.max_size(), true_type());
1346
1347 template <class _Alloc>
1348 auto
1349 __has_max_size_test(const volatile _Alloc& __a)
1350     -> false_type;
1351
1352 template <class _Alloc>
1353 struct __has_max_size
1354     : integral_constant<bool,
1355         is_same<
1356             decltype(__has_max_size_test(declval<_Alloc&>())),
1357             true_type>::value>
1358 {
1359 };
1360
1361 template <class _Alloc>
1362 auto
1363 __has_select_on_container_copy_construction_test(_Alloc&& __a)
1364     -> decltype(__a.select_on_container_copy_construction(), true_type());
1365
1366 template <class _Alloc>
1367 auto
1368 __has_select_on_container_copy_construction_test(const volatile _Alloc& __a)
1369     -> false_type;
1370
1371 template <class _Alloc>
1372 struct __has_select_on_container_copy_construction
1373     : integral_constant<bool,
1374         is_same<
1375             decltype(__has_select_on_container_copy_construction_test(declval<_Alloc&>())),
1376             true_type>::value>
1377 {
1378 };
1379
1380 #else  // _LIBCPP_HAS_NO_ADVANCED_SFINAE
1381
1382 #ifndef _LIBCPP_HAS_NO_VARIADICS
1383
1384 template <class _Alloc, class _Pointer, class ..._Args>
1385 struct __has_construct
1386     : false_type
1387 {
1388 };
1389
1390 #endif  // _LIBCPP_HAS_NO_VARIADICS
1391
1392 template <class _Alloc, class _Pointer>
1393 struct __has_destroy
1394     : false_type
1395 {
1396 };
1397
1398 template <class _Alloc>
1399 struct __has_max_size
1400     : true_type
1401 {
1402 };
1403
1404 template <class _Alloc>
1405 struct __has_select_on_container_copy_construction
1406     : false_type
1407 {
1408 };
1409
1410 #endif  // _LIBCPP_HAS_NO_ADVANCED_SFINAE
1411
1412 template <class _Alloc, class _Ptr, bool = __has_difference_type<_Alloc>::value>
1413 struct __alloc_traits_difference_type
1414 {
1415     typedef typename pointer_traits<_Ptr>::difference_type type;
1416 };
1417
1418 template <class _Alloc, class _Ptr>
1419 struct __alloc_traits_difference_type<_Alloc, _Ptr, true>
1420 {
1421     typedef typename _Alloc::difference_type type;
1422 };
1423
1424 template <class _Alloc>
1425 struct _LIBCPP_VISIBLE allocator_traits
1426 {
1427     typedef _Alloc                              allocator_type;
1428     typedef typename allocator_type::value_type value_type;
1429
1430     typedef typename __pointer_type<value_type, allocator_type>::type pointer;
1431     typedef typename __const_pointer<value_type, pointer, allocator_type>::type const_pointer;
1432     typedef typename __void_pointer<pointer, allocator_type>::type void_pointer;
1433     typedef typename __const_void_pointer<pointer, allocator_type>::type const_void_pointer;
1434
1435     typedef typename __alloc_traits_difference_type<allocator_type, pointer>::type difference_type;
1436     typedef typename __size_type<allocator_type, difference_type>::type size_type;
1437
1438     typedef typename __propagate_on_container_copy_assignment<allocator_type>::type
1439                      propagate_on_container_copy_assignment;
1440     typedef typename __propagate_on_container_move_assignment<allocator_type>::type
1441                      propagate_on_container_move_assignment;
1442     typedef typename __propagate_on_container_swap<allocator_type>::type
1443                      propagate_on_container_swap;
1444
1445 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1446     template <class _Tp> using rebind_alloc =
1447                   typename __allocator_traits_rebind<allocator_type, _Tp>::type;
1448     template <class _Tp> using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;
1449 #else  // _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1450     template <class _Tp> struct rebind_alloc
1451         {typedef typename __allocator_traits_rebind<allocator_type, _Tp>::type other;};
1452     template <class _Tp> struct rebind_traits
1453         {typedef allocator_traits<typename rebind_alloc<_Tp>::other> other;};
1454 #endif  // _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1455
1456     _LIBCPP_INLINE_VISIBILITY
1457     static pointer allocate(allocator_type& __a, size_type __n)
1458         {return __a.allocate(__n);}
1459     _LIBCPP_INLINE_VISIBILITY
1460     static pointer allocate(allocator_type& __a, size_type __n, const_void_pointer __hint)
1461         {return allocate(__a, __n, __hint,
1462             __has_allocate_hint<allocator_type, size_type, const_void_pointer>());}
1463
1464     _LIBCPP_INLINE_VISIBILITY
1465     static void deallocate(allocator_type& __a, pointer __p, size_type __n) _NOEXCEPT
1466         {__a.deallocate(__p, __n);}
1467
1468 #ifndef _LIBCPP_HAS_NO_VARIADICS
1469     template <class _Tp, class... _Args>
1470         _LIBCPP_INLINE_VISIBILITY
1471         static void construct(allocator_type& __a, _Tp* __p, _Args&&... __args)
1472             {__construct(__has_construct<allocator_type, pointer, _Args...>(),
1473                          __a, __p, _VSTD::forward<_Args>(__args)...);}
1474 #else  // _LIBCPP_HAS_NO_VARIADICS
1475     template <class _Tp>
1476         _LIBCPP_INLINE_VISIBILITY
1477         static void construct(allocator_type& __a, _Tp* __p)
1478             {
1479                 ::new ((void*)__p) _Tp();
1480             }
1481     template <class _Tp, class _A0>
1482         _LIBCPP_INLINE_VISIBILITY
1483         static void construct(allocator_type& __a, _Tp* __p, const _A0& __a0)
1484             {
1485                 ::new ((void*)__p) _Tp(__a0);
1486             }
1487     template <class _Tp, class _A0, class _A1>
1488         _LIBCPP_INLINE_VISIBILITY
1489         static void construct(allocator_type& __a, _Tp* __p, const _A0& __a0,
1490                               const _A1& __a1)
1491             {
1492                 ::new ((void*)__p) _Tp(__a0, __a1);
1493             }
1494     template <class _Tp, class _A0, class _A1, class _A2>
1495         _LIBCPP_INLINE_VISIBILITY
1496         static void construct(allocator_type& __a, _Tp* __p, const _A0& __a0,
1497                               const _A1& __a1, const _A2& __a2)
1498             {
1499                 ::new ((void*)__p) _Tp(__a0, __a1, __a2);
1500             }
1501 #endif  // _LIBCPP_HAS_NO_VARIADICS
1502
1503     template <class _Tp>
1504         _LIBCPP_INLINE_VISIBILITY
1505         static void destroy(allocator_type& __a, _Tp* __p)
1506             {__destroy(__has_destroy<allocator_type, _Tp*>(), __a, __p);}
1507
1508     _LIBCPP_INLINE_VISIBILITY
1509     static size_type max_size(const allocator_type& __a)
1510         {return __max_size(__has_max_size<const allocator_type>(), __a);}
1511
1512     _LIBCPP_INLINE_VISIBILITY
1513     static allocator_type
1514         select_on_container_copy_construction(const allocator_type& __a)
1515             {return select_on_container_copy_construction(
1516                 __has_select_on_container_copy_construction<const allocator_type>(),
1517                 __a);}
1518
1519 private:
1520
1521     _LIBCPP_INLINE_VISIBILITY
1522     static pointer allocate(allocator_type& __a, size_type __n,
1523         const_void_pointer __hint, true_type)
1524         {return __a.allocate(__n, __hint);}
1525     _LIBCPP_INLINE_VISIBILITY
1526     static pointer allocate(allocator_type& __a, size_type __n,
1527         const_void_pointer __hint, false_type)
1528         {return __a.allocate(__n);}
1529
1530 #ifndef _LIBCPP_HAS_NO_VARIADICS
1531     template <class _Tp, class... _Args>
1532         _LIBCPP_INLINE_VISIBILITY
1533         static void __construct(true_type, allocator_type& __a, _Tp* __p, _Args&&... __args)
1534             {__a.construct(__p, _VSTD::forward<_Args>(__args)...);}
1535     template <class _Tp, class... _Args>
1536         _LIBCPP_INLINE_VISIBILITY
1537         static void __construct(false_type, allocator_type&, _Tp* __p, _Args&&... __args)
1538             {
1539                 ::new ((void*)__p) _Tp(_VSTD::forward<_Args>(__args)...);
1540             }
1541 #endif  // _LIBCPP_HAS_NO_VARIADICS
1542
1543     template <class _Tp>
1544         _LIBCPP_INLINE_VISIBILITY
1545         static void __destroy(true_type, allocator_type& __a, _Tp* __p)
1546             {__a.destroy(__p);}
1547     template <class _Tp>
1548         _LIBCPP_INLINE_VISIBILITY
1549         static void __destroy(false_type, allocator_type&, _Tp* __p)
1550             {
1551                 __p->~_Tp();
1552             }
1553
1554     _LIBCPP_INLINE_VISIBILITY
1555     static size_type __max_size(true_type, const allocator_type& __a)
1556             {return __a.max_size();}
1557     _LIBCPP_INLINE_VISIBILITY
1558     static size_type __max_size(false_type, const allocator_type&)
1559             {return numeric_limits<size_type>::max();}
1560
1561     _LIBCPP_INLINE_VISIBILITY
1562     static allocator_type
1563         select_on_container_copy_construction(true_type, const allocator_type& __a)
1564             {return __a.select_on_container_copy_construction();}
1565     _LIBCPP_INLINE_VISIBILITY
1566     static allocator_type
1567         select_on_container_copy_construction(false_type, const allocator_type& __a)
1568             {return __a;}
1569 };
1570
1571 // uses_allocator
1572
1573 template <class _Tp>
1574 struct __has_allocator_type
1575 {
1576 private:
1577     struct __two {char _; char __;};
1578     template <class _Up> static __two __test(...);
1579     template <class _Up> static char __test(typename _Up::allocator_type* = 0);
1580 public:
1581     static const bool value = sizeof(__test<_Tp>(0)) == 1;
1582 };
1583
1584 template <class _Tp, class _Alloc, bool = __has_allocator_type<_Tp>::value>
1585 struct __uses_allocator
1586     : public integral_constant<bool,
1587         is_convertible<_Alloc, typename _Tp::allocator_type>::value>
1588 {
1589 };
1590
1591 template <class _Tp, class _Alloc>
1592 struct __uses_allocator<_Tp, _Alloc, false>
1593     : public false_type
1594 {
1595 };
1596
1597 template <class _Tp, class _Alloc>
1598 struct _LIBCPP_VISIBLE uses_allocator
1599     : public __uses_allocator<_Tp, _Alloc>
1600 {
1601 };
1602
1603 #ifndef _LIBCPP_HAS_NO_VARIADICS
1604
1605 // uses-allocator construction
1606
1607 template <class _Tp, class _Alloc, class ..._Args>
1608 struct __uses_alloc_ctor_imp
1609 {
1610     static const bool __ua = uses_allocator<_Tp, _Alloc>::value;
1611     static const bool __ic =
1612         is_constructible<_Tp, allocator_arg_t, _Alloc, _Args...>::value;
1613     static const int value = __ua ? 2 - __ic : 0;
1614 };
1615
1616 template <class _Tp, class _Alloc, class ..._Args>
1617 struct __uses_alloc_ctor
1618     : integral_constant<int, __uses_alloc_ctor_imp<_Tp, _Alloc, _Args...>::value>
1619     {};
1620
1621 #endif  // _LIBCPP_HAS_NO_VARIADICS
1622
1623 // allocator
1624
1625 template <class _Tp>
1626 class _LIBCPP_VISIBLE allocator
1627 {
1628 public:
1629     typedef size_t            size_type;
1630     typedef ptrdiff_t         difference_type;
1631     typedef _Tp*              pointer;
1632     typedef const _Tp*        const_pointer;
1633     typedef _Tp&              reference;
1634     typedef const _Tp&        const_reference;
1635     typedef _Tp               value_type;
1636
1637     typedef true_type propagate_on_container_move_assignment;
1638
1639     template <class _Up> struct rebind {typedef allocator<_Up> other;};
1640
1641     _LIBCPP_INLINE_VISIBILITY allocator() _NOEXCEPT {}
1642     template <class _Up> _LIBCPP_INLINE_VISIBILITY allocator(const allocator<_Up>&) _NOEXCEPT {}
1643     _LIBCPP_INLINE_VISIBILITY pointer address(reference __x) const _NOEXCEPT
1644         {return _VSTD::addressof(__x);}
1645     _LIBCPP_INLINE_VISIBILITY const_pointer address(const_reference __x) const _NOEXCEPT
1646         {return _VSTD::addressof(__x);}
1647     _LIBCPP_INLINE_VISIBILITY pointer allocate(size_type __n, allocator<void>::const_pointer = 0)
1648         {return static_cast<pointer>(::operator new(__n * sizeof(_Tp)));}
1649     _LIBCPP_INLINE_VISIBILITY void deallocate(pointer __p, size_type) _NOEXCEPT
1650         {::operator delete((void*)__p);}
1651     _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT
1652         {return size_type(~0) / sizeof(_Tp);}
1653 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1654     template <class _Up, class... _Args>
1655         _LIBCPP_INLINE_VISIBILITY
1656         void
1657         construct(_Up* __p, _Args&&... __args)
1658         {
1659             ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
1660         }
1661 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1662         _LIBCPP_INLINE_VISIBILITY
1663         void
1664         construct(pointer __p)
1665         {
1666             ::new((void*)__p) _Tp();
1667         }
1668 # if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1669     template <class _A0>
1670         _LIBCPP_INLINE_VISIBILITY
1671         typename enable_if
1672         <
1673             !is_convertible<_A0, __rv<_A0> >::value,
1674             void
1675         >::type
1676         construct(pointer __p, _A0& __a0)
1677         {
1678             ::new((void*)__p) _Tp(__a0);
1679         }
1680     template <class _A0>
1681         _LIBCPP_INLINE_VISIBILITY
1682         typename enable_if
1683         <
1684             !is_convertible<_A0, __rv<_A0> >::value,
1685             void
1686         >::type
1687         construct(pointer __p, const _A0& __a0)
1688         {
1689             ::new((void*)__p) _Tp(__a0);
1690         }
1691     template <class _A0>
1692         _LIBCPP_INLINE_VISIBILITY
1693         typename enable_if
1694         <
1695             is_convertible<_A0, __rv<_A0> >::value,
1696             void
1697         >::type
1698         construct(pointer __p, _A0 __a0)
1699         {
1700             ::new((void*)__p) _Tp(_VSTD::move(__a0));
1701         }
1702 # endif  // defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1703     template <class _A0, class _A1>
1704         _LIBCPP_INLINE_VISIBILITY
1705         void
1706         construct(pointer __p, _A0& __a0, _A1& __a1)
1707         {
1708             ::new((void*)__p) _Tp(__a0, __a1);
1709         }
1710     template <class _A0, class _A1>
1711         _LIBCPP_INLINE_VISIBILITY
1712         void
1713         construct(pointer __p, const _A0& __a0, _A1& __a1)
1714         {
1715             ::new((void*)__p) _Tp(__a0, __a1);
1716         }
1717     template <class _A0, class _A1>
1718         _LIBCPP_INLINE_VISIBILITY
1719         void
1720         construct(pointer __p, _A0& __a0, const _A1& __a1)
1721         {
1722             ::new((void*)__p) _Tp(__a0, __a1);
1723         }
1724     template <class _A0, class _A1>
1725         _LIBCPP_INLINE_VISIBILITY
1726         void
1727         construct(pointer __p, const _A0& __a0, const _A1& __a1)
1728         {
1729             ::new((void*)__p) _Tp(__a0, __a1);
1730         }
1731 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1732     _LIBCPP_INLINE_VISIBILITY void destroy(pointer __p) {__p->~_Tp();}
1733 };
1734
1735 template <class _Tp, class _Up>
1736 inline _LIBCPP_INLINE_VISIBILITY
1737 bool operator==(const allocator<_Tp>&, const allocator<_Up>&) _NOEXCEPT {return true;}
1738
1739 template <class _Tp, class _Up>
1740 inline _LIBCPP_INLINE_VISIBILITY
1741 bool operator!=(const allocator<_Tp>&, const allocator<_Up>&) _NOEXCEPT {return false;}
1742
1743 template <class _OutputIterator, class _Tp>
1744 class _LIBCPP_VISIBLE raw_storage_iterator
1745     : public iterator<output_iterator_tag,
1746                       _Tp,                                         // purposefully not C++03
1747                       ptrdiff_t,                                   // purposefully not C++03
1748                       _Tp*,                                        // purposefully not C++03
1749                       raw_storage_iterator<_OutputIterator, _Tp>&> // purposefully not C++03
1750 {
1751 private:
1752     _OutputIterator __x_;
1753 public:
1754     _LIBCPP_INLINE_VISIBILITY explicit raw_storage_iterator(_OutputIterator __x) : __x_(__x) {}
1755     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator*() {return *this;}
1756     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator=(const _Tp& __element)
1757         {::new(&*__x_) _Tp(__element); return *this;}
1758     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator++() {++__x_; return *this;}
1759     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator  operator++(int)
1760         {raw_storage_iterator __t(*this); ++__x_; return __t;}
1761 };
1762
1763 template <class _Tp>
1764 pair<_Tp*, ptrdiff_t>
1765 get_temporary_buffer(ptrdiff_t __n) _NOEXCEPT
1766 {
1767     pair<_Tp*, ptrdiff_t> __r(0, 0);
1768     const ptrdiff_t __m = (~ptrdiff_t(0) ^
1769                            ptrdiff_t(ptrdiff_t(1) << (sizeof(ptrdiff_t) * __CHAR_BIT__ - 1)))
1770                            / sizeof(_Tp);
1771     if (__n > __m)
1772         __n = __m;
1773     while (__n > 0)
1774     {
1775         __r.first = static_cast<_Tp*>(::operator new(__n * sizeof(_Tp), nothrow));
1776         if (__r.first)
1777         {
1778             __r.second = __n;
1779             break;
1780         }
1781         __n /= 2;
1782     }
1783     return __r;
1784 }
1785
1786 template <class _Tp>
1787 inline _LIBCPP_INLINE_VISIBILITY
1788 void return_temporary_buffer(_Tp* __p) _NOEXCEPT {::operator delete(__p);}
1789
1790 template <class _Tp>
1791 struct auto_ptr_ref
1792 {
1793     _Tp* __ptr_;
1794 };
1795
1796 template<class _Tp>
1797 class _LIBCPP_VISIBLE auto_ptr
1798 {
1799 private:
1800     _Tp* __ptr_;
1801 public:
1802     typedef _Tp element_type;
1803
1804     _LIBCPP_INLINE_VISIBILITY explicit auto_ptr(_Tp* __p = 0) throw() : __ptr_(__p) {}
1805     _LIBCPP_INLINE_VISIBILITY auto_ptr(auto_ptr& __p) throw() : __ptr_(__p.release()) {}
1806     template<class _Up> _LIBCPP_INLINE_VISIBILITY auto_ptr(auto_ptr<_Up>& __p) throw()
1807         : __ptr_(__p.release()) {}
1808     _LIBCPP_INLINE_VISIBILITY auto_ptr& operator=(auto_ptr& __p) throw()
1809         {reset(__p.release()); return *this;}
1810     template<class _Up> _LIBCPP_INLINE_VISIBILITY auto_ptr& operator=(auto_ptr<_Up>& __p) throw()
1811         {reset(__p.release()); return *this;}
1812     _LIBCPP_INLINE_VISIBILITY auto_ptr& operator=(auto_ptr_ref<_Tp> __p) throw()
1813         {reset(__p.__ptr_); return *this;}
1814     _LIBCPP_INLINE_VISIBILITY ~auto_ptr() throw() {delete __ptr_;}
1815
1816     _LIBCPP_INLINE_VISIBILITY _Tp& operator*() const throw()
1817         {return *__ptr_;}
1818     _LIBCPP_INLINE_VISIBILITY _Tp* operator->() const throw() {return __ptr_;}
1819     _LIBCPP_INLINE_VISIBILITY _Tp* get() const throw() {return __ptr_;}
1820     _LIBCPP_INLINE_VISIBILITY _Tp* release() throw()
1821     {
1822         _Tp* __t = __ptr_;
1823         __ptr_ = 0;
1824         return __t;
1825     }
1826     _LIBCPP_INLINE_VISIBILITY void reset(_Tp* __p = 0) throw()
1827     {
1828         if (__ptr_ != __p)
1829             delete __ptr_;
1830         __ptr_ = __p;
1831     }
1832
1833     _LIBCPP_INLINE_VISIBILITY auto_ptr(auto_ptr_ref<_Tp> __p) throw() : __ptr_(__p.__ptr_) {}
1834     template<class _Up> _LIBCPP_INLINE_VISIBILITY operator auto_ptr_ref<_Up>() throw()
1835         {auto_ptr_ref<_Up> __t; __t.__ptr_ = release(); return __t;}
1836     template<class _Up> _LIBCPP_INLINE_VISIBILITY operator auto_ptr<_Up>() throw()
1837         {return auto_ptr<_Up>(release());}
1838 };
1839
1840 template <>
1841 class _LIBCPP_VISIBLE auto_ptr<void>
1842 {
1843 public:
1844     typedef void element_type;
1845 };
1846
1847 template <class _T1, class _T2, bool = is_same<typename remove_cv<_T1>::type,
1848                                                      typename remove_cv<_T2>::type>::value,
1849                                 bool = is_empty<_T1>::value,
1850                                 bool = is_empty<_T2>::value>
1851 struct __libcpp_compressed_pair_switch;
1852
1853 template <class _T1, class _T2, bool IsSame>
1854 struct __libcpp_compressed_pair_switch<_T1, _T2, IsSame, false, false> {enum {value = 0};};
1855
1856 template <class _T1, class _T2, bool IsSame>
1857 struct __libcpp_compressed_pair_switch<_T1, _T2, IsSame, true, false>  {enum {value = 1};};
1858
1859 template <class _T1, class _T2, bool IsSame>
1860 struct __libcpp_compressed_pair_switch<_T1, _T2, IsSame, false, true>  {enum {value = 2};};
1861
1862 template <class _T1, class _T2>
1863 struct __libcpp_compressed_pair_switch<_T1, _T2, false, true, true>    {enum {value = 3};};
1864
1865 template <class _T1, class _T2>
1866 struct __libcpp_compressed_pair_switch<_T1, _T2, true, true, true>     {enum {value = 1};};
1867
1868 template <class _T1, class _T2, unsigned = __libcpp_compressed_pair_switch<_T1, _T2>::value>
1869 class __libcpp_compressed_pair_imp;
1870
1871 template <class _T1, class _T2>
1872 class __libcpp_compressed_pair_imp<_T1, _T2, 0>
1873 {
1874 private:
1875     _T1 __first_;
1876     _T2 __second_;
1877 public:
1878     typedef _T1 _T1_param;
1879     typedef _T2 _T2_param;
1880
1881     typedef typename remove_reference<_T1>::type& _T1_reference;
1882     typedef typename remove_reference<_T2>::type& _T2_reference;
1883
1884     typedef const typename remove_reference<_T1>::type& _T1_const_reference;
1885     typedef const typename remove_reference<_T2>::type& _T2_const_reference;
1886
1887     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp() {}
1888     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T1_param __t1, int = 0)
1889         : __first_(_VSTD::forward<_T1_param>(__t1)) {}
1890     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T2_param __t2, int* = 0)
1891         : __second_(_VSTD::forward<_T2_param>(__t2)) {}
1892     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp(_T1_param __t1, _T2_param __t2)
1893         : __first_(_VSTD::forward<_T1_param>(__t1)), __second_(_VSTD::forward<_T2_param>(__t2)) {}
1894
1895 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
1896
1897     _LIBCPP_INLINE_VISIBILITY
1898     __libcpp_compressed_pair_imp(const __libcpp_compressed_pair_imp& __p)
1899         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
1900                    is_nothrow_copy_constructible<_T2>::value)
1901         : __first_(__p.first()),
1902           __second_(__p.second()) {}
1903
1904     _LIBCPP_INLINE_VISIBILITY
1905     __libcpp_compressed_pair_imp& operator=(const __libcpp_compressed_pair_imp& __p)
1906         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
1907                    is_nothrow_copy_assignable<_T2>::value)
1908         {
1909             __first_ = __p.first();
1910             __second_ = __p.second();
1911             return *this;
1912         }
1913
1914 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1915
1916     _LIBCPP_INLINE_VISIBILITY
1917     __libcpp_compressed_pair_imp(__libcpp_compressed_pair_imp&& __p)
1918         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
1919                    is_nothrow_move_constructible<_T2>::value)
1920         : __first_(_VSTD::forward<_T1>(__p.first())),
1921           __second_(_VSTD::forward<_T2>(__p.second())) {}
1922
1923     _LIBCPP_INLINE_VISIBILITY
1924     __libcpp_compressed_pair_imp& operator=(__libcpp_compressed_pair_imp&& __p)
1925         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
1926                    is_nothrow_move_assignable<_T2>::value)
1927         {
1928             __first_ = _VSTD::forward<_T1>(__p.first());
1929             __second_ = _VSTD::forward<_T2>(__p.second());
1930             return *this;
1931         }
1932
1933 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1934
1935 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
1936
1937     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return __first_;}
1938     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return __first_;}
1939
1940     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return __second_;}
1941     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return __second_;}
1942
1943     _LIBCPP_INLINE_VISIBILITY void swap(__libcpp_compressed_pair_imp& __x)
1944         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
1945                    __is_nothrow_swappable<_T1>::value)
1946     {
1947         using _VSTD::swap;
1948         swap(__first_, __x.__first_);
1949         swap(__second_, __x.__second_);
1950     }
1951 };
1952
1953 template <class _T1, class _T2>
1954 class __libcpp_compressed_pair_imp<_T1, _T2, 1>
1955     : private _T1
1956 {
1957 private:
1958     _T2 __second_;
1959 public:
1960     typedef _T1 _T1_param;
1961     typedef _T2 _T2_param;
1962
1963     typedef _T1&                                        _T1_reference;
1964     typedef typename remove_reference<_T2>::type& _T2_reference;
1965
1966     typedef const _T1&                                        _T1_const_reference;
1967     typedef const typename remove_reference<_T2>::type& _T2_const_reference;
1968
1969     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp() {}
1970     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T1_param __t1, int = 0)
1971         : _T1(_VSTD::forward<_T1_param>(__t1)) {}
1972     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T2_param __t2, int* = 0)
1973         : __second_(_VSTD::forward<_T2_param>(__t2)) {}
1974     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp(_T1_param __t1, _T2_param __t2)
1975         : _T1(_VSTD::forward<_T1_param>(__t1)), __second_(_VSTD::forward<_T2_param>(__t2)) {}
1976
1977 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
1978
1979     _LIBCPP_INLINE_VISIBILITY
1980     __libcpp_compressed_pair_imp(const __libcpp_compressed_pair_imp& __p)
1981         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
1982                    is_nothrow_copy_constructible<_T2>::value)
1983         : _T1(__p.first()), __second_(__p.second()) {}
1984
1985     _LIBCPP_INLINE_VISIBILITY
1986     __libcpp_compressed_pair_imp& operator=(const __libcpp_compressed_pair_imp& __p)
1987         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
1988                    is_nothrow_copy_assignable<_T2>::value)
1989         {
1990             _T1::operator=(__p.first());
1991             __second_ = __p.second();
1992             return *this;
1993         }
1994
1995 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1996
1997     _LIBCPP_INLINE_VISIBILITY
1998     __libcpp_compressed_pair_imp(__libcpp_compressed_pair_imp&& __p)
1999         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2000                    is_nothrow_move_constructible<_T2>::value)
2001         : _T1(_VSTD::move(__p.first())), __second_(_VSTD::forward<_T2>(__p.second())) {}
2002
2003     _LIBCPP_INLINE_VISIBILITY
2004     __libcpp_compressed_pair_imp& operator=(__libcpp_compressed_pair_imp&& __p)
2005         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
2006                    is_nothrow_move_assignable<_T2>::value)
2007         {
2008             _T1::operator=(_VSTD::move(__p.first()));
2009             __second_ = _VSTD::forward<_T2>(__p.second());
2010             return *this;
2011         }
2012
2013 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2014
2015 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2016
2017     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return *this;}
2018     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return *this;}
2019
2020     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return __second_;}
2021     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return __second_;}
2022
2023     _LIBCPP_INLINE_VISIBILITY void swap(__libcpp_compressed_pair_imp& __x)
2024         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2025                    __is_nothrow_swappable<_T1>::value)
2026     {
2027         using _VSTD::swap;
2028         swap(__second_, __x.__second_);
2029     }
2030 };
2031
2032 template <class _T1, class _T2>
2033 class __libcpp_compressed_pair_imp<_T1, _T2, 2>
2034     : private _T2
2035 {
2036 private:
2037     _T1 __first_;
2038 public:
2039     typedef _T1 _T1_param;
2040     typedef _T2 _T2_param;
2041
2042     typedef typename remove_reference<_T1>::type& _T1_reference;
2043     typedef _T2&                                        _T2_reference;
2044
2045     typedef const typename remove_reference<_T1>::type& _T1_const_reference;
2046     typedef const _T2&                                        _T2_const_reference;
2047
2048     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp() {}
2049     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T1_param __t1)
2050         : __first_(_VSTD::forward<_T1_param>(__t1)) {}
2051     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T2_param __t2)
2052         : _T2(_VSTD::forward<_T2_param>(__t2)) {}
2053     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp(_T1_param __t1, _T2_param __t2)
2054         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2055                    is_nothrow_move_constructible<_T2>::value)
2056         : _T2(_VSTD::forward<_T2_param>(__t2)), __first_(_VSTD::forward<_T1_param>(__t1)) {}
2057
2058 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2059
2060     _LIBCPP_INLINE_VISIBILITY
2061     __libcpp_compressed_pair_imp(const __libcpp_compressed_pair_imp& __p)
2062         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
2063                    is_nothrow_copy_constructible<_T2>::value)
2064         : _T2(__p.second()), __first_(__p.first()) {}
2065
2066     _LIBCPP_INLINE_VISIBILITY
2067     __libcpp_compressed_pair_imp& operator=(const __libcpp_compressed_pair_imp& __p)
2068         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
2069                    is_nothrow_copy_assignable<_T2>::value)
2070         {
2071             _T2::operator=(__p.second());
2072             __first_ = __p.first();
2073             return *this;
2074         }
2075
2076 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2077
2078     _LIBCPP_INLINE_VISIBILITY
2079     __libcpp_compressed_pair_imp(__libcpp_compressed_pair_imp&& __p)
2080         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2081                    is_nothrow_move_constructible<_T2>::value)
2082         : _T2(_VSTD::forward<_T2>(__p.second())), __first_(_VSTD::move(__p.first())) {}
2083
2084     _LIBCPP_INLINE_VISIBILITY
2085     __libcpp_compressed_pair_imp& operator=(__libcpp_compressed_pair_imp&& __p)
2086         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
2087                    is_nothrow_move_assignable<_T2>::value)
2088         {
2089             _T2::operator=(_VSTD::forward<_T2>(__p.second()));
2090             __first_ = _VSTD::move(__p.first());
2091             return *this;
2092         }
2093
2094 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2095
2096 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2097
2098     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return __first_;}
2099     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return __first_;}
2100
2101     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return *this;}
2102     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return *this;}
2103
2104     _LIBCPP_INLINE_VISIBILITY void swap(__libcpp_compressed_pair_imp& __x)
2105         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2106                    __is_nothrow_swappable<_T1>::value)
2107     {
2108         using _VSTD::swap;
2109         swap(__first_, __x.__first_);
2110     }
2111 };
2112
2113 template <class _T1, class _T2>
2114 class __libcpp_compressed_pair_imp<_T1, _T2, 3>
2115     : private _T1,
2116       private _T2
2117 {
2118 public:
2119     typedef _T1 _T1_param;
2120     typedef _T2 _T2_param;
2121
2122     typedef _T1& _T1_reference;
2123     typedef _T2& _T2_reference;
2124
2125     typedef const _T1& _T1_const_reference;
2126     typedef const _T2& _T2_const_reference;
2127
2128     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp() {}
2129     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T1_param __t1)
2130         : _T1(_VSTD::forward<_T1_param>(__t1)) {}
2131     _LIBCPP_INLINE_VISIBILITY explicit __libcpp_compressed_pair_imp(_T2_param __t2)
2132         : _T2(_VSTD::forward<_T2_param>(__t2)) {}
2133     _LIBCPP_INLINE_VISIBILITY __libcpp_compressed_pair_imp(_T1_param __t1, _T2_param __t2)
2134         : _T1(_VSTD::forward<_T1_param>(__t1)), _T2(_VSTD::forward<_T2_param>(__t2)) {}
2135
2136 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2137
2138     _LIBCPP_INLINE_VISIBILITY
2139     __libcpp_compressed_pair_imp(const __libcpp_compressed_pair_imp& __p)
2140         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
2141                    is_nothrow_copy_constructible<_T2>::value)
2142         : _T1(__p.first()), _T2(__p.second()) {}
2143
2144     _LIBCPP_INLINE_VISIBILITY
2145     __libcpp_compressed_pair_imp& operator=(const __libcpp_compressed_pair_imp& __p)
2146         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
2147                    is_nothrow_copy_assignable<_T2>::value)
2148         {
2149             _T1::operator=(__p.first());
2150             _T2::operator=(__p.second());
2151             return *this;
2152         }
2153
2154 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2155
2156     _LIBCPP_INLINE_VISIBILITY
2157     __libcpp_compressed_pair_imp(__libcpp_compressed_pair_imp&& __p)
2158         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2159                    is_nothrow_move_constructible<_T2>::value)
2160         : _T1(_VSTD::move(__p.first())), _T2(_VSTD::move(__p.second())) {}
2161
2162     _LIBCPP_INLINE_VISIBILITY
2163     __libcpp_compressed_pair_imp& operator=(__libcpp_compressed_pair_imp&& __p)
2164         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
2165                    is_nothrow_move_assignable<_T2>::value)
2166         {
2167             _T1::operator=(_VSTD::move(__p.first()));
2168             _T2::operator=(_VSTD::move(__p.second()));
2169             return *this;
2170         }
2171
2172 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2173
2174 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2175
2176     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return *this;}
2177     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return *this;}
2178
2179     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return *this;}
2180     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return *this;}
2181
2182     _LIBCPP_INLINE_VISIBILITY void swap(__libcpp_compressed_pair_imp& __x)
2183         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2184                    __is_nothrow_swappable<_T1>::value)
2185     {
2186     }
2187 };
2188
2189 template <class _T1, class _T2>
2190 class __compressed_pair
2191     : private __libcpp_compressed_pair_imp<_T1, _T2>
2192 {
2193     typedef __libcpp_compressed_pair_imp<_T1, _T2> base;
2194 public:
2195     typedef typename base::_T1_param _T1_param;
2196     typedef typename base::_T2_param _T2_param;
2197
2198     typedef typename base::_T1_reference _T1_reference;
2199     typedef typename base::_T2_reference _T2_reference;
2200
2201     typedef typename base::_T1_const_reference _T1_const_reference;
2202     typedef typename base::_T2_const_reference _T2_const_reference;
2203
2204     _LIBCPP_INLINE_VISIBILITY __compressed_pair() {}
2205     _LIBCPP_INLINE_VISIBILITY explicit __compressed_pair(_T1_param __t1, int = 0)
2206         : base(_VSTD::forward<_T1_param>(__t1)) {}
2207     _LIBCPP_INLINE_VISIBILITY explicit __compressed_pair(_T2_param __t2, int* = 0)
2208         : base(_VSTD::forward<_T2_param>(__t2)) {}
2209     _LIBCPP_INLINE_VISIBILITY __compressed_pair(_T1_param __t1, _T2_param __t2)
2210         : base(_VSTD::forward<_T1_param>(__t1), _VSTD::forward<_T2_param>(__t2)) {}
2211
2212 #ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2213
2214     _LIBCPP_INLINE_VISIBILITY
2215     __compressed_pair(const __compressed_pair& __p)
2216         _NOEXCEPT_(is_nothrow_copy_constructible<_T1>::value &&
2217                    is_nothrow_copy_constructible<_T2>::value)
2218         : base(__p) {}
2219
2220     _LIBCPP_INLINE_VISIBILITY
2221     __compressed_pair& operator=(const __compressed_pair& __p)
2222         _NOEXCEPT_(is_nothrow_copy_assignable<_T1>::value &&
2223                    is_nothrow_copy_assignable<_T2>::value)
2224         {
2225             base::operator=(__p);
2226             return *this;
2227         }
2228
2229 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2230     _LIBCPP_INLINE_VISIBILITY
2231     __compressed_pair(__compressed_pair&& __p)
2232         _NOEXCEPT_(is_nothrow_move_constructible<_T1>::value &&
2233                    is_nothrow_move_constructible<_T2>::value)
2234         : base(_VSTD::move(__p)) {}
2235
2236     _LIBCPP_INLINE_VISIBILITY
2237     __compressed_pair& operator=(__compressed_pair&& __p)
2238         _NOEXCEPT_(is_nothrow_move_assignable<_T1>::value &&
2239                    is_nothrow_move_assignable<_T2>::value)
2240         {
2241             base::operator=(_VSTD::move(__p));
2242             return *this;
2243         }
2244 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2245
2246 #endif  // _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
2247
2248     _LIBCPP_INLINE_VISIBILITY _T1_reference       first() _NOEXCEPT       {return base::first();}
2249     _LIBCPP_INLINE_VISIBILITY _T1_const_reference first() const _NOEXCEPT {return base::first();}
2250
2251     _LIBCPP_INLINE_VISIBILITY _T2_reference       second() _NOEXCEPT       {return base::second();}
2252     _LIBCPP_INLINE_VISIBILITY _T2_const_reference second() const _NOEXCEPT {return base::second();}
2253
2254     _LIBCPP_INLINE_VISIBILITY void swap(__compressed_pair& __x)
2255         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2256                    __is_nothrow_swappable<_T1>::value)
2257         {base::swap(__x);}
2258 };
2259
2260 template <class _T1, class _T2>
2261 inline _LIBCPP_INLINE_VISIBILITY
2262 void
2263 swap(__compressed_pair<_T1, _T2>& __x, __compressed_pair<_T1, _T2>& __y)
2264         _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
2265                    __is_nothrow_swappable<_T1>::value)
2266     {__x.swap(__y);}
2267
2268 template <class _Tp>
2269 struct _LIBCPP_VISIBLE default_delete
2270 {
2271     _LIBCPP_INLINE_VISIBILITY default_delete() _NOEXCEPT {}
2272     template <class _Up>
2273         _LIBCPP_INLINE_VISIBILITY default_delete(const default_delete<_Up>&,
2274              typename enable_if<is_convertible<_Up*, _Tp*>::value>::type* = 0) _NOEXCEPT {}
2275     _LIBCPP_INLINE_VISIBILITY void operator() (_Tp* __ptr) const _NOEXCEPT
2276         {
2277             static_assert(sizeof(_Tp) > 0, "default_delete can not delete incomplete type");
2278             delete __ptr;
2279         }
2280 };
2281
2282 template <class _Tp>
2283 struct _LIBCPP_VISIBLE default_delete<_Tp[]>
2284 {
2285     _LIBCPP_INLINE_VISIBILITY void operator() (_Tp* __ptr) const _NOEXCEPT
2286         {
2287             static_assert(sizeof(_Tp) > 0, "default_delete can not delete incomplete type");
2288             delete [] __ptr;
2289         }
2290 private:
2291     template <class _Up> void operator() (_Up*) const;
2292 };
2293
2294 template <class _Tp, class _Dp = default_delete<_Tp> >
2295 class _LIBCPP_VISIBLE unique_ptr
2296 {
2297 public:
2298     typedef _Tp element_type;
2299     typedef _Dp deleter_type;
2300     typedef typename __pointer_type<_Tp, deleter_type>::type pointer;
2301 private:
2302     __compressed_pair<pointer, deleter_type> __ptr_;
2303
2304 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2305     unique_ptr(const unique_ptr&);
2306     unique_ptr& operator=(const unique_ptr&);
2307     template <class _Up, class _Ep>
2308         unique_ptr(const unique_ptr<_Up, _Ep>&);
2309     template <class _Up, class _Ep>
2310         unique_ptr& operator=(const unique_ptr<_Up, _Ep>&);
2311 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2312     unique_ptr(unique_ptr&);
2313     template <class _Up, class _Ep>
2314         unique_ptr(unique_ptr<_Up, _Ep>&);
2315     unique_ptr& operator=(unique_ptr&);
2316     template <class _Up, class _Ep>
2317         unique_ptr& operator=(unique_ptr<_Up, _Ep>&);
2318 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2319
2320     struct __nat {int __for_bool_;};
2321
2322     typedef       typename remove_reference<deleter_type>::type& _Dp_reference;
2323     typedef const typename remove_reference<deleter_type>::type& _Dp_const_reference;
2324 public:
2325     _LIBCPP_INLINE_VISIBILITY unique_ptr() _NOEXCEPT
2326         : __ptr_(pointer())
2327         {
2328             static_assert(!is_pointer<deleter_type>::value,
2329                 "unique_ptr constructed with null function pointer deleter");
2330         }
2331     _LIBCPP_INLINE_VISIBILITY unique_ptr(nullptr_t) _NOEXCEPT
2332         : __ptr_(pointer())
2333         {
2334             static_assert(!is_pointer<deleter_type>::value,
2335                 "unique_ptr constructed with null function pointer deleter");
2336         }
2337     _LIBCPP_INLINE_VISIBILITY explicit unique_ptr(pointer __p) _NOEXCEPT
2338         : __ptr_(_VSTD::move(__p))
2339         {
2340             static_assert(!is_pointer<deleter_type>::value,
2341                 "unique_ptr constructed with null function pointer deleter");
2342         }
2343
2344 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2345     _LIBCPP_INLINE_VISIBILITY unique_ptr(pointer __p, typename conditional<
2346                                         is_reference<deleter_type>::value,
2347                                         deleter_type,
2348                                         typename add_lvalue_reference<const deleter_type>::type>::type __d)
2349              _NOEXCEPT
2350         : __ptr_(__p, __d) {}
2351
2352     _LIBCPP_INLINE_VISIBILITY unique_ptr(pointer __p, typename remove_reference<deleter_type>::type&& __d)
2353              _NOEXCEPT
2354         : __ptr_(__p, _VSTD::move(__d))
2355         {
2356             static_assert(!is_reference<deleter_type>::value, "rvalue deleter bound to reference");
2357         }
2358     _LIBCPP_INLINE_VISIBILITY unique_ptr(unique_ptr&& __u) _NOEXCEPT
2359         : __ptr_(__u.release(), _VSTD::forward<deleter_type>(__u.get_deleter())) {}
2360     template <class _Up, class _Ep>
2361         _LIBCPP_INLINE_VISIBILITY
2362         unique_ptr(unique_ptr<_Up, _Ep>&& __u,
2363                    typename enable_if
2364                       <
2365                         !is_array<_Up>::value &&
2366                          is_convertible<typename unique_ptr<_Up, _Ep>::pointer, pointer>::value &&
2367                          is_convertible<_Ep, deleter_type>::value &&
2368                          (
2369                             !is_reference<deleter_type>::value ||
2370                             is_same<deleter_type, _Ep>::value
2371                          ),
2372                          __nat
2373                       >::type = __nat()) _NOEXCEPT
2374             : __ptr_(__u.release(), _VSTD::forward<_Ep>(__u.get_deleter())) {}
2375
2376     template <class _Up>
2377         _LIBCPP_INLINE_VISIBILITY unique_ptr(auto_ptr<_Up>&& __p,
2378                 typename enable_if<
2379                                       is_convertible<_Up*, _Tp*>::value &&
2380                                       is_same<_Dp, default_delete<_Tp> >::value,
2381                                       __nat
2382                                   >::type = __nat()) _NOEXCEPT
2383             : __ptr_(__p.release())
2384             {
2385             }
2386
2387         _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(unique_ptr&& __u) _NOEXCEPT
2388             {
2389                 reset(__u.release());
2390                 __ptr_.second() = _VSTD::forward<deleter_type>(__u.get_deleter());
2391                 return *this;
2392             }
2393
2394         template <class _Up, class _Ep>
2395             _LIBCPP_INLINE_VISIBILITY
2396             typename enable_if
2397             <
2398                 !is_array<_Up>::value,
2399                 unique_ptr&
2400             >::type
2401             operator=(unique_ptr<_Up, _Ep>&& __u) _NOEXCEPT
2402             {
2403                 reset(__u.release());
2404                 __ptr_.second() = _VSTD::forward<_Ep>(__u.get_deleter());
2405                 return *this;
2406             }
2407 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2408
2409     _LIBCPP_INLINE_VISIBILITY operator __rv<unique_ptr>()
2410     {
2411         return __rv<unique_ptr>(*this);
2412     }
2413
2414     _LIBCPP_INLINE_VISIBILITY unique_ptr(__rv<unique_ptr> __u)
2415         : __ptr_(__u->release(), _VSTD::forward<deleter_type>(__u->get_deleter())) {}
2416
2417     template <class _Up, class _Ep>
2418     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(unique_ptr<_Up, _Ep> __u)
2419     {
2420         reset(__u.release());
2421         __ptr_.second() = _VSTD::forward<deleter_type>(__u.get_deleter());
2422         return *this;
2423     }
2424
2425     _LIBCPP_INLINE_VISIBILITY unique_ptr(pointer __p, deleter_type __d)
2426         : __ptr_(_VSTD::move(__p), _VSTD::move(__d)) {}
2427
2428     template <class _Up>
2429         _LIBCPP_INLINE_VISIBILITY
2430                 typename enable_if<
2431                                       is_convertible<_Up*, _Tp*>::value &&
2432                                       is_same<_Dp, default_delete<_Tp> >::value,
2433                                       unique_ptr&
2434                                   >::type
2435         operator=(auto_ptr<_Up> __p)
2436             {reset(__p.release()); return *this;}
2437
2438 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2439     _LIBCPP_INLINE_VISIBILITY ~unique_ptr() {reset();}
2440
2441     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(nullptr_t) _NOEXCEPT
2442     {
2443         reset();
2444         return *this;
2445     }
2446
2447     _LIBCPP_INLINE_VISIBILITY typename add_lvalue_reference<_Tp>::type operator*() const
2448         {return *__ptr_.first();}
2449     _LIBCPP_INLINE_VISIBILITY pointer operator->() const _NOEXCEPT {return __ptr_.first();}
2450     _LIBCPP_INLINE_VISIBILITY pointer get() const _NOEXCEPT {return __ptr_.first();}
2451     _LIBCPP_INLINE_VISIBILITY       _Dp_reference get_deleter() _NOEXCEPT
2452         {return __ptr_.second();}
2453     _LIBCPP_INLINE_VISIBILITY _Dp_const_reference get_deleter() const _NOEXCEPT
2454         {return __ptr_.second();}
2455     _LIBCPP_INLINE_VISIBILITY operator int __nat::*() const
2456              _NOEXCEPT
2457         {return __ptr_.first() ? &__nat::__for_bool_ : 0;}
2458
2459     _LIBCPP_INLINE_VISIBILITY pointer release() _NOEXCEPT
2460     {
2461         pointer __t = __ptr_.first();
2462         __ptr_.first() = pointer();
2463         return __t;
2464     }
2465
2466     _LIBCPP_INLINE_VISIBILITY void reset(pointer __p = pointer()) _NOEXCEPT
2467     {
2468         pointer __tmp = __ptr_.first();
2469         __ptr_.first() = __p;
2470         if (__tmp)
2471             __ptr_.second()(__tmp);
2472     }
2473
2474     _LIBCPP_INLINE_VISIBILITY void swap(unique_ptr& __u) _NOEXCEPT
2475         {__ptr_.swap(__u.__ptr_);}
2476 };
2477
2478 template <class _Tp, class _Dp>
2479 class _LIBCPP_VISIBLE unique_ptr<_Tp[], _Dp>
2480 {
2481 public:
2482     typedef _Tp element_type;
2483     typedef _Dp deleter_type;
2484     typedef typename __pointer_type<_Tp, deleter_type>::type pointer;
2485 private:
2486     __compressed_pair<pointer, deleter_type> __ptr_;
2487
2488 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2489     unique_ptr(const unique_ptr&);
2490     unique_ptr& operator=(const unique_ptr&);
2491 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2492     unique_ptr(unique_ptr&);
2493     template <class _Up>
2494         unique_ptr(unique_ptr<_Up>&);
2495     unique_ptr& operator=(unique_ptr&);
2496     template <class _Up>
2497         unique_ptr& operator=(unique_ptr<_Up>&);
2498 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2499
2500     struct __nat {int __for_bool_;};
2501
2502     typedef       typename remove_reference<deleter_type>::type& _Dp_reference;
2503     typedef const typename remove_reference<deleter_type>::type& _Dp_const_reference;
2504 public:
2505     _LIBCPP_INLINE_VISIBILITY unique_ptr() _NOEXCEPT
2506         : __ptr_(pointer())
2507         {
2508             static_assert(!is_pointer<deleter_type>::value,
2509                 "unique_ptr constructed with null function pointer deleter");
2510         }
2511     _LIBCPP_INLINE_VISIBILITY unique_ptr(nullptr_t) _NOEXCEPT
2512         : __ptr_(pointer())
2513         {
2514             static_assert(!is_pointer<deleter_type>::value,
2515                 "unique_ptr constructed with null function pointer deleter");
2516         }
2517 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2518     template <class _P,
2519               class = typename enable_if<is_same<_P, pointer>::value>::type
2520              >
2521     _LIBCPP_INLINE_VISIBILITY explicit unique_ptr(_P __p) _NOEXCEPT
2522         : __ptr_(__p)
2523         {
2524             static_assert(!is_pointer<deleter_type>::value,
2525                 "unique_ptr constructed with null function pointer deleter");
2526         }
2527
2528     template <class _P,
2529               class = typename enable_if<is_same<_P, pointer>::value>::type
2530              >
2531     _LIBCPP_INLINE_VISIBILITY unique_ptr(_P __p, typename conditional<
2532                                        is_reference<deleter_type>::value,
2533                                        deleter_type,
2534                                        typename add_lvalue_reference<const deleter_type>::type>::type __d)
2535              _NOEXCEPT
2536         : __ptr_(__p, __d) {}
2537
2538     _LIBCPP_INLINE_VISIBILITY unique_ptr(nullptr_t, typename conditional<
2539                                        is_reference<deleter_type>::value,
2540                                        deleter_type,
2541                                        typename add_lvalue_reference<const deleter_type>::type>::type __d)
2542              _NOEXCEPT
2543         : __ptr_(pointer(), __d) {}
2544
2545     template <class _P,
2546               class = typename enable_if<is_same<_P, pointer>::value ||
2547                                          is_same<_P, nullptr_t>::value>::type
2548              >
2549     _LIBCPP_INLINE_VISIBILITY unique_ptr(_P __p, typename remove_reference<deleter_type>::type&& __d)
2550              _NOEXCEPT
2551         : __ptr_(__p, _VSTD::move(__d))
2552         {
2553             static_assert(!is_reference<deleter_type>::value, "rvalue deleter bound to reference");
2554         }
2555
2556     _LIBCPP_INLINE_VISIBILITY unique_ptr(nullptr_t, typename remove_reference<deleter_type>::type&& __d)
2557              _NOEXCEPT
2558         : __ptr_(pointer(), _VSTD::move(__d))
2559         {
2560             static_assert(!is_reference<deleter_type>::value, "rvalue deleter bound to reference");
2561         }
2562
2563     _LIBCPP_INLINE_VISIBILITY unique_ptr(unique_ptr&& __u) _NOEXCEPT
2564         : __ptr_(__u.release(), _VSTD::forward<deleter_type>(__u.get_deleter())) {}
2565
2566     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(unique_ptr&& __u) _NOEXCEPT
2567         {
2568             reset(__u.release());
2569             __ptr_.second() = _VSTD::forward<deleter_type>(__u.get_deleter());
2570             return *this;
2571         }
2572 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2573
2574     _LIBCPP_INLINE_VISIBILITY explicit unique_ptr(pointer __p)
2575         : __ptr_(__p)
2576         {
2577             static_assert(!is_pointer<deleter_type>::value,
2578                 "unique_ptr constructed with null function pointer deleter");
2579         }
2580
2581     _LIBCPP_INLINE_VISIBILITY unique_ptr(pointer __p, deleter_type __d)
2582         : __ptr_(__p, _VSTD::forward<deleter_type>(__d)) {}
2583
2584     _LIBCPP_INLINE_VISIBILITY unique_ptr(nullptr_t, deleter_type __d)
2585         : __ptr_(pointer(), _VSTD::forward<deleter_type>(__d)) {}
2586
2587     _LIBCPP_INLINE_VISIBILITY operator __rv<unique_ptr>()
2588     {
2589         return __rv<unique_ptr>(*this);
2590     }
2591
2592     _LIBCPP_INLINE_VISIBILITY unique_ptr(__rv<unique_ptr> __u)
2593         : __ptr_(__u->release(), _VSTD::forward<deleter_type>(__u->get_deleter())) {}
2594
2595     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(__rv<unique_ptr> __u)
2596     {
2597         reset(__u->release());
2598         __ptr_.second() = _VSTD::forward<deleter_type>(__u->get_deleter());
2599         return *this;
2600     }
2601
2602 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2603     _LIBCPP_INLINE_VISIBILITY ~unique_ptr() {reset();}
2604
2605     _LIBCPP_INLINE_VISIBILITY unique_ptr& operator=(nullptr_t) _NOEXCEPT
2606     {
2607         reset();
2608         return *this;
2609     }
2610
2611     _LIBCPP_INLINE_VISIBILITY typename add_lvalue_reference<_Tp>::type operator[](size_t __i) const
2612         {return __ptr_.first()[__i];}
2613     _LIBCPP_INLINE_VISIBILITY pointer get() const _NOEXCEPT {return __ptr_.first();}
2614     _LIBCPP_INLINE_VISIBILITY       _Dp_reference get_deleter() _NOEXCEPT
2615         {return __ptr_.second();}
2616     _LIBCPP_INLINE_VISIBILITY _Dp_const_reference get_deleter() const _NOEXCEPT
2617         {return __ptr_.second();}
2618     _LIBCPP_INLINE_VISIBILITY operator int __nat::*() const _NOEXCEPT
2619         {return __ptr_.first() ? &__nat::__for_bool_ : 0;}
2620
2621     _LIBCPP_INLINE_VISIBILITY pointer release() _NOEXCEPT
2622     {
2623         pointer __t = __ptr_.first();
2624         __ptr_.first() = pointer();
2625         return __t;
2626     }
2627
2628 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2629     template <class _P,
2630               class = typename enable_if<is_same<_P, pointer>::value>::type
2631              >
2632     _LIBCPP_INLINE_VISIBILITY void reset(_P __p) _NOEXCEPT
2633     {
2634         pointer __tmp = __ptr_.first();
2635         __ptr_.first() = __p;
2636         if (__tmp)
2637             __ptr_.second()(__tmp);
2638     }
2639     _LIBCPP_INLINE_VISIBILITY void reset(nullptr_t) _NOEXCEPT
2640     {
2641         pointer __tmp = __ptr_.first();
2642         __ptr_.first() = nullptr;
2643         if (__tmp)
2644             __ptr_.second()(__tmp);
2645     }
2646     _LIBCPP_INLINE_VISIBILITY void reset() _NOEXCEPT
2647     {
2648         pointer __tmp = __ptr_.first();
2649         __ptr_.first() = nullptr;
2650         if (__tmp)
2651             __ptr_.second()(__tmp);
2652     }
2653 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2654     _LIBCPP_INLINE_VISIBILITY void reset(pointer __p = pointer())
2655     {
2656         pointer __tmp = __ptr_.first();
2657         __ptr_.first() = __p;
2658         if (__tmp)
2659             __ptr_.second()(__tmp);
2660     }
2661 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2662
2663     _LIBCPP_INLINE_VISIBILITY void swap(unique_ptr& __u) {__ptr_.swap(__u.__ptr_);}
2664 private:
2665
2666 #ifdef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2667     template <class _Up>
2668         explicit unique_ptr(_Up);
2669     template <class _Up>
2670         unique_ptr(_Up __u,
2671                    typename conditional<
2672                                        is_reference<deleter_type>::value,
2673                                        deleter_type,
2674                                        typename add_lvalue_reference<const deleter_type>::type>::type,
2675                    typename enable_if
2676                       <
2677                          is_convertible<_Up, pointer>::value,
2678                          __nat
2679                       >::type = __nat());
2680 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2681 };
2682
2683 template <class _Tp, class _Dp>
2684 inline _LIBCPP_INLINE_VISIBILITY
2685 void
2686 swap(unique_ptr<_Tp, _Dp>& __x, unique_ptr<_Tp, _Dp>& __y) _NOEXCEPT {__x.swap(__y);}
2687
2688 template <class _T1, class _D1, class _T2, class _D2>
2689 inline _LIBCPP_INLINE_VISIBILITY
2690 bool
2691 operator==(const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return __x.get() == __y.get();}
2692
2693 template <class _T1, class _D1, class _T2, class _D2>
2694 inline _LIBCPP_INLINE_VISIBILITY
2695 bool
2696 operator!=(const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return !(__x == __y);}
2697
2698 template <class _T1, class _D1, class _T2, class _D2>
2699 inline _LIBCPP_INLINE_VISIBILITY
2700 bool
2701 operator< (const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return __x.get() < __y.get();}
2702
2703 template <class _T1, class _D1, class _T2, class _D2>
2704 inline _LIBCPP_INLINE_VISIBILITY
2705 bool
2706 operator> (const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return __y < __x;}
2707
2708 template <class _T1, class _D1, class _T2, class _D2>
2709 inline _LIBCPP_INLINE_VISIBILITY
2710 bool
2711 operator<=(const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return !(__y < __x);}
2712
2713 template <class _T1, class _D1, class _T2, class _D2>
2714 inline _LIBCPP_INLINE_VISIBILITY
2715 bool
2716 operator>=(const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y) {return !(__x < __y);}
2717
2718 template <class _Tp> struct hash;
2719
2720 template<class _Tp>
2721 struct _LIBCPP_VISIBLE hash<_Tp*>
2722     : public unary_function<_Tp*, size_t>
2723 {
2724     _LIBCPP_INLINE_VISIBILITY
2725     size_t operator()(_Tp* __v) const _NOEXCEPT
2726     {
2727         const size_t* const __p = reinterpret_cast<const size_t*>(&__v);
2728         return *__p;
2729     }
2730 };
2731
2732 template <class _Tp, class _Dp>
2733 struct _LIBCPP_VISIBLE hash<unique_ptr<_Tp, _Dp> >
2734 {
2735     typedef unique_ptr<_Tp, _Dp> argument_type;
2736     typedef size_t               result_type;
2737     _LIBCPP_INLINE_VISIBILITY
2738     result_type operator()(const argument_type& __ptr) const _NOEXCEPT
2739     {
2740         typedef typename argument_type::pointer pointer;
2741         return hash<pointer>()(__ptr.get());
2742     }
2743 };
2744
2745 struct __destruct_n
2746 {
2747 private:
2748     size_t size;
2749
2750     template <class _Tp>
2751     _LIBCPP_INLINE_VISIBILITY void __process(_Tp* __p, false_type) _NOEXCEPT
2752         {for (size_t __i = 0; __i < size; ++__i, ++__p) __p->~_Tp();}
2753
2754     template <class _Tp>
2755     _LIBCPP_INLINE_VISIBILITY void __process(_Tp*, true_type) _NOEXCEPT
2756         {}
2757
2758     _LIBCPP_INLINE_VISIBILITY void __incr(false_type) _NOEXCEPT
2759         {++size;}
2760     _LIBCPP_INLINE_VISIBILITY void __incr(true_type) _NOEXCEPT
2761         {}
2762
2763     _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, false_type) _NOEXCEPT
2764         {size = __s;}
2765     _LIBCPP_INLINE_VISIBILITY void __set(size_t, true_type) _NOEXCEPT
2766         {}
2767 public:
2768     _LIBCPP_INLINE_VISIBILITY explicit __destruct_n(size_t __s) _NOEXCEPT
2769         : size(__s) {}
2770
2771     template <class _Tp>
2772     _LIBCPP_INLINE_VISIBILITY void __incr(_Tp*) _NOEXCEPT
2773         {__incr(integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
2774
2775     template <class _Tp>
2776     _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, _Tp*) _NOEXCEPT
2777         {__set(__s, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
2778
2779     template <class _Tp>
2780     _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) _NOEXCEPT
2781         {__process(__p, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
2782 };
2783
2784 template <class _Alloc>
2785 class __allocator_destructor
2786 {
2787     typedef allocator_traits<_Alloc> __alloc_traits;
2788 public:
2789     typedef typename __alloc_traits::pointer pointer;
2790     typedef typename __alloc_traits::size_type size_type;
2791 private:
2792     _Alloc& __alloc_;
2793     size_type __s_;
2794 public:
2795     _LIBCPP_INLINE_VISIBILITY __allocator_destructor(_Alloc& __a, size_type __s)
2796              _NOEXCEPT
2797         : __alloc_(__a), __s_(__s) {}
2798     _LIBCPP_INLINE_VISIBILITY
2799     void operator()(pointer __p) _NOEXCEPT
2800         {__alloc_traits::deallocate(__alloc_, __p, __s_);}
2801 };
2802
2803 template <class _InputIterator, class _ForwardIterator>
2804 _ForwardIterator
2805 uninitialized_copy(_InputIterator __f, _InputIterator __l, _ForwardIterator __r)
2806 {
2807     __destruct_n __d(0);
2808     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2809     unique_ptr<value_type, __destruct_n&> __h(&*__r, __d);
2810     for (; __f != __l; ++__f, ++__r, __d.__incr((value_type*)0))
2811         ::new(&*__r) value_type(*__f);
2812     __h.release();
2813     return __r;
2814 }
2815
2816 template <class _InputIterator, class _Size, class _ForwardIterator>
2817 _ForwardIterator
2818 uninitialized_copy_n(_InputIterator __f, _Size __n, _ForwardIterator __r)
2819 {
2820     __destruct_n __d(0);
2821     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2822     unique_ptr<value_type, __destruct_n&> __h(&*__r, __d);
2823     for (; __n > 0; ++__f, ++__r, __d.__incr((value_type*)0), --__n)
2824         ::new(&*__r) value_type(*__f);
2825     __h.release();
2826     return __r;
2827 }
2828
2829 template <class _ForwardIterator, class _Tp>
2830 void
2831 uninitialized_fill(_ForwardIterator __f, _ForwardIterator __l, const _Tp& __x)
2832 {
2833     __destruct_n __d(0);
2834     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2835     unique_ptr<value_type, __destruct_n&> __h(&*__f, __d);
2836     for (; __f != __l; ++__f, __d.__incr((value_type*)0))
2837         ::new(&*__f) value_type(__x);
2838     __h.release();
2839 }
2840
2841 template <class _ForwardIterator, class _Size, class _Tp>
2842 _ForwardIterator
2843 uninitialized_fill_n(_ForwardIterator __f, _Size __n, const _Tp& __x)
2844 {
2845     __destruct_n __d(0);
2846     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
2847     unique_ptr<value_type, __destruct_n&> __h(&*__f, __d);
2848     for (; __n > 0; ++__f, --__n, __d.__incr((value_type*)0))
2849         ::new(&*__f) value_type(__x);
2850     __h.release();
2851     return __f;
2852 }
2853
2854 class _LIBCPP_EXCEPTION_ABI bad_weak_ptr
2855     : public std::exception
2856 {
2857 public:
2858     virtual ~bad_weak_ptr() _NOEXCEPT;
2859     virtual const char* what() const  _NOEXCEPT;
2860 };
2861
2862 template<class _Tp> class weak_ptr;
2863
2864 class __shared_count
2865 {
2866     __shared_count(const __shared_count&);
2867     __shared_count& operator=(const __shared_count&);
2868
2869 protected:
2870     long __shared_owners_;
2871     virtual ~__shared_count();
2872 private:
2873     virtual void __on_zero_shared() _NOEXCEPT = 0;
2874
2875 public:
2876     _LIBCPP_INLINE_VISIBILITY
2877     explicit __shared_count(long __refs = 0) _NOEXCEPT
2878         : __shared_owners_(__refs) {}
2879
2880     void __add_shared() _NOEXCEPT;
2881     bool __release_shared() _NOEXCEPT;
2882     _LIBCPP_INLINE_VISIBILITY
2883     long use_count() const _NOEXCEPT {return __shared_owners_ + 1;}
2884 };
2885
2886 class __shared_weak_count
2887     : private __shared_count
2888 {
2889     long __shared_weak_owners_;
2890
2891 public:
2892     _LIBCPP_INLINE_VISIBILITY
2893     explicit __shared_weak_count(long __refs = 0) _NOEXCEPT
2894         : __shared_count(__refs),
2895           __shared_weak_owners_(__refs) {}
2896 protected:
2897     virtual ~__shared_weak_count();
2898
2899 public:
2900     void __add_shared() _NOEXCEPT;
2901     void __add_weak() _NOEXCEPT;
2902     void __release_shared() _NOEXCEPT;
2903     void __release_weak() _NOEXCEPT;
2904     _LIBCPP_INLINE_VISIBILITY
2905     long use_count() const _NOEXCEPT {return __shared_count::use_count();}
2906     __shared_weak_count* lock() _NOEXCEPT;
2907
2908     virtual const void* __get_deleter(const type_info&) const _NOEXCEPT;
2909 private:
2910     virtual void __on_zero_shared_weak() _NOEXCEPT = 0;
2911 };
2912
2913 template <class _Tp, class _Dp, class _Alloc>
2914 class __shared_ptr_pointer
2915     : public __shared_weak_count
2916 {
2917     __compressed_pair<__compressed_pair<_Tp, _Dp>, _Alloc> __data_;
2918 public:
2919     _LIBCPP_INLINE_VISIBILITY
2920     __shared_ptr_pointer(_Tp __p, _Dp __d, _Alloc __a)
2921         :  __data_(__compressed_pair<_Tp, _Dp>(__p, _VSTD::move(__d)), _VSTD::move(__a)) {}
2922
2923 #ifndef _LIBCPP_NO_RTTI
2924     virtual const void* __get_deleter(const type_info&) const _NOEXCEPT;
2925 #endif
2926
2927 private:
2928     virtual void __on_zero_shared() _NOEXCEPT;
2929     virtual void __on_zero_shared_weak() _NOEXCEPT;
2930 };
2931
2932 #ifndef _LIBCPP_NO_RTTI
2933
2934 template <class _Tp, class _Dp, class _Alloc>
2935 const void*
2936 __shared_ptr_pointer<_Tp, _Dp, _Alloc>::__get_deleter(const type_info& __t) const _NOEXCEPT
2937 {
2938     return __t == typeid(_Dp) ? &__data_.first().second() : 0;
2939 }
2940
2941 #endif  // _LIBCPP_NO_RTTI
2942
2943 template <class _Tp, class _Dp, class _Alloc>
2944 void
2945 __shared_ptr_pointer<_Tp, _Dp, _Alloc>::__on_zero_shared() _NOEXCEPT
2946 {
2947     __data_.first().second()(__data_.first().first());
2948     __data_.first().second().~_Dp();
2949 }
2950
2951 template <class _Tp, class _Dp, class _Alloc>
2952 void
2953 __shared_ptr_pointer<_Tp, _Dp, _Alloc>::__on_zero_shared_weak() _NOEXCEPT
2954 {
2955     typename _Alloc::template rebind<__shared_ptr_pointer>::other __a(__data_.second());
2956     __data_.second().~_Alloc();
2957     __a.deallocate(this, 1);
2958 }
2959
2960 template <class _Tp, class _Alloc>
2961 class __shared_ptr_emplace
2962     : public __shared_weak_count
2963 {
2964     __compressed_pair<_Alloc, _Tp> __data_;
2965 public:
2966 #ifndef _LIBCPP_HAS_NO_VARIADICS
2967
2968     _LIBCPP_INLINE_VISIBILITY
2969     __shared_ptr_emplace(_Alloc __a)
2970         :  __data_(_VSTD::move(__a)) {}
2971
2972     template <class ..._Args>
2973         _LIBCPP_INLINE_VISIBILITY
2974         __shared_ptr_emplace(_Alloc __a, _Args&& ...__args)
2975             :  __data_(_VSTD::move(__a), _Tp(_VSTD::forward<_Args>(__args)...)) {}
2976
2977 #else  // _LIBCPP_HAS_NO_VARIADICS
2978
2979     _LIBCPP_INLINE_VISIBILITY
2980     __shared_ptr_emplace(_Alloc __a)
2981         :  __data_(__a) {}
2982
2983     template <class _A0>
2984         _LIBCPP_INLINE_VISIBILITY
2985         __shared_ptr_emplace(_Alloc __a, _A0& __a0)
2986             :  __data_(__a, _Tp(__a0)) {}
2987
2988     template <class _A0, class _A1>
2989         _LIBCPP_INLINE_VISIBILITY
2990         __shared_ptr_emplace(_Alloc __a, _A0& __a0, _A1& __a1)
2991             :  __data_(__a, _Tp(__a0, __a1)) {}
2992
2993     template <class _A0, class _A1, class _A2>
2994         _LIBCPP_INLINE_VISIBILITY
2995         __shared_ptr_emplace(_Alloc __a, _A0& __a0, _A1& __a1, _A2& __a2)
2996             :  __data_(__a, _Tp(__a0, __a1, __a2)) {}
2997
2998 #endif  // _LIBCPP_HAS_NO_VARIADICS
2999
3000 private:
3001     virtual void __on_zero_shared() _NOEXCEPT;
3002     virtual void __on_zero_shared_weak() _NOEXCEPT;
3003 public:
3004     _LIBCPP_INLINE_VISIBILITY
3005     _Tp* get() _NOEXCEPT {return &__data_.second();}
3006 };
3007
3008 template <class _Tp, class _Alloc>
3009 void
3010 __shared_ptr_emplace<_Tp, _Alloc>::__on_zero_shared() _NOEXCEPT
3011 {
3012     __data_.second().~_Tp();
3013 }
3014
3015 template <class _Tp, class _Alloc>
3016 void
3017 __shared_ptr_emplace<_Tp, _Alloc>::__on_zero_shared_weak() _NOEXCEPT
3018 {
3019     typename _Alloc::template rebind<__shared_ptr_emplace>::other __a(__data_.first());
3020     __data_.first().~_Alloc();
3021     __a.deallocate(this, 1);
3022 }
3023
3024 template<class _Tp> class enable_shared_from_this;
3025
3026 template<class _Tp>
3027 class _LIBCPP_VISIBLE shared_ptr
3028 {
3029 public:
3030     typedef _Tp element_type;
3031 private:
3032     element_type*      __ptr_;
3033     __shared_weak_count* __cntrl_;
3034
3035     struct __nat {int __for_bool_;};
3036 public:
3037     shared_ptr() _NOEXCEPT;
3038     shared_ptr(nullptr_t) _NOEXCEPT;
3039     template<class _Yp> explicit shared_ptr(_Yp* __p);
3040     template<class _Yp, class _Dp> shared_ptr(_Yp* __p, _Dp __d);
3041     template<class _Yp, class _Dp, class _Alloc> shared_ptr(_Yp* __p, _Dp __d, _Alloc __a);
3042     template <class _Dp> shared_ptr(nullptr_t __p, _Dp __d);
3043     template <class _Dp, class _Alloc> shared_ptr(nullptr_t __p, _Dp __d, _Alloc __a);
3044     template<class _Yp> shared_ptr(const shared_ptr<_Yp>& __r, element_type* __p) _NOEXCEPT;
3045     shared_ptr(const shared_ptr& __r) _NOEXCEPT;
3046     template<class _Yp>
3047         shared_ptr(const shared_ptr<_Yp>& __r,
3048                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type = __nat())
3049                        _NOEXCEPT;
3050 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3051     shared_ptr(shared_ptr&& __r) _NOEXCEPT;
3052     template<class _Yp> shared_ptr(shared_ptr<_Yp>&& __r,
3053                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type = __nat())
3054                        _NOEXCEPT;
3055 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3056     template<class _Yp> explicit shared_ptr(const weak_ptr<_Yp>& __r,
3057                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type= __nat());
3058 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3059     template<class _Yp> shared_ptr(auto_ptr<_Yp>&& __r);
3060 #else
3061     template<class _Yp> shared_ptr(auto_ptr<_Yp> __r);
3062 #endif
3063 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3064 private:
3065     template <class _Yp, class _Dp> shared_ptr(const unique_ptr<_Yp, _Dp>& __r);// = delete;
3066 public:
3067     template <class _Yp, class _Dp> shared_ptr(unique_ptr<_Yp, _Dp>&&,
3068        typename enable_if<!is_lvalue_reference<_Dp>::value, __nat>::type = __nat());
3069     template <class _Yp, class _Dp> shared_ptr(unique_ptr<_Yp, _Dp>&&,
3070        typename enable_if<is_lvalue_reference<_Dp>::value, __nat>::type = __nat());
3071 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3072     template <class _Yp, class _Dp> shared_ptr(unique_ptr<_Yp, _Dp>,
3073        typename enable_if<!is_lvalue_reference<_Dp>::value, __nat>::type = __nat());
3074     template <class _Yp, class _Dp> shared_ptr(unique_ptr<_Yp, _Dp>,
3075        typename enable_if<is_lvalue_reference<_Dp>::value, __nat>::type = __nat());
3076 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3077
3078     ~shared_ptr();
3079
3080     shared_ptr& operator=(const shared_ptr& __r) _NOEXCEPT;
3081     template<class _Yp> shared_ptr& operator=(const shared_ptr<_Yp>& __r) _NOEXCEPT;
3082 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3083     shared_ptr& operator=(shared_ptr&& __r) _NOEXCEPT;
3084     template<class _Yp> shared_ptr& operator=(shared_ptr<_Yp>&& __r);
3085     template<class _Yp> shared_ptr& operator=(auto_ptr<_Yp>&& __r);
3086 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3087     template<class _Yp> shared_ptr& operator=(auto_ptr<_Yp> __r);
3088 #endif
3089 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3090 private:
3091     template <class _Yp, class _Dp> shared_ptr& operator=(const unique_ptr<_Yp, _Dp>& __r);// = delete;
3092 public:
3093     template <class _Yp, class _Dp> shared_ptr& operator=(unique_ptr<_Yp, _Dp>&& __r);
3094 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3095     template <class _Yp, class _Dp> shared_ptr& operator=(unique_ptr<_Yp, _Dp> __r);
3096 #endif
3097
3098     void swap(shared_ptr& __r) _NOEXCEPT;
3099     void reset() _NOEXCEPT;
3100     template<class _Yp> void reset(_Yp* __p) _NOEXCEPT;
3101     template<class _Yp, class _Dp> void reset(_Yp* __p, _Dp __d);
3102     template<class _Yp, class _Dp, class _Alloc> void reset(_Yp* __p, _Dp __d, _Alloc __a);
3103
3104     _LIBCPP_INLINE_VISIBILITY
3105     element_type* get() const _NOEXCEPT {return __ptr_;}
3106     _LIBCPP_INLINE_VISIBILITY
3107     typename add_lvalue_reference<element_type>::type operator*() const _NOEXCEPT
3108         {return *__ptr_;}
3109     _LIBCPP_INLINE_VISIBILITY
3110     element_type* operator->() const _NOEXCEPT {return __ptr_;}
3111     _LIBCPP_INLINE_VISIBILITY
3112     long use_count() const _NOEXCEPT {return __cntrl_ ? __cntrl_->use_count() : 0;}
3113     _LIBCPP_INLINE_VISIBILITY
3114     bool unique() const _NOEXCEPT {return use_count() == 1;}
3115     _LIBCPP_INLINE_VISIBILITY
3116     /*explicit*/ operator bool() const _NOEXCEPT {return get() != 0;}
3117     template <class _U>
3118         _LIBCPP_INLINE_VISIBILITY
3119         bool owner_before(shared_ptr<_U> const& __p) const
3120         {return __cntrl_ < __p.__cntrl_;}
3121     template <class _U>
3122         _LIBCPP_INLINE_VISIBILITY
3123         bool owner_before(weak_ptr<_U> const& __p) const
3124         {return __cntrl_ < __p.__cntrl_;}
3125
3126 #ifndef _LIBCPP_NO_RTTI
3127     template <class _Dp>
3128         _LIBCPP_INLINE_VISIBILITY
3129         _Dp* __get_deleter() const _NOEXCEPT
3130             {return (_Dp*)(__cntrl_ ? __cntrl_->__get_deleter(typeid(_Dp)) : 0);}
3131 #endif  // _LIBCPP_NO_RTTI
3132
3133 #ifndef _LIBCPP_HAS_NO_VARIADICS
3134
3135     template<class ..._Args>
3136         static
3137         shared_ptr<_Tp>
3138         make_shared(_Args&& ...__args);
3139
3140     template<class _Alloc, class ..._Args>
3141         static
3142         shared_ptr<_Tp>
3143         allocate_shared(const _Alloc& __a, _Args&& ...__args);
3144
3145 #else  // _LIBCPP_HAS_NO_VARIADICS
3146
3147     static shared_ptr<_Tp> make_shared();
3148
3149     template<class _A0>
3150         static shared_ptr<_Tp> make_shared(_A0&);
3151
3152     template<class _A0, class _A1>
3153         static shared_ptr<_Tp> make_shared(_A0&, _A1&);
3154
3155     template<class _A0, class _A1, class _A2>
3156         static shared_ptr<_Tp> make_shared(_A0&, _A1&, _A2&);
3157
3158     template<class _Alloc>
3159         static shared_ptr<_Tp>
3160         allocate_shared(const _Alloc& __a);
3161
3162     template<class _Alloc, class _A0>
3163         static shared_ptr<_Tp>
3164         allocate_shared(const _Alloc& __a, _A0& __a0);
3165
3166     template<class _Alloc, class _A0, class _A1>
3167         static shared_ptr<_Tp>
3168         allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1);
3169
3170     template<class _Alloc, class _A0, class _A1, class _A2>
3171         static shared_ptr<_Tp>
3172         allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2);
3173
3174 #endif  // _LIBCPP_HAS_NO_VARIADICS
3175
3176 private:
3177
3178     template <class _Yp>
3179         _LIBCPP_INLINE_VISIBILITY
3180         void
3181         __enable_weak_this(const enable_shared_from_this<_Yp>* __e) _NOEXCEPT
3182         {
3183             if (__e)
3184                 __e->__weak_this_ = *this;
3185         }
3186
3187     _LIBCPP_INLINE_VISIBILITY
3188     void __enable_weak_this(const void*) _NOEXCEPT {}
3189
3190     template <class _Up> friend class _LIBCPP_VISIBLE shared_ptr;
3191     template <class _Up> friend class _LIBCPP_VISIBLE weak_ptr;
3192 };
3193
3194 template<class _Tp>
3195 inline _LIBCPP_INLINE_VISIBILITY
3196 shared_ptr<_Tp>::shared_ptr() _NOEXCEPT
3197     : __ptr_(0),
3198       __cntrl_(0)
3199 {
3200 }
3201
3202 template<class _Tp>
3203 inline _LIBCPP_INLINE_VISIBILITY
3204 shared_ptr<_Tp>::shared_ptr(nullptr_t) _NOEXCEPT
3205     : __ptr_(0),
3206       __cntrl_(0)
3207 {
3208 }
3209
3210 template<class _Tp>
3211 template<class _Yp>
3212 shared_ptr<_Tp>::shared_ptr(_Yp* __p)
3213     : __ptr_(__p)
3214 {
3215     unique_ptr<_Yp> __hold(__p);
3216     typedef __shared_ptr_pointer<_Yp*, default_delete<_Yp>, allocator<_Yp> > _CntrlBlk;
3217     __cntrl_ = new _CntrlBlk(__p, default_delete<_Yp>(), allocator<_Yp>());
3218     __hold.release();
3219     __enable_weak_this(__p);
3220 }
3221
3222 template<class _Tp>
3223 template<class _Yp, class _Dp>
3224 shared_ptr<_Tp>::shared_ptr(_Yp* __p, _Dp __d)
3225     : __ptr_(__p)
3226 {
3227 #ifndef _LIBCPP_NO_EXCEPTIONS
3228     try
3229     {
3230 #endif  // _LIBCPP_NO_EXCEPTIONS
3231         typedef __shared_ptr_pointer<_Yp*, _Dp, allocator<_Yp> > _CntrlBlk;
3232         __cntrl_ = new _CntrlBlk(__p, __d, allocator<_Yp>());
3233         __enable_weak_this(__p);
3234 #ifndef _LIBCPP_NO_EXCEPTIONS
3235     }
3236     catch (...)
3237     {
3238         __d(__p);
3239         throw;
3240     }
3241 #endif  // _LIBCPP_NO_EXCEPTIONS
3242 }
3243
3244 template<class _Tp>
3245 template<class _Dp>
3246 shared_ptr<_Tp>::shared_ptr(nullptr_t __p, _Dp __d)
3247     : __ptr_(0)
3248 {
3249 #ifndef _LIBCPP_NO_EXCEPTIONS
3250     try
3251     {
3252 #endif  // _LIBCPP_NO_EXCEPTIONS
3253         typedef __shared_ptr_pointer<nullptr_t, _Dp, allocator<_Tp> > _CntrlBlk;
3254         __cntrl_ = new _CntrlBlk(__p, __d, allocator<_Tp>());
3255 #ifndef _LIBCPP_NO_EXCEPTIONS
3256     }
3257     catch (...)
3258     {
3259         __d(__p);
3260         throw;
3261     }
3262 #endif  // _LIBCPP_NO_EXCEPTIONS
3263 }
3264
3265 template<class _Tp>
3266 template<class _Yp, class _Dp, class _Alloc>
3267 shared_ptr<_Tp>::shared_ptr(_Yp* __p, _Dp __d, _Alloc __a)
3268     : __ptr_(__p)
3269 {
3270 #ifndef _LIBCPP_NO_EXCEPTIONS
3271     try
3272     {
3273 #endif  // _LIBCPP_NO_EXCEPTIONS
3274         typedef __shared_ptr_pointer<_Yp*, _Dp, _Alloc> _CntrlBlk;
3275         typedef typename _Alloc::template rebind<_CntrlBlk>::other _A2;
3276         typedef __allocator_destructor<_A2> _D2;
3277         _A2 __a2(__a);
3278         unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
3279         ::new(__hold2.get()) _CntrlBlk(__p, __d, __a);
3280         __cntrl_ = __hold2.release();
3281         __enable_weak_this(__p);
3282 #ifndef _LIBCPP_NO_EXCEPTIONS
3283     }
3284     catch (...)
3285     {
3286         __d(__p);
3287         throw;
3288     }
3289 #endif  // _LIBCPP_NO_EXCEPTIONS
3290 }
3291
3292 template<class _Tp>
3293 template<class _Dp, class _Alloc>
3294 shared_ptr<_Tp>::shared_ptr(nullptr_t __p, _Dp __d, _Alloc __a)
3295     : __ptr_(0)
3296 {
3297 #ifndef _LIBCPP_NO_EXCEPTIONS
3298     try
3299     {
3300 #endif  // _LIBCPP_NO_EXCEPTIONS
3301         typedef __shared_ptr_pointer<nullptr_t, _Dp, _Alloc> _CntrlBlk;
3302         typedef typename _Alloc::template rebind<_CntrlBlk>::other _A2;
3303         typedef __allocator_destructor<_A2> _D2;
3304         _A2 __a2(__a);
3305         unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
3306         ::new(__hold2.get()) _CntrlBlk(__p, __d, __a);
3307         __cntrl_ = __hold2.release();
3308 #ifndef _LIBCPP_NO_EXCEPTIONS
3309     }
3310     catch (...)
3311     {
3312         __d(__p);
3313         throw;
3314     }
3315 #endif  // _LIBCPP_NO_EXCEPTIONS
3316 }
3317
3318 template<class _Tp>
3319 template<class _Yp>
3320 inline _LIBCPP_INLINE_VISIBILITY
3321 shared_ptr<_Tp>::shared_ptr(const shared_ptr<_Yp>& __r, element_type *__p) _NOEXCEPT
3322     : __ptr_(__p),
3323       __cntrl_(__r.__cntrl_)
3324 {
3325     if (__cntrl_)
3326         __cntrl_->__add_shared();
3327 }
3328
3329 template<class _Tp>
3330 inline _LIBCPP_INLINE_VISIBILITY
3331 shared_ptr<_Tp>::shared_ptr(const shared_ptr& __r) _NOEXCEPT
3332     : __ptr_(__r.__ptr_),
3333       __cntrl_(__r.__cntrl_)
3334 {
3335     if (__cntrl_)
3336         __cntrl_->__add_shared();
3337 }
3338
3339 template<class _Tp>
3340 template<class _Yp>
3341 inline _LIBCPP_INLINE_VISIBILITY
3342 shared_ptr<_Tp>::shared_ptr(const shared_ptr<_Yp>& __r,
3343                             typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type)
3344          _NOEXCEPT
3345     : __ptr_(__r.__ptr_),
3346       __cntrl_(__r.__cntrl_)
3347 {
3348     if (__cntrl_)
3349         __cntrl_->__add_shared();
3350 }
3351
3352 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3353
3354 template<class _Tp>
3355 inline _LIBCPP_INLINE_VISIBILITY
3356 shared_ptr<_Tp>::shared_ptr(shared_ptr&& __r) _NOEXCEPT
3357     : __ptr_(__r.__ptr_),
3358       __cntrl_(__r.__cntrl_)
3359 {
3360     __r.__ptr_ = 0;
3361     __r.__cntrl_ = 0;
3362 }
3363
3364 template<class _Tp>
3365 template<class _Yp>
3366 inline _LIBCPP_INLINE_VISIBILITY
3367 shared_ptr<_Tp>::shared_ptr(shared_ptr<_Yp>&& __r,
3368                             typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type)
3369          _NOEXCEPT
3370     : __ptr_(__r.__ptr_),
3371       __cntrl_(__r.__cntrl_)
3372 {
3373     __r.__ptr_ = 0;
3374     __r.__cntrl_ = 0;
3375 }
3376
3377 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3378
3379 template<class _Tp>
3380 template<class _Yp>
3381 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3382 shared_ptr<_Tp>::shared_ptr(auto_ptr<_Yp>&& __r)
3383 #else
3384 shared_ptr<_Tp>::shared_ptr(auto_ptr<_Yp> __r)
3385 #endif
3386     : __ptr_(__r.get())
3387 {
3388     typedef __shared_ptr_pointer<_Yp*, default_delete<_Yp>, allocator<_Yp> > _CntrlBlk;
3389     __cntrl_ = new _CntrlBlk(__r.get(), default_delete<_Yp>(), allocator<_Yp>());
3390     __enable_weak_this(__r.get());
3391     __r.release();
3392 }
3393
3394 template<class _Tp>
3395 template <class _Yp, class _Dp>
3396 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3397 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp>&& __r,
3398 #else
3399 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp> __r,
3400 #endif
3401            typename enable_if<!is_lvalue_reference<_Dp>::value, __nat>::type)
3402     : __ptr_(__r.get())
3403 {
3404     typedef __shared_ptr_pointer<_Yp*, _Dp, allocator<_Yp> > _CntrlBlk;
3405     __cntrl_ = new _CntrlBlk(__r.get(), __r.get_deleter(), allocator<_Yp>());
3406     __enable_weak_this(__r.get());
3407     __r.release();
3408 }
3409
3410 template<class _Tp>
3411 template <class _Yp, class _Dp>
3412 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3413 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp>&& __r,
3414 #else
3415 shared_ptr<_Tp>::shared_ptr(unique_ptr<_Yp, _Dp> __r,
3416 #endif
3417            typename enable_if<is_lvalue_reference<_Dp>::value, __nat>::type)
3418     : __ptr_(__r.get())
3419 {
3420     typedef __shared_ptr_pointer<_Yp*,
3421                                  reference_wrapper<typename remove_reference<_Dp>::type>,
3422                                  allocator<_Yp> > _CntrlBlk;
3423     __cntrl_ = new _CntrlBlk(__r.get(), ref(__r.get_deleter()), allocator<_Yp>());
3424     __enable_weak_this(__r.get());
3425     __r.release();
3426 }
3427
3428 #ifndef _LIBCPP_HAS_NO_VARIADICS
3429
3430 template<class _Tp>
3431 template<class ..._Args>
3432 shared_ptr<_Tp>
3433 shared_ptr<_Tp>::make_shared(_Args&& ...__args)
3434 {
3435     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
3436     typedef allocator<_CntrlBlk> _A2;
3437     typedef __allocator_destructor<_A2> _D2;
3438     _A2 __a2;
3439     unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
3440     ::new(__hold2.get()) _CntrlBlk(__a2, _VSTD::forward<_Args>(__args)...);
3441     shared_ptr<_Tp> __r;
3442     __r.__ptr_ = __hold2.get()->get();
3443     __r.__cntrl_ = __hold2.release();
3444     __r.__enable_weak_this(__r.__ptr_);
3445     return __r;
3446 }
3447
3448 template<class _Tp>
3449 template<class _Alloc, class ..._Args>
3450 shared_ptr<_Tp>
3451 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _Args&& ...__args)
3452 {
3453     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
3454     typedef typename _Alloc::template rebind<_CntrlBlk>::other _A2;
3455     typedef __allocator_destructor<_A2> _D2;
3456     _A2 __a2(__a);
3457     unique_ptr<_CntrlBlk, _D2> __hold2(__a2.allocate(1), _D2(__a2, 1));
3458     ::new(__hold2.get()) _CntrlBlk(__a, _VSTD::forward<_Args>(__args)...);
3459     shared_ptr<_Tp> __r;
3460     __r.__ptr_ = __hold2.get()->get();
3461     __r.__cntrl_ = __hold2.release();
3462     __r.__enable_weak_this(__r.__ptr_);
3463     return __r;
3464 }
3465
3466 #else  // _LIBCPP_HAS_NO_VARIADICS
3467
3468 template<class _Tp>
3469 shared_ptr<_Tp>
3470 shared_ptr<_Tp>::make_shared()
3471 {
3472     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
3473     typedef allocator<_CntrlBlk> _Alloc2;
3474     typedef __allocator_destructor<_Alloc2> _D2;
3475     _Alloc2 __alloc2;
3476     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
3477     ::new(__hold2.get()) _CntrlBlk(__alloc2);
3478     shared_ptr<_Tp> __r;
3479     __r.__ptr_ = __hold2.get()->get();
3480     __r.__cntrl_ = __hold2.release();
3481     __r.__enable_weak_this(__r.__ptr_);
3482     return __r;
3483 }
3484
3485 template<class _Tp>
3486 template<class _A0>
3487 shared_ptr<_Tp>
3488 shared_ptr<_Tp>::make_shared(_A0& __a0)
3489 {
3490     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
3491     typedef allocator<_CntrlBlk> _Alloc2;
3492     typedef __allocator_destructor<_Alloc2> _D2;
3493     _Alloc2 __alloc2;
3494     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
3495     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0);
3496     shared_ptr<_Tp> __r;
3497     __r.__ptr_ = __hold2.get()->get();
3498     __r.__cntrl_ = __hold2.release();
3499     __r.__enable_weak_this(__r.__ptr_);
3500     return __r;
3501 }
3502
3503 template<class _Tp>
3504 template<class _A0, class _A1>
3505 shared_ptr<_Tp>
3506 shared_ptr<_Tp>::make_shared(_A0& __a0, _A1& __a1)
3507 {
3508     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
3509     typedef allocator<_CntrlBlk> _Alloc2;
3510     typedef __allocator_destructor<_Alloc2> _D2;
3511     _Alloc2 __alloc2;
3512     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
3513     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0, __a1);
3514     shared_ptr<_Tp> __r;
3515     __r.__ptr_ = __hold2.get()->get();
3516     __r.__cntrl_ = __hold2.release();
3517     __r.__enable_weak_this(__r.__ptr_);
3518     return __r;
3519 }
3520
3521 template<class _Tp>
3522 template<class _A0, class _A1, class _A2>
3523 shared_ptr<_Tp>
3524 shared_ptr<_Tp>::make_shared(_A0& __a0, _A1& __a1, _A2& __a2)
3525 {
3526     typedef __shared_ptr_emplace<_Tp, allocator<_Tp> > _CntrlBlk;
3527     typedef allocator<_CntrlBlk> _Alloc2;
3528     typedef __allocator_destructor<_Alloc2> _D2;
3529     _Alloc2 __alloc2;
3530     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
3531     ::new(__hold2.get()) _CntrlBlk(__alloc2, __a0, __a1, __a2);
3532     shared_ptr<_Tp> __r;
3533     __r.__ptr_ = __hold2.get()->get();
3534     __r.__cntrl_ = __hold2.release();
3535     __r.__enable_weak_this(__r.__ptr_);
3536     return __r;
3537 }
3538
3539 template<class _Tp>
3540 template<class _Alloc>
3541 shared_ptr<_Tp>
3542 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a)
3543 {
3544     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
3545     typedef typename _Alloc::template rebind<_CntrlBlk>::other _Alloc2;
3546     typedef __allocator_destructor<_Alloc2> _D2;
3547     _Alloc2 __alloc2(__a);
3548     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
3549     ::new(__hold2.get()) _CntrlBlk(__a);
3550     shared_ptr<_Tp> __r;
3551     __r.__ptr_ = __hold2.get()->get();
3552     __r.__cntrl_ = __hold2.release();
3553     __r.__enable_weak_this(__r.__ptr_);
3554     return __r;
3555 }
3556
3557 template<class _Tp>
3558 template<class _Alloc, class _A0>
3559 shared_ptr<_Tp>
3560 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0)
3561 {
3562     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
3563     typedef typename _Alloc::template rebind<_CntrlBlk>::other _Alloc2;
3564     typedef __allocator_destructor<_Alloc2> _D2;
3565     _Alloc2 __alloc2(__a);
3566     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
3567     ::new(__hold2.get()) _CntrlBlk(__a, __a0);
3568     shared_ptr<_Tp> __r;
3569     __r.__ptr_ = __hold2.get()->get();
3570     __r.__cntrl_ = __hold2.release();
3571     __r.__enable_weak_this(__r.__ptr_);
3572     return __r;
3573 }
3574
3575 template<class _Tp>
3576 template<class _Alloc, class _A0, class _A1>
3577 shared_ptr<_Tp>
3578 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1)
3579 {
3580     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
3581     typedef typename _Alloc::template rebind<_CntrlBlk>::other _Alloc2;
3582     typedef __allocator_destructor<_Alloc2> _D2;
3583     _Alloc2 __alloc2(__a);
3584     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
3585     ::new(__hold2.get()) _CntrlBlk(__a, __a0, __a1);
3586     shared_ptr<_Tp> __r;
3587     __r.__ptr_ = __hold2.get()->get();
3588     __r.__cntrl_ = __hold2.release();
3589     __r.__enable_weak_this(__r.__ptr_);
3590     return __r;
3591 }
3592
3593 template<class _Tp>
3594 template<class _Alloc, class _A0, class _A1, class _A2>
3595 shared_ptr<_Tp>
3596 shared_ptr<_Tp>::allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2)
3597 {
3598     typedef __shared_ptr_emplace<_Tp, _Alloc> _CntrlBlk;
3599     typedef typename _Alloc::template rebind<_CntrlBlk>::other _Alloc2;
3600     typedef __allocator_destructor<_Alloc2> _D2;
3601     _Alloc2 __alloc2(__a);
3602     unique_ptr<_CntrlBlk, _D2> __hold2(__alloc2.allocate(1), _D2(__alloc2, 1));
3603     ::new(__hold2.get()) _CntrlBlk(__a, __a0, __a1, __a2);
3604     shared_ptr<_Tp> __r;
3605     __r.__ptr_ = __hold2.get()->get();
3606     __r.__cntrl_ = __hold2.release();
3607     __r.__enable_weak_this(__r.__ptr_);
3608     return __r;
3609 }
3610
3611 #endif  // _LIBCPP_HAS_NO_VARIADICS
3612
3613 template<class _Tp>
3614 shared_ptr<_Tp>::~shared_ptr()
3615 {
3616     if (__cntrl_)
3617         __cntrl_->__release_shared();
3618 }
3619
3620 template<class _Tp>
3621 inline _LIBCPP_INLINE_VISIBILITY
3622 shared_ptr<_Tp>&
3623 shared_ptr<_Tp>::operator=(const shared_ptr& __r) _NOEXCEPT
3624 {
3625     shared_ptr(__r).swap(*this);
3626     return *this;
3627 }
3628
3629 template<class _Tp>
3630 template<class _Yp>
3631 inline _LIBCPP_INLINE_VISIBILITY
3632 shared_ptr<_Tp>&
3633 shared_ptr<_Tp>::operator=(const shared_ptr<_Yp>& __r) _NOEXCEPT
3634 {
3635     shared_ptr(__r).swap(*this);
3636     return *this;
3637 }
3638
3639 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3640
3641 template<class _Tp>
3642 inline _LIBCPP_INLINE_VISIBILITY
3643 shared_ptr<_Tp>&
3644 shared_ptr<_Tp>::operator=(shared_ptr&& __r) _NOEXCEPT
3645 {
3646     shared_ptr(_VSTD::move(__r)).swap(*this);
3647     return *this;
3648 }
3649
3650 template<class _Tp>
3651 template<class _Yp>
3652 inline _LIBCPP_INLINE_VISIBILITY
3653 shared_ptr<_Tp>&
3654 shared_ptr<_Tp>::operator=(shared_ptr<_Yp>&& __r)
3655 {
3656     shared_ptr(_VSTD::move(__r)).swap(*this);
3657     return *this;
3658 }
3659
3660 template<class _Tp>
3661 template<class _Yp>
3662 inline _LIBCPP_INLINE_VISIBILITY
3663 shared_ptr<_Tp>&
3664 shared_ptr<_Tp>::operator=(auto_ptr<_Yp>&& __r)
3665 {
3666     shared_ptr(_VSTD::move(__r)).swap(*this);
3667     return *this;
3668 }
3669
3670 template<class _Tp>
3671 template <class _Yp, class _Dp>
3672 inline _LIBCPP_INLINE_VISIBILITY
3673 shared_ptr<_Tp>&
3674 shared_ptr<_Tp>::operator=(unique_ptr<_Yp, _Dp>&& __r)
3675 {
3676     shared_ptr(_VSTD::move(__r)).swap(*this);
3677     return *this;
3678 }
3679
3680 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3681
3682 template<class _Tp>
3683 template<class _Yp>
3684 inline _LIBCPP_INLINE_VISIBILITY
3685 shared_ptr<_Tp>&
3686 shared_ptr<_Tp>::operator=(auto_ptr<_Yp> __r)
3687 {
3688     shared_ptr(__r).swap(*this);
3689     return *this;
3690 }
3691
3692 template<class _Tp>
3693 template <class _Yp, class _Dp>
3694 inline _LIBCPP_INLINE_VISIBILITY
3695 shared_ptr<_Tp>&
3696 shared_ptr<_Tp>::operator=(unique_ptr<_Yp, _Dp> __r)
3697 {
3698     shared_ptr(_VSTD::move(__r)).swap(*this);
3699     return *this;
3700 }
3701
3702 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3703
3704 template<class _Tp>
3705 inline _LIBCPP_INLINE_VISIBILITY
3706 void
3707 shared_ptr<_Tp>::swap(shared_ptr& __r) _NOEXCEPT
3708 {
3709     _VSTD::swap(__ptr_, __r.__ptr_);
3710     _VSTD::swap(__cntrl_, __r.__cntrl_);
3711 }
3712
3713 template<class _Tp>
3714 inline _LIBCPP_INLINE_VISIBILITY
3715 void
3716 shared_ptr<_Tp>::reset() _NOEXCEPT
3717 {
3718     shared_ptr().swap(*this);
3719 }
3720
3721 template<class _Tp>
3722 template<class _Yp>
3723 inline _LIBCPP_INLINE_VISIBILITY
3724 void
3725 shared_ptr<_Tp>::reset(_Yp* __p)
3726 {
3727     shared_ptr(__p).swap(*this);
3728 }
3729
3730 template<class _Tp>
3731 template<class _Yp, class _Dp>
3732 inline _LIBCPP_INLINE_VISIBILITY
3733 void
3734 shared_ptr<_Tp>::reset(_Yp* __p, _Dp __d)
3735 {
3736     shared_ptr(__p, __d).swap(*this);
3737 }
3738
3739 template<class _Tp>
3740 template<class _Yp, class _Dp, class _Alloc>
3741 inline _LIBCPP_INLINE_VISIBILITY
3742 void
3743 shared_ptr<_Tp>::reset(_Yp* __p, _Dp __d, _Alloc __a)
3744 {
3745     shared_ptr(__p, __d, __a).swap(*this);
3746 }
3747
3748 #ifndef _LIBCPP_HAS_NO_VARIADICS
3749
3750 template<class _Tp, class ..._Args>
3751 inline _LIBCPP_INLINE_VISIBILITY
3752 shared_ptr<_Tp>
3753 make_shared(_Args&& ...__args)
3754 {
3755     return shared_ptr<_Tp>::make_shared(_VSTD::forward<_Args>(__args)...);
3756 }
3757
3758 template<class _Tp, class _Alloc, class ..._Args>
3759 inline _LIBCPP_INLINE_VISIBILITY
3760 shared_ptr<_Tp>
3761 allocate_shared(const _Alloc& __a, _Args&& ...__args)
3762 {
3763     return shared_ptr<_Tp>::allocate_shared(__a, _VSTD::forward<_Args>(__args)...);
3764 }
3765
3766 #else  // _LIBCPP_HAS_NO_VARIADICS
3767
3768 template<class _Tp>
3769 inline _LIBCPP_INLINE_VISIBILITY
3770 shared_ptr<_Tp>
3771 make_shared()
3772 {
3773     return shared_ptr<_Tp>::make_shared();
3774 }
3775
3776 template<class _Tp, class _A0>
3777 inline _LIBCPP_INLINE_VISIBILITY
3778 shared_ptr<_Tp>
3779 make_shared(_A0& __a0)
3780 {
3781     return shared_ptr<_Tp>::make_shared(__a0);
3782 }
3783
3784 template<class _Tp, class _A0, class _A1>
3785 inline _LIBCPP_INLINE_VISIBILITY
3786 shared_ptr<_Tp>
3787 make_shared(_A0& __a0, _A1& __a1)
3788 {
3789     return shared_ptr<_Tp>::make_shared(__a0, __a1);
3790 }
3791
3792 template<class _Tp, class _A0, class _A1, class _A2>
3793 inline _LIBCPP_INLINE_VISIBILITY
3794 shared_ptr<_Tp>
3795 make_shared(_A0& __a0, _A1& __a1, _A2& __a2)
3796 {
3797     return shared_ptr<_Tp>::make_shared(__a0, __a1, __a2);
3798 }
3799
3800 template<class _Tp, class _Alloc>
3801 inline _LIBCPP_INLINE_VISIBILITY
3802 shared_ptr<_Tp>
3803 allocate_shared(const _Alloc& __a)
3804 {
3805     return shared_ptr<_Tp>::allocate_shared(__a);
3806 }
3807
3808 template<class _Tp, class _Alloc, class _A0>
3809 inline _LIBCPP_INLINE_VISIBILITY
3810 shared_ptr<_Tp>
3811 allocate_shared(const _Alloc& __a, _A0& __a0)
3812 {
3813     return shared_ptr<_Tp>::allocate_shared(__a, __a0);
3814 }
3815
3816 template<class _Tp, class _Alloc, class _A0, class _A1>
3817 inline _LIBCPP_INLINE_VISIBILITY
3818 shared_ptr<_Tp>
3819 allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1)
3820 {
3821     return shared_ptr<_Tp>::allocate_shared(__a, __a0, __a1);
3822 }
3823
3824 template<class _Tp, class _Alloc, class _A0, class _A1, class _A2>
3825 inline _LIBCPP_INLINE_VISIBILITY
3826 shared_ptr<_Tp>
3827 allocate_shared(const _Alloc& __a, _A0& __a0, _A1& __a1, _A2& __a2)
3828 {
3829     return shared_ptr<_Tp>::allocate_shared(__a, __a0, __a1, __a2);
3830 }
3831
3832 #endif  // _LIBCPP_HAS_NO_VARIADICS
3833
3834 template<class _Tp, class _Up>
3835 inline _LIBCPP_INLINE_VISIBILITY
3836 bool
3837 operator==(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
3838 {
3839     return __x.get() == __y.get();
3840 }
3841
3842 template<class _Tp, class _Up>
3843 inline _LIBCPP_INLINE_VISIBILITY
3844 bool
3845 operator!=(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
3846 {
3847     return !(__x == __y);
3848 }
3849
3850 template<class _Tp, class _Up>
3851 inline _LIBCPP_INLINE_VISIBILITY
3852 bool
3853 operator<(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
3854 {
3855     return __x.get() < __y.get();
3856 }
3857
3858 template<class _Tp>
3859 inline _LIBCPP_INLINE_VISIBILITY
3860 void
3861 swap(shared_ptr<_Tp>& __x, shared_ptr<_Tp>& __y) _NOEXCEPT
3862 {
3863     __x.swap(__y);
3864 }
3865
3866 template<class _Tp, class _Up>
3867 inline _LIBCPP_INLINE_VISIBILITY
3868 shared_ptr<_Tp>
3869 static_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
3870 {
3871     return shared_ptr<_Tp>(__r, static_cast<_Tp*>(__r.get()));
3872 }
3873
3874 template<class _Tp, class _Up>
3875 inline _LIBCPP_INLINE_VISIBILITY
3876 shared_ptr<_Tp>
3877 dynamic_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
3878 {
3879     _Tp* __p = dynamic_cast<_Tp*>(__r.get());
3880     return __p ? shared_ptr<_Tp>(__r, __p) : shared_ptr<_Tp>();
3881 }
3882
3883 template<class _Tp, class _Up>
3884 shared_ptr<_Tp>
3885 const_pointer_cast(const shared_ptr<_Up>& __r) _NOEXCEPT
3886 {
3887     return shared_ptr<_Tp>(__r, const_cast<_Tp*>(__r.get()));
3888 }
3889
3890 #ifndef _LIBCPP_NO_RTTI
3891
3892 template<class _Dp, class _Tp>
3893 inline _LIBCPP_INLINE_VISIBILITY
3894 _Dp*
3895 get_deleter(const shared_ptr<_Tp>& __p) _NOEXCEPT
3896 {
3897     return __p.template __get_deleter<_Dp>();
3898 }
3899
3900 #endif  // _LIBCPP_NO_RTTI
3901
3902 template<class _Tp>
3903 class _LIBCPP_VISIBLE weak_ptr
3904 {
3905 public:
3906     typedef _Tp element_type;
3907 private:
3908     element_type*        __ptr_;
3909     __shared_weak_count* __cntrl_;
3910
3911 public:
3912     weak_ptr() _NOEXCEPT;
3913     template<class _Yp> weak_ptr(shared_ptr<_Yp> const& __r,
3914                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
3915                         _NOEXCEPT;
3916     weak_ptr(weak_ptr const& __r) _NOEXCEPT;
3917     template<class _Yp> weak_ptr(weak_ptr<_Yp> const& __r,
3918                    typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type = 0)
3919                          _NOEXCEPT;
3920
3921     ~weak_ptr();
3922
3923     weak_ptr& operator=(weak_ptr const& __r) _NOEXCEPT;
3924     template<class _Yp> weak_ptr& operator=(weak_ptr<_Yp> const& __r) _NOEXCEPT;
3925     template<class _Yp> weak_ptr& operator=(shared_ptr<_Yp> const& __r) _NOEXCEPT;
3926
3927     void swap(weak_ptr& __r) _NOEXCEPT;
3928     void reset() _NOEXCEPT;
3929
3930     _LIBCPP_INLINE_VISIBILITY
3931     long use_count() const _NOEXCEPT
3932         {return __cntrl_ ? __cntrl_->use_count() : 0;}
3933     _LIBCPP_INLINE_VISIBILITY
3934     bool expired() const _NOEXCEPT
3935         {return __cntrl_ == 0 || __cntrl_->use_count() == 0;}
3936     shared_ptr<_Tp> lock() const _NOEXCEPT;
3937     template<class _Up>
3938         _LIBCPP_INLINE_VISIBILITY
3939         bool owner_before(const shared_ptr<_Up>& __r) const
3940         {return __cntrl_ < __r.__cntrl_;}
3941     template<class _Up>
3942         _LIBCPP_INLINE_VISIBILITY
3943         bool owner_before(const weak_ptr<_Up>& __r) const
3944         {return __cntrl_ < __r.__cntrl_;}
3945
3946     template <class _Up> friend class _LIBCPP_VISIBLE weak_ptr;
3947     template <class _Up> friend class _LIBCPP_VISIBLE shared_ptr;
3948 };
3949
3950 template<class _Tp>
3951 inline _LIBCPP_INLINE_VISIBILITY
3952 weak_ptr<_Tp>::weak_ptr() _NOEXCEPT
3953     : __ptr_(0),
3954       __cntrl_(0)
3955 {
3956 }
3957
3958 template<class _Tp>
3959 inline _LIBCPP_INLINE_VISIBILITY
3960 weak_ptr<_Tp>::weak_ptr(weak_ptr const& __r) _NOEXCEPT
3961     : __ptr_(__r.__ptr_),
3962       __cntrl_(__r.__cntrl_)
3963 {
3964     if (__cntrl_)
3965         __cntrl_->__add_weak();
3966 }
3967
3968 template<class _Tp>
3969 template<class _Yp>
3970 inline _LIBCPP_INLINE_VISIBILITY
3971 weak_ptr<_Tp>::weak_ptr(shared_ptr<_Yp> const& __r,
3972                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
3973                          _NOEXCEPT
3974     : __ptr_(__r.__ptr_),
3975       __cntrl_(__r.__cntrl_)
3976 {
3977     if (__cntrl_)
3978         __cntrl_->__add_weak();
3979 }
3980
3981 template<class _Tp>
3982 template<class _Yp>
3983 inline _LIBCPP_INLINE_VISIBILITY
3984 weak_ptr<_Tp>::weak_ptr(weak_ptr<_Yp> const& __r,
3985                         typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat*>::type)
3986          _NOEXCEPT
3987     : __ptr_(__r.__ptr_),
3988       __cntrl_(__r.__cntrl_)
3989 {
3990     if (__cntrl_)
3991         __cntrl_->__add_weak();
3992 }
3993
3994 template<class _Tp>
3995 weak_ptr<_Tp>::~weak_ptr()
3996 {
3997     if (__cntrl_)
3998         __cntrl_->__release_weak();
3999 }
4000
4001 template<class _Tp>
4002 inline _LIBCPP_INLINE_VISIBILITY
4003 weak_ptr<_Tp>&
4004 weak_ptr<_Tp>::operator=(weak_ptr const& __r) _NOEXCEPT
4005 {
4006     weak_ptr(__r).swap(*this);
4007     return *this;
4008 }
4009
4010 template<class _Tp>
4011 template<class _Yp>
4012 inline _LIBCPP_INLINE_VISIBILITY
4013 weak_ptr<_Tp>&
4014 weak_ptr<_Tp>::operator=(weak_ptr<_Yp> const& __r) _NOEXCEPT
4015 {
4016     weak_ptr(__r).swap(*this);
4017     return *this;
4018 }
4019
4020 template<class _Tp>
4021 template<class _Yp>
4022 inline _LIBCPP_INLINE_VISIBILITY
4023 weak_ptr<_Tp>&
4024 weak_ptr<_Tp>::operator=(shared_ptr<_Yp> const& __r) _NOEXCEPT
4025 {
4026     weak_ptr(__r).swap(*this);
4027     return *this;
4028 }
4029
4030 template<class _Tp>
4031 inline _LIBCPP_INLINE_VISIBILITY
4032 void
4033 weak_ptr<_Tp>::swap(weak_ptr& __r) _NOEXCEPT
4034 {
4035     _VSTD::swap(__ptr_, __r.__ptr_);
4036     _VSTD::swap(__cntrl_, __r.__cntrl_);
4037 }
4038
4039 template<class _Tp>
4040 inline _LIBCPP_INLINE_VISIBILITY
4041 void
4042 swap(weak_ptr<_Tp>& __x, weak_ptr<_Tp>& __y) _NOEXCEPT
4043 {
4044     __x.swap(__y);
4045 }
4046
4047 template<class _Tp>
4048 inline _LIBCPP_INLINE_VISIBILITY
4049 void
4050 weak_ptr<_Tp>::reset() _NOEXCEPT
4051 {
4052     weak_ptr().swap(*this);
4053 }
4054
4055 template<class _Tp>
4056 template<class _Yp>
4057 shared_ptr<_Tp>::shared_ptr(const weak_ptr<_Yp>& __r,
4058                             typename enable_if<is_convertible<_Yp*, _Tp*>::value, __nat>::type)
4059     : __ptr_(__r.__ptr_),
4060       __cntrl_(__r.__cntrl_ ? __r.__cntrl_->lock() : __r.__cntrl_)
4061 {
4062     if (__cntrl_ == 0)
4063 #ifndef _LIBCPP_NO_EXCEPTIONS
4064         throw bad_weak_ptr();
4065 #else
4066         assert(!"bad_weak_ptr");
4067 #endif
4068 }
4069
4070 template<class _Tp>
4071 shared_ptr<_Tp>
4072 weak_ptr<_Tp>::lock() const _NOEXCEPT
4073 {
4074     shared_ptr<_Tp> __r;
4075     __r.__cntrl_ = __cntrl_ ? __cntrl_->lock() : __cntrl_;
4076     if (__r.__cntrl_)
4077         __r.__ptr_ = __ptr_;
4078     return __r;
4079 }
4080
4081 template <class _Tp> struct owner_less;
4082
4083 template <class _Tp>
4084 struct _LIBCPP_VISIBLE owner_less<shared_ptr<_Tp> >
4085     : binary_function<shared_ptr<_Tp>, shared_ptr<_Tp>, bool>
4086 {
4087     typedef bool result_type;
4088     _LIBCPP_INLINE_VISIBILITY
4089     bool operator()(shared_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const
4090         {return __x.owner_before(__y);}
4091     _LIBCPP_INLINE_VISIBILITY
4092     bool operator()(shared_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const
4093         {return __x.owner_before(__y);}
4094     _LIBCPP_INLINE_VISIBILITY
4095     bool operator()(  weak_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const
4096         {return __x.owner_before(__y);}
4097 };
4098
4099 template <class _Tp>
4100 struct _LIBCPP_VISIBLE owner_less<weak_ptr<_Tp> >
4101     : binary_function<weak_ptr<_Tp>, weak_ptr<_Tp>, bool>
4102 {
4103     typedef bool result_type;
4104     _LIBCPP_INLINE_VISIBILITY
4105     bool operator()(  weak_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const
4106         {return __x.owner_before(__y);}
4107     _LIBCPP_INLINE_VISIBILITY
4108     bool operator()(shared_ptr<_Tp> const& __x,   weak_ptr<_Tp> const& __y) const
4109         {return __x.owner_before(__y);}
4110     _LIBCPP_INLINE_VISIBILITY
4111     bool operator()(  weak_ptr<_Tp> const& __x, shared_ptr<_Tp> const& __y) const
4112         {return __x.owner_before(__y);}
4113 };
4114
4115 template<class _Tp>
4116 class _LIBCPP_VISIBLE enable_shared_from_this
4117 {
4118     mutable weak_ptr<_Tp> __weak_this_;
4119 protected:
4120     _LIBCPP_INLINE_VISIBILITY
4121     enable_shared_from_this() _NOEXCEPT {}
4122     _LIBCPP_INLINE_VISIBILITY
4123     enable_shared_from_this(enable_shared_from_this const&) _NOEXCEPT {}
4124     _LIBCPP_INLINE_VISIBILITY
4125     enable_shared_from_this& operator=(enable_shared_from_this const&) _NOEXCEPT
4126         {return *this;}
4127     _LIBCPP_INLINE_VISIBILITY
4128     ~enable_shared_from_this() {}
4129 public:
4130     _LIBCPP_INLINE_VISIBILITY
4131     shared_ptr<_Tp> shared_from_this()
4132         {return shared_ptr<_Tp>(__weak_this_);}
4133     _LIBCPP_INLINE_VISIBILITY
4134     shared_ptr<_Tp const> shared_from_this() const
4135         {return shared_ptr<const _Tp>(__weak_this_);}
4136
4137     template <class _Up> friend class shared_ptr;
4138 };
4139
4140 template <class _Tp>
4141 struct _LIBCPP_VISIBLE hash<shared_ptr<_Tp> >
4142 {
4143     typedef shared_ptr<_Tp>      argument_type;
4144     typedef size_t               result_type;
4145     _LIBCPP_INLINE_VISIBILITY
4146     result_type operator()(const argument_type& __ptr) const _NOEXCEPT
4147     {
4148         return hash<_Tp*>()(__ptr.get());
4149     }
4150 };
4151
4152 template<class _CharT, class _Traits, class _Y>
4153 inline _LIBCPP_INLINE_VISIBILITY
4154 basic_ostream<_CharT, _Traits>&
4155 operator<<(basic_ostream<_CharT, _Traits>& __os, shared_ptr<_Y> const& __p);
4156
4157 //enum class
4158 struct _LIBCPP_VISIBLE pointer_safety
4159 {
4160     enum _
4161     {
4162         relaxed,
4163         preferred,
4164         strict
4165     };
4166
4167     _ __v_;
4168
4169     _LIBCPP_INLINE_VISIBILITY
4170     pointer_safety(_ __v) : __v_(__v) {}
4171     _LIBCPP_INLINE_VISIBILITY
4172     operator int() const {return __v_;}
4173 };
4174
4175 void declare_reachable(void* __p);
4176 void declare_no_pointers(char* __p, size_t __n);
4177 void undeclare_no_pointers(char* __p, size_t __n);
4178 pointer_safety get_pointer_safety() _NOEXCEPT;
4179 void* __undeclare_reachable(void* __p);
4180
4181 template <class _Tp>
4182 inline _LIBCPP_INLINE_VISIBILITY
4183 _Tp*
4184 undeclare_reachable(_Tp* __p)
4185 {
4186     return static_cast<_Tp*>(__undeclare_reachable(__p));
4187 }
4188
4189 void* align(size_t __align, size_t __sz, void*& __ptr, size_t& __space);
4190
4191 _LIBCPP_END_NAMESPACE_STD
4192
4193 #endif  // _LIBCPP_MEMORY