// hash_map extension header
#pragma once
#ifndef _HASH_MAP_
#define _HASH_MAP_
#ifndef RC_INVOKED
#include <xhash>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,_STL_WARNING_LEVEL)
 #pragma warning(disable: _STL_DISABLED_WARNINGS)
 _STL_DISABLE_CLANG_WARNINGS
 #pragma push_macro("new")
 #undef new

 #ifndef _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS
  #error <hash_map> is deprecated and will be REMOVED. Please use <unordered_map>. You can define \
_SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS to acknowledge that you have received this warning.
 #endif /* _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS */

namespace stdext {
using _STD allocator;
using _STD enable_if_t;
using _STD is_constructible_v;
using _STD pair;
using _STD swap;
using _STD _Hash;
using _STD _Is_nothrow_swappable;
using _STD _Swap_adl;
using _STD _Xout_of_range;

		// CLASS TEMPLATE _Hmap_traits
template<class _Kty,	// key type
	class _Ty,	// mapped type
	class _Tr,	// comparator predicate type
	class _Alloc,	// actual allocator type (should be value allocator)
	bool _Mfl>	// true if multiple equivalent keys are permitted
	class _Hmap_traits
		: public _Tr
	{	// traits required to make _Hash behave like a map
public:
	typedef _Kty key_type;
	typedef pair<const _Kty, _Ty> value_type;
	typedef _Tr key_compare;
	typedef _Alloc allocator_type;
#if _HAS_CXX17
	using node_type = _STD _Node_handle<
		_STD _List_node<value_type, typename _STD allocator_traits<_Alloc>::void_pointer>,
		_Alloc, _STD _Node_handle_map_base, _Kty, _Ty>;
#endif /* _HAS_CXX17 */

	enum
		{	// make multi parameter visible as an enum constant
		_Multi = _Mfl};

	static constexpr bool _Standard = false;

	_Hmap_traits(const _Tr& _Traits = _Tr())
		: _Tr(_Traits), _Max_buckets(0.0F)
		{	// construct with specified comparator
		}

	class value_compare
		{	// functor for comparing two element values
	public:
		typedef value_type first_argument_type;
		typedef value_type second_argument_type;
		typedef bool result_type;

		bool operator()(const value_type& _Left,
			const value_type& _Right) const
			{	// test if _Left precedes _Right by comparing just keys
			return (_Keycompobj(_Left.first, _Right.first));
			}

		value_compare(const key_compare& _Keycomparg)
			: _Keycompobj(_Keycomparg)
			{	// construct with specified predicate
			}

		key_compare _Keycompobj;
		};

	template<class _Ty1,
		class _Ty2>
		static const _Kty& _Kfn(const pair<_Ty1, _Ty2>& _Val)
		{	// extract key from element value
		return (_Val.first);
		}

	template<class _Ty1,
		class _Ty2>
		static const _Ty2& _Nonkfn(const pair<_Ty1, _Ty2>& _Val)
		{	// extract non-key from element value
		return (_Val.second);
		}

	float& _Get_max_bucket_size() _NOEXCEPT
		{	// return reference to current maximum bucket size
		return (_Max_buckets);
		}

	const float& _Get_max_bucket_size() const _NOEXCEPT
		{	// return const reference to current maximum bucket size
		return (_Max_buckets);
		}

	void swap(_Hmap_traits& _Rhs) _NOEXCEPT_COND(_Is_nothrow_swappable<_Tr>::value)
		{
		_Swap_adl(static_cast<_Tr&>(*this), static_cast<_Tr&>(_Rhs));
		_STD swap(_Max_buckets, _Rhs._Max_buckets);
		}

	float _Max_buckets;	// current maximum bucket size
	};

