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