contrib/libc++/include/memory

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