LCOM1920-T02G10

// -*- C++ -*-

//===-------------------------- unordered_map -----------------------------===//

//

//                     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_UNORDERED_MAP

#define _LIBCPP_UNORDERED_MAP

/*

    unordered_map synopsis

#include <initializer_list>

namespace std

{

template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,

          class Alloc = allocator<pair<const Key, T>>>

class unordered_map

{

public:

    // types

    typedef Key                                                        key_type;

    typedef T                                                          mapped_type;

    typedef Hash                                                       hasher;

    typedef Pred                                                       key_equal;

    typedef Alloc                                                      allocator_type;

    typedef pair<const key_type, mapped_type>                          value_type;

    typedef value_type&                                                reference;

    typedef const value_type&                                          const_reference;

    typedef typename allocator_traits<allocator_type>::pointer         pointer;

    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;

    typedef typename allocator_traits<allocator_type>::size_type       size_type;

    typedef typename allocator_traits<allocator_type>::difference_type difference_type;

    typedef /unspecified/ iterator;

    typedef /unspecified/ const_iterator;

    typedef /unspecified/ local_iterator;

    typedef /unspecified/ const_local_iterator;

    unordered_map()

        noexcept(

            is_nothrow_default_constructible<hasher>::value &&

            is_nothrow_default_constructible<key_equal>::value &&

            is_nothrow_default_constructible<allocator_type>::value);

    explicit unordered_map(size_type n, const hasher& hf = hasher(),

                           const key_equal& eql = key_equal(),

                           const allocator_type& a = allocator_type());

    template <class InputIterator>

        unordered_map(InputIterator f, InputIterator l,

                      size_type n = 0, const hasher& hf = hasher(),

                      const key_equal& eql = key_equal(),

                      const allocator_type& a = allocator_type());

    explicit unordered_map(const allocator_type&);

    unordered_map(const unordered_map&);

    unordered_map(const unordered_map&, const Allocator&);

    unordered_map(unordered_map&&)

        noexcept(

            is_nothrow_move_constructible<hasher>::value &&

            is_nothrow_move_constructible<key_equal>::value &&

            is_nothrow_move_constructible<allocator_type>::value);

    unordered_map(unordered_map&&, const Allocator&);

    unordered_map(initializer_list<value_type>, size_type n = 0,

                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),

                  const allocator_type& a = allocator_type());

    unordered_map(size_type n, const allocator_type& a)

      : unordered_map(n, hasher(), key_equal(), a) {}  // C++14

    unordered_map(size_type n, const hasher& hf, const allocator_type& a)

      : unordered_map(n, hf, key_equal(), a) {}  // C++14

    template <class InputIterator>

      unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)

      : unordered_map(f, l, n, hasher(), key_equal(), a) {}  // C++14

    template <class InputIterator>

      unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,

        const allocator_type& a)

      : unordered_map(f, l, n, hf, key_equal(), a) {}  // C++14

    unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)

      : unordered_map(il, n, hasher(), key_equal(), a) {}  // C++14

    unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,

      const allocator_type& a)

      : unordered_map(il, n, hf, key_equal(), a) {}  // C++14

    ~unordered_map();

    unordered_map& operator=(const unordered_map&);

    unordered_map& operator=(unordered_map&&)

        noexcept(

            allocator_type::propagate_on_container_move_assignment::value &&

            is_nothrow_move_assignable<allocator_type>::value &&

            is_nothrow_move_assignable<hasher>::value &&

            is_nothrow_move_assignable<key_equal>::value);

    unordered_map& operator=(initializer_list<value_type>);

    allocator_type get_allocator() const noexcept;

    bool      empty() const noexcept;

    size_type size() const noexcept;

    size_type max_size() const noexcept;

    iterator       begin() noexcept;

    iterator       end() noexcept;

    const_iterator begin()  const noexcept;

    const_iterator end()    const noexcept;

    const_iterator cbegin() const noexcept;

    const_iterator cend()   const noexcept;

    template <class... Args>

        pair<iterator, bool> emplace(Args&&... args);

    template <class... Args>

        iterator emplace_hint(const_iterator position, Args&&... args);

    pair<iterator, bool> insert(const value_type& obj);

    template <class P>

        pair<iterator, bool> insert(P&& obj);

    iterator insert(const_iterator hint, const value_type& obj);

    template <class P>

        iterator insert(const_iterator hint, P&& obj);

    template <class InputIterator>

        void insert(InputIterator first, InputIterator last);

    void insert(initializer_list<value_type>);

    template <class... Args>

        pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17

    template <class... Args>

        pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17

    template <class... Args>

        iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17

    template <class... Args>

        iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17

    template <class M>

        pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);            // C++17

    template <class M>

        pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);                 // C++17

    template <class M>

        iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);   // C++17

    template <class M>

        iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17

    iterator erase(const_iterator position);

    iterator erase(iterator position);  // C++14

    size_type erase(const key_type& k);

    iterator erase(const_iterator first, const_iterator last);

    void clear() noexcept;

    void swap(unordered_map&)

        noexcept(

            (!allocator_type::propagate_on_container_swap::value ||

             __is_nothrow_swappable<allocator_type>::value) &&

            __is_nothrow_swappable<hasher>::value &&

            __is_nothrow_swappable<key_equal>::value);

    hasher hash_function() const;

    key_equal key_eq() const;

    iterator       find(const key_type& k);

    const_iterator find(const key_type& k) const;

    size_type count(const key_type& k) const;

    pair<iterator, iterator>             equal_range(const key_type& k);

    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;

    mapped_type& operator[](const key_type& k);

    mapped_type& operator[](key_type&& k);

    mapped_type&       at(const key_type& k);

    const mapped_type& at(const key_type& k) const;

    size_type bucket_count() const noexcept;

    size_type max_bucket_count() const noexcept;

    size_type bucket_size(size_type n) const;

    size_type bucket(const key_type& k) const;

    local_iterator       begin(size_type n);

    local_iterator       end(size_type n);

    const_local_iterator begin(size_type n) const;

    const_local_iterator end(size_type n) const;

    const_local_iterator cbegin(size_type n) const;

    const_local_iterator cend(size_type n) const;

    float load_factor() const noexcept;

    float max_load_factor() const noexcept;

    void max_load_factor(float z);

    void rehash(size_type n);

    void reserve(size_type n);

};

template <class Key, class T, class Hash, class Pred, class Alloc>

    void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,

              unordered_map<Key, T, Hash, Pred, Alloc>& y)

              noexcept(noexcept(x.swap(y)));

template <class Key, class T, class Hash, class Pred, class Alloc>

    bool

    operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,

               const unordered_map<Key, T, Hash, Pred, Alloc>& y);

template <class Key, class T, class Hash, class Pred, class Alloc>

    bool

    operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,

               const unordered_map<Key, T, Hash, Pred, Alloc>& y);

template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,

          class Alloc = allocator<pair<const Key, T>>>

class unordered_multimap

{

public:

    // types

    typedef Key                                                        key_type;

    typedef T                                                          mapped_type;

    typedef Hash                                                       hasher;

    typedef Pred                                                       key_equal;

    typedef Alloc                                                      allocator_type;

    typedef pair<const key_type, mapped_type>                          value_type;

    typedef value_type&                                                reference;

    typedef const value_type&                                          const_reference;

    typedef typename allocator_traits<allocator_type>::pointer         pointer;

    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;

    typedef typename allocator_traits<allocator_type>::size_type       size_type;

    typedef typename allocator_traits<allocator_type>::difference_type difference_type;

    typedef /unspecified/ iterator;

    typedef /unspecified/ const_iterator;

    typedef /unspecified/ local_iterator;

    typedef /unspecified/ const_local_iterator;

    unordered_multimap()

        noexcept(

            is_nothrow_default_constructible<hasher>::value &&

            is_nothrow_default_constructible<key_equal>::value &&

            is_nothrow_default_constructible<allocator_type>::value);

    explicit unordered_multimap(size_type n, const hasher& hf = hasher(),

                           const key_equal& eql = key_equal(),

                           const allocator_type& a = allocator_type());

    template <class InputIterator>

        unordered_multimap(InputIterator f, InputIterator l,

                      size_type n = 0, const hasher& hf = hasher(),

                      const key_equal& eql = key_equal(),

                      const allocator_type& a = allocator_type());

    explicit unordered_multimap(const allocator_type&);

    unordered_multimap(const unordered_multimap&);

    unordered_multimap(const unordered_multimap&, const Allocator&);

    unordered_multimap(unordered_multimap&&)

        noexcept(

            is_nothrow_move_constructible<hasher>::value &&

            is_nothrow_move_constructible<key_equal>::value &&

            is_nothrow_move_constructible<allocator_type>::value);

    unordered_multimap(unordered_multimap&&, const Allocator&);

    unordered_multimap(initializer_list<value_type>, size_type n = 0,

                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),

                  const allocator_type& a = allocator_type());

    unordered_multimap(size_type n, const allocator_type& a)

      : unordered_multimap(n, hasher(), key_equal(), a) {}  // C++14

    unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)

      : unordered_multimap(n, hf, key_equal(), a) {}  // C++14

    template <class InputIterator>

      unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)

      : unordered_multimap(f, l, n, hasher(), key_equal(), a) {}  // C++14

    template <class InputIterator>

      unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,

        const allocator_type& a)

      : unordered_multimap(f, l, n, hf, key_equal(), a) {}  // C++14

    unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)

      : unordered_multimap(il, n, hasher(), key_equal(), a) {}  // C++14

    unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,

      const allocator_type& a)

      : unordered_multimap(il, n, hf, key_equal(), a) {}  // C++14

    ~unordered_multimap();

    unordered_multimap& operator=(const unordered_multimap&);

    unordered_multimap& operator=(unordered_multimap&&)

        noexcept(

            allocator_type::propagate_on_container_move_assignment::value &&

            is_nothrow_move_assignable<allocator_type>::value &&

            is_nothrow_move_assignable<hasher>::value &&

            is_nothrow_move_assignable<key_equal>::value);

    unordered_multimap& operator=(initializer_list<value_type>);

    allocator_type get_allocator() const noexcept;

    bool      empty() const noexcept;

    size_type size() const noexcept;

    size_type max_size() const noexcept;

    iterator       begin() noexcept;

    iterator       end() noexcept;

    const_iterator begin()  const noexcept;

    const_iterator end()    const noexcept;

    const_iterator cbegin() const noexcept;

    const_iterator cend()   const noexcept;

    template <class... Args>

        iterator emplace(Args&&... args);

    template <class... Args>

        iterator emplace_hint(const_iterator position, Args&&... args);

    iterator insert(const value_type& obj);

    template <class P>

        iterator insert(P&& obj);

    iterator insert(const_iterator hint, const value_type& obj);

    template <class P>

        iterator insert(const_iterator hint, P&& obj);

    template <class InputIterator>

        void insert(InputIterator first, InputIterator last);

    void insert(initializer_list<value_type>);

    iterator erase(const_iterator position);

    iterator erase(iterator position);  // C++14

    size_type erase(const key_type& k);

    iterator erase(const_iterator first, const_iterator last);

    void clear() noexcept;

    void swap(unordered_multimap&)

        noexcept(

            (!allocator_type::propagate_on_container_swap::value ||

             __is_nothrow_swappable<allocator_type>::value) &&

            __is_nothrow_swappable<hasher>::value &&

            __is_nothrow_swappable<key_equal>::value);

    hasher hash_function() const;

    key_equal key_eq() const;

    iterator       find(const key_type& k);

    const_iterator find(const key_type& k) const;

    size_type count(const key_type& k) const;

    pair<iterator, iterator>             equal_range(const key_type& k);

    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;

    size_type bucket_count() const noexcept;

    size_type max_bucket_count() const noexcept;

    size_type bucket_size(size_type n) const;

    size_type bucket(const key_type& k) const;

    local_iterator       begin(size_type n);

    local_iterator       end(size_type n);

    const_local_iterator begin(size_type n) const;

    const_local_iterator end(size_type n) const;

    const_local_iterator cbegin(size_type n) const;

    const_local_iterator cend(size_type n) const;

    float load_factor() const noexcept;

    float max_load_factor() const noexcept;

    void max_load_factor(float z);

    void rehash(size_type n);

    void reserve(size_type n);

};

template <class Key, class T, class Hash, class Pred, class Alloc>

    void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,

              unordered_multimap<Key, T, Hash, Pred, Alloc>& y)

              noexcept(noexcept(x.swap(y)));

template <class Key, class T, class Hash, class Pred, class Alloc>

    bool

    operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,

               const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);

template <class Key, class T, class Hash, class Pred, class Alloc>

    bool

    operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,

               const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);

}  // std

*/

