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