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