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
00062 #ifndef __SGI_STL_INTERNAL_HASH_SET_H
00063 #define __SGI_STL_INTERNAL_HASH_SET_H
00064
00065 #include <ext/stl_hashtable.h>
00066 #include <bits/concept_check.h>
00067
00068 namespace __gnu_cxx
00069 {
00070 using std::equal_to;
00071 using std::allocator;
00072 using std::pair;
00073 using std::_Identity;
00074
00075
00076
00077 template <class _Value,
00078 class _HashFcn = hash<_Value>,
00079 class _EqualKey = equal_to<_Value>,
00080 class _Alloc = allocator<_Value> >
00081 class hash_set;
00082
00083 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00084 inline bool
00085 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
00086 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2);
00087
00088
00089
00090
00091
00092
00093 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00094 class hash_set
00095 {
00096
00097 __glibcpp_class_requires(_Value, _SGIAssignableConcept)
00098 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
00099 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
00100
00101 private:
00102 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
00103 _EqualKey, _Alloc> _Ht;
00104 _Ht _M_ht;
00105
00106 public:
00107 typedef typename _Ht::key_type key_type;
00108 typedef typename _Ht::value_type value_type;
00109 typedef typename _Ht::hasher hasher;
00110 typedef typename _Ht::key_equal key_equal;
00111
00112 typedef typename _Ht::size_type size_type;
00113 typedef typename _Ht::difference_type difference_type;
00114 typedef typename _Alloc::pointer pointer;
00115 typedef typename _Alloc::const_pointer const_pointer;
00116 typedef typename _Alloc::reference reference;
00117 typedef typename _Alloc::const_reference const_reference;
00118
00119 typedef typename _Ht::const_iterator iterator;
00120 typedef typename _Ht::const_iterator const_iterator;
00121
00122 typedef typename _Ht::allocator_type allocator_type;
00123
00124 hasher hash_funct() const { return _M_ht.hash_funct(); }
00125 key_equal key_eq() const { return _M_ht.key_eq(); }
00126 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
00127
00128 public:
00129 hash_set()
00130 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00131 explicit hash_set(size_type __n)
00132 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00133 hash_set(size_type __n, const hasher& __hf)
00134 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00135 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
00136 const allocator_type& __a = allocator_type())
00137 : _M_ht(__n, __hf, __eql, __a) {}
00138
00139 template <class _InputIterator>
00140 hash_set(_InputIterator __f, _InputIterator __l)
00141 : _M_ht(100, hasher(), key_equal(), allocator_type())
00142 { _M_ht.insert_unique(__f, __l); }
00143 template <class _InputIterator>
00144 hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
00145 : _M_ht(__n, hasher(), key_equal(), allocator_type())
00146 { _M_ht.insert_unique(__f, __l); }
00147 template <class _InputIterator>
00148 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
00149 const hasher& __hf)
00150 : _M_ht(__n, __hf, key_equal(), allocator_type())
00151 { _M_ht.insert_unique(__f, __l); }
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 public:
00160 size_type size() const { return _M_ht.size(); }
00161 size_type max_size() const { return _M_ht.max_size(); }
00162 bool empty() const { return _M_ht.empty(); }
00163 void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
00164
00165 template <class _Val, class _HF, class _EqK, class _Al>
00166 friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&,
00167 const hash_set<_Val, _HF, _EqK, _Al>&);
00168
00169 iterator begin() const { return _M_ht.begin(); }
00170 iterator end() const { return _M_ht.end(); }
00171
00172 public:
00173 pair<iterator, bool> insert(const value_type& __obj)
00174 {
00175 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
00176 return pair<iterator,bool>(__p.first, __p.second);
00177 }
00178 template <class _InputIterator>
00179 void insert(_InputIterator __f, _InputIterator __l)
00180 { _M_ht.insert_unique(__f,__l); }
00181 pair<iterator, bool> insert_noresize(const value_type& __obj)
00182 {
00183 pair<typename _Ht::iterator, bool> __p =
00184 _M_ht.insert_unique_noresize(__obj);
00185 return pair<iterator, bool>(__p.first, __p.second);
00186 }
00187
00188 iterator find(const key_type& __key) const { return _M_ht.find(__key); }
00189
00190 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
00191
00192 pair<iterator, iterator> equal_range(const key_type& __key) const
00193 { return _M_ht.equal_range(__key); }
00194
00195 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
00196 void erase(iterator __it) { _M_ht.erase(__it); }
00197 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
00198 void clear() { _M_ht.clear(); }
00199
00200 public:
00201 void resize(size_type __hint) { _M_ht.resize(__hint); }
00202 size_type bucket_count() const { return _M_ht.bucket_count(); }
00203 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
00204 size_type elems_in_bucket(size_type __n) const
00205 { return _M_ht.elems_in_bucket(__n); }
00206 };
00207
00208 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00209 inline bool
00210 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
00211 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
00212 {
00213 return __hs1._M_ht == __hs2._M_ht;
00214 }
00215
00216 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00217 inline bool
00218 operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
00219 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) {
00220 return !(__hs1 == __hs2);
00221 }
00222
00223 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00224 inline void
00225 swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00226 hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
00227 {
00228 __hs1.swap(__hs2);
00229 }
00230
00231
00232 template <class _Value,
00233 class _HashFcn = hash<_Value>,
00234 class _EqualKey = equal_to<_Value>,
00235 class _Alloc = allocator<_Value> >
00236 class hash_multiset;
00237
00238 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00239 inline bool
00240 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00241 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2);
00242
00243
00244
00245
00246
00247
00248
00249 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00250 class hash_multiset
00251 {
00252
00253 __glibcpp_class_requires(_Value, _SGIAssignableConcept)
00254 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
00255 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
00256
00257 private:
00258 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
00259 _EqualKey, _Alloc> _Ht;
00260 _Ht _M_ht;
00261
00262 public:
00263 typedef typename _Ht::key_type key_type;
00264 typedef typename _Ht::value_type value_type;
00265 typedef typename _Ht::hasher hasher;
00266 typedef typename _Ht::key_equal key_equal;
00267
00268 typedef typename _Ht::size_type size_type;
00269 typedef typename _Ht::difference_type difference_type;
00270 typedef typename _Alloc::pointer pointer;
00271 typedef typename _Alloc::const_pointer const_pointer;
00272 typedef typename _Alloc::reference reference;
00273 typedef typename _Alloc::const_reference const_reference;
00274
00275 typedef typename _Ht::const_iterator iterator;
00276 typedef typename _Ht::const_iterator const_iterator;
00277
00278 typedef typename _Ht::allocator_type allocator_type;
00279
00280 hasher hash_funct() const { return _M_ht.hash_funct(); }
00281 key_equal key_eq() const { return _M_ht.key_eq(); }
00282 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
00283
00284 public:
00285 hash_multiset()
00286 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00287 explicit hash_multiset(size_type __n)
00288 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00289 hash_multiset(size_type __n, const hasher& __hf)
00290 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00291 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
00292 const allocator_type& __a = allocator_type())
00293 : _M_ht(__n, __hf, __eql, __a) {}
00294
00295 template <class _InputIterator>
00296 hash_multiset(_InputIterator __f, _InputIterator __l)
00297 : _M_ht(100, hasher(), key_equal(), allocator_type())
00298 { _M_ht.insert_equal(__f, __l); }
00299 template <class _InputIterator>
00300 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
00301 : _M_ht(__n, hasher(), key_equal(), allocator_type())
00302 { _M_ht.insert_equal(__f, __l); }
00303 template <class _InputIterator>
00304 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
00305 const hasher& __hf)
00306 : _M_ht(__n, __hf, key_equal(), allocator_type())
00307 { _M_ht.insert_equal(__f, __l); }
00308 template <class _InputIterator>
00309 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
00310 const hasher& __hf, const key_equal& __eql,
00311 const allocator_type& __a = allocator_type())
00312 : _M_ht(__n, __hf, __eql, __a)
00313 { _M_ht.insert_equal(__f, __l); }
00314
00315 public:
00316 size_type size() const { return _M_ht.size(); }
00317 size_type max_size() const { return _M_ht.max_size(); }
00318 bool empty() const { return _M_ht.empty(); }
00319 void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
00320
00321 template <class _Val, class _HF, class _EqK, class _Al>
00322 friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&,
00323 const hash_multiset<_Val, _HF, _EqK, _Al>&);
00324
00325 iterator begin() const { return _M_ht.begin(); }
00326 iterator end() const { return _M_ht.end(); }
00327
00328 public:
00329 iterator insert(const value_type& __obj)
00330 { return _M_ht.insert_equal(__obj); }
00331 template <class _InputIterator>
00332 void insert(_InputIterator __f, _InputIterator __l)
00333 { _M_ht.insert_equal(__f,__l); }
00334 iterator insert_noresize(const value_type& __obj)
00335 { return _M_ht.insert_equal_noresize(__obj); }
00336
00337 iterator find(const key_type& __key) const { return _M_ht.find(__key); }
00338
00339 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
00340
00341 pair<iterator, iterator> equal_range(const key_type& __key) const
00342 { return _M_ht.equal_range(__key); }
00343
00344 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
00345 void erase(iterator __it) { _M_ht.erase(__it); }
00346 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
00347 void clear() { _M_ht.clear(); }
00348
00349 public:
00350 void resize(size_type __hint) { _M_ht.resize(__hint); }
00351 size_type bucket_count() const { return _M_ht.bucket_count(); }
00352 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
00353 size_type elems_in_bucket(size_type __n) const
00354 { return _M_ht.elems_in_bucket(__n); }
00355 };
00356
00357 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00358 inline bool
00359 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00360 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
00361 {
00362 return __hs1._M_ht == __hs2._M_ht;
00363 }
00364
00365 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00366 inline bool
00367 operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00368 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
00369 return !(__hs1 == __hs2);
00370 }
00371
00372 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
00373 inline void
00374 swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
00375 hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
00376 __hs1.swap(__hs2);
00377 }
00378
00379 }
00380
00381 namespace std
00382 {
00383
00384
00385
00386 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00387 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
00388 protected:
00389 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
00390 _Container* container;
00391 public:
00392 typedef _Container container_type;
00393 typedef output_iterator_tag iterator_category;
00394 typedef void value_type;
00395 typedef void difference_type;
00396 typedef void pointer;
00397 typedef void reference;
00398
00399 insert_iterator(_Container& __x) : container(&__x) {}
00400 insert_iterator(_Container& __x, typename _Container::iterator)
00401 : container(&__x) {}
00402 insert_iterator<_Container>&
00403 operator=(const typename _Container::value_type& __value) {
00404 container->insert(__value);
00405 return *this;
00406 }
00407 insert_iterator<_Container>& operator*() { return *this; }
00408 insert_iterator<_Container>& operator++() { return *this; }
00409 insert_iterator<_Container>& operator++(int) { return *this; }
00410 };
00411
00412 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
00413 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
00414 protected:
00415 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
00416 _Container* container;
00417 typename _Container::iterator iter;
00418 public:
00419 typedef _Container container_type;
00420 typedef output_iterator_tag iterator_category;
00421 typedef void value_type;
00422 typedef void difference_type;
00423 typedef void pointer;
00424 typedef void reference;
00425
00426 insert_iterator(_Container& __x) : container(&__x) {}
00427 insert_iterator(_Container& __x, typename _Container::iterator)
00428 : container(&__x) {}
00429 insert_iterator<_Container>&
00430 operator=(const typename _Container::value_type& __value) {
00431 container->insert(__value);
00432 return *this;
00433 }
00434 insert_iterator<_Container>& operator*() { return *this; }
00435 insert_iterator<_Container>& operator++() { return *this; }
00436 insert_iterator<_Container>& operator++(int) { return *this; }
00437 };
00438
00439 }
00440
00441 #endif
00442
00443
00444
00445