00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061 #ifndef _HASH_SET
00062 #define _HASH_SET 1
00063
00064 #include <bits/c++config.h>
00065 #include <ext/hashtable.h>
00066 #include <bits/concept_check.h>
00067
00068 _GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT)
00069
00070 using std::equal_to;
00071 using std::allocator;
00072 using std::pair;
00073 using std::_Identity;
00074
00075
00076
00077
00078
00079
00080 template<class _Value, class _HashFcn = hash<_Value>,
00081 class _EqualKey = equal_to<_Value>,
00082 class _Alloc = allocator<_Value> >
00083 class hash_set
00084 {
00085
00086 __glibcxx_class_requires(_Value, _SGIAssignableConcept)
00087 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
00088 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
00089
00090 private:
00091 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
00092 _EqualKey, _Alloc> _Ht;
00093 _Ht _M_ht;
00094
00095 public:
00096 typedef typename _Ht::key_type key_type;
00097 typedef typename _Ht::value_type value_type;
00098 typedef typename _Ht::hasher hasher;
00099 typedef typename _Ht::key_equal key_equal;
00100
00101 typedef typename _Ht::size_type size_type;
00102 typedef typename _Ht::difference_type difference_type;
00103 typedef typename _Alloc::pointer pointer;
00104 typedef typename _Alloc::const_pointer const_pointer;
00105 typedef typename _Alloc::reference reference;
00106 typedef typename _Alloc::const_reference const_reference;
00107
00108 typedef typename _Ht::const_iterator iterator;
00109 typedef typename _Ht::const_iterator const_iterator;
00110
00111 typedef typename _Ht::allocator_type allocator_type;
00112
00113 hasher
00114 hash_funct() const
00115 { return _M_ht.hash_funct(); }
00116
00117 key_equal
00118 key_eq() const
00119 { return _M_ht.key_eq(); }
00120
00121 allocator_type
00122 get_allocator() const
00123 { return _M_ht.get_allocator(); }
00124
00125 public:
00126 hash_set()
00127 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00128
00129 explicit
00130 hash_set(size_type __n)
00131 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00132
00133 hash_set(size_type __n, const hasher& __hf)
00134 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00135
00136 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
00137 const allocator_type& __a = allocator_type())
00138 : _M_ht(__n, __hf, __eql, __a) {}
00139
00140 template<class _InputIterator>
00141 hash_set(_InputIterator __f, _InputIterator __l)
00142 : _M_ht(100, hasher(), key_equal(), allocator_type())
00143 { _M_ht.insert_unique(__f, __l); }
00144
00145 template<class _InputIterator>
00146 hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
00147 : _M_ht(__n, hasher(), key_equal(), allocator_type())
00148 { _M_ht.insert_unique(__f, __l); }
00149
00150 template<class _InputIterator>
00151 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
00152 const hasher& __hf)
00153 : _M_ht(__n, __hf, key_equal(), allocator_type())
00154 { _M_ht.insert_unique(__f, __l); }
00155
00156 template<class _InputIterator>
00157 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
00158 const hasher& __hf, const key_equal& __eql,
00159 const allocator_type& __a = allocator_type())
00160 : _M_ht(__n, __hf, __eql, __a)
00161 { _M_ht.insert_unique(__f, __l); }
00162
00163 public:
00164 size_type
00165 size() const
00166 { return _M_ht.size(); }
00167
00168 size_type
00169 max_size() const
00170 { return _M_ht.max_size(); }
00171
00172 bool
00173 empty() const
00174 { return _M_ht.empty(); }
00175
00176 void
00177 swap(hash_set& __hs)
00178 { _M_ht.swap(__hs._M_ht); }
00179
00180 template<class _Val, class _HF, class _EqK, class _Al>
00181 friend bool
00182 operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
00183 const hash_set<_Val, _HF, _EqK, _Al>&);
00184
00185 iterator
00186 begin() const
00187 { return _M_ht.begin(); }
00188
00189 iterator
00190 end() const
00191 { return _M_ht.end(); }
00192
00193 public:
00194 pair<iterator, bool>
00195 insert(const value_type& __obj)
00196 {
00197 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
00198 return pair<iterator,bool>(__p.first, __p.second);
00199 }
00200
00201 template<class _InputIterator>
00202 void
00203 insert(_InputIterator __f, _InputIterator __l)
00204 { _M_ht.insert_unique(__f, __l); }
00205
00206 pair<iterator, bool>
00207 insert_noresize(const value_type& __obj)
00208 {
00209 pair<typename _Ht::iterator, bool> __p
00210 = _M_ht.insert_unique_noresize(__obj);
00211 return pair<iterator, bool>(__p.first, __p.second);
00212 }
00213
00214 iterator
00215 find(const key_type& __key) const
00216 { return _M_ht.find(__key); }
00217
00218 size_type
00219 count(const key_type& __key) const
00220 { return _M_ht.count(__key); }
00221
00222 pair<iterator, iterator>
00223 equal_range(const key_type& __key) const
00224 { return _M_ht.equal_range(__key); }
00225
00226 size_type
00227 erase(const key_type& __key)
00228 {return _M_ht.erase(__key); }
00229
00230 void
00231 erase(iterator __it)
00232 { _M_ht.erase(__it); }
00233
00234 void
00235 erase(iterator __f, iterator __l)
00236 { _M_ht.erase(__f, __l); }
00237
00238 void
00239 clear()
00240 { _M_ht.clear(); }
00241
00242 public:
00243 void
00244 resize(size_type __hint)
00245 { _M_ht.resize(__hint); }
00246
00247 size_type
00248 bucket_count() const
00249 { return _M_ht.bucket_count(); }
00250
00251 size_type
00252 max_bucket_count() const
00253 { return _M_ht.max_bucket_count(); }
00254
00255 size_type
00256 elems_in_bucket(size_type __n) const
00257 { return _M_ht.elems_in_bucket(__n); }
00258 };
00259
00260 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00261 inline bool
00262 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
00263 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
00264 { return __hs1._M_ht == __hs2._M_ht; }
00265
00266 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00267 inline bool
00268 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
00269 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
00270 { return !(__hs1 == __hs2); }
00271
00272 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00273 inline void
00274 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
00275 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
00276 { __hs1.swap(__hs2); }
00277
00278
00279
00280
00281
00282
00283
00284 template<class _Value,
00285 class _HashFcn = hash<_Value>,
00286 class _EqualKey = equal_to<_Value>,
00287 class _Alloc = allocator<_Value> >
00288 class hash_multiset
00289 {
00290
00291 __glibcxx_class_requires(_Value, _SGIAssignableConcept)
00292 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
00293 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
00294
00295 private:
00296 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
00297 _EqualKey, _Alloc> _Ht;
00298 _Ht _M_ht;
00299
00300 public:
00301 typedef typename _Ht::key_type key_type;
00302 typedef typename _Ht::value_type value_type;
00303 typedef typename _Ht::hasher hasher;
00304 typedef typename _Ht::key_equal key_equal;
00305
00306 typedef typename _Ht::size_type size_type;
00307 typedef typename _Ht::difference_type difference_type;
00308 typedef typename _Alloc::pointer pointer;
00309 typedef typename _Alloc::const_pointer const_pointer;
00310 typedef typename _Alloc::reference reference;
00311 typedef typename _Alloc::const_reference const_reference;
00312
00313 typedef typename _Ht::const_iterator iterator;
00314 typedef typename _Ht::const_iterator const_iterator;
00315
00316 typedef typename _Ht::allocator_type allocator_type;
00317
00318 hasher
00319 hash_funct() const
00320 { return _M_ht.hash_funct(); }
00321
00322 key_equal
00323 key_eq() const
00324 { return _M_ht.key_eq(); }
00325
00326 allocator_type
00327 get_allocator() const
00328 { return _M_ht.get_allocator(); }
00329
00330 public:
00331 hash_multiset()
00332 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00333
00334 explicit
00335 hash_multiset(size_type __n)
00336 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00337
00338 hash_multiset(size_type __n, const hasher& __hf)
00339 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00340
00341 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
00342 const allocator_type& __a = allocator_type())
00343 : _M_ht(__n, __hf, __eql, __a) {}
00344
00345 template<class _InputIterator>
00346 hash_multiset(_InputIterator __f, _InputIterator __l)
00347 : _M_ht(100, hasher(), key_equal(), allocator_type())
00348 { _M_ht.insert_equal(__f, __l); }
00349
00350 template<class _InputIterator>
00351 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
00352 : _M_ht(__n, hasher(), key_equal(), allocator_type())
00353 { _M_ht.insert_equal(__f, __l); }
00354
00355 template<class _InputIterator>
00356 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
00357 const hasher& __hf)
00358 : _M_ht(__n, __hf, key_equal(), allocator_type())
00359 { _M_ht.insert_equal(__f, __l); }
00360
00361 template<class _InputIterator>
00362 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
00363 const hasher& __hf, const key_equal& __eql,
00364 const allocator_type& __a = allocator_type())
00365 : _M_ht(__n, __hf, __eql, __a)
00366 { _M_ht.insert_equal(__f, __l); }
00367
00368 public:
00369 size_type
00370 size() const
00371 { return _M_ht.size(); }
00372
00373 size_type
00374 max_size() const
00375 { return _M_ht.max_size(); }
00376
00377 bool
00378 empty() const
00379 { return _M_ht.empty(); }
00380
00381 void
00382 swap(hash_multiset& hs)
00383 { _M_ht.swap(hs._M_ht); }
00384
00385 template<class _Val, class _HF, class _EqK, class _Al>
00386 friend bool
00387 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
00388 const hash_multiset<_Val, _HF, _EqK, _Al>&);
00389
00390 iterator
00391 begin() const
00392 { return _M_ht.begin(); }
00393
00394 iterator
00395 end() const
00396 { return _M_ht.end(); }
00397
00398 public:
00399 iterator
00400 insert(const value_type& __obj)
00401 { return _M_ht.insert_equal(__obj); }
00402
00403 template<class _InputIterator>
00404 void
00405 insert(_InputIterator __f, _InputIterator __l)
00406 { _M_ht.insert_equal(__f,__l); }
00407
00408 iterator
00409 insert_noresize(const value_type& __obj)
00410 { return _M_ht.insert_equal_noresize(__obj); }
00411
00412 iterator
00413 find(const key_type& __key) const
00414 { return _M_ht.find(__key); }
00415
00416 size_type
00417 count(const key_type& __key) const
00418 { return _M_ht.count(__key); }
00419
00420 pair<iterator, iterator>
00421 equal_range(const key_type& __key) const
00422 { return _M_ht.equal_range(__key); }
00423
00424 size_type
00425 erase(const key_type& __key)
00426 { return _M_ht.erase(__key); }
00427
00428 void
00429 erase(iterator __it)
00430 { _M_ht.erase(__it); }
00431
00432 void
00433 erase(iterator __f, iterator __l)
00434 { _M_ht.erase(__f, __l); }
00435
00436 void
00437 clear()
00438 { _M_ht.clear(); }
00439
00440 public:
00441 void
00442 resize(size_type __hint)
00443 { _M_ht.resize(__hint); }
00444
00445 size_type
00446 bucket_count() const
00447 { return _M_ht.bucket_count(); }
00448
00449 size_type
00450 max_bucket_count() const
00451 { return _M_ht.max_bucket_count(); }
00452
00453 size_type
00454 elems_in_bucket(size_type __n) const
00455 { return _M_ht.elems_in_bucket(__n); }
00456 };
00457
00458 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00459 inline bool
00460 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
00461 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
00462 { return __hs1._M_ht == __hs2._M_ht; }
00463
00464 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00465 inline bool
00466 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
00467 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
00468 { return !(__hs1 == __hs2); }
00469
00470 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00471 inline void
00472 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
00473 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
00474 { __hs1.swap(__hs2); }
00475
00476 _GLIBCXX_END_NESTED_NAMESPACE
00477
00478 #ifdef _GLIBCXX_DEBUG
00479 # include <debug/hash_set>
00480 #endif
00481
00482 _GLIBCXX_BEGIN_NAMESPACE(std)
00483
00484
00485
00486 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00487 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
00488 _EqualKey, _Alloc> >
00489 {
00490 protected:
00491 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
00492 _Container;
00493 _Container* container;
00494
00495 public:
00496 typedef _Container container_type;
00497 typedef output_iterator_tag iterator_category;
00498 typedef void value_type;
00499 typedef void difference_type;
00500 typedef void pointer;
00501 typedef void reference;
00502
00503 insert_iterator(_Container& __x)
00504 : container(&__x) {}
00505
00506 insert_iterator(_Container& __x, typename _Container::iterator)
00507 : container(&__x) {}
00508
00509 insert_iterator<_Container>&
00510 operator=(const typename _Container::value_type& __value)
00511 {
00512 container->insert(__value);
00513 return *this;
00514 }
00515
00516 insert_iterator<_Container>&
00517 operator*()
00518 { return *this; }
00519
00520 insert_iterator<_Container>&
00521 operator++()
00522 { return *this; }
00523
00524 insert_iterator<_Container>&
00525 operator++(int)
00526 { return *this; }
00527 };
00528
00529 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00530 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
00531 _EqualKey, _Alloc> >
00532 {
00533 protected:
00534 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
00535 _Container;
00536 _Container* container;
00537 typename _Container::iterator iter;
00538
00539 public:
00540 typedef _Container container_type;
00541 typedef output_iterator_tag iterator_category;
00542 typedef void value_type;
00543 typedef void difference_type;
00544 typedef void pointer;
00545 typedef void reference;
00546
00547 insert_iterator(_Container& __x)
00548 : container(&__x) {}
00549
00550 insert_iterator(_Container& __x, typename _Container::iterator)
00551 : container(&__x) {}
00552
00553 insert_iterator<_Container>&
00554 operator=(const typename _Container::value_type& __value)
00555 {
00556 container->insert(__value);
00557 return *this;
00558 }
00559
00560 insert_iterator<_Container>&
00561 operator*()
00562 { return *this; }
00563
00564 insert_iterator<_Container>&
00565 operator++()
00566 { return *this; }
00567
00568 insert_iterator<_Container>&
00569 operator++(int) { return *this; }
00570 };
00571
00572 _GLIBCXX_END_NAMESPACE
00573
00574 #endif