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