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_MAP
00063
#define _HASH_MAP 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::_Select1st;
00074
00075
00076
00077
template<
class _Key,
class _Tp,
class _HashFcn = hash<_Key>,
00078
class _EqualKey = equal_to<_Key>,
class _Alloc = allocator<_Tp> >
00079
class hash_map;
00080
00081
template<
class _Key,
class _Tp,
class _HashFn,
class _EqKey,
class _Alloc>
00082
inline bool operator==(
const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
00083
const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);
00084
00085
00086
00087
00088
00089
template <
class _Key,
class _Tp,
class _HashFcn,
class _EqualKey,
00090
class _Alloc>
00091
class hash_map
00092 {
00093
private:
00094
typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
00095 _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
00096 _Ht _M_ht;
00097
00098
public:
00099
typedef typename _Ht::key_type key_type;
00100
typedef _Tp data_type;
00101
typedef _Tp mapped_type;
00102
typedef typename _Ht::value_type value_type;
00103
typedef typename _Ht::hasher hasher;
00104
typedef typename _Ht::key_equal key_equal;
00105
00106
typedef typename _Ht::size_type size_type;
00107
typedef typename _Ht::difference_type difference_type;
00108
typedef typename _Ht::pointer pointer;
00109
typedef typename _Ht::const_pointer const_pointer;
00110
typedef typename _Ht::reference reference;
00111
typedef typename _Ht::const_reference const_reference;
00112
00113
typedef typename _Ht::iterator iterator;
00114
typedef typename _Ht::const_iterator const_iterator;
00115
00116
typedef typename _Ht::allocator_type allocator_type;
00117
00118 hasher hash_funct()
const {
return _M_ht.hash_funct(); }
00119 key_equal key_eq()
const {
return _M_ht.key_eq(); }
00120 allocator_type get_allocator()
const {
return _M_ht.get_allocator(); }
00121
00122
public:
00123
hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00124
explicit hash_map(size_type __n)
00125 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00126
hash_map(size_type __n,
const hasher& __hf)
00127 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00128
hash_map(size_type __n,
const hasher& __hf,
const key_equal& __eql,
00129
const allocator_type& __a = allocator_type())
00130 : _M_ht(__n, __hf, __eql, __a) {}
00131
00132
template <
class _InputIterator>
00133
hash_map(_InputIterator __f, _InputIterator __l)
00134 : _M_ht(100, hasher(), key_equal(), allocator_type())
00135 { _M_ht.insert_unique(__f, __l); }
00136
template <
class _InputIterator>
00137
hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
00138 : _M_ht(__n, hasher(), key_equal(), allocator_type())
00139 { _M_ht.insert_unique(__f, __l); }
00140
template <
class _InputIterator>
00141
hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00142
const hasher& __hf)
00143 : _M_ht(__n, __hf, key_equal(), allocator_type())
00144 { _M_ht.insert_unique(__f, __l); }
00145
template <
class _InputIterator>
00146
hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00147
const hasher& __hf,
const key_equal& __eql,
00148
const allocator_type& __a = allocator_type())
00149 : _M_ht(__n, __hf, __eql, __a)
00150 { _M_ht.insert_unique(__f, __l); }
00151
00152
public:
00153 size_type size()
const {
return _M_ht.size(); }
00154 size_type max_size()
const {
return _M_ht.max_size(); }
00155
bool empty()
const {
return _M_ht.empty(); }
00156
void swap(
hash_map& __hs) { _M_ht.swap(__hs._M_ht); }
00157
00158
template <
class _K1,
class _T1,
class _HF,
class _EqK,
class _Al>
00159
friend bool operator== (
const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
00160
const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
00161
00162 iterator begin() {
return _M_ht.begin(); }
00163 iterator end() {
return _M_ht.end(); }
00164 const_iterator begin()
const {
return _M_ht.begin(); }
00165 const_iterator end()
const {
return _M_ht.end(); }
00166
00167
public:
00168
pair<iterator,bool> insert(
const value_type& __obj)
00169 {
return _M_ht.insert_unique(__obj); }
00170
template <
class _InputIterator>
00171
void insert(_InputIterator __f, _InputIterator __l)
00172 { _M_ht.insert_unique(__f,__l); }
00173
pair<iterator,bool> insert_noresize(
const value_type& __obj)
00174 {
return _M_ht.insert_unique_noresize(__obj); }
00175
00176 iterator find(
const key_type& __key) {
return _M_ht.find(__key); }
00177 const_iterator find(
const key_type& __key)
const
00178
{
return _M_ht.find(__key); }
00179
00180 _Tp& operator[](
const key_type& __key) {
00181
return _M_ht.find_or_insert(value_type(__key, _Tp())).second;
00182 }
00183
00184 size_type count(
const key_type& __key)
const {
return _M_ht.count(__key); }
00185
00186
pair<iterator, iterator> equal_range(
const key_type& __key)
00187 {
return _M_ht.equal_range(__key); }
00188
pair<const_iterator, const_iterator>
00189
equal_range(
const key_type& __key)
const
00190
{
return _M_ht.equal_range(__key); }
00191
00192 size_type erase(
const key_type& __key) {
return _M_ht.erase(__key); }
00193
void erase(iterator __it) { _M_ht.erase(__it); }
00194
void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
00195
void clear() { _M_ht.clear(); }
00196
00197
void resize(size_type __hint) { _M_ht.resize(__hint); }
00198 size_type bucket_count()
const {
return _M_ht.bucket_count(); }
00199 size_type max_bucket_count()
const {
return _M_ht.max_bucket_count(); }
00200 size_type elems_in_bucket(size_type __n)
const
00201
{
return _M_ht.elems_in_bucket(__n); }
00202 };
00203
00204
template <
class _Key,
class _Tp,
class _HashFcn,
class _EqlKey,
class _Alloc>
00205
inline bool
00206 operator==(
const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
00207
const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
00208 {
00209
return __hm1._M_ht == __hm2._M_ht;
00210 }
00211
00212
template <
class _Key,
class _Tp,
class _HashFcn,
class _EqlKey,
class _Alloc>
00213
inline bool
00214 operator!=(
const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
00215
const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) {
00216
return !(__hm1 == __hm2);
00217 }
00218
00219
template <
class _Key,
class _Tp,
class _HashFcn,
class _EqlKey,
class _Alloc>
00220
inline void
00221
swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
00222 hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
00223 {
00224 __hm1.swap(__hm2);
00225 }
00226
00227
00228
00229
template <
class _Key,
class _Tp,
00230
class _HashFcn = hash<_Key>,
00231
class _EqualKey = equal_to<_Key>,
00232
class _Alloc = allocator<_Tp> >
00233
class hash_multimap;
00234
00235
template <
class _Key,
class _Tp,
class _HF,
class _EqKey,
class _Alloc>
00236
inline bool
00237 operator==(
const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
00238
const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2);
00239
00240
00241
00242
00243
00244
00245
template <
class _Key,
class _Tp,
class _HashFcn,
class _EqualKey,
class _Alloc>
00246
class hash_multimap
00247 {
00248
00249 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00250 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00251 __glibcxx_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept)
00252 __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
00253
00254 private:
00255 typedef hashtable<
pair<const _Key, _Tp>, _Key, _HashFcn,
00256 _Select1st<
pair<const _Key, _Tp> >, _EqualKey, _Alloc>
00257 _Ht;
00258 _Ht _M_ht;
00259
00260 public:
00261 typedef typename _Ht::key_type key_type;
00262 typedef _Tp data_type;
00263 typedef _Tp mapped_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 _Ht::pointer pointer;
00271 typedef typename _Ht::const_pointer const_pointer;
00272 typedef typename _Ht::reference reference;
00273 typedef typename _Ht::const_reference const_reference;
00274
00275 typedef typename _Ht::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_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00286
explicit hash_multimap(size_type __n)
00287 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00288 hash_multimap(size_type __n,
const hasher& __hf)
00289 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00290 hash_multimap(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_multimap(_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_multimap(_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_multimap(_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_multimap(_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_multimap& __hs) { _M_ht.swap(__hs._M_ht); }
00319
00320
template <
class _K1,
class _T1,
class _HF,
class _EqK,
class _Al>
00321
friend bool operator== (
const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
00322
const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
00323
00324 iterator begin() {
return _M_ht.begin(); }
00325 iterator end() {
return _M_ht.end(); }
00326 const_iterator begin()
const {
return _M_ht.begin(); }
00327 const_iterator end()
const {
return _M_ht.end(); }
00328
00329
public:
00330 iterator insert(
const value_type& __obj)
00331 {
return _M_ht.insert_equal(__obj); }
00332
template <
class _InputIterator>
00333
void insert(_InputIterator __f, _InputIterator __l)
00334 { _M_ht.insert_equal(__f,__l); }
00335 iterator insert_noresize(
const value_type& __obj)
00336 {
return _M_ht.insert_equal_noresize(__obj); }
00337
00338 iterator find(
const key_type& __key) {
return _M_ht.find(__key); }
00339 const_iterator find(
const key_type& __key)
const
00340
{
return _M_ht.find(__key); }
00341
00342 size_type count(
const key_type& __key)
const {
return _M_ht.count(__key); }
00343
00344 pair<iterator, iterator>
equal_range(
const key_type& __key)
00345 {
return _M_ht.equal_range(__key); }
00346 pair<const_iterator, const_iterator>
00347
equal_range(
const key_type& __key)
const
00348
{
return _M_ht.equal_range(__key); }
00349
00350 size_type erase(
const key_type& __key) {
return _M_ht.erase(__key); }
00351
void erase(iterator __it) { _M_ht.erase(__it); }
00352
void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
00353
void clear() { _M_ht.clear(); }
00354
00355
public:
00356
void resize(size_type __hint) { _M_ht.resize(__hint); }
00357 size_type bucket_count()
const {
return _M_ht.bucket_count(); }
00358 size_type max_bucket_count()
const {
return _M_ht.max_bucket_count(); }
00359 size_type elems_in_bucket(size_type __n)
const
00360
{
return _M_ht.elems_in_bucket(__n); }
00361 };
00362
00363
template <
class _Key,
class _Tp,
class _HF,
class _EqKey,
class _Alloc>
00364
inline bool
00365 operator==(
const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
00366
const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2)
00367 {
00368
return __hm1._M_ht == __hm2._M_ht;
00369 }
00370
00371
template <
class _Key,
class _Tp,
class _HF,
class _EqKey,
class _Alloc>
00372
inline bool
00373 operator!=(
const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
00374
const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) {
00375
return !(__hm1 == __hm2);
00376 }
00377
00378
template <
class _Key,
class _Tp,
class _HashFcn,
class _EqlKey,
class _Alloc>
00379
inline void
00380
swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
00381 hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
00382 {
00383 __hm1.swap(__hm2);
00384 }
00385
00386 }
00387
00388
namespace std
00389 {
00390
00391
00392
00393
template <
class _Key,
class _Tp,
class _HashFn,
class _EqKey,
class _Alloc>
00394
class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
00395
protected:
00396
typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
00397 _Container* container;
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
template <
class _Key,
class _Tp,
class _HashFn,
class _EqKey,
class _Alloc>
00420
class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
00421
protected:
00422
typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
00423 _Container* container;
00424
typename _Container::iterator iter;
00425
public:
00426
typedef _Container
container_type;
00427
typedef output_iterator_tag
iterator_category;
00428
typedef void value_type;
00429
typedef void difference_type;
00430
typedef void pointer;
00431
typedef void reference;
00432
00433
insert_iterator(_Container& __x) : container(&__x) {}
00434
insert_iterator(_Container& __x,
typename _Container::iterator)
00435 : container(&__x) {}
00436 insert_iterator<_Container>&
00437
operator=(
const typename _Container::value_type& __value) {
00438 container->insert(__value);
00439
return *
this;
00440 }
00441 insert_iterator<_Container>&
operator*() {
return *
this; }
00442 insert_iterator<_Container>&
operator++() {
return *
this; }
00443 insert_iterator<_Container>&
operator++(
int) {
return *
this; }
00444 };
00445 }
00446
00447
#endif