// -*- C++ -*-//===-------------------------- hash_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_HASH_MAP#define _LIBCPP_HASH_MAP/*hash_map synopsisnamespace __gnu_cxx{template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,class Alloc = allocator<pair<const Key, T>>>class hash_map{public:// typestypedef 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;explicit hash_map(size_type n = 193, const hasher& hf = hasher(),const key_equal& eql = key_equal(),const allocator_type& a = allocator_type());template <class InputIterator>hash_map(InputIterator f, InputIterator l,size_type n = 193, const hasher& hf = hasher(),const key_equal& eql = key_equal(),const allocator_type& a = allocator_type());hash_map(const hash_map&);~hash_map();hash_map& operator=(const hash_map&);allocator_type get_allocator() const;bool empty() const;size_type size() const;size_type max_size() const;iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;pair<iterator, bool> insert(const value_type& obj);template <class InputIterator>void insert(InputIterator first, InputIterator last);void erase(const_iterator position);size_type erase(const key_type& k);void erase(const_iterator first, const_iterator last);void clear();void swap(hash_map&);hasher hash_funct() 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);size_type bucket_count() const;size_type max_bucket_count() const;size_type elems_in_bucket(size_type n) const;void resize(size_type n);};template <class Key, class T, class Hash, class Pred, class Alloc>void swap(hash_map<Key, T, Hash, Pred, Alloc>& x,hash_map<Key, T, Hash, Pred, Alloc>& y);template <class Key, class T, class Hash, class Pred, class Alloc>booloperator==(const hash_map<Key, T, Hash, Pred, Alloc>& x,const hash_map<Key, T, Hash, Pred, Alloc>& y);template <class Key, class T, class Hash, class Pred, class Alloc>booloperator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x,const hash_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 hash_multimap{public:// typestypedef 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;explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(),const key_equal& eql = key_equal(),const allocator_type& a = allocator_type());template <class InputIterator>hash_multimap(InputIterator f, InputIterator l,size_type n = 193, const hasher& hf = hasher(),const key_equal& eql = key_equal(),const allocator_type& a = allocator_type());explicit hash_multimap(const allocator_type&);hash_multimap(const hash_multimap&);~hash_multimap();hash_multimap& operator=(const hash_multimap&);allocator_type get_allocator() const;bool empty() const;size_type size() const;size_type max_size() const;iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;iterator insert(const value_type& obj);template <class InputIterator>void insert(InputIterator first, InputIterator last);void erase(const_iterator position);size_type erase(const key_type& k);void erase(const_iterator first, const_iterator last);void clear();void swap(hash_multimap&);hasher hash_funct() 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;size_type max_bucket_count() const;size_type elems_in_bucket(size_type n) const;void resize(size_type n);};template <class Key, class T, class Hash, class Pred, class Alloc>void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x,hash_multimap<Key, T, Hash, Pred, Alloc>& y);template <class Key, class T, class Hash, class Pred, class Alloc>booloperator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,const hash_multimap<Key, T, Hash, Pred, Alloc>& y);template <class Key, class T, class Hash, class Pred, class Alloc>booloperator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,const hash_multimap<Key, T, Hash, Pred, Alloc>& y);} // __gnu_cxx*/#include <__config>#include <__hash_table>#include <functional>#include <stdexcept>#include <type_traits>#include <ext/__hash>#if __DEPRECATED#if defined(_MSC_VER) && ! defined(__clang__)_LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>")#else# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>#endif#endif#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)#pragma GCC system_header#endifnamespace __gnu_cxx {using namespace std;template <class _Tp, class _Hash,bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>class __hash_map_hasher: private _Hash{public:_LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {}_LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {}_LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;}_LIBCPP_INLINE_VISIBILITYsize_t operator()(const _Tp& __x) const{return static_cast<const _Hash&>(*this)(__x.first);}_LIBCPP_INLINE_VISIBILITYsize_t operator()(const typename _Tp::first_type& __x) const{return static_cast<const _Hash&>(*this)(__x);}};template <class _Tp, class _Hash>class __hash_map_hasher<_Tp, _Hash, false>{_Hash __hash_;public:_LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {}_LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {}_LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;}_LIBCPP_INLINE_VISIBILITYsize_t operator()(const _Tp& __x) const{return __hash_(__x.first);}_LIBCPP_INLINE_VISIBILITYsize_t operator()(const typename _Tp::first_type& __x) const{return __hash_(__x);}};template <class _Tp, class _Pred,bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>class __hash_map_equal: private _Pred{public:_LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {}_LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {}_LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;}_LIBCPP_INLINE_VISIBILITYbool operator()(const _Tp& __x, const _Tp& __y) const{return static_cast<const _Pred&>(*this)(__x.first, __y.first);}_LIBCPP_INLINE_VISIBILITYbool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const{return static_cast<const _Pred&>(*this)(__x, __y.first);}_LIBCPP_INLINE_VISIBILITYbool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const{return static_cast<const _Pred&>(*this)(__x.first, __y);}_LIBCPP_INLINE_VISIBILITYbool operator()(const typename _Tp::first_type& __x,const typename _Tp::first_type& __y) const{return static_cast<const _Pred&>(*this)(__x, __y);}};template <class _Tp, class _Pred>class __hash_map_equal<_Tp, _Pred, false>{_Pred __pred_;public:_LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {}_LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {}_LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;}_LIBCPP_INLINE_VISIBILITYbool operator()(const _Tp& __x, const _Tp& __y) const{return __pred_(__x.first, __y.first);}_LIBCPP_INLINE_VISIBILITYbool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const{return __pred_(__x, __y.first);}_LIBCPP_INLINE_VISIBILITYbool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const{return __pred_(__x.first, __y);}_LIBCPP_INLINE_VISIBILITYbool operator()(const typename _Tp::first_type& __x,const typename _Tp::first_type& __y) const{return __pred_(__x, __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::first_type first_type;typedef typename 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_VISIBILITYexplicit __hash_map_node_destructor(allocator_type& __na): __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): __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_VISIBILITYvoid operator()(pointer __p){if (__second_constructed)__alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));if (__first_constructed)__alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));if (__p)__alloc_traits::deallocate(__na_, __p, 1);}};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::first_type key_type;typedef typename _HashIterator::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_ALIASESrebind<value_type>#elserebind<value_type>::other#endifpointer;_LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {}_LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {}_LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();}_LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();}_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_VISIBILITYbool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y){return __x.__i_ == __y.__i_;}friend _LIBCPP_INLINE_VISIBILITYbool 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 hash_map;template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_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::first_type key_type;typedef typename _HashIterator::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_ALIASESrebind<const value_type>#elserebind<const value_type>::other#endifpointer;_LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {}_LIBCPP_INLINE_VISIBILITY__hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}_LIBCPP_INLINE_VISIBILITY__hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i): __i_(__i.__i_) {}_LIBCPP_INLINE_VISIBILITYreference operator*() const {return *operator->();}_LIBCPP_INLINE_VISIBILITYpointer operator->() const {return (pointer)__i_.operator->();}_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_VISIBILITYbool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y){return __x.__i_ == __y.__i_;}friend _LIBCPP_INLINE_VISIBILITYbool 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 hash_map;template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_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 hash_map{public:// typestypedef _Key key_type;typedef _Tp mapped_type;typedef _Tp data_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;private:typedef pair<key_type, mapped_type> __value_type;typedef __hash_map_hasher<__value_type, hasher> __hasher;typedef __hash_map_equal<__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;_LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);}explicit hash_map(size_type __n, const hasher& __hf = hasher(),const key_equal& __eql = key_equal());hash_map(size_type __n, const hasher& __hf,const key_equal& __eql,const allocator_type& __a);template <class _InputIterator>hash_map(_InputIterator __first, _InputIterator __last);template <class _InputIterator>hash_map(_InputIterator __first, _InputIterator __last,size_type __n, const hasher& __hf = hasher(),const key_equal& __eql = key_equal());template <class _InputIterator>hash_map(_InputIterator __first, _InputIterator __last,size_type __n, const hasher& __hf,const key_equal& __eql,const allocator_type& __a);hash_map(const hash_map& __u);_LIBCPP_INLINE_VISIBILITYallocator_type get_allocator() const{return allocator_type(__table_.__node_alloc());}_LIBCPP_INLINE_VISIBILITYbool empty() const {return __table_.size() == 0;}_LIBCPP_INLINE_VISIBILITYsize_type size() const {return __table_.size();}_LIBCPP_INLINE_VISIBILITYsize_type max_size() const {return __table_.max_size();}_LIBCPP_INLINE_VISIBILITYiterator begin() {return __table_.begin();}_LIBCPP_INLINE_VISIBILITYiterator end() {return __table_.end();}_LIBCPP_INLINE_VISIBILITYconst_iterator begin() const {return __table_.begin();}_LIBCPP_INLINE_VISIBILITYconst_iterator end() const {return __table_.end();}_LIBCPP_INLINE_VISIBILITYpair<iterator, bool> insert(const value_type& __x){return __table_.__insert_unique(__x);}_LIBCPP_INLINE_VISIBILITYiterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}template <class _InputIterator>void insert(_InputIterator __first, _InputIterator __last);_LIBCPP_INLINE_VISIBILITYvoid erase(const_iterator __p) {__table_.erase(__p.__i_);}_LIBCPP_INLINE_VISIBILITYsize_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}_LIBCPP_INLINE_VISIBILITYvoid erase(const_iterator __first, const_iterator __last){__table_.erase(__first.__i_, __last.__i_);}_LIBCPP_INLINE_VISIBILITYvoid clear() {__table_.clear();}_LIBCPP_INLINE_VISIBILITYvoid swap(hash_map& __u) {__table_.swap(__u.__table_);}_LIBCPP_INLINE_VISIBILITYhasher hash_funct() const{return __table_.hash_function().hash_function();}_LIBCPP_INLINE_VISIBILITYkey_equal key_eq() const{return __table_.key_eq().key_eq();}_LIBCPP_INLINE_VISIBILITYiterator find(const key_type& __k) {return __table_.find(__k);}_LIBCPP_INLINE_VISIBILITYconst_iterator find(const key_type& __k) const {return __table_.find(__k);}_LIBCPP_INLINE_VISIBILITYsize_type count(const key_type& __k) const {return __table_.__count_unique(__k);}_LIBCPP_INLINE_VISIBILITYpair<iterator, iterator> equal_range(const key_type& __k){return __table_.__equal_range_unique(__k);}_LIBCPP_INLINE_VISIBILITYpair<const_iterator, const_iterator> equal_range(const key_type& __k) const{return __table_.__equal_range_unique(__k);}mapped_type& operator[](const key_type& __k);_LIBCPP_INLINE_VISIBILITYsize_type bucket_count() const {return __table_.bucket_count();}_LIBCPP_INLINE_VISIBILITYsize_type max_bucket_count() const {return __table_.max_bucket_count();}_LIBCPP_INLINE_VISIBILITYsize_type elems_in_bucket(size_type __n) const{return __table_.bucket_size(__n);}_LIBCPP_INLINE_VISIBILITYvoid resize(size_type __n) {__table_.rehash(__n);}private:__node_holder __construct_node(const key_type& __k);};template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(size_type __n, const hasher& __hf, const key_equal& __eql): __table_(__hf, __eql){__table_.rehash(__n);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,const allocator_type& __a): __table_(__hf, __eql, __a){__table_.rehash(__n);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>template <class _InputIterator>hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last){__table_.rehash(193);insert(__first, __last);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>template <class _InputIterator>hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last, size_type __n,const hasher& __hf, const key_equal& __eql): __table_(__hf, __eql){__table_.rehash(__n);insert(__first, __last);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>template <class _InputIterator>hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last, size_type __n,const hasher& __hf, const key_equal& __eql, const allocator_type& __a): __table_(__hf, __eql, __a){__table_.rehash(__n);insert(__first, __last);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(const hash_map& __u): __table_(__u.__table_){__table_.rehash(__u.bucket_count());insert(__u.begin(), __u.end());}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holderhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k){__node_allocator& __na = __table_.__node_alloc();__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));__node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);__h.get_deleter().__first_constructed = true;__node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));__h.get_deleter().__second_constructed = true;return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>template <class _InputIterator>inline _LIBCPP_INLINE_VISIBILITYvoidhash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,_InputIterator __last){for (; __first != __last; ++__first)__table_.__insert_unique(*__first);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>_Tp&hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k){iterator __i = find(__k);if (__i != end())return __i->second;__node_holder __h = __construct_node(__k);pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());__h.release();return __r.first->second;}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>inline _LIBCPP_INLINE_VISIBILITYvoidswap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){__x.swap(__y);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>booloperator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){if (__x.size() != __y.size())return false;typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iteratorconst_iterator;for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();__i != __ex; ++__i){const_iterator __j = __y.find(__i->first);if (__j == __ey || !(*__i == *__j))return false;}return true;}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>inline _LIBCPP_INLINE_VISIBILITYbooloperator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){return !(__x == __y);}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 hash_multimap{public:// typestypedef _Key key_type;typedef _Tp mapped_type;typedef _Tp data_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;private:typedef pair<key_type, mapped_type> __value_type;typedef __hash_map_hasher<__value_type, hasher> __hasher;typedef __hash_map_equal<__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_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;_LIBCPP_INLINE_VISIBILITYhash_multimap() {__table_.rehash(193);}explicit hash_multimap(size_type __n, const hasher& __hf = hasher(),const key_equal& __eql = key_equal());hash_multimap(size_type __n, const hasher& __hf,const key_equal& __eql,const allocator_type& __a);template <class _InputIterator>hash_multimap(_InputIterator __first, _InputIterator __last);template <class _InputIterator>hash_multimap(_InputIterator __first, _InputIterator __last,size_type __n, const hasher& __hf = hasher(),const key_equal& __eql = key_equal());template <class _InputIterator>hash_multimap(_InputIterator __first, _InputIterator __last,size_type __n, const hasher& __hf,const key_equal& __eql,const allocator_type& __a);hash_multimap(const hash_multimap& __u);_LIBCPP_INLINE_VISIBILITYallocator_type get_allocator() const{return allocator_type(__table_.__node_alloc());}_LIBCPP_INLINE_VISIBILITYbool empty() const {return __table_.size() == 0;}_LIBCPP_INLINE_VISIBILITYsize_type size() const {return __table_.size();}_LIBCPP_INLINE_VISIBILITYsize_type max_size() const {return __table_.max_size();}_LIBCPP_INLINE_VISIBILITYiterator begin() {return __table_.begin();}_LIBCPP_INLINE_VISIBILITYiterator end() {return __table_.end();}_LIBCPP_INLINE_VISIBILITYconst_iterator begin() const {return __table_.begin();}_LIBCPP_INLINE_VISIBILITYconst_iterator end() const {return __table_.end();}_LIBCPP_INLINE_VISIBILITYiterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}_LIBCPP_INLINE_VISIBILITYiterator insert(const_iterator, const value_type& __x) {return insert(__x);}template <class _InputIterator>void insert(_InputIterator __first, _InputIterator __last);_LIBCPP_INLINE_VISIBILITYvoid erase(const_iterator __p) {__table_.erase(__p.__i_);}_LIBCPP_INLINE_VISIBILITYsize_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}_LIBCPP_INLINE_VISIBILITYvoid erase(const_iterator __first, const_iterator __last){__table_.erase(__first.__i_, __last.__i_);}_LIBCPP_INLINE_VISIBILITYvoid clear() {__table_.clear();}_LIBCPP_INLINE_VISIBILITYvoid swap(hash_multimap& __u) {__table_.swap(__u.__table_);}_LIBCPP_INLINE_VISIBILITYhasher hash_funct() const{return __table_.hash_function().hash_function();}_LIBCPP_INLINE_VISIBILITYkey_equal key_eq() const{return __table_.key_eq().key_eq();}_LIBCPP_INLINE_VISIBILITYiterator find(const key_type& __k) {return __table_.find(__k);}_LIBCPP_INLINE_VISIBILITYconst_iterator find(const key_type& __k) const {return __table_.find(__k);}_LIBCPP_INLINE_VISIBILITYsize_type count(const key_type& __k) const {return __table_.__count_multi(__k);}_LIBCPP_INLINE_VISIBILITYpair<iterator, iterator> equal_range(const key_type& __k){return __table_.__equal_range_multi(__k);}_LIBCPP_INLINE_VISIBILITYpair<const_iterator, const_iterator> equal_range(const key_type& __k) const{return __table_.__equal_range_multi(__k);}_LIBCPP_INLINE_VISIBILITYsize_type bucket_count() const {return __table_.bucket_count();}_LIBCPP_INLINE_VISIBILITYsize_type max_bucket_count() const {return __table_.max_bucket_count();}_LIBCPP_INLINE_VISIBILITYsize_type elems_in_bucket(size_type __n) const{return __table_.bucket_size(__n);}_LIBCPP_INLINE_VISIBILITYvoid resize(size_type __n) {__table_.rehash(__n);}};template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql): __table_(__hf, __eql){__table_.rehash(__n);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,const allocator_type& __a): __table_(__hf, __eql, __a){__table_.rehash(__n);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>template <class _InputIterator>hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last){__table_.rehash(193);insert(__first, __last);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>template <class _InputIterator>hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last, size_type __n,const hasher& __hf, const key_equal& __eql): __table_(__hf, __eql){__table_.rehash(__n);insert(__first, __last);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>template <class _InputIterator>hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last, size_type __n,const hasher& __hf, const key_equal& __eql, const allocator_type& __a): __table_(__hf, __eql, __a){__table_.rehash(__n);insert(__first, __last);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(const hash_multimap& __u): __table_(__u.__table_){__table_.rehash(__u.bucket_count());insert(__u.begin(), __u.end());}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>template <class _InputIterator>inline _LIBCPP_INLINE_VISIBILITYvoidhash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,_InputIterator __last){for (; __first != __last; ++__first)__table_.__insert_multi(*__first);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>inline _LIBCPP_INLINE_VISIBILITYvoidswap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){__x.swap(__y);}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>booloperator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){if (__x.size() != __y.size())return false;typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iteratorconst_iterator;typedef pair<const_iterator, const_iterator> _EqRng;for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;){_EqRng __xeq = __x.equal_range(__i->first);_EqRng __yeq = __y.equal_range(__i->first);if (_VSTD::distance(__xeq.first, __xeq.second) !=_VSTD::distance(__yeq.first, __yeq.second) ||!_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))return false;__i = __xeq.second;}return true;}template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>inline _LIBCPP_INLINE_VISIBILITYbooloperator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y){return !(__x == __y);}} // __gnu_cxx#endif // _LIBCPP_HASH_MAP