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