LCOM1920-T02G10

// -*- C++ -*-

//===-------------------------- memory ------------------------------------===//

//

//                     The LLVM Compiler Infrastructure

//

// This file is dual licensed under the MIT and the University of Illinois Open

// Source Licenses. See LICENSE.TXT for details.

//

//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_MEMORY

#define _LIBCPP_MEMORY

/*

    memory synopsis

namespace std

{

struct allocator_arg_t { };

constexpr allocator_arg_t allocator_arg = allocator_arg_t();

template <class T, class Alloc> struct uses_allocator;

template <class Ptr>

struct pointer_traits

{

    typedef Ptr pointer;

    typedef <details> element_type;

    typedef <details> difference_type;

    template <class U> using rebind = <details>;

    static pointer pointer_to(<details>);

};

template <class T>

struct pointer_traits<T*>

{

    typedef T* pointer;

    typedef T element_type;

    typedef ptrdiff_t difference_type;

    template <class U> using rebind = U*;

    static pointer pointer_to(<details>) noexcept;

};

template <class Alloc>

struct allocator_traits

{

    typedef Alloc                        allocator_type;

    typedef typename allocator_type::value_type

                                         value_type;

    typedef Alloc::pointer | value_type* pointer;

    typedef Alloc::const_pointer

          | pointer_traits<pointer>::rebind<const value_type>

                                         const_pointer;

    typedef Alloc::void_pointer

          | pointer_traits<pointer>::rebind<void>

                                         void_pointer;

    typedef Alloc::const_void_pointer

          | pointer_traits<pointer>::rebind<const void>

                                         const_void_pointer;

    typedef Alloc::difference_type

          | pointer_traits<pointer>::difference_type

                                         difference_type;

    typedef Alloc::size_type

          | make_unsigned<difference_type>::type

                                         size_type;

    typedef Alloc::propagate_on_container_copy_assignment

          | false_type                   propagate_on_container_copy_assignment;

    typedef Alloc::propagate_on_container_move_assignment

          | false_type                   propagate_on_container_move_assignment;

    typedef Alloc::propagate_on_container_swap

          | false_type                   propagate_on_container_swap;

    typedef Alloc::is_always_equal

          | is_empty                     is_always_equal;

    template <class T> using rebind_alloc  = Alloc::rebind<U>::other | Alloc<T, Args...>;

    template <class T> using rebind_traits = allocator_traits<rebind_alloc<T>>;

    static pointer allocate(allocator_type& a, size_type n);

    static pointer allocate(allocator_type& a, size_type n, const_void_pointer hint);

    static void deallocate(allocator_type& a, pointer p, size_type n) noexcept;

    template <class T, class... Args>

        static void construct(allocator_type& a, T* p, Args&&... args);

    template <class T>

        static void destroy(allocator_type& a, T* p);

    static size_type max_size(const allocator_type& a); // noexcept in C++14

    static allocator_type

        select_on_container_copy_construction(const allocator_type& a);

};

template <>

class allocator<void>

{

public:

    typedef void*                                 pointer;

    typedef const void*                           const_pointer;

    typedef void                                  value_type;

    template <class _Up> struct rebind {typedef allocator<_Up> other;};

};

template <class T>

class allocator

{

public:

    typedef size_t                                size_type;

    typedef ptrdiff_t                             difference_type;

    typedef T*                                    pointer;

    typedef const T*                              const_pointer;

    typedef typename add_lvalue_reference<T>::type       reference;

    typedef typename add_lvalue_reference<const T>::type const_reference;

    typedef T                                     value_type;

    template <class U> struct rebind {typedef allocator<U> other;};

    allocator() noexcept;

    allocator(const allocator&) noexcept;

    template <class U> allocator(const allocator<U>&) noexcept;

    ~allocator();

    pointer address(reference x) const noexcept;

    const_pointer address(const_reference x) const noexcept;

    pointer allocate(size_type, allocator<void>::const_pointer hint = 0);

    void deallocate(pointer p, size_type n) noexcept;

    size_type max_size() const noexcept;

    template<class U, class... Args>

        void construct(U* p, Args&&... args);

    template <class U>

        void destroy(U* p);

};

template <class T, class U>

bool operator==(const allocator<T>&, const allocator<U>&) noexcept;

template <class T, class U>

bool operator!=(const allocator<T>&, const allocator<U>&) noexcept;

template <class OutputIterator, class T>

class raw_storage_iterator

    : public iterator<output_iterator_tag,

                      T,                               // purposefully not C++03

                      ptrdiff_t,                       // purposefully not C++03

                      T*,                              // purposefully not C++03

                      raw_storage_iterator&>           // purposefully not C++03

{

public:

    explicit raw_storage_iterator(OutputIterator x);

    raw_storage_iterator& operator*();

    raw_storage_iterator& operator=(const T& element);

    raw_storage_iterator& operator++();

    raw_storage_iterator  operator++(int);

};

template <class T> pair<T*,ptrdiff_t> get_temporary_buffer(ptrdiff_t n) noexcept;

template <class T> void               return_temporary_buffer(T* p) noexcept;

template <class T> T* addressof(T& r) noexcept;

template <class InputIterator, class ForwardIterator>

ForwardIterator

uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);

template <class InputIterator, class Size, class ForwardIterator>

ForwardIterator

uninitialized_copy_n(InputIterator first, Size n, ForwardIterator result);

template <class ForwardIterator, class T>

void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

template <class ForwardIterator, class Size, class T>

ForwardIterator

uninitialized_fill_n(ForwardIterator first, Size n, const T& x);

template <class Y> struct auto_ptr_ref {};

template<class X>

class auto_ptr

{

public:

    typedef X element_type;

    explicit auto_ptr(X* p =0) throw();

    auto_ptr(auto_ptr&) throw();

    template<class Y> auto_ptr(auto_ptr<Y>&) throw();

    auto_ptr& operator=(auto_ptr&) throw();

    template<class Y> auto_ptr& operator=(auto_ptr<Y>&) throw();

    auto_ptr& operator=(auto_ptr_ref<X> r) throw();

    ~auto_ptr() throw();

    typename add_lvalue_reference<X>::type operator*() const throw();

    X* operator->() const throw();

    X* get() const throw();

    X* release() throw();

    void reset(X* p =0) throw();

    auto_ptr(auto_ptr_ref<X>) throw();

    template<class Y> operator auto_ptr_ref<Y>() throw();

    template<class Y> operator auto_ptr<Y>() throw();

};

template <class T>

struct default_delete

{

    constexpr default_delete() noexcept = default;

    template <class U> default_delete(const default_delete<U>&) noexcept;

    void operator()(T*) const noexcept;

};

template <class T>

struct default_delete<T[]>

{

    constexpr default_delete() noexcept = default;

    void operator()(T*) const noexcept;

    template <class U> void operator()(U*) const = delete;

};

template <class T, class D = default_delete<T>>

class unique_ptr

{

public:

    typedef see below pointer;

    typedef T element_type;

    typedef D deleter_type;

    // constructors

    constexpr unique_ptr() noexcept;

    explicit unique_ptr(pointer p) noexcept;

    unique_ptr(pointer p, see below d1) noexcept;

    unique_ptr(pointer p, see below d2) noexcept;

    unique_ptr(unique_ptr&& u) noexcept;

    unique_ptr(nullptr_t) noexcept : unique_ptr() { }

    template <class U, class E>

        unique_ptr(unique_ptr<U, E>&& u) noexcept;

    template <class U>

        unique_ptr(auto_ptr<U>&& u) noexcept;

    // destructor

    ~unique_ptr();

    // assignment

    unique_ptr& operator=(unique_ptr&& u) noexcept;

    template <class U, class E> unique_ptr& operator=(unique_ptr<U, E>&& u) noexcept;

    unique_ptr& operator=(nullptr_t) noexcept;

    // observers

    typename add_lvalue_reference<T>::type operator*() const;

    pointer operator->() const noexcept;

    pointer get() const noexcept;

    deleter_type& get_deleter() noexcept;

    const deleter_type& get_deleter() const noexcept;

    explicit operator bool() const noexcept;

    // modifiers

    pointer release() noexcept;

    void reset(pointer p = pointer()) noexcept;

    void swap(unique_ptr& u) noexcept;

};

template <class T, class D>

class unique_ptr<T[], D>

{

public:

    typedef implementation-defined pointer;

    typedef T element_type;

    typedef D deleter_type;

    // constructors

    constexpr unique_ptr() noexcept;

    explicit unique_ptr(pointer p) noexcept;

    unique_ptr(pointer p, see below d) noexcept;

    unique_ptr(pointer p, see below d) noexcept;

    unique_ptr(unique_ptr&& u) noexcept;

    unique_ptr(nullptr_t) noexcept : unique_ptr() { }

    // destructor

    ~unique_ptr();

    // assignment

    unique_ptr& operator=(unique_ptr&& u) noexcept;

    unique_ptr& operator=(nullptr_t) noexcept;

    // observers

    T& operator[](size_t i) const;

    pointer get() const noexcept;

    deleter_type& get_deleter() noexcept;

    const deleter_type& get_deleter() const noexcept;

    explicit operator bool() const noexcept;

    // modifiers

    pointer release() noexcept;

    void reset(pointer p = pointer()) noexcept;

    void reset(nullptr_t) noexcept;

    template <class U> void reset(U) = delete;

    void swap(unique_ptr& u) noexcept;

};

template <class T, class D>

    void swap(unique_ptr<T, D>& x, unique_ptr<T, D>& y) noexcept;

template <class T1, class D1, class T2, class D2>

    bool operator==(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);

template <class T1, class D1, class T2, class D2>

    bool operator!=(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);

template <class T1, class D1, class T2, class D2>

    bool operator<(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);

template <class T1, class D1, class T2, class D2>

    bool operator<=(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);

template <class T1, class D1, class T2, class D2>

    bool operator>(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);

template <class T1, class D1, class T2, class D2>

    bool operator>=(const unique_ptr<T1, D1>& x, const unique_ptr<T2, D2>& y);

template <class T, class D>

    bool operator==(const unique_ptr<T, D>& x, nullptr_t) noexcept;

template <class T, class D>

    bool operator==(nullptr_t, const unique_ptr<T, D>& y) noexcept;

template <class T, class D>

    bool operator!=(const unique_ptr<T, D>& x, nullptr_t) noexcept;

template <class T, class D>

    bool operator!=(nullptr_t, const unique_ptr<T, D>& y) noexcept;

template <class T, class D>

    bool operator<(const unique_ptr<T, D>& x, nullptr_t);

template <class T, class D>

    bool operator<(nullptr_t, const unique_ptr<T, D>& y);

template <class T, class D>

    bool operator<=(const unique_ptr<T, D>& x, nullptr_t);

template <class T, class D>

    bool operator<=(nullptr_t, const unique_ptr<T, D>& y);

template <class T, class D>

    bool operator>(const unique_ptr<T, D>& x, nullptr_t);

template <class T, class D>

    bool operator>(nullptr_t, const unique_ptr<T, D>& y);

template <class T, class D>

    bool operator>=(const unique_ptr<T, D>& x, nullptr_t);

template <class T, class D>

    bool operator>=(nullptr_t, const unique_ptr<T, D>& y);

class bad_weak_ptr

    : public std::exception

{

    bad_weak_ptr() noexcept;

};

template<class T, class... Args> unique_ptr<T> make_unique(Args&&... args);     // C++14

template<class T>                unique_ptr<T> make_unique(size_t n);           // C++14

template<class T, class... Args> unspecified   make_unique(Args&&...) = delete; // C++14, T == U[N]

template<class T>

class shared_ptr

{

public:

    typedef T element_type;

    // constructors:

    constexpr shared_ptr() noexcept;

    template<class Y> explicit shared_ptr(Y* p);

    template<class Y, class D> shared_ptr(Y* p, D d);

    template<class Y, class D, class A> shared_ptr(Y* p, D d, A a);

    template <class D> shared_ptr(nullptr_t p, D d);

    template <class D, class A> shared_ptr(nullptr_t p, D d, A a);

    template<class Y> shared_ptr(const shared_ptr<Y>& r, T *p) noexcept;

    shared_ptr(const shared_ptr& r) noexcept;

    template<class Y> shared_ptr(const shared_ptr<Y>& r) noexcept;

    shared_ptr(shared_ptr&& r) noexcept;

    template<class Y> shared_ptr(shared_ptr<Y>&& r) noexcept;

    template<class Y> explicit shared_ptr(const weak_ptr<Y>& r);

    template<class Y> shared_ptr(auto_ptr<Y>&& r);

    template <class Y, class D> shared_ptr(unique_ptr<Y, D>&& r);

    shared_ptr(nullptr_t) : shared_ptr() { }

    // destructor:

    ~shared_ptr();

    // assignment:

    shared_ptr& operator=(const shared_ptr& r) noexcept;

    template<class Y> shared_ptr& operator=(const shared_ptr<Y>& r) noexcept;

    shared_ptr& operator=(shared_ptr&& r) noexcept;

    template<class Y> shared_ptr& operator=(shared_ptr<Y>&& r);

    template<class Y> shared_ptr& operator=(auto_ptr<Y>&& r);

    template <class Y, class D> shared_ptr& operator=(unique_ptr<Y, D>&& r);

    // modifiers:

    void swap(shared_ptr& r) noexcept;

    void reset() noexcept;

    template<class Y> void reset(Y* p);

    template<class Y, class D> void reset(Y* p, D d);

    template<class Y, class D, class A> void reset(Y* p, D d, A a);

    // observers:

    T* get() const noexcept;

    T& operator*() const noexcept;

    T* operator->() const noexcept;

    long use_count() const noexcept;

    bool unique() const noexcept;

    explicit operator bool() const noexcept;

    template<class U> bool owner_before(shared_ptr<U> const& b) const;

    template<class U> bool owner_before(weak_ptr<U> const& b) const;

};

// shared_ptr comparisons:

template<class T, class U>

    bool operator==(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;

template<class T, class U>

    bool operator!=(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;

template<class T, class U>

    bool operator<(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;

template<class T, class U>

    bool operator>(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;

template<class T, class U>

    bool operator<=(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;

template<class T, class U>

    bool operator>=(shared_ptr<T> const& a, shared_ptr<U> const& b) noexcept;

template <class T>

    bool operator==(const shared_ptr<T>& x, nullptr_t) noexcept;

template <class T>

    bool operator==(nullptr_t, const shared_ptr<T>& y) noexcept;

template <class T>

    bool operator!=(const shared_ptr<T>& x, nullptr_t) noexcept;

template <class T>

    bool operator!=(nullptr_t, const shared_ptr<T>& y) noexcept;

template <class T>

    bool operator<(const shared_ptr<T>& x, nullptr_t) noexcept;

template <class T>

bool operator<(nullptr_t, const shared_ptr<T>& y) noexcept;

template <class T>

    bool operator<=(const shared_ptr<T>& x, nullptr_t) noexcept;

template <class T>

    bool operator<=(nullptr_t, const shared_ptr<T>& y) noexcept;

template <class T>

    bool operator>(const shared_ptr<T>& x, nullptr_t) noexcept;

template <class T>

    bool operator>(nullptr_t, const shared_ptr<T>& y) noexcept;

template <class T>

    bool operator>=(const shared_ptr<T>& x, nullptr_t) noexcept;

template <class T>

    bool operator>=(nullptr_t, const shared_ptr<T>& y) noexcept;

// shared_ptr specialized algorithms:

template<class T> void swap(shared_ptr<T>& a, shared_ptr<T>& b) noexcept;

// shared_ptr casts:

template<class T, class U>

    shared_ptr<T> static_pointer_cast(shared_ptr<U> const& r) noexcept;

template<class T, class U>

    shared_ptr<T> dynamic_pointer_cast(shared_ptr<U> const& r) noexcept;

template<class T, class U>

    shared_ptr<T> const_pointer_cast(shared_ptr<U> const& r) noexcept;

// shared_ptr I/O:

template<class E, class T, class Y>

    basic_ostream<E, T>& operator<< (basic_ostream<E, T>& os, shared_ptr<Y> const& p);

// shared_ptr get_deleter:

template<class D, class T> D* get_deleter(shared_ptr<T> const& p) noexcept;

template<class T, class... Args>

    shared_ptr<T> make_shared(Args&&... args);

template<class T, class A, class... Args>

    shared_ptr<T> allocate_shared(const A& a, Args&&... args);

template<class T>

class weak_ptr

{

public:

    typedef T element_type;

    // constructors

    constexpr weak_ptr() noexcept;

    template<class Y> weak_ptr(shared_ptr<Y> const& r) noexcept;

    weak_ptr(weak_ptr const& r) noexcept;

    template<class Y> weak_ptr(weak_ptr<Y> const& r) noexcept;

    weak_ptr(weak_ptr&& r) noexcept;                      // C++14

    template<class Y> weak_ptr(weak_ptr<Y>&& r) noexcept; // C++14

    // destructor

    ~weak_ptr();

    // assignment

    weak_ptr& operator=(weak_ptr const& r) noexcept;

    template<class Y> weak_ptr& operator=(weak_ptr<Y> const& r) noexcept;

    template<class Y> weak_ptr& operator=(shared_ptr<Y> const& r) noexcept;

    weak_ptr& operator=(weak_ptr&& r) noexcept;                      // C++14

    template<class Y> weak_ptr& operator=(weak_ptr<Y>&& r) noexcept; // C++14

    // modifiers

    void swap(weak_ptr& r) noexcept;

    void reset() noexcept;

    // observers

    long use_count() const noexcept;

    bool expired() const noexcept;

    shared_ptr<T> lock() const noexcept;

    template<class U> bool owner_before(shared_ptr<U> const& b) const;

    template<class U> bool owner_before(weak_ptr<U> const& b) const;

};

// weak_ptr specialized algorithms:

template<class T> void swap(weak_ptr<T>& a, weak_ptr<T>& b) noexcept;

// class owner_less:

template<class T> struct owner_less;

template<class T>

struct owner_less<shared_ptr<T>>

    : binary_function<shared_ptr<T>, shared_ptr<T>, bool>

{

    typedef bool result_type;

    bool operator()(shared_ptr<T> const&, shared_ptr<T> const&) const;

    bool operator()(shared_ptr<T> const&, weak_ptr<T> const&) const;

    bool operator()(weak_ptr<T> const&, shared_ptr<T> const&) const;

};

template<class T>

struct owner_less<weak_ptr<T>>

    : binary_function<weak_ptr<T>, weak_ptr<T>, bool>

{

    typedef bool result_type;

    bool operator()(weak_ptr<T> const&, weak_ptr<T> const&) const;

    bool operator()(shared_ptr<T> const&, weak_ptr<T> const&) const;

    bool operator()(weak_ptr<T> const&, shared_ptr<T> const&) const;

};

template<class T>

class enable_shared_from_this

{

protected:

    constexpr enable_shared_from_this() noexcept;

    enable_shared_from_this(enable_shared_from_this const&) noexcept;

    enable_shared_from_this& operator=(enable_shared_from_this const&) noexcept;

    ~enable_shared_from_this();

public:

    shared_ptr<T> shared_from_this();

    shared_ptr<T const> shared_from_this() const;

};

template<class T>

    bool atomic_is_lock_free(const shared_ptr<T>* p);

template<class T>

    shared_ptr<T> atomic_load(const shared_ptr<T>* p);

template<class T>

    shared_ptr<T> atomic_load_explicit(const shared_ptr<T>* p, memory_order mo);

template<class T>

    void atomic_store(shared_ptr<T>* p, shared_ptr<T> r);

template<class T>

    void atomic_store_explicit(shared_ptr<T>* p, shared_ptr<T> r, memory_order mo);

template<class T>

    shared_ptr<T> atomic_exchange(shared_ptr<T>* p, shared_ptr<T> r);

template<class T>

    shared_ptr<T>

    atomic_exchange_explicit(shared_ptr<T>* p, shared_ptr<T> r, memory_order mo);

template<class T>

    bool

    atomic_compare_exchange_weak(shared_ptr<T>* p, shared_ptr<T>* v, shared_ptr<T> w);

template<class T>

    bool

    atomic_compare_exchange_strong( shared_ptr<T>* p, shared_ptr<T>* v, shared_ptr<T> w);

template<class T>

    bool

    atomic_compare_exchange_weak_explicit(shared_ptr<T>* p, shared_ptr<T>* v,

                                          shared_ptr<T> w, memory_order success,

                                          memory_order failure);

template<class T>

    bool

    atomic_compare_exchange_strong_explicit(shared_ptr<T>* p, shared_ptr<T>* v,

                                            shared_ptr<T> w, memory_order success,

                                            memory_order failure);

// Hash support

template <class T> struct hash;

template <class T, class D> struct hash<unique_ptr<T, D> >;

template <class T> struct hash<shared_ptr<T> >;

// Pointer safety

enum class pointer_safety { relaxed, preferred, strict };

void declare_reachable(void *p);

template <class T> T *undeclare_reachable(T *p);

void declare_no_pointers(char *p, size_t n);

void undeclare_no_pointers(char *p, size_t n);

pointer_safety get_pointer_safety() noexcept;

void* align(size_t alignment, size_t size, void*& ptr, size_t& space);

}  // std

*/

