hash_set revision 97403
1// Hashing set 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_set 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 __SGI_STL_INTERNAL_HASH_SET_H 63#define __SGI_STL_INTERNAL_HASH_SET_H 64 65#include <ext/stl_hashtable.h> 66#include <bits/concept_check.h> 67 68namespace __gnu_cxx 69{ 70using std::equal_to; 71using std::allocator; 72using std::pair; 73using std::_Identity; 74 75// Forward declaration of equality operator; needed for friend declaration. 76 77template <class _Value, 78 class _HashFcn = hash<_Value>, 79 class _EqualKey = equal_to<_Value>, 80 class _Alloc = allocator<_Value> > 81class hash_set; 82 83template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 84inline bool 85operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 86 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2); 87 88template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 89class hash_set 90{ 91 // concept requirements 92 __glibcpp_class_requires(_Value, _SGIAssignableConcept) 93 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept); 94 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept); 95 96private: 97 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 98 _EqualKey, _Alloc> _Ht; 99 _Ht _M_ht; 100 101public: 102 typedef typename _Ht::key_type key_type; 103 typedef typename _Ht::value_type value_type; 104 typedef typename _Ht::hasher hasher; 105 typedef typename _Ht::key_equal key_equal; 106 107 typedef typename _Ht::size_type size_type; 108 typedef typename _Ht::difference_type difference_type; 109 typedef typename _Ht::const_pointer pointer; 110 typedef typename _Ht::const_pointer const_pointer; 111 typedef typename _Ht::const_reference reference; 112 typedef typename _Ht::const_reference const_reference; 113 114 typedef typename _Ht::const_iterator iterator; 115 typedef typename _Ht::const_iterator const_iterator; 116 117 typedef typename _Ht::allocator_type allocator_type; 118 119 hasher hash_funct() const { return _M_ht.hash_funct(); } 120 key_equal key_eq() const { return _M_ht.key_eq(); } 121 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 122 123public: 124 hash_set() 125 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 126 explicit hash_set(size_type __n) 127 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 128 hash_set(size_type __n, const hasher& __hf) 129 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 130 hash_set(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_set(_InputIterator __f, _InputIterator __l) 136 : _M_ht(100, hasher(), key_equal(), allocator_type()) 137 { _M_ht.insert_unique(__f, __l); } 138 template <class _InputIterator> 139 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 140 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 141 { _M_ht.insert_unique(__f, __l); } 142 template <class _InputIterator> 143 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 144 const hasher& __hf) 145 : _M_ht(__n, __hf, key_equal(), allocator_type()) 146 { _M_ht.insert_unique(__f, __l); } 147 template <class _InputIterator> 148 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 149 const hasher& __hf, const key_equal& __eql, 150 const allocator_type& __a = allocator_type()) 151 : _M_ht(__n, __hf, __eql, __a) 152 { _M_ht.insert_unique(__f, __l); } 153 154public: 155 size_type size() const { return _M_ht.size(); } 156 size_type max_size() const { return _M_ht.max_size(); } 157 bool empty() const { return _M_ht.empty(); } 158 void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); } 159 160 template <class _Val, class _HF, class _EqK, class _Al> 161 friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&, 162 const hash_set<_Val, _HF, _EqK, _Al>&); 163 164 iterator begin() const { return _M_ht.begin(); } 165 iterator end() const { return _M_ht.end(); } 166 167public: 168 pair<iterator, bool> insert(const value_type& __obj) 169 { 170 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 171 return pair<iterator,bool>(__p.first, __p.second); 172 } 173 template <class _InputIterator> 174 void insert(_InputIterator __f, _InputIterator __l) 175 { _M_ht.insert_unique(__f,__l); } 176 pair<iterator, bool> insert_noresize(const value_type& __obj) 177 { 178 pair<typename _Ht::iterator, bool> __p = 179 _M_ht.insert_unique_noresize(__obj); 180 return pair<iterator, bool>(__p.first, __p.second); 181 } 182 183 iterator find(const key_type& __key) const { return _M_ht.find(__key); } 184 185 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 186 187 pair<iterator, iterator> equal_range(const key_type& __key) const 188 { return _M_ht.equal_range(__key); } 189 190 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 191 void erase(iterator __it) { _M_ht.erase(__it); } 192 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 193 void clear() { _M_ht.clear(); } 194 195public: 196 void resize(size_type __hint) { _M_ht.resize(__hint); } 197 size_type bucket_count() const { return _M_ht.bucket_count(); } 198 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 199 size_type elems_in_bucket(size_type __n) const 200 { return _M_ht.elems_in_bucket(__n); } 201}; 202 203template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 204inline bool 205operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 206 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) 207{ 208 return __hs1._M_ht == __hs2._M_ht; 209} 210 211template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 212inline bool 213operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 214 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) { 215 return !(__hs1 == __hs2); 216} 217 218template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 219inline void 220swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 221 hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) 222{ 223 __hs1.swap(__hs2); 224} 225 226 227template <class _Value, 228 class _HashFcn = hash<_Value>, 229 class _EqualKey = equal_to<_Value>, 230 class _Alloc = allocator<_Value> > 231class hash_multiset; 232 233template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 234inline bool 235operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 236 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2); 237 238 239template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 240class hash_multiset 241{ 242 // concept requirements 243 __glibcpp_class_requires(_Value, _SGIAssignableConcept) 244 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept); 245 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept); 246 247private: 248 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 249 _EqualKey, _Alloc> _Ht; 250 _Ht _M_ht; 251 252public: 253 typedef typename _Ht::key_type key_type; 254 typedef typename _Ht::value_type value_type; 255 typedef typename _Ht::hasher hasher; 256 typedef typename _Ht::key_equal key_equal; 257 258 typedef typename _Ht::size_type size_type; 259 typedef typename _Ht::difference_type difference_type; 260 typedef typename _Ht::const_pointer pointer; 261 typedef typename _Ht::const_pointer const_pointer; 262 typedef typename _Ht::const_reference reference; 263 typedef typename _Ht::const_reference const_reference; 264 265 typedef typename _Ht::const_iterator iterator; 266 typedef typename _Ht::const_iterator const_iterator; 267 268 typedef typename _Ht::allocator_type allocator_type; 269 270 hasher hash_funct() const { return _M_ht.hash_funct(); } 271 key_equal key_eq() const { return _M_ht.key_eq(); } 272 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 273 274public: 275 hash_multiset() 276 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 277 explicit hash_multiset(size_type __n) 278 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 279 hash_multiset(size_type __n, const hasher& __hf) 280 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 281 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 282 const allocator_type& __a = allocator_type()) 283 : _M_ht(__n, __hf, __eql, __a) {} 284 285 template <class _InputIterator> 286 hash_multiset(_InputIterator __f, _InputIterator __l) 287 : _M_ht(100, hasher(), key_equal(), allocator_type()) 288 { _M_ht.insert_equal(__f, __l); } 289 template <class _InputIterator> 290 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) 291 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 292 { _M_ht.insert_equal(__f, __l); } 293 template <class _InputIterator> 294 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 295 const hasher& __hf) 296 : _M_ht(__n, __hf, key_equal(), allocator_type()) 297 { _M_ht.insert_equal(__f, __l); } 298 template <class _InputIterator> 299 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 300 const hasher& __hf, const key_equal& __eql, 301 const allocator_type& __a = allocator_type()) 302 : _M_ht(__n, __hf, __eql, __a) 303 { _M_ht.insert_equal(__f, __l); } 304 305public: 306 size_type size() const { return _M_ht.size(); } 307 size_type max_size() const { return _M_ht.max_size(); } 308 bool empty() const { return _M_ht.empty(); } 309 void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); } 310 311 template <class _Val, class _HF, class _EqK, class _Al> 312 friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&, 313 const hash_multiset<_Val, _HF, _EqK, _Al>&); 314 315 iterator begin() const { return _M_ht.begin(); } 316 iterator end() const { return _M_ht.end(); } 317 318public: 319 iterator insert(const value_type& __obj) 320 { return _M_ht.insert_equal(__obj); } 321 template <class _InputIterator> 322 void insert(_InputIterator __f, _InputIterator __l) 323 { _M_ht.insert_equal(__f,__l); } 324 iterator insert_noresize(const value_type& __obj) 325 { return _M_ht.insert_equal_noresize(__obj); } 326 327 iterator find(const key_type& __key) const { return _M_ht.find(__key); } 328 329 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 330 331 pair<iterator, iterator> equal_range(const key_type& __key) const 332 { return _M_ht.equal_range(__key); } 333 334 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 335 void erase(iterator __it) { _M_ht.erase(__it); } 336 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 337 void clear() { _M_ht.clear(); } 338 339public: 340 void resize(size_type __hint) { _M_ht.resize(__hint); } 341 size_type bucket_count() const { return _M_ht.bucket_count(); } 342 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 343 size_type elems_in_bucket(size_type __n) const 344 { return _M_ht.elems_in_bucket(__n); } 345}; 346 347template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 348inline bool 349operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 350 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) 351{ 352 return __hs1._M_ht == __hs2._M_ht; 353} 354 355template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 356inline bool 357operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 358 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { 359 return !(__hs1 == __hs2); 360} 361 362template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 363inline void 364swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 365 hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { 366 __hs1.swap(__hs2); 367} 368 369} // namespace __gnu_cxx 370 371namespace std 372{ 373// Specialization of insert_iterator so that it will work for hash_set 374// and hash_multiset. 375 376template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 377class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > { 378protected: 379 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 380 _Container* container; 381public: 382 typedef _Container container_type; 383 typedef output_iterator_tag iterator_category; 384 typedef void value_type; 385 typedef void difference_type; 386 typedef void pointer; 387 typedef void reference; 388 389 insert_iterator(_Container& __x) : container(&__x) {} 390 insert_iterator(_Container& __x, typename _Container::iterator) 391 : container(&__x) {} 392 insert_iterator<_Container>& 393 operator=(const typename _Container::value_type& __value) { 394 container->insert(__value); 395 return *this; 396 } 397 insert_iterator<_Container>& operator*() { return *this; } 398 insert_iterator<_Container>& operator++() { return *this; } 399 insert_iterator<_Container>& operator++(int) { return *this; } 400}; 401 402template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 403class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > { 404protected: 405 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 406 _Container* container; 407 typename _Container::iterator iter; 408public: 409 typedef _Container container_type; 410 typedef output_iterator_tag iterator_category; 411 typedef void value_type; 412 typedef void difference_type; 413 typedef void pointer; 414 typedef void reference; 415 416 insert_iterator(_Container& __x) : container(&__x) {} 417 insert_iterator(_Container& __x, typename _Container::iterator) 418 : container(&__x) {} 419 insert_iterator<_Container>& 420 operator=(const typename _Container::value_type& __value) { 421 container->insert(__value); 422 return *this; 423 } 424 insert_iterator<_Container>& operator*() { return *this; } 425 insert_iterator<_Container>& operator++() { return *this; } 426 insert_iterator<_Container>& operator++(int) { return *this; } 427}; 428 429} // namespace std 430 431#endif /* __SGI_STL_INTERNAL_HASH_SET_H */ 432 433// Local Variables: 434// mode:C++ 435// End: 436