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