#include <__config>

#include <__hash_table>

#include <functional>

#include <stdexcept>

#include <__debug>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

#pragma GCC system_header

#endif

_LIBCPP_BEGIN_NAMESPACE_STD

template <class _Key, class _Cp, class _Hash,

          bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value

         >

class __unordered_map_hasher

    : private _Hash

{

public:

    _LIBCPP_INLINE_VISIBILITY

    __unordered_map_hasher()

        _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)

        : _Hash() {}

    _LIBCPP_INLINE_VISIBILITY

    __unordered_map_hasher(const _Hash& __h)

        _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)

        : _Hash(__h) {}

    _LIBCPP_INLINE_VISIBILITY

    const _Hash& hash_function() const _NOEXCEPT {return *this;}

    _LIBCPP_INLINE_VISIBILITY

    size_t operator()(const _Cp& __x) const

        {return static_cast<const _Hash&>(*this)(__x.__cc.first);}

    _LIBCPP_INLINE_VISIBILITY

    size_t operator()(const _Key& __x) const

        {return static_cast<const _Hash&>(*this)(__x);}

    void swap(__unordered_map_hasher&__y)

        _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)

    {

        using _VSTD::swap;

        swap(static_cast<const _Hash&>(*this), static_cast<const _Hash&>(__y));

    }

};