		// CLASS TEMPLATE hash_map
template<class _Kty,
	class _Ty,
	class _Tr = hash_compare<_Kty, less<_Kty> >,
	class _Alloc = allocator<pair<const _Kty, _Ty> > >
	class hash_map
		: public _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, false> >
	{	// hash table of {key, mapped} values, unique keys
public:
	typedef _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, false> > _Mybase;
	typedef _Kty key_type;
	typedef _Ty mapped_type;
	typedef _Ty referent_type;
	typedef _Tr key_compare;
	typedef typename _Mybase::value_compare value_compare;
	typedef typename _Mybase::value_type value_type;
	typedef typename _Mybase::allocator_type allocator_type;
	typedef typename _Mybase::size_type size_type;
	typedef typename _Mybase::difference_type difference_type;
	typedef typename _Mybase::pointer pointer;
	typedef typename _Mybase::const_pointer const_pointer;
	typedef value_type& reference;
	typedef const value_type& const_reference;
	typedef typename _Mybase::iterator iterator;
	typedef typename _Mybase::const_iterator const_iterator;
	typedef typename _Mybase::_Pairib _Pairib;
	typedef typename _Mybase::_Alnode _Alnode;
	typedef typename _Mybase::_Alnode_traits _Alnode_traits;
#if _HAS_CXX17
	using insert_return_type = _STD _Insert_return_type<iterator, typename _Mybase::node_type>;
#endif /* _HAS_CXX17 */

	hash_map()
		: _Mybase(key_compare(), allocator_type())
		{	// construct empty map from defaults
		}

	explicit hash_map(const allocator_type& _Al)
		: _Mybase(key_compare(), _Al)
		{	// construct empty map from defaults, allocator
		}

	hash_map(const hash_map& _Right)
		: _Mybase(_Right, _Alnode_traits::select_on_container_copy_construction(_Right._List._Getal()))
		{	// construct map by copying _Right
		}

	hash_map(const hash_map& _Right, const allocator_type& _Al)
		: _Mybase(_Right, _Al)
		{	// construct map by copying _Right, allocator
		}

	explicit hash_map(const key_compare& _Traits)
		: _Mybase(_Traits, allocator_type())
		{	// construct empty map from comparator
		}

	hash_map(const key_compare& _Traits, const allocator_type& _Al)
		: _Mybase(_Traits, _Al)
		{	// construct empty map from comparator and allocator
		}

	template<class _Iter>
		hash_map(_Iter _First, _Iter _Last)
		: _Mybase(key_compare(), allocator_type())
		{	// construct map from sequence, defaults
		insert(_First, _Last);
		}

	template<class _Iter>
		hash_map(_Iter _First, _Iter _Last,
			const key_compare& _Traits)
		: _Mybase(_Traits, allocator_type())
		{	// construct map from sequence, comparator
		insert(_First, _Last);
		}

	template<class _Iter>
		hash_map(_Iter _First, _Iter _Last,
			const key_compare& _Traits,
			const allocator_type& _Al)
		: _Mybase(_Traits, _Al)
		{	// construct map from sequence, comparator, and allocator
		insert(_First, _Last);
		}

	hash_map& operator=(const hash_map& _Right)
		{	// assign by copying _Right
		_Mybase::operator=(_Right);
		return (*this);
		}

	hash_map(hash_map&& _Right)
		: _Mybase(_STD move(_Right))
		{	// construct map by moving _Right
		}

	hash_map(hash_map&& _Right, const allocator_type& _Al)
		: _Mybase(_STD move(_Right), _Al)
		{	// construct map by moving _Right, allocator
		}

	hash_map& operator=(hash_map&& _Right)
		{	// assign by moving _Right
		_Mybase::operator=(_STD move(_Right));
		return (*this);
		}

	mapped_type& operator[](key_type&& _Keyval)
		{	// find element matching _Keyval or insert with default mapped
		iterator _Where = this->lower_bound(_Keyval);
		if (_Where == this->end())
			_Where = insert(
				pair<key_type, mapped_type>(
					_STD move(_Keyval),
					mapped_type())).first;
		return (_Where->second);
		}

	void swap(hash_map& _Right)
		_NOEXCEPT_COND(_NOEXCEPT_OPER(_Mybase::swap(_Right))) // strengthened
		{	// exchange contents with non-movable _Right
		_Mybase::swap(_Right);
		}

	using _Mybase::insert;

	template<class _Valty,
		class = enable_if_t<is_constructible_v<value_type, _Valty>>>
		_Pairib insert(_Valty&& _Val)
		{	// insert _Val
		return (this->emplace(_STD forward<_Valty>(_Val)));
		}

	template<class _Valty,
		class = enable_if_t<is_constructible_v<value_type, _Valty>>>
		iterator insert(const_iterator _Where, _Valty&& _Val)
		{	// insert _Val with hint
		return (this->emplace_hint(_Where, _STD forward<_Valty>(_Val)));
		}

	hash_map(_STD initializer_list<value_type> _Ilist)
		: _Mybase(key_compare(), allocator_type())
		{	// construct from initializer_list, defaults
		insert(_Ilist);
		}

	hash_map(_STD initializer_list<value_type> _Ilist,
		const key_compare& _Pred)
		: _Mybase(_Pred, allocator_type())
		{	// construct from initializer_list, comparator
		insert(_Ilist);
		}

	hash_map(_STD initializer_list<value_type> _Ilist,
		const key_compare& _Pred, const allocator_type& _Al)
		: _Mybase(_Pred, _Al)
		{	// construct from initializer_list, comparator, and allocator
		insert(_Ilist);
		}

	hash_map& operator=(_STD initializer_list<value_type> _Ilist)
		{	// assign initializer_list
		this->clear();
		insert(_Ilist);
		return (*this);
		}

	mapped_type& operator[](const key_type& _Keyval)
		{	// find element matching _Keyval or insert with default mapped
		iterator _Where = this->lower_bound(_Keyval);
		if (_Where == this->end())
			_Where = insert(
				pair<key_type, mapped_type>(
					_Keyval,
					mapped_type())).first;
		return (_Where->second);
		}

	mapped_type& at(const key_type& _Keyval)
		{	// find element matching _Keyval
		iterator _Where = this->lower_bound(_Keyval);
		if (_Where == this->end())
			_Xout_of_range("invalid hash_map<K, T> key");
		return (_Where->second);
		}

	const mapped_type& at(const key_type& _Keyval) const
		{	// find element matching _Keyval
		const_iterator _Where = this->lower_bound(_Keyval);
		if (_Where == this->end())
			_Xout_of_range("invalid hash_map<K, T> key");
		return (_Where->second);
		}

	typedef _STD reverse_iterator<iterator> reverse_iterator;
	typedef _STD reverse_iterator<const_iterator> const_reverse_iterator;

	reverse_iterator rbegin() _NOEXCEPT
		{	// return iterator for beginning of reversed mutable sequence
		return (reverse_iterator(this->end()));
		}

	const_reverse_iterator rbegin() const _NOEXCEPT
		{	// return iterator for beginning of reversed nonmutable sequence
		return (const_reverse_iterator(this->end()));
		}

	reverse_iterator rend() _NOEXCEPT
		{	// return iterator for end of reversed mutable sequence
		return (reverse_iterator(this->begin()));
		}

	const_reverse_iterator rend() const _NOEXCEPT
		{	// return iterator for end of reversed nonmutable sequence
		return (const_reverse_iterator(this->begin()));
		}

	const_reverse_iterator crbegin() const _NOEXCEPT
		{	// return iterator for beginning of reversed nonmutable sequence
		return (rbegin());
		}

	const_reverse_iterator crend() const _NOEXCEPT
		{	// return iterator for end of reversed nonmutable sequence
		return (rend());
		}

	using _Mybase::_Unchecked_begin;
	using _Mybase::_Unchecked_end;
	};

template<class _Kty,
	class _Ty,
	class _Tr,
	class _Alloc> inline
	void swap(hash_map<_Kty, _Ty, _Tr, _Alloc>& _Left,
		hash_map<_Kty, _Ty, _Tr, _Alloc>& _Right)
		_NOEXCEPT_COND(_NOEXCEPT_OPER(_Left.swap(_Right))) // strengthened
	{	// swap _Left and _Right hash_maps
	_Left.swap(_Right);
	}

template<class _Kty,
	class _Ty,
	class _Tr,
	class _Alloc> inline
	bool operator==(
		const hash_map<_Kty, _Ty, _Tr, _Alloc>& _Left,
		const hash_map<_Kty, _Ty, _Tr, _Alloc>& _Right)
	{	// test for hash_map equality
	return (_STD _Hash_equal(_Left, _Right));
	}

template<class _Kty,
	class _Ty,
	class _Tr,
	class _Alloc> inline
	bool operator!=(
		const hash_map<_Kty, _Ty, _Tr, _Alloc>& _Left,
		const hash_map<_Kty, _Ty, _Tr, _Alloc>& _Right)
	{	// test for hash_map inequality
	return (!(_Left == _Right));
	}

		// CLASS TEMPLATE hash_multimap
template<class _Kty,
	class _Ty,
	class _Tr = hash_compare<_Kty, less<_Kty> >,
	class _Alloc = allocator<pair<const _Kty, _Ty> > >
	class hash_multimap
		: public _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, true> >
	{	// hash table of {key, mapped} values, non-unique keys
public:
	typedef _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, true> > _Mybase;
	typedef _Kty key_type;
	typedef _Ty mapped_type;
	typedef _Ty referent_type;	// old name, magically gone
	typedef _Tr key_compare;
	typedef typename _Mybase::value_compare value_compare;
	typedef typename _Mybase::value_type value_type;
	typedef typename _Mybase::allocator_type allocator_type;
	typedef typename _Mybase::size_type size_type;
	typedef typename _Mybase::difference_type difference_type;
	typedef typename _Mybase::pointer pointer;
	typedef typename _Mybase::const_pointer const_pointer;
	typedef value_type& reference;
	typedef const value_type& const_reference;
	typedef typename _Mybase::iterator iterator;
	typedef typename _Mybase::const_iterator const_iterator;
	typedef typename _Mybase::_Alnode _Alnode;
	typedef typename _Mybase::_Alnode_traits _Alnode_traits;

	hash_multimap()
		: _Mybase(key_compare(), allocator_type())
		{	// construct empty map from defaults
		}

	explicit hash_multimap(const allocator_type& _Al)
		: _Mybase(key_compare(), _Al)
		{	// construct empty map from defaults, allocator
		}

	hash_multimap(const hash_multimap& _Right)
		: _Mybase(_Right, _Alnode_traits::select_on_container_copy_construction(_Right._List._Getal()))
		{	// construct map by copying _Right
		}

	hash_multimap(const hash_multimap& _Right, const allocator_type& _Al)
		: _Mybase(_Right, _Al)
		{	// construct map by copying _Right, allocator
		}

	explicit hash_multimap(const key_compare& _Traits)
		: _Mybase(_Traits, allocator_type())
		{	// construct empty map from comparator
		}

	hash_multimap(const key_compare& _Traits, const allocator_type& _Al)
		: _Mybase(_Traits, _Al)
		{	// construct empty map from comparator and allocator
		}

	template<class _Iter>
		hash_multimap(_Iter _First, _Iter _Last)
		: _Mybase(key_compare(), allocator_type())
		{	// construct map from sequence, defaults
		insert(_First, _Last);
		}

	template<class _Iter>
		hash_multimap(_Iter _First, _Iter _Last,
			const key_compare& _Traits)
		: _Mybase(_Traits, allocator_type())
		{	// construct map from sequence, comparator
		insert(_First, _Last);
		}

	template<class _Iter>
		hash_multimap(_Iter _First, _Iter _Last,
			const key_compare& _Traits,
			const allocator_type& _Al)
		: _Mybase(_Traits, _Al)
		{	// construct map from sequence, comparator, and allocator
		insert(_First, _Last);
		}

	hash_multimap& operator=(const hash_multimap& _Right)
		{	// assign by copying _Right
		_Mybase::operator=(_Right);
		return (*this);
		}

	hash_multimap(hash_multimap&& _Right)
		: _Mybase(_STD move(_Right))
		{	// construct map by moving _Right
		}

	hash_multimap(hash_multimap&& _Right, const allocator_type& _Al)
		: _Mybase(_STD move(_Right), _Al)
		{	// construct map by moving _Right, allocator
		}

	hash_multimap& operator=(hash_multimap&& _Right)
		{	// assign by moving _Right
		_Mybase::operator=(_STD move(_Right));
		return (*this);
		}

	void swap(hash_multimap& _Right)
		_NOEXCEPT_COND(_NOEXCEPT_OPER(_Mybase::swap(_Right))) // strengthened
		{	// exchange contents with non-movable _Right
		_Mybase::swap(_Right);
		}

	using _Mybase::insert;

	template<class _Valty,
		class = enable_if_t<is_constructible_v<value_type, _Valty>>>
		iterator insert(_Valty&& _Val)
		{	// insert _Val
		return (this->emplace(_STD forward<_Valty>(_Val)).first);
		}

	template<class _Valty,
		class = enable_if_t<is_constructible_v<value_type, _Valty>>>
		iterator insert(const_iterator _Where, _Valty&& _Val)
		{	// insert _Val with hint
		return (this->emplace_hint(_Where, _STD forward<_Valty>(_Val)));
		}

	hash_multimap(_STD initializer_list<value_type> _Ilist)
		: _Mybase(key_compare(), allocator_type())
		{	// construct from initializer_list, defaults
		insert(_Ilist);
		}

	hash_multimap(_STD initializer_list<value_type> _Ilist,
		const key_compare& _Pred)
		: _Mybase(_Pred, allocator_type())
		{	// construct from initializer_list, comparator
		insert(_Ilist);
		}

	hash_multimap(_STD initializer_list<value_type> _Ilist,
		const key_compare& _Pred, const allocator_type& _Al)
		: _Mybase(_Pred, _Al)
		{	// construct from initializer_list, comparator, and allocator
		insert(_Ilist);
		}

	hash_multimap& operator=(_STD initializer_list<value_type> _Ilist)
		{	// assign initializer_list
		this->clear();
		insert(_Ilist);
		return (*this);
		}

	typedef _STD reverse_iterator<iterator> reverse_iterator;
	typedef _STD reverse_iterator<const_iterator> const_reverse_iterator;

	reverse_iterator rbegin() _NOEXCEPT
		{	// return iterator for beginning of reversed mutable sequence
		return (reverse_iterator(this->end()));
		}

	const_reverse_iterator rbegin() const _NOEXCEPT
		{	// return iterator for beginning of reversed nonmutable sequence
		return (const_reverse_iterator(this->end()));
		}

	reverse_iterator rend() _NOEXCEPT
		{	// return iterator for end of reversed mutable sequence
		return (reverse_iterator(this->begin()));
		}

	const_reverse_iterator rend() const _NOEXCEPT
		{	// return iterator for end of reversed nonmutable sequence
		return (const_reverse_iterator(this->begin()));
		}

	const_reverse_iterator crbegin() const _NOEXCEPT
		{	// return iterator for beginning of reversed nonmutable sequence
		return (rbegin());
		}

	const_reverse_iterator crend() const _NOEXCEPT
		{	// return iterator for end of reversed nonmutable sequence
		return (rend());
		}

	using _Mybase::_Unchecked_begin;
	using _Mybase::_Unchecked_end;
	};

template<class _Kty,
	class _Ty,
	class _Tr,
	class _Alloc> inline
	void swap(hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Left,
		hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Right)
		_NOEXCEPT_COND(_NOEXCEPT_OPER(_Left.swap(_Right))) // strengthened
	{	// swap _Left and _Right hash_multimaps
	_Left.swap(_Right);
	}

template<class _Kty,
	class _Ty,
	class _Tr,
	class _Alloc> inline
	bool operator==(
		const hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Left,
		const hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Right)
	{	// test for hash_multimap equality
	return (_STD _Hash_equal(_Left, _Right));
	}

template<class _Kty,
	class _Ty,
	class _Tr,
	class _Alloc> inline
	bool operator!=(
		const hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Left,
		const hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Right)
	{	// test for hash_multimap inequality
	return (!(_Left == _Right));
	}
}	// namespace stdext
_STD_BEGIN
using stdext::hash_map;
using stdext::hash_multimap;
_STD_END

 #pragma pop_macro("new")
 _STL_RESTORE_CLANG_WARNINGS
 #pragma warning(pop)
 #pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _HASH_MAP_ */

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */
