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