#include <__config>

#include <type_traits>

#include <typeinfo>

#include <cstddef>

#include <cstdint>

#include <new>

#include <utility>

#include <limits>

#include <iterator>

#include <__functional_base>

#include <iosfwd>

#include <tuple>

#include <cstring>

#if defined(_LIBCPP_NO_EXCEPTIONS)

    #include <cassert>

#endif

#if !defined(_LIBCPP_HAS_NO_ATOMIC_HEADER)

#  include <atomic>

#endif

#include <__undef_min_max>

#include <__undef___deallocate>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

#pragma GCC system_header

#endif

_LIBCPP_BEGIN_NAMESPACE_STD

template <class _ValueType>

inline _LIBCPP_ALWAYS_INLINE

_ValueType __libcpp_relaxed_load(_ValueType const* __value) {

#if !defined(_LIBCPP_HAS_NO_THREADS) && \

    defined(__ATOMIC_RELAXED) &&        \

    (__has_builtin(__atomic_load_n) || _GNUC_VER >= 407)

    return __atomic_load_n(__value, __ATOMIC_RELAXED);

#else

    return *__value;

#endif

}

// addressof moved to <__functional_base>

template <class _Tp> class allocator;

template <>

class _LIBCPP_TYPE_VIS_ONLY allocator<void>

