1// Hashing set implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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_set 57 * This file is a GNU extension to the Standard C++ Library (possibly 58 * containing extensions from the HP/SGI STL subset). 59 */ 60 61#ifndef _HASH_SET 62#define _HASH_SET 1 63 64#include <bits/c++config.h> 65#include <ext/hashtable.h> 66#include <bits/concept_check.h> 67 68_GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT) 69 70 using std::equal_to; 71 using std::allocator; 72 using std::pair; 73 using std::_Identity; 74 75 /** 76 * This is an SGI extension. 77 * @ingroup SGIextensions 78 * @doctodo 79 */ 80 template<class _Value, class _HashFcn = hash<_Value>, 81 class _EqualKey = equal_to<_Value>, 82 class _Alloc = allocator<_Value> > 83 class hash_set 84 { 85 // concept requirements 86 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 87 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 88 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 89 90 private: 91 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 92 _EqualKey, _Alloc> _Ht; 93 _Ht _M_ht; 94 95 public: 96 typedef typename _Ht::key_type key_type; 97 typedef typename _Ht::value_type value_type; 98 typedef typename _Ht::hasher hasher; 99 typedef typename _Ht::key_equal key_equal; 100 101 typedef typename _Ht::size_type size_type; 102 typedef typename _Ht::difference_type difference_type; 103 typedef typename _Alloc::pointer pointer; 104 typedef typename _Alloc::const_pointer const_pointer; 105 typedef typename _Alloc::reference reference; 106 typedef typename _Alloc::const_reference const_reference; 107 108 typedef typename _Ht::const_iterator iterator; 109 typedef typename _Ht::const_iterator const_iterator; 110 111 typedef typename _Ht::allocator_type allocator_type; 112 113 hasher 114 hash_funct() const 115 { return _M_ht.hash_funct(); } 116 117 key_equal 118 key_eq() const 119 { return _M_ht.key_eq(); } 120 121 allocator_type 122 get_allocator() const 123 { return _M_ht.get_allocator(); } 124 125 public: 126 hash_set() 127 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 128 129 explicit 130 hash_set(size_type __n) 131 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 132 133 hash_set(size_type __n, const hasher& __hf) 134 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 135 136 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 137 const allocator_type& __a = allocator_type()) 138 : _M_ht(__n, __hf, __eql, __a) {} 139 140 template<class _InputIterator> 141 hash_set(_InputIterator __f, _InputIterator __l) 142 : _M_ht(100, hasher(), key_equal(), allocator_type()) 143 { _M_ht.insert_unique(__f, __l); } 144 145 template<class _InputIterator> 146 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 147 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 148 { _M_ht.insert_unique(__f, __l); } 149 150 template<class _InputIterator> 151 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 152 const hasher& __hf) 153 : _M_ht(__n, __hf, key_equal(), allocator_type()) 154 { _M_ht.insert_unique(__f, __l); } 155 156 template<class _InputIterator> 157 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 158 const hasher& __hf, const key_equal& __eql, 159 const allocator_type& __a = allocator_type()) 160 : _M_ht(__n, __hf, __eql, __a) 161 { _M_ht.insert_unique(__f, __l); } 162 163 public: 164 size_type 165 size() const 166 { return _M_ht.size(); } 167 168 size_type 169 max_size() const 170 { return _M_ht.max_size(); } 171 172 bool 173 empty() const 174 { return _M_ht.empty(); } 175 176 void 177 swap(hash_set& __hs) 178 { _M_ht.swap(__hs._M_ht); } 179 180 template<class _Val, class _HF, class _EqK, class _Al> 181 friend bool 182 operator==(const hash_set<_Val, _HF, _EqK, _Al>&, 183 const hash_set<_Val, _HF, _EqK, _Al>&); 184 185 iterator 186 begin() const 187 { return _M_ht.begin(); } 188 189 iterator 190 end() const 191 { return _M_ht.end(); } 192 193 public: 194 pair<iterator, bool> 195 insert(const value_type& __obj) 196 { 197 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 198 return pair<iterator,bool>(__p.first, __p.second); 199 } 200 201 template<class _InputIterator> 202 void 203 insert(_InputIterator __f, _InputIterator __l) 204 { _M_ht.insert_unique(__f, __l); } 205 206 pair<iterator, bool> 207 insert_noresize(const value_type& __obj) 208 { 209 pair<typename _Ht::iterator, bool> __p 210 = _M_ht.insert_unique_noresize(__obj); 211 return pair<iterator, bool>(__p.first, __p.second); 212 } 213 214 iterator 215 find(const key_type& __key) const 216 { return _M_ht.find(__key); } 217 218 size_type 219 count(const key_type& __key) const 220 { return _M_ht.count(__key); } 221 222 pair<iterator, iterator> 223 equal_range(const key_type& __key) const 224 { return _M_ht.equal_range(__key); } 225 226 size_type 227 erase(const key_type& __key) 228 {return _M_ht.erase(__key); } 229 230 void 231 erase(iterator __it) 232 { _M_ht.erase(__it); } 233 234 void 235 erase(iterator __f, iterator __l) 236 { _M_ht.erase(__f, __l); } 237 238 void 239 clear() 240 { _M_ht.clear(); } 241 242 public: 243 void 244 resize(size_type __hint) 245 { _M_ht.resize(__hint); } 246 247 size_type 248 bucket_count() const 249 { return _M_ht.bucket_count(); } 250 251 size_type 252 max_bucket_count() const 253 { return _M_ht.max_bucket_count(); } 254 255 size_type 256 elems_in_bucket(size_type __n) const 257 { return _M_ht.elems_in_bucket(__n); } 258 }; 259 260 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 261 inline bool 262 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 263 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 264 { return __hs1._M_ht == __hs2._M_ht; } 265 266 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 267 inline bool 268 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 269 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 270 { return !(__hs1 == __hs2); } 271 272 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 273 inline void 274 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 275 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 276 { __hs1.swap(__hs2); } 277 278 279 /** 280 * This is an SGI extension. 281 * @ingroup SGIextensions 282 * @doctodo 283 */ 284 template<class _Value, 285 class _HashFcn = hash<_Value>, 286 class _EqualKey = equal_to<_Value>, 287 class _Alloc = allocator<_Value> > 288 class hash_multiset 289 { 290 // concept requirements 291 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 292 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 293 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 294 295 private: 296 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 297 _EqualKey, _Alloc> _Ht; 298 _Ht _M_ht; 299 300 public: 301 typedef typename _Ht::key_type key_type; 302 typedef typename _Ht::value_type value_type; 303 typedef typename _Ht::hasher hasher; 304 typedef typename _Ht::key_equal key_equal; 305 306 typedef typename _Ht::size_type size_type; 307 typedef typename _Ht::difference_type difference_type; 308 typedef typename _Alloc::pointer pointer; 309 typedef typename _Alloc::const_pointer const_pointer; 310 typedef typename _Alloc::reference reference; 311 typedef typename _Alloc::const_reference const_reference; 312 313 typedef typename _Ht::const_iterator iterator; 314 typedef typename _Ht::const_iterator const_iterator; 315 316 typedef typename _Ht::allocator_type allocator_type; 317 318 hasher 319 hash_funct() const 320 { return _M_ht.hash_funct(); } 321 322 key_equal 323 key_eq() const 324 { return _M_ht.key_eq(); } 325 326 allocator_type 327 get_allocator() const 328 { return _M_ht.get_allocator(); } 329 330 public: 331 hash_multiset() 332 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 333 334 explicit 335 hash_multiset(size_type __n) 336 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 337 338 hash_multiset(size_type __n, const hasher& __hf) 339 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 340 341 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 342 const allocator_type& __a = allocator_type()) 343 : _M_ht(__n, __hf, __eql, __a) {} 344 345 template<class _InputIterator> 346 hash_multiset(_InputIterator __f, _InputIterator __l) 347 : _M_ht(100, hasher(), key_equal(), allocator_type()) 348 { _M_ht.insert_equal(__f, __l); } 349 350 template<class _InputIterator> 351 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) 352 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 353 { _M_ht.insert_equal(__f, __l); } 354 355 template<class _InputIterator> 356 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 357 const hasher& __hf) 358 : _M_ht(__n, __hf, key_equal(), allocator_type()) 359 { _M_ht.insert_equal(__f, __l); } 360 361 template<class _InputIterator> 362 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 363 const hasher& __hf, const key_equal& __eql, 364 const allocator_type& __a = allocator_type()) 365 : _M_ht(__n, __hf, __eql, __a) 366 { _M_ht.insert_equal(__f, __l); } 367 368 public: 369 size_type 370 size() const 371 { return _M_ht.size(); } 372 373 size_type 374 max_size() const 375 { return _M_ht.max_size(); } 376 377 bool 378 empty() const 379 { return _M_ht.empty(); } 380 381 void 382 swap(hash_multiset& hs) 383 { _M_ht.swap(hs._M_ht); } 384 385 template<class _Val, class _HF, class _EqK, class _Al> 386 friend bool 387 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&, 388 const hash_multiset<_Val, _HF, _EqK, _Al>&); 389 390 iterator 391 begin() const 392 { return _M_ht.begin(); } 393 394 iterator 395 end() const 396 { return _M_ht.end(); } 397 398 public: 399 iterator 400 insert(const value_type& __obj) 401 { return _M_ht.insert_equal(__obj); } 402 403 template<class _InputIterator> 404 void 405 insert(_InputIterator __f, _InputIterator __l) 406 { _M_ht.insert_equal(__f,__l); } 407 408 iterator 409 insert_noresize(const value_type& __obj) 410 { return _M_ht.insert_equal_noresize(__obj); } 411 412 iterator 413 find(const key_type& __key) const 414 { return _M_ht.find(__key); } 415 416 size_type 417 count(const key_type& __key) const 418 { return _M_ht.count(__key); } 419 420 pair<iterator, iterator> 421 equal_range(const key_type& __key) const 422 { return _M_ht.equal_range(__key); } 423 424 size_type 425 erase(const key_type& __key) 426 { return _M_ht.erase(__key); } 427 428 void 429 erase(iterator __it) 430 { _M_ht.erase(__it); } 431 432 void 433 erase(iterator __f, iterator __l) 434 { _M_ht.erase(__f, __l); } 435 436 void 437 clear() 438 { _M_ht.clear(); } 439 440 public: 441 void 442 resize(size_type __hint) 443 { _M_ht.resize(__hint); } 444 445 size_type 446 bucket_count() const 447 { return _M_ht.bucket_count(); } 448 449 size_type 450 max_bucket_count() const 451 { return _M_ht.max_bucket_count(); } 452 453 size_type 454 elems_in_bucket(size_type __n) const 455 { return _M_ht.elems_in_bucket(__n); } 456 }; 457 458 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 459 inline bool 460 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 461 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 462 { return __hs1._M_ht == __hs2._M_ht; } 463 464 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 465 inline bool 466 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 467 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 468 { return !(__hs1 == __hs2); } 469 470 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 471 inline void 472 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 473 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 474 { __hs1.swap(__hs2); } 475 476_GLIBCXX_END_NESTED_NAMESPACE 477 478#ifdef _GLIBCXX_DEBUG 479# include <debug/hash_set> 480#endif 481 482_GLIBCXX_BEGIN_NAMESPACE(std) 483 484 // Specialization of insert_iterator so that it will work for hash_set 485 // and hash_multiset. 486 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 487 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, 488 _EqualKey, _Alloc> > 489 { 490 protected: 491 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> 492 _Container; 493 _Container* container; 494 495 public: 496 typedef _Container container_type; 497 typedef output_iterator_tag iterator_category; 498 typedef void value_type; 499 typedef void difference_type; 500 typedef void pointer; 501 typedef void reference; 502 503 insert_iterator(_Container& __x) 504 : container(&__x) {} 505 506 insert_iterator(_Container& __x, typename _Container::iterator) 507 : container(&__x) {} 508 509 insert_iterator<_Container>& 510 operator=(const typename _Container::value_type& __value) 511 { 512 container->insert(__value); 513 return *this; 514 } 515 516 insert_iterator<_Container>& 517 operator*() 518 { return *this; } 519 520 insert_iterator<_Container>& 521 operator++() 522 { return *this; } 523 524 insert_iterator<_Container>& 525 operator++(int) 526 { return *this; } 527 }; 528 529 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 530 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, 531 _EqualKey, _Alloc> > 532 { 533 protected: 534 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> 535 _Container; 536 _Container* container; 537 typename _Container::iterator iter; 538 539 public: 540 typedef _Container container_type; 541 typedef output_iterator_tag iterator_category; 542 typedef void value_type; 543 typedef void difference_type; 544 typedef void pointer; 545 typedef void reference; 546 547 insert_iterator(_Container& __x) 548 : container(&__x) {} 549 550 insert_iterator(_Container& __x, typename _Container::iterator) 551 : container(&__x) {} 552 553 insert_iterator<_Container>& 554 operator=(const typename _Container::value_type& __value) 555 { 556 container->insert(__value); 557 return *this; 558 } 559 560 insert_iterator<_Container>& 561 operator*() 562 { return *this; } 563 564 insert_iterator<_Container>& 565 operator++() 566 { return *this; } 567 568 insert_iterator<_Container>& 569 operator++(int) { return *this; } 570 }; 571 572_GLIBCXX_END_NAMESPACE 573 574#endif 575