197403Sobrien// Hashing map implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * Copyright (c) 1996 3297403Sobrien * Silicon Graphics Computer Systems, Inc. 3397403Sobrien * 3497403Sobrien * Permission to use, copy, modify, distribute and sell this software 3597403Sobrien * and its documentation for any purpose is hereby granted without fee, 3697403Sobrien * provided that the above copyright notice appear in all copies and 3797403Sobrien * that both that copyright notice and this permission notice appear 3897403Sobrien * in supporting documentation. Silicon Graphics makes no 3997403Sobrien * representations about the suitability of this software for any 4097403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4197403Sobrien * 4297403Sobrien * 4397403Sobrien * Copyright (c) 1994 4497403Sobrien * Hewlett-Packard Company 4597403Sobrien * 4697403Sobrien * Permission to use, copy, modify, distribute and sell this software 4797403Sobrien * and its documentation for any purpose is hereby granted without fee, 4897403Sobrien * provided that the above copyright notice appear in all copies and 4997403Sobrien * that both that copyright notice and this permission notice appear 5097403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 5197403Sobrien * representations about the suitability of this software for any 5297403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5397403Sobrien * 5497403Sobrien */ 5597403Sobrien 5697403Sobrien/** @file ext/hash_map 5797403Sobrien * This file is a GNU extension to the Standard C++ Library (possibly 58169691Skan * containing extensions from the HP/SGI STL subset). 5997403Sobrien */ 6097403Sobrien 61132720Skan#ifndef _HASH_MAP 62132720Skan#define _HASH_MAP 1 6397403Sobrien 64169691Skan#include <bits/c++config.h> 65132720Skan#include <ext/hashtable.h> 6697403Sobrien#include <bits/concept_check.h> 6797403Sobrien 68169691Skan_GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT) 69169691Skan 70132720Skan using std::equal_to; 71132720Skan using std::allocator; 72132720Skan using std::pair; 73132720Skan using std::_Select1st; 7497403Sobrien 75169691Skan /** 76169691Skan * This is an SGI extension. 77169691Skan * @ingroup SGIextensions 78169691Skan * @doctodo 79169691Skan */ 80169691Skan template<class _Key, class _Tp, class _HashFn = hash<_Key>, 81169691Skan class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> > 82169691Skan class hash_map 83169691Skan { 84169691Skan private: 85169691Skan typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn, 86169691Skan _Select1st<pair<const _Key, _Tp> >, 87169691Skan _EqualKey, _Alloc> _Ht; 8897403Sobrien 89169691Skan _Ht _M_ht; 9097403Sobrien 91169691Skan public: 92169691Skan typedef typename _Ht::key_type key_type; 93169691Skan typedef _Tp data_type; 94169691Skan typedef _Tp mapped_type; 95169691Skan typedef typename _Ht::value_type value_type; 96169691Skan typedef typename _Ht::hasher hasher; 97169691Skan typedef typename _Ht::key_equal key_equal; 98169691Skan 99169691Skan typedef typename _Ht::size_type size_type; 100169691Skan typedef typename _Ht::difference_type difference_type; 101169691Skan typedef typename _Ht::pointer pointer; 102169691Skan typedef typename _Ht::const_pointer const_pointer; 103169691Skan typedef typename _Ht::reference reference; 104169691Skan typedef typename _Ht::const_reference const_reference; 105169691Skan 106169691Skan typedef typename _Ht::iterator iterator; 107169691Skan typedef typename _Ht::const_iterator const_iterator; 108169691Skan 109169691Skan typedef typename _Ht::allocator_type allocator_type; 110169691Skan 111169691Skan hasher 112169691Skan hash_funct() const 113169691Skan { return _M_ht.hash_funct(); } 114132720Skan 115169691Skan key_equal 116169691Skan key_eq() const 117169691Skan { return _M_ht.key_eq(); } 11897403Sobrien 119169691Skan allocator_type 120169691Skan get_allocator() const 121169691Skan { return _M_ht.get_allocator(); } 12297403Sobrien 123169691Skan public: 124169691Skan hash_map() 125169691Skan : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 126169691Skan 127169691Skan explicit 128169691Skan hash_map(size_type __n) 129169691Skan : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 13097403Sobrien 131169691Skan hash_map(size_type __n, const hasher& __hf) 132169691Skan : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 13397403Sobrien 134169691Skan hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, 135169691Skan const allocator_type& __a = allocator_type()) 136169691Skan : _M_ht(__n, __hf, __eql, __a) {} 13797403Sobrien 138169691Skan template<class _InputIterator> 139169691Skan hash_map(_InputIterator __f, _InputIterator __l) 140169691Skan : _M_ht(100, hasher(), key_equal(), allocator_type()) 141169691Skan { _M_ht.insert_unique(__f, __l); } 14297403Sobrien 143169691Skan template<class _InputIterator> 144169691Skan hash_map(_InputIterator __f, _InputIterator __l, size_type __n) 145169691Skan : _M_ht(__n, hasher(), key_equal(), allocator_type()) 146169691Skan { _M_ht.insert_unique(__f, __l); } 14797403Sobrien 148169691Skan template<class _InputIterator> 149169691Skan hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 150169691Skan const hasher& __hf) 151169691Skan : _M_ht(__n, __hf, key_equal(), allocator_type()) 152169691Skan { _M_ht.insert_unique(__f, __l); } 15397403Sobrien 154169691Skan template<class _InputIterator> 155169691Skan hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 156169691Skan const hasher& __hf, const key_equal& __eql, 157169691Skan const allocator_type& __a = allocator_type()) 158169691Skan : _M_ht(__n, __hf, __eql, __a) 159169691Skan { _M_ht.insert_unique(__f, __l); } 16097403Sobrien 161169691Skan public: 162169691Skan size_type 163169691Skan size() const 164169691Skan { return _M_ht.size(); } 165169691Skan 166169691Skan size_type 167169691Skan max_size() const 168169691Skan { return _M_ht.max_size(); } 169169691Skan 170169691Skan bool 171169691Skan empty() const 172169691Skan { return _M_ht.empty(); } 173169691Skan 174169691Skan void 175169691Skan swap(hash_map& __hs) 176169691Skan { _M_ht.swap(__hs._M_ht); } 17797403Sobrien 178169691Skan template<class _K1, class _T1, class _HF, class _EqK, class _Al> 179169691Skan friend bool 180169691Skan operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&, 181169691Skan const hash_map<_K1, _T1, _HF, _EqK, _Al>&); 18297403Sobrien 183169691Skan iterator 184169691Skan begin() 185169691Skan { return _M_ht.begin(); } 18697403Sobrien 187169691Skan iterator 188169691Skan end() 189169691Skan { return _M_ht.end(); } 190132720Skan 191169691Skan const_iterator 192169691Skan begin() const 193169691Skan { return _M_ht.begin(); } 19497403Sobrien 195169691Skan const_iterator 196169691Skan end() const 197169691Skan { return _M_ht.end(); } 19897403Sobrien 199169691Skan public: 200169691Skan pair<iterator, bool> 201169691Skan insert(const value_type& __obj) 202169691Skan { return _M_ht.insert_unique(__obj); } 20397403Sobrien 204169691Skan template<class _InputIterator> 205169691Skan void 206169691Skan insert(_InputIterator __f, _InputIterator __l) 207169691Skan { _M_ht.insert_unique(__f, __l); } 20897403Sobrien 209169691Skan pair<iterator, bool> 210169691Skan insert_noresize(const value_type& __obj) 211169691Skan { return _M_ht.insert_unique_noresize(__obj); } 21297403Sobrien 213169691Skan iterator 214169691Skan find(const key_type& __key) 215169691Skan { return _M_ht.find(__key); } 21697403Sobrien 217169691Skan const_iterator 218169691Skan find(const key_type& __key) const 219169691Skan { return _M_ht.find(__key); } 22097403Sobrien 221169691Skan _Tp& 222169691Skan operator[](const key_type& __key) 223169691Skan { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; } 22497403Sobrien 225169691Skan size_type 226169691Skan count(const key_type& __key) const 227169691Skan { return _M_ht.count(__key); } 22897403Sobrien 229169691Skan pair<iterator, iterator> 230169691Skan equal_range(const key_type& __key) 231169691Skan { return _M_ht.equal_range(__key); } 23297403Sobrien 233169691Skan pair<const_iterator, const_iterator> 234169691Skan equal_range(const key_type& __key) const 235169691Skan { return _M_ht.equal_range(__key); } 236169691Skan 237169691Skan size_type 238169691Skan erase(const key_type& __key) 239169691Skan {return _M_ht.erase(__key); } 240169691Skan 241169691Skan void 242169691Skan erase(iterator __it) 243169691Skan { _M_ht.erase(__it); } 244169691Skan 245169691Skan void 246169691Skan erase(iterator __f, iterator __l) 247169691Skan { _M_ht.erase(__f, __l); } 248169691Skan 249169691Skan void 250169691Skan clear() 251169691Skan { _M_ht.clear(); } 252169691Skan 253169691Skan void 254169691Skan resize(size_type __hint) 255169691Skan { _M_ht.resize(__hint); } 256169691Skan 257169691Skan size_type 258169691Skan bucket_count() const 259169691Skan { return _M_ht.bucket_count(); } 260169691Skan 261169691Skan size_type 262169691Skan max_bucket_count() const 263169691Skan { return _M_ht.max_bucket_count(); } 264169691Skan 265169691Skan size_type 266169691Skan elems_in_bucket(size_type __n) const 267169691Skan { return _M_ht.elems_in_bucket(__n); } 268169691Skan }; 269169691Skan 270169691Skan template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc> 271169691Skan inline bool 272169691Skan operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1, 273169691Skan const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2) 274169691Skan { return __hm1._M_ht == __hm2._M_ht; } 275169691Skan 276169691Skan template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc> 277169691Skan inline bool 278169691Skan operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1, 279169691Skan const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2) 280169691Skan { return !(__hm1 == __hm2); } 281169691Skan 282169691Skan template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc> 283169691Skan inline void 284169691Skan swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1, 285169691Skan hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2) 286169691Skan { __hm1.swap(__hm2); } 287169691Skan 288169691Skan 289169691Skan /** 290169691Skan * This is an SGI extension. 291169691Skan * @ingroup SGIextensions 292169691Skan * @doctodo 293169691Skan */ 294169691Skan template<class _Key, class _Tp, 295169691Skan class _HashFn = hash<_Key>, 296169691Skan class _EqualKey = equal_to<_Key>, 297169691Skan class _Alloc = allocator<_Tp> > 298169691Skan class hash_multimap 299169691Skan { 300169691Skan // concept requirements 301169691Skan __glibcxx_class_requires(_Key, _SGIAssignableConcept) 302169691Skan __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 303169691Skan __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept) 304169691Skan __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept) 305169691Skan 306169691Skan private: 307169691Skan typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn, 308169691Skan _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> 30997403Sobrien _Ht; 31097403Sobrien 311169691Skan _Ht _M_ht; 31297403Sobrien 313169691Skan public: 314169691Skan typedef typename _Ht::key_type key_type; 315169691Skan typedef _Tp data_type; 316169691Skan typedef _Tp mapped_type; 317169691Skan typedef typename _Ht::value_type value_type; 318169691Skan typedef typename _Ht::hasher hasher; 319169691Skan typedef typename _Ht::key_equal key_equal; 320169691Skan 321169691Skan typedef typename _Ht::size_type size_type; 322169691Skan typedef typename _Ht::difference_type difference_type; 323169691Skan typedef typename _Ht::pointer pointer; 324169691Skan typedef typename _Ht::const_pointer const_pointer; 325169691Skan typedef typename _Ht::reference reference; 326169691Skan typedef typename _Ht::const_reference const_reference; 327169691Skan 328169691Skan typedef typename _Ht::iterator iterator; 329169691Skan typedef typename _Ht::const_iterator const_iterator; 330169691Skan 331169691Skan typedef typename _Ht::allocator_type allocator_type; 332169691Skan 333169691Skan hasher 334169691Skan hash_funct() const 335169691Skan { return _M_ht.hash_funct(); } 33697403Sobrien 337169691Skan key_equal 338169691Skan key_eq() const 339169691Skan { return _M_ht.key_eq(); } 34097403Sobrien 341169691Skan allocator_type 342169691Skan get_allocator() const 343169691Skan { return _M_ht.get_allocator(); } 34497403Sobrien 345169691Skan public: 346169691Skan hash_multimap() 347169691Skan : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 34897403Sobrien 349169691Skan explicit 350169691Skan hash_multimap(size_type __n) 351169691Skan : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 35297403Sobrien 353169691Skan hash_multimap(size_type __n, const hasher& __hf) 354169691Skan : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 35597403Sobrien 356169691Skan hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, 357169691Skan const allocator_type& __a = allocator_type()) 358169691Skan : _M_ht(__n, __hf, __eql, __a) {} 35997403Sobrien 360169691Skan template<class _InputIterator> 361169691Skan hash_multimap(_InputIterator __f, _InputIterator __l) 362169691Skan : _M_ht(100, hasher(), key_equal(), allocator_type()) 363169691Skan { _M_ht.insert_equal(__f, __l); } 36497403Sobrien 365169691Skan template<class _InputIterator> 366169691Skan hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) 367169691Skan : _M_ht(__n, hasher(), key_equal(), allocator_type()) 368169691Skan { _M_ht.insert_equal(__f, __l); } 36997403Sobrien 370169691Skan template<class _InputIterator> 371169691Skan hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 372169691Skan const hasher& __hf) 373169691Skan : _M_ht(__n, __hf, key_equal(), allocator_type()) 374169691Skan { _M_ht.insert_equal(__f, __l); } 37597403Sobrien 376169691Skan template<class _InputIterator> 377169691Skan hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 378169691Skan const hasher& __hf, const key_equal& __eql, 379169691Skan const allocator_type& __a = allocator_type()) 380169691Skan : _M_ht(__n, __hf, __eql, __a) 381169691Skan { _M_ht.insert_equal(__f, __l); } 38297403Sobrien 383169691Skan public: 384169691Skan size_type 385169691Skan size() const 386169691Skan { return _M_ht.size(); } 387132720Skan 388169691Skan size_type 389169691Skan max_size() const 390169691Skan { return _M_ht.max_size(); } 39197403Sobrien 392169691Skan bool 393169691Skan empty() const 394169691Skan { return _M_ht.empty(); } 39597403Sobrien 396169691Skan void 397169691Skan swap(hash_multimap& __hs) 398169691Skan { _M_ht.swap(__hs._M_ht); } 39997403Sobrien 400169691Skan template<class _K1, class _T1, class _HF, class _EqK, class _Al> 401169691Skan friend bool 402169691Skan operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&, 403169691Skan const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&); 40497403Sobrien 405169691Skan iterator 406169691Skan begin() 407169691Skan { return _M_ht.begin(); } 40897403Sobrien 409169691Skan iterator 410169691Skan end() 411169691Skan { return _M_ht.end(); } 41297403Sobrien 413169691Skan const_iterator 414169691Skan begin() const 415169691Skan { return _M_ht.begin(); } 41697403Sobrien 417169691Skan const_iterator 418169691Skan end() const 419169691Skan { return _M_ht.end(); } 42097403Sobrien 421169691Skan public: 422169691Skan iterator 423169691Skan insert(const value_type& __obj) 424169691Skan { return _M_ht.insert_equal(__obj); } 42597403Sobrien 426169691Skan template<class _InputIterator> 427169691Skan void 428169691Skan insert(_InputIterator __f, _InputIterator __l) 429169691Skan { _M_ht.insert_equal(__f,__l); } 43097403Sobrien 431169691Skan iterator 432169691Skan insert_noresize(const value_type& __obj) 433169691Skan { return _M_ht.insert_equal_noresize(__obj); } 43497403Sobrien 435169691Skan iterator 436169691Skan find(const key_type& __key) 437169691Skan { return _M_ht.find(__key); } 43897403Sobrien 439169691Skan const_iterator 440169691Skan find(const key_type& __key) const 441169691Skan { return _M_ht.find(__key); } 442169691Skan 443169691Skan size_type 444169691Skan count(const key_type& __key) const 445169691Skan { return _M_ht.count(__key); } 446169691Skan 447169691Skan pair<iterator, iterator> 448169691Skan equal_range(const key_type& __key) 449169691Skan { return _M_ht.equal_range(__key); } 450169691Skan 451169691Skan pair<const_iterator, const_iterator> 452169691Skan equal_range(const key_type& __key) const 453169691Skan { return _M_ht.equal_range(__key); } 454169691Skan 455169691Skan size_type 456169691Skan erase(const key_type& __key) 457169691Skan { return _M_ht.erase(__key); } 458169691Skan 459169691Skan void 460169691Skan erase(iterator __it) 461169691Skan { _M_ht.erase(__it); } 462169691Skan 463169691Skan void 464169691Skan erase(iterator __f, iterator __l) 465169691Skan { _M_ht.erase(__f, __l); } 466169691Skan 467169691Skan void 468169691Skan clear() 469169691Skan { _M_ht.clear(); } 470169691Skan 471169691Skan public: 472169691Skan void 473169691Skan resize(size_type __hint) 474169691Skan { _M_ht.resize(__hint); } 475169691Skan 476169691Skan size_type 477169691Skan bucket_count() const 478169691Skan { return _M_ht.bucket_count(); } 479169691Skan 480169691Skan size_type 481169691Skan max_bucket_count() const 482169691Skan { return _M_ht.max_bucket_count(); } 483169691Skan 484169691Skan size_type 485169691Skan elems_in_bucket(size_type __n) const 486169691Skan { return _M_ht.elems_in_bucket(__n); } 487169691Skan }; 488169691Skan 489169691Skan template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 490169691Skan inline bool 491169691Skan operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1, 492169691Skan const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2) 493169691Skan { return __hm1._M_ht == __hm2._M_ht; } 494169691Skan 495169691Skan template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 496169691Skan inline bool 497169691Skan operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1, 498169691Skan const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2) 499169691Skan { return !(__hm1 == __hm2); } 500169691Skan 501169691Skan template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc> 502169691Skan inline void 503169691Skan swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1, 504169691Skan hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2) 505169691Skan { __hm1.swap(__hm2); } 506169691Skan 507169691Skan_GLIBCXX_END_NESTED_NAMESPACE 508169691Skan 509169691Skan#ifdef _GLIBCXX_DEBUG 510169691Skan# include <debug/hash_map> 511132720Skan#endif 512169691Skan 513169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 514169691Skan 515169691Skan // Specialization of insert_iterator so that it will work for hash_map 516169691Skan // and hash_multimap. 517169691Skan template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 518169691Skan class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, 519169691Skan _EqKey, _Alloc> > 520169691Skan { 521169691Skan protected: 522169691Skan typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> 523169691Skan _Container; 524169691Skan _Container* container; 525169691Skan 526169691Skan public: 527169691Skan typedef _Container container_type; 528169691Skan typedef output_iterator_tag iterator_category; 529169691Skan typedef void value_type; 530169691Skan typedef void difference_type; 531169691Skan typedef void pointer; 532169691Skan typedef void reference; 533169691Skan 534169691Skan insert_iterator(_Container& __x) 535169691Skan : container(&__x) {} 536169691Skan 537169691Skan insert_iterator(_Container& __x, typename _Container::iterator) 538169691Skan : container(&__x) {} 539169691Skan 540169691Skan insert_iterator<_Container>& 541169691Skan operator=(const typename _Container::value_type& __value) 542169691Skan { 543169691Skan container->insert(__value); 544169691Skan return *this; 545169691Skan } 546169691Skan 547169691Skan insert_iterator<_Container>& 548169691Skan operator*() 549169691Skan { return *this; } 550169691Skan 551169691Skan insert_iterator<_Container>& 552169691Skan operator++() { return *this; } 553169691Skan 554169691Skan insert_iterator<_Container>& 555169691Skan operator++(int) 556169691Skan { return *this; } 557169691Skan }; 558169691Skan 559169691Skan template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 560169691Skan class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, 561169691Skan _EqKey, _Alloc> > 562169691Skan { 563169691Skan protected: 564169691Skan typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> 565169691Skan _Container; 566169691Skan _Container* container; 567169691Skan typename _Container::iterator iter; 568169691Skan 569169691Skan public: 570169691Skan typedef _Container container_type; 571169691Skan typedef output_iterator_tag iterator_category; 572169691Skan typedef void value_type; 573169691Skan typedef void difference_type; 574169691Skan typedef void pointer; 575169691Skan typedef void reference; 576169691Skan 577169691Skan insert_iterator(_Container& __x) 578169691Skan : container(&__x) {} 579169691Skan 580169691Skan insert_iterator(_Container& __x, typename _Container::iterator) 581169691Skan : container(&__x) {} 582169691Skan 583169691Skan insert_iterator<_Container>& 584169691Skan operator=(const typename _Container::value_type& __value) 585169691Skan { 586169691Skan container->insert(__value); 587169691Skan return *this; 588169691Skan } 589169691Skan 590169691Skan insert_iterator<_Container>& 591169691Skan operator*() 592169691Skan { return *this; } 593169691Skan 594169691Skan insert_iterator<_Container>& 595169691Skan operator++() 596169691Skan { return *this; } 597169691Skan 598169691Skan insert_iterator<_Container>& 599169691Skan operator++(int) 600169691Skan { return *this; } 601169691Skan }; 602169691Skan 603169691Skan_GLIBCXX_END_NAMESPACE 604169691Skan 605169691Skan#endif 606