include/c++/stl/stl/_hash_map.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Copyright (c) 1996,1997
   7  * Silicon Graphics Computer Systems, Inc.
   8  *
   9  * Copyright (c) 1997
  10  * Moscow Center for SPARC Technology
  11  *
  12  * Copyright (c) 1999
  13  * Boris Fomitchev
  14  *
  15  * This material is provided "as is", with absolutely no warranty expressed
  16  * or implied. Any use is at your own risk.
  17  *
  18  * Permission to use or copy this software for any purpose is hereby granted
  19  * without fee, provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  */
  25
  26 /* NOTE: This is an internal header file, included by other STL headers.
  27  *   You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _STLP_INTERNAL_HASH_MAP_H
  31 #define _STLP_INTERNAL_HASH_MAP_H
  32
  33 #ifndef _STLP_INTERNAL_HASHTABLE_H
  34 #  include <stl/_hashtable.h>
  35 #endif
  36
  37 _STLP_BEGIN_NAMESPACE
  38
  39 //Specific iterator traits creation
  40 _STLP_CREATE_HASH_ITERATOR_TRAITS(HashMapTraitsT, traits)
  41
  42 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>),
  43           _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Key>),
  44           _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >
  45 class hash_map
  46 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
  47                : public __stlport_class<hash_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> >
  48 #endif
  49 {
  50 private:
  51   typedef hash_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self;
  52 public:
  53   typedef _Key key_type;
  54   typedef _Tp data_type;
  55   typedef _Tp mapped_type;
  56 #if !defined (__DMC__)
  57   typedef pair<const key_type, data_type> value_type;
  58 #else
  59   /* DMC goes too far in template instanciation and tries to fully instanciate
  60    * slist<pair<const int, string> > for instance. The generation of assignment
  61    * operator fails of course so we are force to use mutable key for this compiler.
  62    */
  63   typedef pair<key_type, data_type> value_type;
  64 #endif
  65 private:
  66   //Specific iterator traits creation
  67   typedef _STLP_PRIV _HashMapTraitsT<value_type> _HashMapTraits;
  68
  69 public:
  70   typedef hashtable<value_type, key_type, _HashFcn, _HashMapTraits,
  71                     _STLP_SELECT1ST(value_type, _Key), _EqualKey, _Alloc > _Ht;
  72
  73   typedef typename _Ht::hasher hasher;
  74   typedef typename _Ht::key_equal key_equal;
  75
  76   typedef typename _Ht::size_type size_type;
  77   typedef typename _Ht::difference_type difference_type;
  78   typedef typename _Ht::pointer pointer;
  79   typedef typename _Ht::const_pointer const_pointer;
  80   typedef typename _Ht::reference reference;
  81   typedef typename _Ht::const_reference const_reference;
  82
  83   typedef typename _Ht::iterator iterator;
  84   typedef typename _Ht::const_iterator const_iterator;
  85
  86   typedef typename _Ht::allocator_type allocator_type;
  87
  88   hasher hash_funct() const { return _M_ht.hash_funct(); }
  89   key_equal key_eq() const { return _M_ht.key_eq(); }
  90   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  91
  92 private:
  93   _Ht _M_ht;
  94   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
  95 public:
  96   hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  97   explicit hash_map(size_type __n)
  98     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  99   hash_map(size_type __n, const hasher& __hf)
 100     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 101   hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
 102            const allocator_type& __a = allocator_type())
 103     : _M_ht(__n, __hf, __eql, __a) {}
 104
 105   hash_map(__move_source<_Self> src)
 106     : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {
 107   }
 108
 109 #ifdef _STLP_MEMBER_TEMPLATES
 110   template <class _InputIterator>
 111   hash_map(_InputIterator __f, _InputIterator __l)
 112     : _M_ht(100, hasher(), key_equal(), allocator_type())
 113     { _M_ht.insert_unique(__f, __l); }
 114   template <class _InputIterator>
 115   hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
 116     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 117     { _M_ht.insert_unique(__f, __l); }
 118   template <class _InputIterator>
 119   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 120            const hasher& __hf)
 121     : _M_ht(__n, __hf, key_equal(), allocator_type())
 122     { _M_ht.insert_unique(__f, __l); }
 123 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
 124   template <class _InputIterator>
 125   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 126            const hasher& __hf, const key_equal& __eql)
 127     : _M_ht(__n, __hf, __eql, allocator_type())
 128     { _M_ht.insert_unique(__f, __l); }
 129 # endif
 130   template <class _InputIterator>
 131   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 132            const hasher& __hf, const key_equal& __eql,
 133            const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 134     : _M_ht(__n, __hf, __eql, __a)
 135     { _M_ht.insert_unique(__f, __l); }
 136
 137 #else
 138   hash_map(const value_type* __f, const value_type* __l)
 139     : _M_ht(100, hasher(), key_equal(), allocator_type())
 140     { _M_ht.insert_unique(__f, __l); }
 141   hash_map(const value_type* __f, const value_type* __l, size_type __n)
 142     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 143     { _M_ht.insert_unique(__f, __l); }
 144   hash_map(const value_type* __f, const value_type* __l, size_type __n,
 145            const hasher& __hf)
 146     : _M_ht(__n, __hf, key_equal(), allocator_type())
 147     { _M_ht.insert_unique(__f, __l); }
 148   hash_map(const value_type* __f, const value_type* __l, size_type __n,
 149            const hasher& __hf, const key_equal& __eql,
 150            const allocator_type& __a = allocator_type())
 151     : _M_ht(__n, __hf, __eql, __a)
 152     { _M_ht.insert_unique(__f, __l); }
 153
 154   hash_map(const_iterator __f, const_iterator __l)
 155     : _M_ht(100, hasher(), key_equal(), allocator_type())
 156     { _M_ht.insert_unique(__f, __l); }
 157   hash_map(const_iterator __f, const_iterator __l, size_type __n)
 158     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 159     { _M_ht.insert_unique(__f, __l); }
 160   hash_map(const_iterator __f, const_iterator __l, size_type __n,
 161            const hasher& __hf)
 162     : _M_ht(__n, __hf, key_equal(), allocator_type())
 163     { _M_ht.insert_unique(__f, __l); }
 164   hash_map(const_iterator __f, const_iterator __l, size_type __n,
 165            const hasher& __hf, const key_equal& __eql,
 166            const allocator_type& __a = allocator_type())
 167     : _M_ht(__n, __hf, __eql, __a)
 168     { _M_ht.insert_unique(__f, __l); }
 169 #endif /*_STLP_MEMBER_TEMPLATES */
 170
 171 public:
 172   size_type size() const { return _M_ht.size(); }
 173   size_type max_size() const { return _M_ht.max_size(); }
 174   bool empty() const { return _M_ht.empty(); }
 175   void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
 176   iterator begin() { return _M_ht.begin(); }
 177   iterator end() { return _M_ht.end(); }
 178   const_iterator begin() const { return _M_ht.begin(); }
 179   const_iterator end() const { return _M_ht.end(); }
 180
 181 public:
 182   pair<iterator,bool> insert(const value_type& __obj)
 183   { return _M_ht.insert_unique(__obj); }
 184 #ifdef _STLP_MEMBER_TEMPLATES
 185   template <class _InputIterator>
 186   void insert(_InputIterator __f, _InputIterator __l)
 187   { _M_ht.insert_unique(__f,__l); }
 188 #else
 189   void insert(const value_type* __f, const value_type* __l)
 190   { _M_ht.insert_unique(__f,__l); }
 191   void insert(const_iterator __f, const_iterator __l)
 192   { _M_ht.insert_unique(__f, __l); }
 193 #endif /*_STLP_MEMBER_TEMPLATES */
 194   pair<iterator,bool> insert_noresize(const value_type& __obj)
 195   { return _M_ht.insert_unique_noresize(__obj); }
 196
 197   _STLP_TEMPLATE_FOR_CONT_EXT
 198   iterator find(const _KT& __key) { return _M_ht.find(__key); }
 199   _STLP_TEMPLATE_FOR_CONT_EXT
 200   const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
 201
 202   _STLP_TEMPLATE_FOR_CONT_EXT
 203   _Tp& operator[](const _KT& __key) {
 204     iterator __it = _M_ht.find(__key);
 205     return (__it == _M_ht.end() ?
 206       _M_ht._M_insert(value_type(__key, _STLP_DEFAULT_CONSTRUCTED(_Tp))).second :
 207       (*__it).second );
 208   }
 209
 210   _STLP_TEMPLATE_FOR_CONT_EXT
 211   size_type count(const _KT& __key) const { return _M_ht.count(__key); }
 212
 213   _STLP_TEMPLATE_FOR_CONT_EXT
 214   pair<iterator, iterator> equal_range(const _KT& __key)
 215   { return _M_ht.equal_range(__key); }
 216   _STLP_TEMPLATE_FOR_CONT_EXT
 217   pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
 218   { return _M_ht.equal_range(__key); }
 219
 220   _STLP_TEMPLATE_FOR_CONT_EXT
 221   size_type erase(const _KT& __key) {return _M_ht.erase(__key); }
 222   void erase(iterator __it) { _M_ht.erase(__it); }
 223   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 224   void clear() { _M_ht.clear(); }
 225
 226   void resize(size_type __hint) { _M_ht.resize(__hint); }
 227   size_type bucket_count() const { return _M_ht.bucket_count(); }
 228   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 229   size_type elems_in_bucket(size_type __n) const
 230   { return _M_ht.elems_in_bucket(__n); }
 231 };
 232
 233 //Specific iterator traits creation
 234 _STLP_CREATE_HASH_ITERATOR_TRAITS(HashMultimapTraitsT, traits)
 235
 236 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>),
 237           _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Key>),
 238           _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >
 239 class hash_multimap
 240 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
 241                     : public __stlport_class<hash_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> >
 242 #endif
 243 {
 244 private:
 245   typedef hash_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self;
 246 public:
 247   typedef _Key key_type;
 248   typedef _Tp data_type;
 249   typedef _Tp mapped_type;
 250 #if !defined (__DMC__)
 251   typedef pair<const key_type, data_type> value_type;
 252 #else
 253   typedef pair<key_type, data_type> value_type;
 254 #endif
 255 private:
 256   //Specific iterator traits creation
 257   typedef _STLP_PRIV _HashMultimapTraitsT<value_type> _HashMultimapTraits;
 258
 259 public:
 260   typedef hashtable<value_type, key_type, _HashFcn, _HashMultimapTraits,
 261                     _STLP_SELECT1ST(value_type,  _Key), _EqualKey, _Alloc > _Ht;
 262
 263   typedef typename _Ht::hasher hasher;
 264   typedef typename _Ht::key_equal key_equal;
 265
 266   typedef typename _Ht::size_type size_type;
 267   typedef typename _Ht::difference_type difference_type;
 268   typedef typename _Ht::pointer pointer;
 269   typedef typename _Ht::const_pointer const_pointer;
 270   typedef typename _Ht::reference reference;
 271   typedef typename _Ht::const_reference const_reference;
 272
 273   typedef typename _Ht::iterator iterator;
 274   typedef typename _Ht::const_iterator const_iterator;
 275
 276   typedef typename _Ht::allocator_type allocator_type;
 277
 278   hasher hash_funct() const { return _M_ht.hash_funct(); }
 279   key_equal key_eq() const { return _M_ht.key_eq(); }
 280   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 281
 282 private:
 283   _Ht _M_ht;
 284   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
 285 public:
 286   hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 287   explicit hash_multimap(size_type __n)
 288     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 289   hash_multimap(size_type __n, const hasher& __hf)
 290     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 291   hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
 292                 const allocator_type& __a = allocator_type())
 293     : _M_ht(__n, __hf, __eql, __a) {}
 294
 295   hash_multimap(__move_source<_Self> src)
 296     : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {
 297   }
 298
 299 #ifdef _STLP_MEMBER_TEMPLATES
 300   template <class _InputIterator>
 301   hash_multimap(_InputIterator __f, _InputIterator __l)
 302     : _M_ht(100, hasher(), key_equal(), allocator_type())
 303     { _M_ht.insert_equal(__f, __l); }
 304   template <class _InputIterator>
 305   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
 306     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 307     { _M_ht.insert_equal(__f, __l); }
 308   template <class _InputIterator>
 309   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 310                 const hasher& __hf)
 311     : _M_ht(__n, __hf, key_equal(), allocator_type())
 312     { _M_ht.insert_equal(__f, __l); }
 313 #  ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
 314   template <class _InputIterator>
 315   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 316                 const hasher& __hf, const key_equal& __eql)
 317     : _M_ht(__n, __hf, __eql, allocator_type())
 318     { _M_ht.insert_equal(__f, __l); }
 319 #  endif
 320   template <class _InputIterator>
 321   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 322                 const hasher& __hf, const key_equal& __eql,
 323                 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 324     : _M_ht(__n, __hf, __eql, __a)
 325     { _M_ht.insert_equal(__f, __l); }
 326
 327 #else
 328   hash_multimap(const value_type* __f, const value_type* __l)
 329     : _M_ht(100, hasher(), key_equal(), allocator_type())
 330     { _M_ht.insert_equal(__f, __l); }
 331   hash_multimap(const value_type* __f, const value_type* __l, size_type __n)
 332     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 333     { _M_ht.insert_equal(__f, __l); }
 334   hash_multimap(const value_type* __f, const value_type* __l, size_type __n,
 335                 const hasher& __hf)
 336     : _M_ht(__n, __hf, key_equal(), allocator_type())
 337     { _M_ht.insert_equal(__f, __l); }
 338   hash_multimap(const value_type* __f, const value_type* __l, size_type __n,
 339                 const hasher& __hf, const key_equal& __eql,
 340                 const allocator_type& __a = allocator_type())
 341     : _M_ht(__n, __hf, __eql, __a)
 342     { _M_ht.insert_equal(__f, __l); }
 343
 344   hash_multimap(const_iterator __f, const_iterator __l)
 345     : _M_ht(100, hasher(), key_equal(), allocator_type())
 346     { _M_ht.insert_equal(__f, __l); }
 347   hash_multimap(const_iterator __f, const_iterator __l, size_type __n)
 348     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 349     { _M_ht.insert_equal(__f, __l); }
 350   hash_multimap(const_iterator __f, const_iterator __l, size_type __n,
 351                 const hasher& __hf)
 352     : _M_ht(__n, __hf, key_equal(), allocator_type())
 353     { _M_ht.insert_equal(__f, __l); }
 354   hash_multimap(const_iterator __f, const_iterator __l, size_type __n,
 355                 const hasher& __hf, const key_equal& __eql,
 356                 const allocator_type& __a = allocator_type())
 357     : _M_ht(__n, __hf, __eql, __a)
 358     { _M_ht.insert_equal(__f, __l); }
 359 #endif /*_STLP_MEMBER_TEMPLATES */
 360
 361 public:
 362   size_type size() const { return _M_ht.size(); }
 363   size_type max_size() const { return _M_ht.max_size(); }
 364   bool empty() const { return _M_ht.empty(); }
 365   void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
 366
 367   iterator begin() { return _M_ht.begin(); }
 368   iterator end() { return _M_ht.end(); }
 369   const_iterator begin() const { return _M_ht.begin(); }
 370   const_iterator end() const { return _M_ht.end(); }
 371
 372 public:
 373   iterator insert(const value_type& __obj)
 374     { return _M_ht.insert_equal(__obj); }
 375 #ifdef _STLP_MEMBER_TEMPLATES
 376   template <class _InputIterator>
 377   void insert(_InputIterator __f, _InputIterator __l)
 378     { _M_ht.insert_equal(__f,__l); }
 379 #else
 380   void insert(const value_type* __f, const value_type* __l) {
 381     _M_ht.insert_equal(__f,__l);
 382   }
 383   void insert(const_iterator __f, const_iterator __l)
 384     { _M_ht.insert_equal(__f, __l); }
 385 #endif /*_STLP_MEMBER_TEMPLATES */
 386   iterator insert_noresize(const value_type& __obj)
 387     { return _M_ht.insert_equal_noresize(__obj); }
 388
 389   _STLP_TEMPLATE_FOR_CONT_EXT
 390   iterator find(const _KT& __key) { return _M_ht.find(__key); }
 391   _STLP_TEMPLATE_FOR_CONT_EXT
 392   const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
 393
 394   _STLP_TEMPLATE_FOR_CONT_EXT
 395   size_type count(const _KT& __key) const { return _M_ht.count(__key); }
 396
 397   _STLP_TEMPLATE_FOR_CONT_EXT
 398   pair<iterator, iterator>
 399   equal_range(const _KT& __key) { return _M_ht.equal_range(__key); }
 400   _STLP_TEMPLATE_FOR_CONT_EXT
 401   pair<const_iterator, const_iterator>
 402   equal_range(const _KT& __key) const { return _M_ht.equal_range(__key); }
 403
 404   _STLP_TEMPLATE_FOR_CONT_EXT
 405   size_type erase(const _KT& __key) {return _M_ht.erase(__key); }
 406   void erase(iterator __it) { _M_ht.erase(__it); }
 407   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 408   void clear() { _M_ht.clear(); }
 409
 410 public:
 411   void resize(size_type __hint) { _M_ht.resize(__hint); }
 412   size_type bucket_count() const { return _M_ht.bucket_count(); }
 413   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 414   size_type elems_in_bucket(size_type __n) const
 415   { return _M_ht.elems_in_bucket(__n); }
 416 };
 417
 418 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
 419 #define _STLP_TEMPLATE_CONTAINER hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>
 420 #include <stl/_relops_hash_cont.h>
 421 #undef _STLP_TEMPLATE_CONTAINER
 422 #define _STLP_TEMPLATE_CONTAINER hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>
 423 #include <stl/_relops_hash_cont.h>
 424 #undef _STLP_TEMPLATE_CONTAINER
 425 #undef _STLP_TEMPLATE_HEADER
 426
 427 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 428 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 429 struct __move_traits<hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > :
 430   _STLP_PRIV __move_traits_help<typename hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht>
 431 {};
 432
 433 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 434 struct __move_traits<hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > :
 435   _STLP_PRIV __move_traits_help<typename hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht>
 436 {};
 437
 438 // Specialization of insert_iterator so that it will work for hash_map
 439 // and hash_multimap.
 440 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 441 class insert_iterator<hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
 442 protected:
 443   typedef hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
 444   _Container* container;
 445 public:
 446   typedef _Container          container_type;
 447   typedef output_iterator_tag iterator_category;
 448   typedef void                value_type;
 449   typedef void                difference_type;
 450   typedef void                pointer;
 451   typedef void                reference;
 452
 453   insert_iterator(_Container& __x) : container(&__x) {}
 454   insert_iterator(_Container& __x, typename _Container::iterator)
 455     : container(&__x) {}
 456   insert_iterator<_Container>&
 457   operator=(const typename _Container::value_type& __val) {
 458     container->insert(__val);
 459     return *this;
 460   }
 461   insert_iterator<_Container>& operator*() { return *this; }
 462   insert_iterator<_Container>& operator++() { return *this; }
 463   insert_iterator<_Container>& operator++(int) { return *this; }
 464 };
 465
 466 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 467 class insert_iterator<hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
 468 protected:
 469   typedef hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
 470   _Container* container;
 471   typename _Container::iterator iter;
 472 public:
 473   typedef _Container          container_type;
 474   typedef output_iterator_tag iterator_category;
 475   typedef void                value_type;
 476   typedef void                difference_type;
 477   typedef void                pointer;
 478   typedef void                reference;
 479
 480   insert_iterator(_Container& __x) : container(&__x) {}
 481   insert_iterator(_Container& __x, typename _Container::iterator)
 482     : container(&__x) {}
 483   insert_iterator<_Container>&
 484   operator=(const typename _Container::value_type& __val) {
 485     container->insert(__val);
 486     return *this;
 487   }
 488   insert_iterator<_Container>& operator*() { return *this; }
 489   insert_iterator<_Container>& operator++() { return *this; }
 490   insert_iterator<_Container>& operator++(int) { return *this; }
 491 };
 492 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 493
 494 _STLP_END_NAMESPACE
 495
 496 #endif /* _STLP_INTERNAL_HASH_MAP_H */
 497
 498 // Local Variables:
 499 // mode:C++
 500 // End: