// Hashing map implementation -*- C++ -*-// Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc.//// This file is part of the GNU ISO C++ Library. This library is free// software; you can redistribute it and/or modify it under the// terms of the GNU General Public License as published by the// Free Software Foundation; either version 2, or (at your option)// any later version.// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the// GNU General Public License for more details.// You should have received a copy of the GNU General Public License along// with this library; see the file COPYING. If not, write to the Free// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,// USA.// As a special exception, you may use this file as part of a free software// library without restriction. Specifically, if other files instantiate// templates or use macros or inline functions from this file, or you compile// this file and link it with other files to produce an executable, this// file does not by itself cause the resulting executable to be covered by// the GNU General Public License. This exception does not however// invalidate any other reasons why the executable file might be covered by// the GNU General Public License./** Copyright (c) 1996* Silicon Graphics Computer Systems, Inc.** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation. Silicon Graphics makes no* representations about the suitability of this software for any* purpose. It is provided "as is" without express or implied warranty.*** Copyright (c) 1994* Hewlett-Packard Company** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation. Hewlett-Packard Company makes no* representations about the suitability of this software for any* purpose. It is provided "as is" without express or implied warranty.**//** @file ext/hash_map* This file is a GNU extension to the Standard C++ Library (possibly* containing extensions from the HP/SGI STL subset).*/#ifndef _HASH_MAP#define _HASH_MAP 1#include <ext/hashtable.h>#include <bits/concept_check.h>namespace __gnu_cxx{using std::equal_to;using std::allocator;using std::pair;using std::_Select1st;// Forward declaration of equality operator; needed for friend// declaration.template<class _Key, class _Tp, class _HashFcn = hash<_Key>,class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >class hash_map;template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>inline booloperator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);/*** This is an SGI extension.* @ingroup SGIextensions* @doctodo*/template <class _Key, class _Tp, class _HashFcn, class _EqualKey,class _Alloc>class hash_map{private:typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFcn,_Select1st<pair<const _Key, _Tp> >,_EqualKey, _Alloc> _Ht;_Ht _M_ht;public:typedef typename _Ht::key_type key_type;typedef _Tp data_type;typedef _Tp mapped_type;typedef typename _Ht::value_type value_type;typedef typename _Ht::hasher hasher;typedef typename _Ht::key_equal key_equal;typedef typename _Ht::size_type size_type;typedef typename _Ht::difference_type difference_type;typedef typename _Ht::pointer pointer;typedef typename _Ht::const_pointer const_pointer;typedef typename _Ht::reference reference;typedef typename _Ht::const_reference const_reference;typedef typename _Ht::iterator iterator;typedef typename _Ht::const_iterator const_iterator;typedef typename _Ht::allocator_type allocator_type;hasherhash_funct() const{ return _M_ht.hash_funct(); }key_equalkey_eq() const{ return _M_ht.key_eq(); }allocator_typeget_allocator() const{ return _M_ht.get_allocator(); }public:hash_map(): _M_ht(100, hasher(), key_equal(), allocator_type()) {}explicithash_map(size_type __n): _M_ht(__n, hasher(), key_equal(), allocator_type()) {}hash_map(size_type __n, const hasher& __hf): _M_ht(__n, __hf, key_equal(), allocator_type()) {}hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,const allocator_type& __a = allocator_type()): _M_ht(__n, __hf, __eql, __a) {}template <class _InputIterator>hash_map(_InputIterator __f, _InputIterator __l): _M_ht(100, hasher(), key_equal(), allocator_type()){ _M_ht.insert_unique(__f, __l); }template <class _InputIterator>hash_map(_InputIterator __f, _InputIterator __l, size_type __n): _M_ht(__n, hasher(), key_equal(), allocator_type()){ _M_ht.insert_unique(__f, __l); }template <class _InputIterator>hash_map(_InputIterator __f, _InputIterator __l, size_type __n,const hasher& __hf): _M_ht(__n, __hf, key_equal(), allocator_type()){ _M_ht.insert_unique(__f, __l); }template <class _InputIterator>hash_map(_InputIterator __f, _InputIterator __l, size_type __n,const hasher& __hf, const key_equal& __eql,const allocator_type& __a = allocator_type()): _M_ht(__n, __hf, __eql, __a){ _M_ht.insert_unique(__f, __l); }public:size_typesize() const{ return _M_ht.size(); }size_typemax_size() const{ return _M_ht.max_size(); }boolempty() const{ return _M_ht.empty(); }voidswap(hash_map& __hs){ _M_ht.swap(__hs._M_ht); }template <class _K1, class _T1, class _HF, class _EqK, class _Al>friend booloperator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,const hash_map<_K1, _T1, _HF, _EqK, _Al>&);iteratorbegin(){ return _M_ht.begin(); }iteratorend(){ return _M_ht.end(); }const_iteratorbegin() const{ return _M_ht.begin(); }const_iteratorend() const{ return _M_ht.end(); }public:pair<iterator, bool>insert(const value_type& __obj){ return _M_ht.insert_unique(__obj); }template <class _InputIterator>voidinsert(_InputIterator __f, _InputIterator __l){ _M_ht.insert_unique(__f, __l); }pair<iterator, bool>insert_noresize(const value_type& __obj){ return _M_ht.insert_unique_noresize(__obj); }iteratorfind(const key_type& __key){ return _M_ht.find(__key); }const_iteratorfind(const key_type& __key) const{ return _M_ht.find(__key); }_Tp&operator[](const key_type& __key){ return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }size_typecount(const key_type& __key) const{ return _M_ht.count(__key); }pair<iterator, iterator>equal_range(const key_type& __key){ return _M_ht.equal_range(__key); }pair<const_iterator, const_iterator>equal_range(const key_type& __key) const{ return _M_ht.equal_range(__key); }size_typeerase(const key_type& __key){return _M_ht.erase(__key); }voiderase(iterator __it){ _M_ht.erase(__it); }voiderase(iterator __f, iterator __l){ _M_ht.erase(__f, __l); }voidclear(){ _M_ht.clear(); }voidresize(size_type __hint){ _M_ht.resize(__hint); }size_typebucket_count() const{ return _M_ht.bucket_count(); }size_typemax_bucket_count() const{ return _M_ht.max_bucket_count(); }size_typeelems_in_bucket(size_type __n) const{ return _M_ht.elems_in_bucket(__n); }};template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>inline booloperator==(const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2){ return __hm1._M_ht == __hm2._M_ht; }template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>inline booloperator!=(const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2){ return !(__hm1 == __hm2); }template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>inline voidswap(hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2){ __hm1.swap(__hm2); }// Forward declaration of equality operator; needed for friend declaration.template <class _Key, class _Tp,class _HashFcn = hash<_Key>,class _EqualKey = equal_to<_Key>,class _Alloc = allocator<_Tp> >class hash_multimap;template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>inline booloperator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2);/*** This is an SGI extension.* @ingroup SGIextensions* @doctodo*/template <class _Key, class _Tp, class _HashFcn, class _EqualKey,class _Alloc>class hash_multimap{// concept requirements__glibcxx_class_requires(_Key, _SGIAssignableConcept)__glibcxx_class_requires(_Tp, _SGIAssignableConcept)__glibcxx_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept)__glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)private:typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,_Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>_Ht;_Ht _M_ht;public:typedef typename _Ht::key_type key_type;typedef _Tp data_type;typedef _Tp mapped_type;typedef typename _Ht::value_type value_type;typedef typename _Ht::hasher hasher;typedef typename _Ht::key_equal key_equal;typedef typename _Ht::size_type size_type;typedef typename _Ht::difference_type difference_type;typedef typename _Ht::pointer pointer;typedef typename _Ht::const_pointer const_pointer;typedef typename _Ht::reference reference;typedef typename _Ht::const_reference const_reference;typedef typename _Ht::iterator iterator;typedef typename _Ht::const_iterator const_iterator;typedef typename _Ht::allocator_type allocator_type;hasherhash_funct() const{ return _M_ht.hash_funct(); }key_equalkey_eq() const{ return _M_ht.key_eq(); }allocator_typeget_allocator() const{ return _M_ht.get_allocator(); }public:hash_multimap(): _M_ht(100, hasher(), key_equal(), allocator_type()) {}explicithash_multimap(size_type __n): _M_ht(__n, hasher(), key_equal(), allocator_type()) {}hash_multimap(size_type __n, const hasher& __hf): _M_ht(__n, __hf, key_equal(), allocator_type()) {}hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,const allocator_type& __a = allocator_type()): _M_ht(__n, __hf, __eql, __a) {}template <class _InputIterator>hash_multimap(_InputIterator __f, _InputIterator __l): _M_ht(100, hasher(), key_equal(), allocator_type()){ _M_ht.insert_equal(__f, __l); }template <class _InputIterator>hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n): _M_ht(__n, hasher(), key_equal(), allocator_type()){ _M_ht.insert_equal(__f, __l); }template <class _InputIterator>hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,const hasher& __hf): _M_ht(__n, __hf, key_equal(), allocator_type()){ _M_ht.insert_equal(__f, __l); }template <class _InputIterator>hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,const hasher& __hf, const key_equal& __eql,const allocator_type& __a = allocator_type()): _M_ht(__n, __hf, __eql, __a){ _M_ht.insert_equal(__f, __l); }public:size_typesize() const{ return _M_ht.size(); }size_typemax_size() const{ return _M_ht.max_size(); }boolempty() const{ return _M_ht.empty(); }voidswap(hash_multimap& __hs){ _M_ht.swap(__hs._M_ht); }template <class _K1, class _T1, class _HF, class _EqK, class _Al>friend booloperator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);iteratorbegin(){ return _M_ht.begin(); }iteratorend(){ return _M_ht.end(); }const_iteratorbegin() const{ return _M_ht.begin(); }const_iteratorend() const{ return _M_ht.end(); }public:iteratorinsert(const value_type& __obj){ return _M_ht.insert_equal(__obj); }template <class _InputIterator>voidinsert(_InputIterator __f, _InputIterator __l){ _M_ht.insert_equal(__f,__l); }iteratorinsert_noresize(const value_type& __obj){ return _M_ht.insert_equal_noresize(__obj); }iteratorfind(const key_type& __key){ return _M_ht.find(__key); }const_iteratorfind(const key_type& __key) const{ return _M_ht.find(__key); }size_typecount(const key_type& __key) const{ return _M_ht.count(__key); }pair<iterator, iterator>equal_range(const key_type& __key){ return _M_ht.equal_range(__key); }pair<const_iterator, const_iterator>equal_range(const key_type& __key) const{ return _M_ht.equal_range(__key); }size_typeerase(const key_type& __key){ return _M_ht.erase(__key); }voiderase(iterator __it){ _M_ht.erase(__it); }voiderase(iterator __f, iterator __l){ _M_ht.erase(__f, __l); }voidclear(){ _M_ht.clear(); }public:voidresize(size_type __hint){ _M_ht.resize(__hint); }size_typebucket_count() const{ return _M_ht.bucket_count(); }size_typemax_bucket_count() const{ return _M_ht.max_bucket_count(); }size_typeelems_in_bucket(size_type __n) const{ return _M_ht.elems_in_bucket(__n); }};template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>inline booloperator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2){ return __hm1._M_ht == __hm2._M_ht; }template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>inline booloperator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2){ return !(__hm1 == __hm2); }template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>inline voidswap(hash_multimap<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,hash_multimap<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2){ __hm1.swap(__hm2); }} // namespace __gnu_cxxnamespace std{// Specialization of insert_iterator so that it will work for hash_map// and hash_multimap.template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,_EqKey, _Alloc> >{protected:typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>_Container;_Container* container;public:typedef _Container container_type;typedef output_iterator_tag iterator_category;typedef void value_type;typedef void difference_type;typedef void pointer;typedef void reference;insert_iterator(_Container& __x): container(&__x) {}insert_iterator(_Container& __x, typename _Container::iterator): container(&__x) {}insert_iterator<_Container>&operator=(const typename _Container::value_type& __value){container->insert(__value);return *this;}insert_iterator<_Container>&operator*(){ return *this; }insert_iterator<_Container>&operator++() { return *this; }insert_iterator<_Container>&operator++(int){ return *this; }};template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,_EqKey, _Alloc> >{protected:typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>_Container;_Container* container;typename _Container::iterator iter;public:typedef _Container container_type;typedef output_iterator_tag iterator_category;typedef void value_type;typedef void difference_type;typedef void pointer;typedef void reference;insert_iterator(_Container& __x): container(&__x) {}insert_iterator(_Container& __x, typename _Container::iterator): container(&__x) {}insert_iterator<_Container>&operator=(const typename _Container::value_type& __value){container->insert(__value);return *this;}insert_iterator<_Container>&operator*(){ return *this; }insert_iterator<_Container>&operator++(){ return *this; }insert_iterator<_Container>&operator++(int){ return *this; }};} // namespace std#ifdef _GLIBCXX_DEBUG# include <debug/hash_map>#endif#endif