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