{

public:

    typedef void*             pointer;

    typedef const void*       const_pointer;

    typedef void              value_type;

    template <class _Up> struct rebind {typedef allocator<_Up> other;};

};

template <>

class _LIBCPP_TYPE_VIS_ONLY allocator<const void>

{

public:

    typedef const void*       pointer;

    typedef const void*       const_pointer;

    typedef const void        value_type;

    template <class _Up> struct rebind {typedef allocator<_Up> other;};

};

// pointer_traits

template <class _Tp>

struct __has_element_type

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::element_type* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Ptr, bool = __has_element_type<_Ptr>::value>

struct __pointer_traits_element_type;

template <class _Ptr>

struct __pointer_traits_element_type<_Ptr, true>

{

    typedef typename _Ptr::element_type type;

};

#ifndef _LIBCPP_HAS_NO_VARIADICS

template <template <class, class...> class _Sp, class _Tp, class ..._Args>

struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, true>

{

    typedef typename _Sp<_Tp, _Args...>::element_type type;

};

template <template <class, class...> class _Sp, class _Tp, class ..._Args>

struct __pointer_traits_element_type<_Sp<_Tp, _Args...>, false>

{

    typedef _Tp type;

};

#else  // _LIBCPP_HAS_NO_VARIADICS

template <template <class> class _Sp, class _Tp>

