1// Hashing map implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009, 2010 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 3, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// Under Section 7 of GPL version 3, you are granted additional 18// permissions described in the GCC Runtime Library Exception, version 19// 3.1, as published by the Free Software Foundation. 20 21// You should have received a copy of the GNU General Public License and 22// a copy of the GCC Runtime Library Exception along with this program; 23// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24// <http://www.gnu.org/licenses/>. 25 26/* 27 * Copyright (c) 1996 28 * Silicon Graphics Computer Systems, Inc. 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Silicon Graphics makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1994 40 * Hewlett-Packard Company 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Hewlett-Packard Company makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 * 50 */ 51 52/** @file backward/hash_map 53 * This file is a GNU extension to the Standard C++ Library (possibly 54 * containing extensions from the HP/SGI STL subset). 55 */ 56 57#ifndef _BACKWARD_HASH_MAP 58#define _BACKWARD_HASH_MAP 1 59 60#include "backward_warning.h" 61#include <bits/c++config.h> 62#include <backward/hashtable.h> 63#include <bits/concept_check.h> 64 65_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 66 67 using std::equal_to; 68 using std::allocator; 69 using std::pair; 70 using std::_Select1st; 71 72 /** 73 * This is an SGI extension. 74 * @ingroup SGIextensions 75 * @doctodo 76 */ 77 template<class _Key, class _Tp, class _HashFn = hash<_Key>, 78 class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> > 79 class hash_map 80 { 81 private: 82 typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn, 83 _Select1st<pair<const _Key, _Tp> >, 84 _EqualKey, _Alloc> _Ht; 85 86 _Ht _M_ht; 87 88 public: 89 typedef typename _Ht::key_type key_type; 90 typedef _Tp data_type; 91 typedef _Tp mapped_type; 92 typedef typename _Ht::value_type value_type; 93 typedef typename _Ht::hasher hasher; 94 typedef typename _Ht::key_equal key_equal; 95 96 typedef typename _Ht::size_type size_type; 97 typedef typename _Ht::difference_type difference_type; 98 typedef typename _Ht::pointer pointer; 99 typedef typename _Ht::const_pointer const_pointer; 100 typedef typename _Ht::reference reference; 101 typedef typename _Ht::const_reference const_reference; 102 103 typedef typename _Ht::iterator iterator; 104 typedef typename _Ht::const_iterator const_iterator; 105 106 typedef typename _Ht::allocator_type allocator_type; 107 108 hasher 109 hash_funct() const 110 { return _M_ht.hash_funct(); } 111 112 key_equal 113 key_eq() const 114 { return _M_ht.key_eq(); } 115 116 allocator_type 117 get_allocator() const 118 { return _M_ht.get_allocator(); } 119 120 hash_map() 121 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 122 123 explicit 124 hash_map(size_type __n) 125 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 126 127 hash_map(size_type __n, const hasher& __hf) 128 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 129 130 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, 131 const allocator_type& __a = allocator_type()) 132 : _M_ht(__n, __hf, __eql, __a) {} 133 134 template<class _InputIterator> 135 hash_map(_InputIterator __f, _InputIterator __l) 136 : _M_ht(100, hasher(), key_equal(), allocator_type()) 137 { _M_ht.insert_unique(__f, __l); } 138 139 template<class _InputIterator> 140 hash_map(_InputIterator __f, _InputIterator __l, size_type __n) 141 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 142 { _M_ht.insert_unique(__f, __l); } 143 144 template<class _InputIterator> 145 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 146 const hasher& __hf) 147 : _M_ht(__n, __hf, key_equal(), allocator_type()) 148 { _M_ht.insert_unique(__f, __l); } 149 150 template<class _InputIterator> 151 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 152 const hasher& __hf, const key_equal& __eql, 153 const allocator_type& __a = allocator_type()) 154 : _M_ht(__n, __hf, __eql, __a) 155 { _M_ht.insert_unique(__f, __l); } 156 157 size_type 158 size() const 159 { return _M_ht.size(); } 160 161 size_type 162 max_size() const 163 { return _M_ht.max_size(); } 164 165 bool 166 empty() const 167 { return _M_ht.empty(); } 168 169 void 170 swap(hash_map& __hs) 171 { _M_ht.swap(__hs._M_ht); } 172 173 template<class _K1, class _T1, class _HF, class _EqK, class _Al> 174 friend bool 175 operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&, 176 const hash_map<_K1, _T1, _HF, _EqK, _Al>&); 177 178 iterator 179 begin() 180 { return _M_ht.begin(); } 181 182 iterator 183 end() 184 { return _M_ht.end(); } 185 186 const_iterator 187 begin() const 188 { return _M_ht.begin(); } 189 190 const_iterator 191 end() const 192 { return _M_ht.end(); } 193 194 pair<iterator, bool> 195 insert(const value_type& __obj) 196 { return _M_ht.insert_unique(__obj); } 197 198 template<class _InputIterator> 199 void 200 insert(_InputIterator __f, _InputIterator __l) 201 { _M_ht.insert_unique(__f, __l); } 202 203 pair<iterator, bool> 204 insert_noresize(const value_type& __obj) 205 { return _M_ht.insert_unique_noresize(__obj); } 206 207 iterator 208 find(const key_type& __key) 209 { return _M_ht.find(__key); } 210 211 const_iterator 212 find(const key_type& __key) const 213 { return _M_ht.find(__key); } 214 215 _Tp& 216 operator[](const key_type& __key) 217 { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; } 218 219 size_type 220 count(const key_type& __key) const 221 { return _M_ht.count(__key); } 222 223 pair<iterator, iterator> 224 equal_range(const key_type& __key) 225 { return _M_ht.equal_range(__key); } 226 227 pair<const_iterator, const_iterator> 228 equal_range(const key_type& __key) const 229 { return _M_ht.equal_range(__key); } 230 231 size_type 232 erase(const key_type& __key) 233 {return _M_ht.erase(__key); } 234 235 void 236 erase(iterator __it) 237 { _M_ht.erase(__it); } 238 239 void 240 erase(iterator __f, iterator __l) 241 { _M_ht.erase(__f, __l); } 242 243 void 244 clear() 245 { _M_ht.clear(); } 246 247 void 248 resize(size_type __hint) 249 { _M_ht.resize(__hint); } 250 251 size_type 252 bucket_count() const 253 { return _M_ht.bucket_count(); } 254 255 size_type 256 max_bucket_count() const 257 { return _M_ht.max_bucket_count(); } 258 259 size_type 260 elems_in_bucket(size_type __n) const 261 { return _M_ht.elems_in_bucket(__n); } 262 }; 263 264 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc> 265 inline bool 266 operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1, 267 const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2) 268 { return __hm1._M_ht == __hm2._M_ht; } 269 270 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc> 271 inline bool 272 operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1, 273 const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2) 274 { return !(__hm1 == __hm2); } 275 276 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc> 277 inline void 278 swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1, 279 hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2) 280 { __hm1.swap(__hm2); } 281 282 283 /** 284 * This is an SGI extension. 285 * @ingroup SGIextensions 286 * @doctodo 287 */ 288 template<class _Key, class _Tp, 289 class _HashFn = hash<_Key>, 290 class _EqualKey = equal_to<_Key>, 291 class _Alloc = allocator<_Tp> > 292 class hash_multimap 293 { 294 // concept requirements 295 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 296 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 297 __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept) 298 __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept) 299 300 private: 301 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn, 302 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> 303 _Ht; 304 305 _Ht _M_ht; 306 307 public: 308 typedef typename _Ht::key_type key_type; 309 typedef _Tp data_type; 310 typedef _Tp mapped_type; 311 typedef typename _Ht::value_type value_type; 312 typedef typename _Ht::hasher hasher; 313 typedef typename _Ht::key_equal key_equal; 314 315 typedef typename _Ht::size_type size_type; 316 typedef typename _Ht::difference_type difference_type; 317 typedef typename _Ht::pointer pointer; 318 typedef typename _Ht::const_pointer const_pointer; 319 typedef typename _Ht::reference reference; 320 typedef typename _Ht::const_reference const_reference; 321 322 typedef typename _Ht::iterator iterator; 323 typedef typename _Ht::const_iterator const_iterator; 324 325 typedef typename _Ht::allocator_type allocator_type; 326 327 hasher 328 hash_funct() const 329 { return _M_ht.hash_funct(); } 330 331 key_equal 332 key_eq() const 333 { return _M_ht.key_eq(); } 334 335 allocator_type 336 get_allocator() const 337 { return _M_ht.get_allocator(); } 338 339 hash_multimap() 340 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 341 342 explicit 343 hash_multimap(size_type __n) 344 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 345 346 hash_multimap(size_type __n, const hasher& __hf) 347 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 348 349 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, 350 const allocator_type& __a = allocator_type()) 351 : _M_ht(__n, __hf, __eql, __a) {} 352 353 template<class _InputIterator> 354 hash_multimap(_InputIterator __f, _InputIterator __l) 355 : _M_ht(100, hasher(), key_equal(), allocator_type()) 356 { _M_ht.insert_equal(__f, __l); } 357 358 template<class _InputIterator> 359 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) 360 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 361 { _M_ht.insert_equal(__f, __l); } 362 363 template<class _InputIterator> 364 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 365 const hasher& __hf) 366 : _M_ht(__n, __hf, key_equal(), allocator_type()) 367 { _M_ht.insert_equal(__f, __l); } 368 369 template<class _InputIterator> 370 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 371 const hasher& __hf, const key_equal& __eql, 372 const allocator_type& __a = allocator_type()) 373 : _M_ht(__n, __hf, __eql, __a) 374 { _M_ht.insert_equal(__f, __l); } 375 376 size_type 377 size() const 378 { return _M_ht.size(); } 379 380 size_type 381 max_size() const 382 { return _M_ht.max_size(); } 383 384 bool 385 empty() const 386 { return _M_ht.empty(); } 387 388 void 389 swap(hash_multimap& __hs) 390 { _M_ht.swap(__hs._M_ht); } 391 392 template<class _K1, class _T1, class _HF, class _EqK, class _Al> 393 friend bool 394 operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&, 395 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&); 396 397 iterator 398 begin() 399 { return _M_ht.begin(); } 400 401 iterator 402 end() 403 { return _M_ht.end(); } 404 405 const_iterator 406 begin() const 407 { return _M_ht.begin(); } 408 409 const_iterator 410 end() const 411 { return _M_ht.end(); } 412 413 iterator 414 insert(const value_type& __obj) 415 { return _M_ht.insert_equal(__obj); } 416 417 template<class _InputIterator> 418 void 419 insert(_InputIterator __f, _InputIterator __l) 420 { _M_ht.insert_equal(__f,__l); } 421 422 iterator 423 insert_noresize(const value_type& __obj) 424 { return _M_ht.insert_equal_noresize(__obj); } 425 426 iterator 427 find(const key_type& __key) 428 { return _M_ht.find(__key); } 429 430 const_iterator 431 find(const key_type& __key) const 432 { return _M_ht.find(__key); } 433 434 size_type 435 count(const key_type& __key) const 436 { return _M_ht.count(__key); } 437 438 pair<iterator, iterator> 439 equal_range(const key_type& __key) 440 { return _M_ht.equal_range(__key); } 441 442 pair<const_iterator, const_iterator> 443 equal_range(const key_type& __key) const 444 { return _M_ht.equal_range(__key); } 445 446 size_type 447 erase(const key_type& __key) 448 { return _M_ht.erase(__key); } 449 450 void 451 erase(iterator __it) 452 { _M_ht.erase(__it); } 453 454 void 455 erase(iterator __f, iterator __l) 456 { _M_ht.erase(__f, __l); } 457 458 void 459 clear() 460 { _M_ht.clear(); } 461 462 void 463 resize(size_type __hint) 464 { _M_ht.resize(__hint); } 465 466 size_type 467 bucket_count() const 468 { return _M_ht.bucket_count(); } 469 470 size_type 471 max_bucket_count() const 472 { return _M_ht.max_bucket_count(); } 473 474 size_type 475 elems_in_bucket(size_type __n) const 476 { return _M_ht.elems_in_bucket(__n); } 477 }; 478 479 template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 480 inline bool 481 operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1, 482 const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2) 483 { return __hm1._M_ht == __hm2._M_ht; } 484 485 template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 486 inline bool 487 operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1, 488 const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2) 489 { return !(__hm1 == __hm2); } 490 491 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc> 492 inline void 493 swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1, 494 hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2) 495 { __hm1.swap(__hm2); } 496 497_GLIBCXX_END_NAMESPACE 498 499_GLIBCXX_BEGIN_NAMESPACE(std) 500 501 // Specialization of insert_iterator so that it will work for hash_map 502 // and hash_multimap. 503 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 504 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, 505 _EqKey, _Alloc> > 506 { 507 protected: 508 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> 509 _Container; 510 _Container* container; 511 512 public: 513 typedef _Container container_type; 514 typedef output_iterator_tag iterator_category; 515 typedef void value_type; 516 typedef void difference_type; 517 typedef void pointer; 518 typedef void reference; 519 520 insert_iterator(_Container& __x) 521 : container(&__x) {} 522 523 insert_iterator(_Container& __x, typename _Container::iterator) 524 : container(&__x) {} 525 526 insert_iterator<_Container>& 527 operator=(const typename _Container::value_type& __value) 528 { 529 container->insert(__value); 530 return *this; 531 } 532 533 insert_iterator<_Container>& 534 operator*() 535 { return *this; } 536 537 insert_iterator<_Container>& 538 operator++() { return *this; } 539 540 insert_iterator<_Container>& 541 operator++(int) 542 { return *this; } 543 }; 544 545 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 546 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, 547 _EqKey, _Alloc> > 548 { 549 protected: 550 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> 551 _Container; 552 _Container* container; 553 typename _Container::iterator iter; 554 555 public: 556 typedef _Container container_type; 557 typedef output_iterator_tag iterator_category; 558 typedef void value_type; 559 typedef void difference_type; 560 typedef void pointer; 561 typedef void reference; 562 563 insert_iterator(_Container& __x) 564 : container(&__x) {} 565 566 insert_iterator(_Container& __x, typename _Container::iterator) 567 : container(&__x) {} 568 569 insert_iterator<_Container>& 570 operator=(const typename _Container::value_type& __value) 571 { 572 container->insert(__value); 573 return *this; 574 } 575 576 insert_iterator<_Container>& 577 operator*() 578 { return *this; } 579 580 insert_iterator<_Container>& 581 operator++() 582 { return *this; } 583 584 insert_iterator<_Container>& 585 operator++(int) 586 { return *this; } 587 }; 588 589_GLIBCXX_END_NAMESPACE 590 591#endif 592