1 // Hashing map implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
32 * Silicon Graphics Computer Systems, Inc.
34 * Permission to use, copy, modify, distribute and sell this software
35 * and its documentation for any purpose is hereby granted without fee,
36 * provided that the above copyright notice appear in all copies and
37 * that both that copyright notice and this permission notice appear
38 * in supporting documentation. Silicon Graphics makes no
39 * representations about the suitability of this software for any
40 * purpose. It is provided "as is" without express or implied warranty.
44 * Hewlett-Packard Company
46 * Permission to use, copy, modify, distribute and sell this software
47 * and its documentation for any purpose is hereby granted without fee,
48 * provided that the above copyright notice appear in all copies and
49 * that both that copyright notice and this permission notice appear
50 * in supporting documentation. Hewlett-Packard Company makes no
51 * representations about the suitability of this software for any
52 * purpose. It is provided "as is" without express or implied warranty.
56 /** @file ext/hash_map
57 * This file is a GNU extension to the Standard C++ Library (possibly
58 * containing extensions from the HP/SGI STL subset).
64 #include <bits/c++config.h>
65 #include <ext/hashtable.h>
66 #include <bits/concept_check.h>
68 _GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT)
73 using std::_Select1st;
76 * This is an SGI extension.
77 * @ingroup SGIextensions
80 template<class _Key, class _Tp, class _HashFn = hash<_Key>,
81 class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
85 typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
86 _Select1st<pair<const _Key, _Tp> >,
87 _EqualKey, _Alloc> _Ht;
92 typedef typename _Ht::key_type key_type;
93 typedef _Tp data_type;
94 typedef _Tp mapped_type;
95 typedef typename _Ht::value_type value_type;
96 typedef typename _Ht::hasher hasher;
97 typedef typename _Ht::key_equal key_equal;
99 typedef typename _Ht::size_type size_type;
100 typedef typename _Ht::difference_type difference_type;
101 typedef typename _Ht::pointer pointer;
102 typedef typename _Ht::const_pointer const_pointer;
103 typedef typename _Ht::reference reference;
104 typedef typename _Ht::const_reference const_reference;
106 typedef typename _Ht::iterator iterator;
107 typedef typename _Ht::const_iterator const_iterator;
109 typedef typename _Ht::allocator_type allocator_type;
113 { return _M_ht.hash_funct(); }
117 { return _M_ht.key_eq(); }
120 get_allocator() const
121 { return _M_ht.get_allocator(); }
125 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
128 hash_map(size_type __n)
129 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
131 hash_map(size_type __n, const hasher& __hf)
132 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
134 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
135 const allocator_type& __a = allocator_type())
136 : _M_ht(__n, __hf, __eql, __a) {}
138 template<class _InputIterator>
139 hash_map(_InputIterator __f, _InputIterator __l)
140 : _M_ht(100, hasher(), key_equal(), allocator_type())
141 { _M_ht.insert_unique(__f, __l); }
143 template<class _InputIterator>
144 hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
145 : _M_ht(__n, hasher(), key_equal(), allocator_type())
146 { _M_ht.insert_unique(__f, __l); }
148 template<class _InputIterator>
149 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
151 : _M_ht(__n, __hf, key_equal(), allocator_type())
152 { _M_ht.insert_unique(__f, __l); }
154 template<class _InputIterator>
155 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
156 const hasher& __hf, const key_equal& __eql,
157 const allocator_type& __a = allocator_type())
158 : _M_ht(__n, __hf, __eql, __a)
159 { _M_ht.insert_unique(__f, __l); }
164 { return _M_ht.size(); }
168 { return _M_ht.max_size(); }
172 { return _M_ht.empty(); }
176 { _M_ht.swap(__hs._M_ht); }
178 template<class _K1, class _T1, class _HF, class _EqK, class _Al>
180 operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
181 const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
185 { return _M_ht.begin(); }
189 { return _M_ht.end(); }
193 { return _M_ht.begin(); }
197 { return _M_ht.end(); }
201 insert(const value_type& __obj)
202 { return _M_ht.insert_unique(__obj); }
204 template<class _InputIterator>
206 insert(_InputIterator __f, _InputIterator __l)
207 { _M_ht.insert_unique(__f, __l); }
210 insert_noresize(const value_type& __obj)
211 { return _M_ht.insert_unique_noresize(__obj); }
214 find(const key_type& __key)
215 { return _M_ht.find(__key); }
218 find(const key_type& __key) const
219 { return _M_ht.find(__key); }
222 operator[](const key_type& __key)
223 { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
226 count(const key_type& __key) const
227 { return _M_ht.count(__key); }
229 pair<iterator, iterator>
230 equal_range(const key_type& __key)
231 { return _M_ht.equal_range(__key); }
233 pair<const_iterator, const_iterator>
234 equal_range(const key_type& __key) const
235 { return _M_ht.equal_range(__key); }
238 erase(const key_type& __key)
239 {return _M_ht.erase(__key); }
243 { _M_ht.erase(__it); }
246 erase(iterator __f, iterator __l)
247 { _M_ht.erase(__f, __l); }
254 resize(size_type __hint)
255 { _M_ht.resize(__hint); }
259 { return _M_ht.bucket_count(); }
262 max_bucket_count() const
263 { return _M_ht.max_bucket_count(); }
266 elems_in_bucket(size_type __n) const
267 { return _M_ht.elems_in_bucket(__n); }
270 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
272 operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
273 const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
274 { return __hm1._M_ht == __hm2._M_ht; }
276 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
278 operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
279 const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
280 { return !(__hm1 == __hm2); }
282 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
284 swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
285 hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
286 { __hm1.swap(__hm2); }
290 * This is an SGI extension.
291 * @ingroup SGIextensions
294 template<class _Key, class _Tp,
295 class _HashFn = hash<_Key>,
296 class _EqualKey = equal_to<_Key>,
297 class _Alloc = allocator<_Tp> >
300 // concept requirements
301 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
302 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
303 __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
304 __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
307 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
308 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
314 typedef typename _Ht::key_type key_type;
315 typedef _Tp data_type;
316 typedef _Tp mapped_type;
317 typedef typename _Ht::value_type value_type;
318 typedef typename _Ht::hasher hasher;
319 typedef typename _Ht::key_equal key_equal;
321 typedef typename _Ht::size_type size_type;
322 typedef typename _Ht::difference_type difference_type;
323 typedef typename _Ht::pointer pointer;
324 typedef typename _Ht::const_pointer const_pointer;
325 typedef typename _Ht::reference reference;
326 typedef typename _Ht::const_reference const_reference;
328 typedef typename _Ht::iterator iterator;
329 typedef typename _Ht::const_iterator const_iterator;
331 typedef typename _Ht::allocator_type allocator_type;
335 { return _M_ht.hash_funct(); }
339 { return _M_ht.key_eq(); }
342 get_allocator() const
343 { return _M_ht.get_allocator(); }
347 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
350 hash_multimap(size_type __n)
351 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
353 hash_multimap(size_type __n, const hasher& __hf)
354 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
356 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
357 const allocator_type& __a = allocator_type())
358 : _M_ht(__n, __hf, __eql, __a) {}
360 template<class _InputIterator>
361 hash_multimap(_InputIterator __f, _InputIterator __l)
362 : _M_ht(100, hasher(), key_equal(), allocator_type())
363 { _M_ht.insert_equal(__f, __l); }
365 template<class _InputIterator>
366 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
367 : _M_ht(__n, hasher(), key_equal(), allocator_type())
368 { _M_ht.insert_equal(__f, __l); }
370 template<class _InputIterator>
371 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
373 : _M_ht(__n, __hf, key_equal(), allocator_type())
374 { _M_ht.insert_equal(__f, __l); }
376 template<class _InputIterator>
377 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
378 const hasher& __hf, const key_equal& __eql,
379 const allocator_type& __a = allocator_type())
380 : _M_ht(__n, __hf, __eql, __a)
381 { _M_ht.insert_equal(__f, __l); }
386 { return _M_ht.size(); }
390 { return _M_ht.max_size(); }
394 { return _M_ht.empty(); }
397 swap(hash_multimap& __hs)
398 { _M_ht.swap(__hs._M_ht); }
400 template<class _K1, class _T1, class _HF, class _EqK, class _Al>
402 operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
403 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
407 { return _M_ht.begin(); }
411 { return _M_ht.end(); }
415 { return _M_ht.begin(); }
419 { return _M_ht.end(); }
423 insert(const value_type& __obj)
424 { return _M_ht.insert_equal(__obj); }
426 template<class _InputIterator>
428 insert(_InputIterator __f, _InputIterator __l)
429 { _M_ht.insert_equal(__f,__l); }
432 insert_noresize(const value_type& __obj)
433 { return _M_ht.insert_equal_noresize(__obj); }
436 find(const key_type& __key)
437 { return _M_ht.find(__key); }
440 find(const key_type& __key) const
441 { return _M_ht.find(__key); }
444 count(const key_type& __key) const
445 { return _M_ht.count(__key); }
447 pair<iterator, iterator>
448 equal_range(const key_type& __key)
449 { return _M_ht.equal_range(__key); }
451 pair<const_iterator, const_iterator>
452 equal_range(const key_type& __key) const
453 { return _M_ht.equal_range(__key); }
456 erase(const key_type& __key)
457 { return _M_ht.erase(__key); }
461 { _M_ht.erase(__it); }
464 erase(iterator __f, iterator __l)
465 { _M_ht.erase(__f, __l); }
473 resize(size_type __hint)
474 { _M_ht.resize(__hint); }
478 { return _M_ht.bucket_count(); }
481 max_bucket_count() const
482 { return _M_ht.max_bucket_count(); }
485 elems_in_bucket(size_type __n) const
486 { return _M_ht.elems_in_bucket(__n); }
489 template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
491 operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
492 const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
493 { return __hm1._M_ht == __hm2._M_ht; }
495 template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
497 operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
498 const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
499 { return !(__hm1 == __hm2); }
501 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
503 swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
504 hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
505 { __hm1.swap(__hm2); }
507 _GLIBCXX_END_NESTED_NAMESPACE
509 #ifdef _GLIBCXX_DEBUG
510 # include <debug/hash_map>
513 _GLIBCXX_BEGIN_NAMESPACE(std)
515 // Specialization of insert_iterator so that it will work for hash_map
516 // and hash_multimap.
517 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
518 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
522 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
524 _Container* container;
527 typedef _Container container_type;
528 typedef output_iterator_tag iterator_category;
529 typedef void value_type;
530 typedef void difference_type;
531 typedef void pointer;
532 typedef void reference;
534 insert_iterator(_Container& __x)
537 insert_iterator(_Container& __x, typename _Container::iterator)
540 insert_iterator<_Container>&
541 operator=(const typename _Container::value_type& __value)
543 container->insert(__value);
547 insert_iterator<_Container>&
551 insert_iterator<_Container>&
552 operator++() { return *this; }
554 insert_iterator<_Container>&
559 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
560 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
564 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
566 _Container* container;
567 typename _Container::iterator iter;
570 typedef _Container container_type;
571 typedef output_iterator_tag iterator_category;
572 typedef void value_type;
573 typedef void difference_type;
574 typedef void pointer;
575 typedef void reference;
577 insert_iterator(_Container& __x)
580 insert_iterator(_Container& __x, typename _Container::iterator)
583 insert_iterator<_Container>&
584 operator=(const typename _Container::value_type& __value)
586 container->insert(__value);
590 insert_iterator<_Container>&
594 insert_iterator<_Container>&
598 insert_iterator<_Container>&
603 _GLIBCXX_END_NAMESPACE