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