template <class _Key, class _Cp, class _Hash>

class __unordered_map_hasher<_Key, _Cp, _Hash, false>

{

    _Hash __hash_;

public:

    _LIBCPP_INLINE_VISIBILITY

    __unordered_map_hasher()

        _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)

        : __hash_() {}

    _LIBCPP_INLINE_VISIBILITY

    __unordered_map_hasher(const _Hash& __h)

        _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)

        : __hash_(__h) {}

    _LIBCPP_INLINE_VISIBILITY

    const _Hash& hash_function() const _NOEXCEPT {return __hash_;}

    _LIBCPP_INLINE_VISIBILITY

    size_t operator()(const _Cp& __x) const

        {return __hash_(__x.__cc.first);}

    _LIBCPP_INLINE_VISIBILITY

    size_t operator()(const _Key& __x) const

        {return __hash_(__x);}

    void swap(__unordered_map_hasher&__y)

        _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)

    {

        using _VSTD::swap;

        swap(__hash_, __y.__hash_);

    }

};

template <class _Key, class _Cp, class _Hash, bool __b>

inline _LIBCPP_INLINE_VISIBILITY

void

swap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x,

     __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y)

    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))

{

    __x.swap(__y);

}

template <class _Key, class _Cp, class _Pred,

          bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value

         >