struct __pointer_traits_element_type<_Sp<_Tp>, true>

{

    typedef typename _Sp<_Tp>::element_type type;

};

template <template <class> class _Sp, class _Tp>

struct __pointer_traits_element_type<_Sp<_Tp>, false>

{

    typedef _Tp type;

};

template <template <class, class> class _Sp, class _Tp, class _A0>

struct __pointer_traits_element_type<_Sp<_Tp, _A0>, true>

{

    typedef typename _Sp<_Tp, _A0>::element_type type;

};

template <template <class, class> class _Sp, class _Tp, class _A0>

struct __pointer_traits_element_type<_Sp<_Tp, _A0>, false>

{

    typedef _Tp type;

};

template <template <class, class, class> class _Sp, class _Tp, class _A0, class _A1>

struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1>, true>

{

    typedef typename _Sp<_Tp, _A0, _A1>::element_type type;

};

template <template <class, class, class> class _Sp, class _Tp, class _A0, class _A1>

struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1>, false>

{

    typedef _Tp type;

};

template <template <class, class, class, class> class _Sp, class _Tp, class _A0,

                                                           class _A1, class _A2>

struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1, _A2>, true>

{

    typedef typename _Sp<_Tp, _A0, _A1, _A2>::element_type type;

};

template <template <class, class, class, class> class _Sp, class _Tp, class _A0,

                                                           class _A1, class _A2>

