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