class __unordered_map_equal

    : private _Pred

{

public:

    _LIBCPP_INLINE_VISIBILITY

    __unordered_map_equal()

        _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)

        : _Pred() {}

    _LIBCPP_INLINE_VISIBILITY

    __unordered_map_equal(const _Pred& __p)

        _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)

        : _Pred(__p) {}

    _LIBCPP_INLINE_VISIBILITY

    const _Pred& key_eq() const _NOEXCEPT {return *this;}

    _LIBCPP_INLINE_VISIBILITY

    bool operator()(const _Cp& __x, const _Cp& __y) const

        {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}

    _LIBCPP_INLINE_VISIBILITY

    bool operator()(const _Cp& __x, const _Key& __y) const

        {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}

    _LIBCPP_INLINE_VISIBILITY

    bool operator()(const _Key& __x, const _Cp& __y) const

        {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}

    void swap(__unordered_map_equal&__y)

        _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)

    {

        using _VSTD::swap;

        swap(static_cast<const _Pred&>(*this), static_cast<const _Pred&>(__y));

    }

};

template <class _Key, class _Cp, class _Pred>

class __unordered_map_equal<_Key, _Cp, _Pred, false>

{

    _Pred __pred_;

public:

    _LIBCPP_INLINE_VISIBILITY

    __unordered_map_equal()

        _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)

        : __pred_() {}

    _LIBCPP_INLINE_VISIBILITY

    __unordered_map_equal(const _Pred& __p)

        _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)

        : __pred_(__p) {}

    _LIBCPP_INLINE_VISIBILITY

    const _Pred& key_eq() const _NOEXCEPT {return __pred_;}

    _LIBCPP_INLINE_VISIBILITY

    bool operator()(const _Cp& __x, const _Cp& __y) const

        {return __pred_(__x.__cc.first, __y.__cc.first);}

    _LIBCPP_INLINE_VISIBILITY

    bool operator()(const _Cp& __x, const _Key& __y) const

        {return __pred_(__x.__cc.first, __y);}

    _LIBCPP_INLINE_VISIBILITY

    bool operator()(const _Key& __x, const _Cp& __y) const

        {return __pred_(__x, __y.__cc.first);}

    void swap(__unordered_map_equal&__y)

        _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)

    {

        using _VSTD::swap;

        swap(__pred_, __y.__pred_);

    }

};

template <class _Key, class _Cp, class _Pred, bool __b>