struct __pointer_traits_element_type<_Sp<_Tp, _A0, _A1, _A2>, false>

{

    typedef _Tp type;

};

#endif  // _LIBCPP_HAS_NO_VARIADICS

template <class _Tp>

struct __has_difference_type

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::difference_type* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Ptr, bool = __has_difference_type<_Ptr>::value>

struct __pointer_traits_difference_type

{

    typedef ptrdiff_t type;

};

template <class _Ptr>

struct __pointer_traits_difference_type<_Ptr, true>

{

    typedef typename _Ptr::difference_type type;

};

template <class _Tp, class _Up>

struct __has_rebind

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Xp> static __two __test(...);

    template <class _Xp> static char __test(typename _Xp::template rebind<_Up>* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Tp, class _Up, bool = __has_rebind<_Tp, _Up>::value>

struct __pointer_traits_rebind

{

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    typedef typename _Tp::template rebind<_Up> type;

#else

    typedef typename _Tp::template rebind<_Up>::other type;

#endif

};

#ifndef _LIBCPP_HAS_NO_VARIADICS

template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, true>

{

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    typedef typename _Sp<_Tp, _Args...>::template rebind<_Up> type;

#else

    typedef typename _Sp<_Tp, _Args...>::template rebind<_Up>::other type;

#endif

};

template <template <class, class...> class _Sp, class _Tp, class ..._Args, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp, _Args...>, _Up, false>

{

    typedef _Sp<_Up, _Args...> type;

};

#else  // _LIBCPP_HAS_NO_VARIADICS

template <template <class> class _Sp, class _Tp, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp>, _Up, true>

{

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    typedef typename _Sp<_Tp>::template rebind<_Up> type;

#else

    typedef typename _Sp<_Tp>::template rebind<_Up>::other type;

#endif

};

template <template <class> class _Sp, class _Tp, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp>, _Up, false>

{

    typedef _Sp<_Up> type;

};

template <template <class, class> class _Sp, class _Tp, class _A0, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp, _A0>, _Up, true>

{

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    typedef typename _Sp<_Tp, _A0>::template rebind<_Up> type;

#else

    typedef typename _Sp<_Tp, _A0>::template rebind<_Up>::other type;

#endif

};

template <template <class, class> class _Sp, class _Tp, class _A0, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp, _A0>, _Up, false>

{

    typedef _Sp<_Up, _A0> type;

};

template <template <class, class, class> class _Sp, class _Tp, class _A0,

                                         class _A1, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1>, _Up, true>

{

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    typedef typename _Sp<_Tp, _A0, _A1>::template rebind<_Up> type;

#else

    typedef typename _Sp<_Tp, _A0, _A1>::template rebind<_Up>::other type;

#endif

};

template <template <class, class, class> class _Sp, class _Tp, class _A0,

                                         class _A1, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1>, _Up, false>

{

    typedef _Sp<_Up, _A0, _A1> type;

};

template <template <class, class, class, class> class _Sp, class _Tp, class _A0,

                                                class _A1, class _A2, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1, _A2>, _Up, true>

{

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    typedef typename _Sp<_Tp, _A0, _A1, _A2>::template rebind<_Up> type;

#else

    typedef typename _Sp<_Tp, _A0, _A1, _A2>::template rebind<_Up>::other type;

#endif

};

template <template <class, class, class, class> class _Sp, class _Tp, class _A0,

                                                class _A1, class _A2, class _Up>

struct __pointer_traits_rebind<_Sp<_Tp, _A0, _A1, _A2>, _Up, false>

{

    typedef _Sp<_Up, _A0, _A1, _A2> type;

};

#endif  // _LIBCPP_HAS_NO_VARIADICS

template <class _Ptr>

struct _LIBCPP_TYPE_VIS_ONLY pointer_traits

{

    typedef _Ptr                                                     pointer;

    typedef typename __pointer_traits_element_type<pointer>::type    element_type;

    typedef typename __pointer_traits_difference_type<pointer>::type difference_type;

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    template <class _Up> using rebind = typename __pointer_traits_rebind<pointer, _Up>::type;

#else

    template <class _Up> struct rebind

        {typedef typename __pointer_traits_rebind<pointer, _Up>::type other;};

#endif  // _LIBCPP_HAS_NO_TEMPLATE_ALIASES

private:

    struct __nat {};

public:

    _LIBCPP_INLINE_VISIBILITY

    static pointer pointer_to(typename conditional<is_void<element_type>::value,

                                           __nat, element_type>::type& __r)

        {return pointer::pointer_to(__r);}

};

template <class _Tp>

struct _LIBCPP_TYPE_VIS_ONLY pointer_traits<_Tp*>

{

    typedef _Tp*      pointer;

    typedef _Tp       element_type;

    typedef ptrdiff_t difference_type;

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    template <class _Up> using rebind = _Up*;

#else

    template <class _Up> struct rebind {typedef _Up* other;};

#endif

private:

    struct __nat {};

public:

    _LIBCPP_INLINE_VISIBILITY

    static pointer pointer_to(typename conditional<is_void<element_type>::value,

                                      __nat, element_type>::type& __r) _NOEXCEPT

        {return _VSTD::addressof(__r);}

};

// allocator_traits

namespace __has_pointer_type_imp

{

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::pointer* = 0);

}

template <class _Tp>

struct __has_pointer_type

    : public integral_constant<bool, sizeof(__has_pointer_type_imp::__test<_Tp>(0)) == 1>

{

};

namespace __pointer_type_imp

{

template <class _Tp, class _Dp, bool = __has_pointer_type<_Dp>::value>

struct __pointer_type

{

