hash_map revision 132720
1// Hashing map implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * Copyright (c) 1996 32 * Silicon Graphics Computer Systems, Inc. 33 * 34 * Permission to use, copy, modify, distribute and sell this software 35 * and its documentation for any purpose is hereby granted without fee, 36 * provided that the above copyright notice appear in all copies and 37 * that both that copyright notice and this permission notice appear 38 * in supporting documentation. Silicon Graphics makes no 39 * representations about the suitability of this software for any 40 * purpose. It is provided "as is" without express or implied warranty. 41 * 42 * 43 * Copyright (c) 1994 44 * Hewlett-Packard Company 45 * 46 * Permission to use, copy, modify, distribute and sell this software 47 * and its documentation for any purpose is hereby granted without fee, 48 * provided that the above copyright notice appear in all copies and 49 * that both that copyright notice and this permission notice appear 50 * in supporting documentation. Hewlett-Packard Company makes no 51 * representations about the suitability of this software for any 52 * purpose. It is provided "as is" without express or implied warranty. 53 * 54 */ 55 56/** @file ext/hash_map 57 * This file is a GNU extension to the Standard C++ Library (possibly 58 * containing extensions from the HP/SGI STL subset). You should only 59 * include this header if you are using GCC 3 or later. 60 */ 61 62#ifndef _HASH_MAP 63#define _HASH_MAP 1 64 65#include <ext/hashtable.h> 66#include <bits/concept_check.h> 67 68namespace __gnu_cxx 69{ 70 using std::equal_to; 71 using std::allocator; 72 using std::pair; 73 using std::_Select1st; 74 75 // Forward declaration of equality operator; needed for friend 76 // declaration. 77 template<class _Key, class _Tp, class _HashFcn = hash<_Key>, 78 class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> > 79 class hash_map; 80 81 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 82 inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&, 83 const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&); 84/** 85 * This is an SGI extension. 86 * @ingroup SGIextensions 87 * @doctodo 88*/ 89template <class _Key, class _Tp, class _HashFcn, class _EqualKey, 90 class _Alloc> 91class hash_map 92{ 93private: 94 typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn, 95 _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht; 96 _Ht _M_ht; 97 98public: 99 typedef typename _Ht::key_type key_type; 100 typedef _Tp data_type; 101 typedef _Tp mapped_type; 102 typedef typename _Ht::value_type value_type; 103 typedef typename _Ht::hasher hasher; 104 typedef typename _Ht::key_equal key_equal; 105 106 typedef typename _Ht::size_type size_type; 107 typedef typename _Ht::difference_type difference_type; 108 typedef typename _Ht::pointer pointer; 109 typedef typename _Ht::const_pointer const_pointer; 110 typedef typename _Ht::reference reference; 111 typedef typename _Ht::const_reference const_reference; 112 113 typedef typename _Ht::iterator iterator; 114 typedef typename _Ht::const_iterator const_iterator; 115 116 typedef typename _Ht::allocator_type allocator_type; 117 118 hasher hash_funct() const { return _M_ht.hash_funct(); } 119 key_equal key_eq() const { return _M_ht.key_eq(); } 120 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 121 122public: 123 hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 124 explicit hash_map(size_type __n) 125 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 126 hash_map(size_type __n, const hasher& __hf) 127 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 128 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, 129 const allocator_type& __a = allocator_type()) 130 : _M_ht(__n, __hf, __eql, __a) {} 131 132 template <class _InputIterator> 133 hash_map(_InputIterator __f, _InputIterator __l) 134 : _M_ht(100, hasher(), key_equal(), allocator_type()) 135 { _M_ht.insert_unique(__f, __l); } 136 template <class _InputIterator> 137 hash_map(_InputIterator __f, _InputIterator __l, size_type __n) 138 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 139 { _M_ht.insert_unique(__f, __l); } 140 template <class _InputIterator> 141 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 142 const hasher& __hf) 143 : _M_ht(__n, __hf, key_equal(), allocator_type()) 144 { _M_ht.insert_unique(__f, __l); } 145 template <class _InputIterator> 146 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 147 const hasher& __hf, const key_equal& __eql, 148 const allocator_type& __a = allocator_type()) 149 : _M_ht(__n, __hf, __eql, __a) 150 { _M_ht.insert_unique(__f, __l); } 151 152public: 153 size_type size() const { return _M_ht.size(); } 154 size_type max_size() const { return _M_ht.max_size(); } 155 bool empty() const { return _M_ht.empty(); } 156 void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); } 157 158 template <class _K1, class _T1, class _HF, class _EqK, class _Al> 159 friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&, 160 const hash_map<_K1, _T1, _HF, _EqK, _Al>&); 161 162 iterator begin() { return _M_ht.begin(); } 163 iterator end() { return _M_ht.end(); } 164 const_iterator begin() const { return _M_ht.begin(); } 165 const_iterator end() const { return _M_ht.end(); } 166 167public: 168 pair<iterator,bool> insert(const value_type& __obj) 169 { return _M_ht.insert_unique(__obj); } 170 template <class _InputIterator> 171 void insert(_InputIterator __f, _InputIterator __l) 172 { _M_ht.insert_unique(__f,__l); } 173 pair<iterator,bool> insert_noresize(const value_type& __obj) 174 { return _M_ht.insert_unique_noresize(__obj); } 175 176 iterator find(const key_type& __key) { return _M_ht.find(__key); } 177 const_iterator find(const key_type& __key) const 178 { return _M_ht.find(__key); } 179 180 _Tp& operator[](const key_type& __key) { 181 return _M_ht.find_or_insert(value_type(__key, _Tp())).second; 182 } 183 184 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 185 186 pair<iterator, iterator> equal_range(const key_type& __key) 187 { return _M_ht.equal_range(__key); } 188 pair<const_iterator, const_iterator> 189 equal_range(const key_type& __key) const 190 { return _M_ht.equal_range(__key); } 191 192 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 193 void erase(iterator __it) { _M_ht.erase(__it); } 194 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 195 void clear() { _M_ht.clear(); } 196 197 void resize(size_type __hint) { _M_ht.resize(__hint); } 198 size_type bucket_count() const { return _M_ht.bucket_count(); } 199 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 200 size_type elems_in_bucket(size_type __n) const 201 { return _M_ht.elems_in_bucket(__n); } 202}; 203 204template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 205inline bool 206operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 207 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 208{ 209 return __hm1._M_ht == __hm2._M_ht; 210} 211 212template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 213inline bool 214operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 215 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) { 216 return !(__hm1 == __hm2); 217} 218 219template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 220inline void 221swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 222 hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 223{ 224 __hm1.swap(__hm2); 225} 226 227// Forward declaration of equality operator; needed for friend declaration. 228 229template <class _Key, class _Tp, 230 class _HashFcn = hash<_Key>, 231 class _EqualKey = equal_to<_Key>, 232 class _Alloc = allocator<_Tp> > 233class hash_multimap; 234 235template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 236inline bool 237operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 238 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2); 239 240/** 241 * This is an SGI extension. 242 * @ingroup SGIextensions 243 * @doctodo 244*/ 245template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc> 246class hash_multimap 247{ 248 // concept requirements 249 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 250 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 251 __glibcxx_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept) 252 __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept) 253 254private: 255 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn, 256 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> 257 _Ht; 258 _Ht _M_ht; 259 260public: 261 typedef typename _Ht::key_type key_type; 262 typedef _Tp data_type; 263 typedef _Tp mapped_type; 264 typedef typename _Ht::value_type value_type; 265 typedef typename _Ht::hasher hasher; 266 typedef typename _Ht::key_equal key_equal; 267 268 typedef typename _Ht::size_type size_type; 269 typedef typename _Ht::difference_type difference_type; 270 typedef typename _Ht::pointer pointer; 271 typedef typename _Ht::const_pointer const_pointer; 272 typedef typename _Ht::reference reference; 273 typedef typename _Ht::const_reference const_reference; 274 275 typedef typename _Ht::iterator iterator; 276 typedef typename _Ht::const_iterator const_iterator; 277 278 typedef typename _Ht::allocator_type allocator_type; 279 280 hasher hash_funct() const { return _M_ht.hash_funct(); } 281 key_equal key_eq() const { return _M_ht.key_eq(); } 282 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 283 284public: 285 hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 286 explicit hash_multimap(size_type __n) 287 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 288 hash_multimap(size_type __n, const hasher& __hf) 289 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 290 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, 291 const allocator_type& __a = allocator_type()) 292 : _M_ht(__n, __hf, __eql, __a) {} 293 294 template <class _InputIterator> 295 hash_multimap(_InputIterator __f, _InputIterator __l) 296 : _M_ht(100, hasher(), key_equal(), allocator_type()) 297 { _M_ht.insert_equal(__f, __l); } 298 template <class _InputIterator> 299 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) 300 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 301 { _M_ht.insert_equal(__f, __l); } 302 template <class _InputIterator> 303 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 304 const hasher& __hf) 305 : _M_ht(__n, __hf, key_equal(), allocator_type()) 306 { _M_ht.insert_equal(__f, __l); } 307 template <class _InputIterator> 308 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 309 const hasher& __hf, const key_equal& __eql, 310 const allocator_type& __a = allocator_type()) 311 : _M_ht(__n, __hf, __eql, __a) 312 { _M_ht.insert_equal(__f, __l); } 313 314public: 315 size_type size() const { return _M_ht.size(); } 316 size_type max_size() const { return _M_ht.max_size(); } 317 bool empty() const { return _M_ht.empty(); } 318 void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); } 319 320 template <class _K1, class _T1, class _HF, class _EqK, class _Al> 321 friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&, 322 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&); 323 324 iterator begin() { return _M_ht.begin(); } 325 iterator end() { return _M_ht.end(); } 326 const_iterator begin() const { return _M_ht.begin(); } 327 const_iterator end() const { return _M_ht.end(); } 328 329public: 330 iterator insert(const value_type& __obj) 331 { return _M_ht.insert_equal(__obj); } 332 template <class _InputIterator> 333 void insert(_InputIterator __f, _InputIterator __l) 334 { _M_ht.insert_equal(__f,__l); } 335 iterator insert_noresize(const value_type& __obj) 336 { return _M_ht.insert_equal_noresize(__obj); } 337 338 iterator find(const key_type& __key) { return _M_ht.find(__key); } 339 const_iterator find(const key_type& __key) const 340 { return _M_ht.find(__key); } 341 342 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 343 344 pair<iterator, iterator> equal_range(const key_type& __key) 345 { return _M_ht.equal_range(__key); } 346 pair<const_iterator, const_iterator> 347 equal_range(const key_type& __key) const 348 { return _M_ht.equal_range(__key); } 349 350 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 351 void erase(iterator __it) { _M_ht.erase(__it); } 352 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 353 void clear() { _M_ht.clear(); } 354 355public: 356 void resize(size_type __hint) { _M_ht.resize(__hint); } 357 size_type bucket_count() const { return _M_ht.bucket_count(); } 358 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 359 size_type elems_in_bucket(size_type __n) const 360 { return _M_ht.elems_in_bucket(__n); } 361}; 362 363template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 364inline bool 365operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 366 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) 367{ 368 return __hm1._M_ht == __hm2._M_ht; 369} 370 371template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 372inline bool 373operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 374 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) { 375 return !(__hm1 == __hm2); 376} 377 378template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 379inline void 380swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 381 hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 382{ 383 __hm1.swap(__hm2); 384} 385 386} // namespace __gnu_cxx 387 388namespace std 389{ 390// Specialization of insert_iterator so that it will work for hash_map 391// and hash_multimap. 392 393template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 394class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 395protected: 396 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 397 _Container* container; 398public: 399 typedef _Container container_type; 400 typedef output_iterator_tag iterator_category; 401 typedef void value_type; 402 typedef void difference_type; 403 typedef void pointer; 404 typedef void reference; 405 406 insert_iterator(_Container& __x) : container(&__x) {} 407 insert_iterator(_Container& __x, typename _Container::iterator) 408 : container(&__x) {} 409 insert_iterator<_Container>& 410 operator=(const typename _Container::value_type& __value) { 411 container->insert(__value); 412 return *this; 413 } 414 insert_iterator<_Container>& operator*() { return *this; } 415 insert_iterator<_Container>& operator++() { return *this; } 416 insert_iterator<_Container>& operator++(int) { return *this; } 417}; 418 419template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 420class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 421protected: 422 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 423 _Container* container; 424 typename _Container::iterator iter; 425public: 426 typedef _Container container_type; 427 typedef output_iterator_tag iterator_category; 428 typedef void value_type; 429 typedef void difference_type; 430 typedef void pointer; 431 typedef void reference; 432 433 insert_iterator(_Container& __x) : container(&__x) {} 434 insert_iterator(_Container& __x, typename _Container::iterator) 435 : container(&__x) {} 436 insert_iterator<_Container>& 437 operator=(const typename _Container::value_type& __value) { 438 container->insert(__value); 439 return *this; 440 } 441 insert_iterator<_Container>& operator*() { return *this; } 442 insert_iterator<_Container>& operator++() { return *this; } 443 insert_iterator<_Container>& operator++(int) { return *this; } 444}; 445} // namespace std 446 447#endif 448