inline _LIBCPP_INLINE_VISIBILITY

void

swap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x,

     __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y)

    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))

{

    __x.swap(__y);

}

template <class _Alloc>

class __hash_map_node_destructor

{

    typedef _Alloc                              allocator_type;

    typedef allocator_traits<allocator_type>    __alloc_traits;

    typedef typename __alloc_traits::value_type::value_type value_type;

public:

    typedef typename __alloc_traits::pointer    pointer;

private:

    typedef typename value_type::value_type::first_type     first_type;

    typedef typename value_type::value_type::second_type    second_type;

    allocator_type& __na_;

    __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);

public:

    bool __first_constructed;

    bool __second_constructed;

    _LIBCPP_INLINE_VISIBILITY

    explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT

        : __na_(__na),

          __first_constructed(false),

          __second_constructed(false)

        {}

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)

        _NOEXCEPT

        : __na_(__x.__na_),

          __first_constructed(__x.__value_constructed),

          __second_constructed(__x.__value_constructed)

        {

            __x.__value_constructed = false;

        }

#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)

        : __na_(__x.__na_),

          __first_constructed(__x.__value_constructed),

          __second_constructed(__x.__value_constructed)

        {

            const_cast<bool&>(__x.__value_constructed) = false;

        }

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    _LIBCPP_INLINE_VISIBILITY

    void operator()(pointer __p) _NOEXCEPT

    {

        if (__second_constructed)

            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));

        if (__first_constructed)

            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));

        if (__p)

            __alloc_traits::deallocate(__na_, __p, 1);

    }

};

#if __cplusplus >= 201103L

template <class _Key, class _Tp>

union __hash_value_type

{

    typedef _Key                                     key_type;

    typedef _Tp                                      mapped_type;

    typedef pair<const key_type, mapped_type>        value_type;

    typedef pair<key_type, mapped_type>              __nc_value_type;

    value_type __cc;

    __nc_value_type __nc;

    template <class ..._Args>

    _LIBCPP_INLINE_VISIBILITY

    __hash_value_type(_Args&& ...__args)

        : __cc(std::forward<_Args>(__args)...) {}

    _LIBCPP_INLINE_VISIBILITY

    __hash_value_type(const __hash_value_type& __v)

        : __cc(__v.__cc) {}

    _LIBCPP_INLINE_VISIBILITY

    __hash_value_type(__hash_value_type&& __v)

        : __nc(_VSTD::move(__v.__nc)) {}

    _LIBCPP_INLINE_VISIBILITY

    __hash_value_type& operator=(const __hash_value_type& __v)

        {__nc = __v.__cc; return *this;}

    _LIBCPP_INLINE_VISIBILITY

    __hash_value_type& operator=(__hash_value_type&& __v)

        {__nc = _VSTD::move(__v.__nc); return *this;}

    _LIBCPP_INLINE_VISIBILITY

    ~__hash_value_type() {__cc.~value_type();}

};

#else

template <class _Key, class _Tp>

struct __hash_value_type

{

    typedef _Key                                     key_type;

    typedef _Tp                                      mapped_type;

    typedef pair<const key_type, mapped_type>        value_type;

    value_type __cc;

    _LIBCPP_INLINE_VISIBILITY

    __hash_value_type() {}

    template <class _A0>

    _LIBCPP_INLINE_VISIBILITY

    __hash_value_type(const _A0& __a0)

        : __cc(__a0) {}

    template <class _A0, class _A1>

    _LIBCPP_INLINE_VISIBILITY

    __hash_value_type(const _A0& __a0, const _A1& __a1)

        : __cc(__a0, __a1) {}

};

#endif

template <class _HashIterator>

class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator

{

    _HashIterator __i_;

    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;

    typedef const typename _HashIterator::value_type::value_type::first_type key_type;

    typedef typename _HashIterator::value_type::value_type::second_type      mapped_type;

public:

    typedef forward_iterator_tag                                 iterator_category;

    typedef pair<key_type, mapped_type>                          value_type;

    typedef typename _HashIterator::difference_type              difference_type;

    typedef value_type&                                          reference;

    typedef typename __pointer_traits::template

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

            rebind<value_type>

#else

            rebind<value_type>::other

#endif