    typedef typename _Dp::pointer type;

};

template <class _Tp, class _Dp>

struct __pointer_type<_Tp, _Dp, false>

{

    typedef _Tp* type;

};

}  // __pointer_type_imp

template <class _Tp, class _Dp>

struct __pointer_type

{

    typedef typename __pointer_type_imp::__pointer_type<_Tp, typename remove_reference<_Dp>::type>::type type;

};

template <class _Tp>

struct __has_const_pointer

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::const_pointer* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Tp, class _Ptr, class _Alloc, bool = __has_const_pointer<_Alloc>::value>

struct __const_pointer

{

    typedef typename _Alloc::const_pointer type;

};

template <class _Tp, class _Ptr, class _Alloc>

struct __const_pointer<_Tp, _Ptr, _Alloc, false>

{

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    typedef typename pointer_traits<_Ptr>::template rebind<const _Tp> type;

#else

    typedef typename pointer_traits<_Ptr>::template rebind<const _Tp>::other type;

#endif

};

template <class _Tp>

struct __has_void_pointer

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::void_pointer* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Ptr, class _Alloc, bool = __has_void_pointer<_Alloc>::value>

struct __void_pointer

{

    typedef typename _Alloc::void_pointer type;

};

template <class _Ptr, class _Alloc>

struct __void_pointer<_Ptr, _Alloc, false>

{

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    typedef typename pointer_traits<_Ptr>::template rebind<void> type;

#else

    typedef typename pointer_traits<_Ptr>::template rebind<void>::other type;

#endif

};

template <class _Tp>

struct __has_const_void_pointer

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::const_void_pointer* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Ptr, class _Alloc, bool = __has_const_void_pointer<_Alloc>::value>

struct __const_void_pointer

{

    typedef typename _Alloc::const_void_pointer type;

};

template <class _Ptr, class _Alloc>

struct __const_void_pointer<_Ptr, _Alloc, false>

{

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    typedef typename pointer_traits<_Ptr>::template rebind<const void> type;

#else

    typedef typename pointer_traits<_Ptr>::template rebind<const void>::other type;

#endif

};

template <class _Tp>

inline _LIBCPP_INLINE_VISIBILITY

_Tp*

__to_raw_pointer(_Tp* __p) _NOEXCEPT

{

    return __p;

}

template <class _Pointer>

inline _LIBCPP_INLINE_VISIBILITY

typename pointer_traits<_Pointer>::element_type*

__to_raw_pointer(_Pointer __p) _NOEXCEPT

{

    return _VSTD::__to_raw_pointer(__p.operator->());

}

template <class _Tp>

struct __has_size_type

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::size_type* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Alloc, class _DiffType, bool = __has_size_type<_Alloc>::value>

struct __size_type

{

    typedef typename make_unsigned<_DiffType>::type type;

};

template <class _Alloc, class _DiffType>

struct __size_type<_Alloc, _DiffType, true>

{

    typedef typename _Alloc::size_type type;

};

template <class _Tp>

struct __has_propagate_on_container_copy_assignment

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::propagate_on_container_copy_assignment* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Alloc, bool = __has_propagate_on_container_copy_assignment<_Alloc>::value>

struct __propagate_on_container_copy_assignment

{

    typedef false_type type;

};

template <class _Alloc>

struct __propagate_on_container_copy_assignment<_Alloc, true>

{

    typedef typename _Alloc::propagate_on_container_copy_assignment type;

};

template <class _Tp>

struct __has_propagate_on_container_move_assignment

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::propagate_on_container_move_assignment* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Alloc, bool = __has_propagate_on_container_move_assignment<_Alloc>::value>

struct __propagate_on_container_move_assignment

{

    typedef false_type type;

};

template <class _Alloc>

struct __propagate_on_container_move_assignment<_Alloc, true>

{

    typedef typename _Alloc::propagate_on_container_move_assignment type;

};

template <class _Tp>

struct __has_propagate_on_container_swap

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::propagate_on_container_swap* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Alloc, bool = __has_propagate_on_container_swap<_Alloc>::value>

struct __propagate_on_container_swap

{

    typedef false_type type;

};

template <class _Alloc>

struct __propagate_on_container_swap<_Alloc, true>

{

    typedef typename _Alloc::propagate_on_container_swap type;

};

template <class _Tp>

