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