                                                                 pointer;

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_iterator() _NOEXCEPT {}

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}

    _LIBCPP_INLINE_VISIBILITY

    reference operator*() const {return __i_->__cc;}

    _LIBCPP_INLINE_VISIBILITY

    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_iterator& operator++() {++__i_; return *this;}

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_iterator operator++(int)

    {

        __hash_map_iterator __t(*this);

        ++(*this);

        return __t;

    }

    friend _LIBCPP_INLINE_VISIBILITY

        bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)

        {return __x.__i_ == __y.__i_;}

    friend _LIBCPP_INLINE_VISIBILITY

        bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)

        {return __x.__i_ != __y.__i_;}

    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;

    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;

    template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;

    template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;

    template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;

};

template <class _HashIterator>

class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator

{

    _HashIterator __i_;

    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;

    typedef const typename _HashIterator::value_type::value_type::first_type key_type;

    typedef typename _HashIterator::value_type::value_type::second_type      mapped_type;

public:

    typedef forward_iterator_tag                                 iterator_category;

    typedef pair<key_type, mapped_type>                          value_type;

    typedef typename _HashIterator::difference_type              difference_type;

    typedef const value_type&                                    reference;

    typedef typename __pointer_traits::template

#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES

            rebind<const value_type>

#else

            rebind<const value_type>::other

#endif

                                                                 pointer;

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_const_iterator() _NOEXCEPT {}

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_const_iterator(

            __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)

                 _NOEXCEPT

                : __i_(__i.__i_) {}

    _LIBCPP_INLINE_VISIBILITY

    reference operator*() const {return __i_->__cc;}

    _LIBCPP_INLINE_VISIBILITY

    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_const_iterator& operator++() {++__i_; return *this;}

    _LIBCPP_INLINE_VISIBILITY

    __hash_map_const_iterator operator++(int)

    {

        __hash_map_const_iterator __t(*this);

        ++(*this);

        return __t;

    }

    friend _LIBCPP_INLINE_VISIBILITY

        bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)

        {return __x.__i_ == __y.__i_;}

    friend _LIBCPP_INLINE_VISIBILITY

        bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)

        {return __x.__i_ != __y.__i_;}

    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;

    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;

    template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;

    template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;

};

template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,

          class _Alloc = allocator<pair<const _Key, _Tp> > >

class _LIBCPP_TYPE_VIS_ONLY unordered_map

{

public:

    // types

    typedef _Key                                           key_type;

    typedef _Tp                                            mapped_type;

    typedef _Hash                                          hasher;

    typedef _Pred                                          key_equal;

    typedef _Alloc                                         allocator_type;

    typedef pair<const key_type, mapped_type>              value_type;

    typedef pair<key_type, mapped_type>                    __nc_value_type;

    typedef value_type&                                    reference;

    typedef const value_type&                              const_reference;

    static_assert((is_same<value_type, typename allocator_type::value_type>::value),

                  "Invalid allocator::value_type");

private:

    typedef __hash_value_type<key_type, mapped_type>                 __value_type;

    typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;

    typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;

    typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,

                                                 __value_type>::type __allocator_type;

    typedef __hash_table<__value_type, __hasher,

                         __key_equal,  __allocator_type>   __table;

    __table __table_;

    typedef typename __table::__node_pointer               __node_pointer;

    typedef typename __table::__node_const_pointer         __node_const_pointer;

    typedef typename __table::__node_traits                __node_traits;

    typedef typename __table::__node_allocator             __node_allocator;

    typedef typename __table::__node                       __node;

    typedef __hash_map_node_destructor<__node_allocator>   _Dp;

    typedef unique_ptr<__node, _Dp>                         __node_holder;

    typedef allocator_traits<allocator_type>               __alloc_traits;

public:

    typedef typename __alloc_traits::pointer         pointer;

    typedef typename __alloc_traits::const_pointer   const_pointer;

    typedef typename __alloc_traits::size_type       size_type;

    typedef typename __alloc_traits::difference_type difference_type;

    typedef __hash_map_iterator<typename __table::iterator>       iterator;

    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;

    typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;

    typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;

    _LIBCPP_INLINE_VISIBILITY

    unordered_map()

        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)

        {

#if _LIBCPP_DEBUG_LEVEL >= 2

            __get_db()->__insert_c(this);

#endif

        }

    explicit unordered_map(size_type __n, const hasher& __hf = hasher(),

                           const key_equal& __eql = key_equal());

    unordered_map(size_type __n, const hasher& __hf,

                  const key_equal& __eql,

                  const allocator_type& __a);

    template <class _InputIterator>

        unordered_map(_InputIterator __first, _InputIterator __last);

    template <class _InputIterator>

        unordered_map(_InputIterator __first, _InputIterator __last,

                      size_type __n, const hasher& __hf = hasher(),

                      const key_equal& __eql = key_equal());

    template <class _InputIterator>

        unordered_map(_InputIterator __first, _InputIterator __last,

                      size_type __n, const hasher& __hf,

                      const key_equal& __eql,

                      const allocator_type& __a);

    explicit unordered_map(const allocator_type& __a);

    unordered_map(const unordered_map& __u);

    unordered_map(const unordered_map& __u, const allocator_type& __a);

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    unordered_map(unordered_map&& __u)

        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);

    unordered_map(unordered_map&& __u, const allocator_type& __a);

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    unordered_map(initializer_list<value_type> __il);

    unordered_map(initializer_list<value_type> __il, size_type __n,

                  const hasher& __hf = hasher(), const key_equal& __eql = key_equal());

    unordered_map(initializer_list<value_type> __il, size_type __n,

                  const hasher& __hf, const key_equal& __eql,

                  const allocator_type& __a);

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

#if _LIBCPP_STD_VER > 11

    _LIBCPP_INLINE_VISIBILITY

    unordered_map(size_type __n, const allocator_type& __a)

      : unordered_map(__n, hasher(), key_equal(), __a) {}

    _LIBCPP_INLINE_VISIBILITY

    unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)

      : unordered_map(__n, __hf, key_equal(), __a) {}

    template <class _InputIterator>

    _LIBCPP_INLINE_VISIBILITY

      unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)

      : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}

    template <class _InputIterator>

    _LIBCPP_INLINE_VISIBILITY

      unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,

        const allocator_type& __a)

      : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}

    _LIBCPP_INLINE_VISIBILITY

    unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)

      : unordered_map(__il, __n, hasher(), key_equal(), __a) {}

    _LIBCPP_INLINE_VISIBILITY

    unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,

      const allocator_type& __a)

      : unordered_map(__il, __n, __hf, key_equal(), __a) {}

#endif

    // ~unordered_map() = default;

    _LIBCPP_INLINE_VISIBILITY

    unordered_map& operator=(const unordered_map& __u)

    {

#if __cplusplus >= 201103L

        __table_ = __u.__table_;

#else

        if (this != &__u) {

            __table_.clear();

            __table_.hash_function() = __u.__table_.hash_function();

            __table_.key_eq() = __u.__table_.key_eq();

            __table_.max_load_factor() = __u.__table_.max_load_factor();

            __table_.__copy_assign_alloc(__u.__table_);

            insert(__u.begin(), __u.end());

        }

#endif

        return *this;

    }

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    unordered_map& operator=(unordered_map&& __u)

        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);

#endif

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    unordered_map& operator=(initializer_list<value_type> __il);

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    allocator_type get_allocator() const _NOEXCEPT

        {return allocator_type(__table_.__node_alloc());}

    _LIBCPP_INLINE_VISIBILITY

    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}

    _LIBCPP_INLINE_VISIBILITY

    size_type size() const _NOEXCEPT  {return __table_.size();}

    _LIBCPP_INLINE_VISIBILITY

    size_type max_size() const _NOEXCEPT {return __table_.max_size();}

    _LIBCPP_INLINE_VISIBILITY

    iterator       begin() _NOEXCEPT        {return __table_.begin();}

    _LIBCPP_INLINE_VISIBILITY

    iterator       end() _NOEXCEPT          {return __table_.end();}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator end()    const _NOEXCEPT {return __table_.end();}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}

    _LIBCPP_INLINE_VISIBILITY

    const_iterator cend()   const _NOEXCEPT {return __table_.end();}

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

#ifndef _LIBCPP_HAS_NO_VARIADICS

    template <class... _Args>

        pair<iterator, bool> emplace(_Args&&... __args);

    template <class... _Args>

        _LIBCPP_INLINE_VISIBILITY

#if _LIBCPP_DEBUG_LEVEL >= 2

        iterator emplace_hint(const_iterator __p, _Args&&... __args)

        {

            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,

                "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"

                " referring to this unordered_map");

            return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;

        }

#else

        iterator emplace_hint(const_iterator, _Args&&... __args)

            {return emplace(_VSTD::forward<_Args>(__args)...).first;}

#endif

#endif  // _LIBCPP_HAS_NO_VARIADICS

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    _LIBCPP_INLINE_VISIBILITY

    pair<iterator, bool> insert(const value_type& __x)

        {return __table_.__insert_unique(__x);}

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    template <class _Pp,

              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>

        _LIBCPP_INLINE_VISIBILITY

        pair<iterator, bool> insert(_Pp&& __x)

            {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    _LIBCPP_INLINE_VISIBILITY

#if _LIBCPP_DEBUG_LEVEL >= 2

    iterator insert(const_iterator __p, const value_type& __x)

        {

            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,

                "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"

                " referring to this unordered_map");

            return insert(__x).first;

        }

#else

    iterator insert(const_iterator, const value_type& __x)

        {return insert(__x).first;}

#endif

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

    template <class _Pp,

              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>

        _LIBCPP_INLINE_VISIBILITY

#if _LIBCPP_DEBUG_LEVEL >= 2

        iterator insert(const_iterator __p, _Pp&& __x)

        {

            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,

                "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"

                " referring to this unordered_map");

            return insert(_VSTD::forward<_Pp>(__x)).first;

        }

#else

        iterator insert(const_iterator, _Pp&& __x)

            {return insert(_VSTD::forward<_Pp>(__x)).first;}

#endif

#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES

    template <class _InputIterator>

        void insert(_InputIterator __first, _InputIterator __last);

#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

    _LIBCPP_INLINE_VISIBILITY

    void insert(initializer_list<value_type> __il)

        {insert(__il.begin(), __il.end());}

#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS

#if _LIBCPP_STD_VER > 14

#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES

#ifndef _LIBCPP_HAS_NO_VARIADICS

    template <class... _Args>

        _LIBCPP_INLINE_VISIBILITY

        pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)

    {

        iterator __p = __table_.find(__k);

        if ( __p != end())

            return _VSTD::make_pair(__p, false);

        else

            return _VSTD::make_pair(

                      emplace_hint(__p,

                        _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),

                        _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),

                      true);

    }

    template <class... _Args>

        _LIBCPP_INLINE_VISIBILITY

        pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)

    {

        iterator __p = __table_.find(__k);

        if ( __p != end())

            return _VSTD::make_pair(__p, false);

        else

            return _VSTD::make_pair(

                      emplace_hint(__p,

                        _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),

                        _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),

                      true);

    }

    template <class... _Args>

        _LIBCPP_INLINE_VISIBILITY

        iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)

    {

        iterator __p = __table_.find(__k);

        if ( __p != end())

            return __p;

        else

            return emplace_hint(__h,

                      _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),

                      _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));

    }

    template <class... _Args>

        _LIBCPP_INLINE_VISIBILITY

        iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)

    {

        iterator __p = __table_.find(__k);

        if ( __p != end())

            return __p;

        else

            return emplace_hint(__h,

                      _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),

                      _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));

    }

    template <class _Vp>

        _LIBCPP_INLINE_VISIBILITY

        pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)

    {

        iterator __p = __table_.find(__k);

        if ( __p != end())

        {

            __p->second = _VSTD::move(__v);

            return _VSTD::make_pair(__p, false);

        }

        return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);

    }

    template <class _Vp>

        _LIBCPP_INLINE_VISIBILITY

        pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)

    {

        iterator __p = __table_.find(__k);

        if ( __p != end())

        {

            __p->second = _VSTD::move(__v);

            return _VSTD::make_pair(__p, false);

        }

        return _VSTD::make_pair(emplace_hint(__p, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v)), true);

    }

    template <class _Vp>

        _LIBCPP_INLINE_VISIBILITY

        iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)

     {

        iterator __p = __table_.find(__k);

        if ( __p != end())

        {

            __p->second = _VSTD::move(__v);

            return __p;

        }

        return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));

     }

    template <class _Vp>

        _LIBCPP_INLINE_VISIBILITY

        iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)

     {

        iterator __p = __table_.find(__k);

        if ( __p != end())

        {

            __p->second = _VSTD::move(__v);

            return __p;

        }

        return emplace_hint(__h, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v));

     }

#endif

#endif

#endif

    _LIBCPP_INLINE_VISIBILITY

    iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}

    _LIBCPP_INLINE_VISIBILITY

    iterator erase(iterator __p)       {return __table_.erase(__p.__i_);}

    _LIBCPP_INLINE_VISIBILITY

    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}

    _LIBCPP_INLINE_VISIBILITY

    iterator erase(const_iterator __first, const_iterator __last)

        {return __table_.erase(__first.__i_, __last.__i_);}

    _LIBCPP_INLINE_VISIBILITY

    void clear() _NOEXCEPT {__table_.clear();}

    _LIBCPP_INLINE_VISIBILITY

    void swap(unordered_map& __u)

        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)