struct __has_is_always_equal

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Up> static __two __test(...);

    template <class _Up> static char __test(typename _Up::is_always_equal* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Alloc, bool = __has_is_always_equal<_Alloc>::value>

struct __is_always_equal

{

    typedef typename _VSTD::is_empty<_Alloc>::type type;

};

template <class _Alloc>

struct __is_always_equal<_Alloc, true>

{

    typedef typename _Alloc::is_always_equal type;

};

template <class _Tp, class _Up, bool = __has_rebind<_Tp, _Up>::value>

struct __has_rebind_other

{

private:

    struct __two {char __lx; char __lxx;};

    template <class _Xp> static __two __test(...);

    template <class _Xp> static char __test(typename _Xp::template rebind<_Up>::other* = 0);

public:

    static const bool value = sizeof(__test<_Tp>(0)) == 1;

};

template <class _Tp, class _Up>

struct __has_rebind_other<_Tp, _Up, false>

{

    static const bool value = false;

};

template <class _Tp, class _Up, bool = __has_rebind_other<_Tp, _Up>::value>

struct __allocator_traits_rebind

{

    typedef typename _Tp::template rebind<_Up>::other type;

};

#ifndef _LIBCPP_HAS_NO_VARIADICS

template <template <class, class...> class _Alloc, class _Tp, class ..._Args, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp, _Args...>, _Up, true>

{

    typedef typename _Alloc<_Tp, _Args...>::template rebind<_Up>::other type;

};

template <template <class, class...> class _Alloc, class _Tp, class ..._Args, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp, _Args...>, _Up, false>

{

    typedef _Alloc<_Up, _Args...> type;

};

#else  // _LIBCPP_HAS_NO_VARIADICS

template <template <class> class _Alloc, class _Tp, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp>, _Up, true>

{

    typedef typename _Alloc<_Tp>::template rebind<_Up>::other type;

};

template <template <class> class _Alloc, class _Tp, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp>, _Up, false>

{

    typedef _Alloc<_Up> type;

};

template <template <class, class> class _Alloc, class _Tp, class _A0, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp, _A0>, _Up, true>

{

    typedef typename _Alloc<_Tp, _A0>::template rebind<_Up>::other type;

};

template <template <class, class> class _Alloc, class _Tp, class _A0, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp, _A0>, _Up, false>

{

    typedef _Alloc<_Up, _A0> type;

};

template <template <class, class, class> class _Alloc, class _Tp, class _A0,

                                         class _A1, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1>, _Up, true>

{

    typedef typename _Alloc<_Tp, _A0, _A1>::template rebind<_Up>::other type;

};

template <template <class, class, class> class _Alloc, class _Tp, class _A0,

                                         class _A1, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1>, _Up, false>

{

    typedef _Alloc<_Up, _A0, _A1> type;

};

template <template <class, class, class, class> class _Alloc, class _Tp, class _A0,

                                                class _A1, class _A2, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1, _A2>, _Up, true>

{

    typedef typename _Alloc<_Tp, _A0, _A1, _A2>::template rebind<_Up>::other type;

};

template <template <class, class, class, class> class _Alloc, class _Tp, class _A0,

                                                class _A1, class _A2, class _Up>

struct __allocator_traits_rebind<_Alloc<_Tp, _A0, _A1, _A2>, _Up, false>

{

    typedef _Alloc<_Up, _A0, _A1, _A2> type;

};

#endif  // _LIBCPP_HAS_NO_VARIADICS

#ifndef _LIBCPP_HAS_NO_ADVANCED_SFINAE

template <class _Alloc, class _SizeType, class _ConstVoidPtr>

auto

__has_allocate_hint_test(_Alloc&& __a, _SizeType&& __sz, _ConstVoidPtr&& __p)

    -> decltype(__a.allocate(__sz, __p), true_type());

template <class _Alloc, class _SizeType, class _ConstVoidPtr>

auto

__has_allocate_hint_test(const _Alloc& __a, _SizeType&& __sz, _ConstVoidPtr&& __p)

    -> false_type;

template <class _Alloc, class _SizeType, class _ConstVoidPtr>

struct __has_allocate_hint

    : integral_constant<bool,

        is_same<

            decltype(__has_allocate_hint_test(declval<_Alloc>(),

                                          declval<_SizeType>(),

                                          declval<_ConstVoidPtr>())),

            true_type>::value>

{

};

#else  // _LIBCPP_HAS_NO_ADVANCED_SFINAE

template <class _Alloc, class _SizeType, class _ConstVoidPtr>

struct __has_allocate_hint

    : true_type

{

};

#endif  // _LIBCPP_HAS_NO_ADVANCED_SFINAE

#if !defined(_LIBCPP_HAS_NO_ADVANCED_SFINAE) && !defined(_LIBCPP_HAS_NO_VARIADICS)

template <class _Alloc, class _Tp, class ..._Args>

decltype(_VSTD::declval<_Alloc>().construct(_VSTD::declval<_Tp*>(),

                                           _VSTD::declval<_Args>()...),

                                           true_type())

__has_construct_test(_Alloc&& __a, _Tp* __p, _Args&& ...__args);

template <class _Alloc, class _Pointer, class ..._Args>

false_type

__has_construct_test(const _Alloc& __a, _Pointer&& __p, _Args&& ...__args);

template <class _Alloc, class _Pointer, class ..._Args>

struct __has_construct

    : integral_constant<bool,

        is_same<

            decltype(__has_construct_test(declval<_Alloc>(),

                                          declval<_Pointer>(),

                                          declval<_Args>()...)),

            true_type>::value>

{

};

template <class _Alloc, class _Pointer>

auto

__has_destroy_test(_Alloc&& __a, _Pointer&& __p)

    -> decltype(__a.destroy(__p), true_type());

template <class _Alloc, class _Pointer>

auto

__has_destroy_test(const _Alloc& __a, _Pointer&& __p)

    -> false_type;

template <class _Alloc, class _Pointer>

struct __has_destroy

    : integral_constant<bool,

        is_same<

            decltype(__has_destroy_test(declval<_Alloc>(),

                                        declval<_Pointer>())),

            true_type>::value>

{

};

template <class _Alloc>

auto

__has_max_size_test(_Alloc&& __a)

    -> decltype(__a.max_size(), true_type());

template <class _Alloc>

auto

__has_max_size_test(const volatile _Alloc& __a)

    -> false_type;

template <class _Alloc>

struct __has_max_size

    : integral_constant<bool,

        is_same<

            decltype(__has_max_size_test(declval<_Alloc&>())),

            true_type>::value>

{

};

template <class _Alloc>

auto

__has_select_on_container_copy_construction_test(_Alloc&& __a)

    -> decltype(__a.select_on_container_copy_construction(), true_type());

template <class _Alloc>

auto

__has_select_on_container_copy_construction_test(const volatile _Alloc& __a)

    -> false_type;

template <class _Alloc>

struct __has_select_on_container_copy_construction

    : integral_constant<bool,

        is_same<

            decltype(__has_select_on_container_copy_construction_test(declval<_Alloc&>())),

            true_type>::value>

{

};

#else  // _LIBCPP_HAS_NO_ADVANCED_SFINAE

#ifndef _LIBCPP_HAS_NO_VARIADICS

template <class _Alloc, class _Pointer, class ..._Args>

struct __has_construct

    : false_type

{

};

#else  // _LIBCPP_HAS_NO_VARIADICS

template <class _Alloc, class _Pointer, class _Args>

struct __has_construct

    : false_type

{

};

#endif  // _LIBCPP_HAS_NO_VARIADICS

template <class _Alloc, class _Pointer>

struct __has_destroy

    : false_type

{

};

template <class _Alloc>

struct __has_max_size

    : true_type

{

};

template <class _Alloc>

struct __has_select_on_container_copy_construction

    : false_type

{

};

#endif  // _LIBCPP_HAS_NO_ADVANCED_SFINAE

template <class _Alloc, class _Ptr, bool = __has_difference_type<_Alloc>::value>

struct __alloc_traits_difference_type

{

    typedef typename pointer_traits<_Ptr>::difference_type type;

};

template <class _Alloc, class _Ptr>

struct __alloc_traits_difference_type<_Alloc, _Ptr, true>

{

    typedef typename _Alloc::difference_type type;

};

template <class _Alloc>

struct _LIBCPP_TYPE_VIS_ONLY allocator_traits

{

    typedef _Alloc                              allocator_type;

    typedef typename allocator_type::value_type value_type;

    typedef typename __pointer_type<value_type, allocator_type>::type pointer;

    typedef typename __const_pointer<value_type, pointer, allocator_type>::type const_pointer;

    typedef typename __void_pointer<pointer, allocator_type>::type void_pointer;

    typedef typename __const_void_pointer<pointer, allocator_type>::type const_void_pointer;

    typedef typename __alloc_traits_difference_type<allocator_type, pointer>::type difference_type;

    typedef typename __size_type<allocator_type, difference_type>::type size_type;

    typedef typename __propagate_on_container_copy_assignment<allocator_type>::type

                     propagate_on_container_copy_assignment;

    typedef typename __propagate_on_container_move_assignment<allocator_type>::type

                     propagate_on_container_move_assignment;

    typedef typename __propagate_on_container_swap<allocator_type>::type

                     propagate_on_container_swap;

    typedef typename __is_always_equal<allocator_type>::type

                     is_always_equal;

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    template <class _Tp> using rebind_alloc =

                  typename __allocator_traits_rebind<allocator_type, _Tp>::type;

    template <class _Tp> using rebind_traits = allocator_traits<rebind_alloc<_Tp>>;

#else  // _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    template <class _Tp> struct rebind_alloc

        {typedef typename __allocator_traits_rebind<allocator_type, _Tp>::type other;};

    template <class _Tp> struct rebind_traits

        {typedef allocator_traits<typename rebind_alloc<_Tp>::other> other;};

#endif  // _LIBCPP_HAS_NO_TEMPLATE_ALIASES

    _LIBCPP_INLINE_VISIBILITY

    static pointer allocate(allocator_type& __a, size_type __n)

        {return __a.allocate(__n);}

    _LIBCPP_INLINE_VISIBILITY

    static pointer allocate(allocator_type& __a, size_type __n, const_void_pointer __hint)

        {return allocate(__a, __n, __hint,

            __has_allocate_hint<allocator_type, size_type, const_void_pointer>());}

    _LIBCPP_INLINE_VISIBILITY

    static void deallocate(allocator_type& __a, pointer __p, size_type __n) _NOEXCEPT

        {__a.deallocate(__p, __n);}

#ifndef _LIBCPP_HAS_NO_VARIADICS

    template <class _Tp, class... _Args>

        _LIBCPP_INLINE_VISIBILITY

        static void construct(allocator_type& __a, _Tp* __p, _Args&&... __args)

            {__construct(__has_construct<allocator_type, _Tp*, _Args...>(),

                         __a, __p, _VSTD::forward<_Args>(__args)...);}

#else  // _LIBCPP_HAS_NO_VARIADICS

    template <class _Tp>

        _LIBCPP_INLINE_VISIBILITY

        static void construct(allocator_type& __a, _Tp* __p)

            {

                ::new ((void*)__p) _Tp();

            }

    template <class _Tp, class _A0>

        _LIBCPP_INLINE_VISIBILITY

        static void construct(allocator_type& __a, _Tp* __p, const _A0& __a0)

            {

                ::new ((void*)__p) _Tp(__a0);

            }

    template <class _Tp, class _A0, class _A1>

        _LIBCPP_INLINE_VISIBILITY

        static void construct(allocator_type& __a, _Tp* __p, const _A0& __a0,

                              const _A1& __a1)

            {

                ::new ((void*)__p) _Tp(__a0, __a1);

            }

    template <class _Tp, class _A0, class _A1, class _A2>

        _LIBCPP_INLINE_VISIBILITY

        static void construct(allocator_type& __a, _Tp* __p, const _A0& __a0,

                              const _A1& __a1, const _A2& __a2)

            {

                ::new ((void*)__p) _Tp(__a0, __a1, __a2);

            }

#endif  // _LIBCPP_HAS_NO_VARIADICS

    template <class _Tp>

        _LIBCPP_INLINE_VISIBILITY

        static void destroy(allocator_type& __a, _Tp* __p)

            {__destroy(__has_destroy<allocator_type, _Tp*>(), __a, __p);}

    _LIBCPP_INLINE_VISIBILITY

    static size_type max_size(const allocator_type& __a) _NOEXCEPT

        {return __max_size(__has_max_size<const allocator_type>(), __a);}

    _LIBCPP_INLINE_VISIBILITY

    static allocator_type

        select_on_container_copy_construction(const allocator_type& __a)

            {return select_on_container_copy_construction(

                __has_select_on_container_copy_construction<const allocator_type>(),

                __a);}

    template <class _Ptr>

        _LIBCPP_INLINE_VISIBILITY

        static

        void

        __construct_forward(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __begin2)

        {

            for (; __begin1 != __end1; ++__begin1, ++__begin2)

                construct(__a, _VSTD::__to_raw_pointer(__begin2), _VSTD::move_if_noexcept(*__begin1));

        }

    template <class _Tp>

        _LIBCPP_INLINE_VISIBILITY

        static

        typename enable_if

        <

            (is_same<allocator_type, allocator<_Tp> >::value

                || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&

             is_trivially_move_constructible<_Tp>::value,

            void

        >::type

        __construct_forward(allocator_type& __a, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2)

        {

            ptrdiff_t _Np = __end1 - __begin1;

            if (_Np > 0)

            {

                _VSTD::memcpy(__begin2, __begin1, _Np * sizeof(_Tp));

                __begin2 += _Np;

            }

        }

    template <class _Iter, class _Ptr>

        _LIBCPP_INLINE_VISIBILITY

        static

        void

        __construct_range_forward(allocator_type& __a, _Iter __begin1, _Iter __end1, _Ptr& __begin2)

        {

            for (; __begin1 != __end1; ++__begin1, (void) ++__begin2)

                construct(__a, _VSTD::__to_raw_pointer(__begin2), *__begin1);

        }

    template <class _Tp>

        _LIBCPP_INLINE_VISIBILITY

        static

        typename enable_if