1 // Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009 Free Software Foundation, Inc.
3 // This file is part of the GNU ISO C++ Library. This library is free
4 // software; you can redistribute it and/or modify it under the
5 // terms of the GNU General Public License as published by the
6 // Free Software Foundation; either version 3, or (at your option)
9 // This library is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
14 // Under Section 7 of GPL version 3, you are granted additional
15 // permissions described in the GCC Runtime Library Exception, version
16 // 3.1, as published by the Free Software Foundation.
18 // You should have received a copy of the GNU General Public License and
19 // a copy of the GCC Runtime Library Exception along with this program;
20 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
21 // <http://www.gnu.org/licenses/>.
25 * Silicon Graphics Computer Systems, Inc.
27 * Permission to use, copy, modify, distribute and sell this software
28 * and its documentation for any purpose is hereby granted without fee,
29 * provided that the above copyright notice appear in all copies and
30 * that both that copyright notice and this permission notice appear
31 * in supporting documentation. Silicon Graphics makes no
32 * representations about the suitability of this software for any
33 * purpose. It is provided "as is" without express or implied warranty.
37 * Hewlett-Packard Company
39 * Permission to use, copy, modify, distribute and sell this software
40 * and its documentation for any purpose is hereby granted without fee,
41 * provided that the above copyright notice appear in all copies and
42 * that both that copyright notice and this permission notice appear
43 * in supporting documentation. Hewlett-Packard Company makes no
44 * representations about the suitability of this software for any
45 * purpose. It is provided "as is" without express or implied warranty.
48 #ifndef __INTERPKERNELHASHMAP__
49 #define __INTERPKERNELHASHMAP__
51 #include "InterpKernelStlExt.hxx"
52 #include "InterpKernelHashTable.hxx"
54 namespace INTERP_KERNEL
56 template<class _Key, class _Tp, class _HashFn = hash<_Key>,
57 class _EqualKey = std::equal_to<_Key>, class _Alloc = std::allocator<_Tp> >
61 typedef hashtable<std::pair<const _Key, _Tp>,_Key, _HashFn,
62 STLEXT::Select1st<std::pair<const _Key, _Tp> >,
63 _EqualKey, _Alloc> _Ht;
68 typedef typename _Ht::key_type key_type;
69 typedef _Tp data_type;
70 typedef _Tp mapped_type;
71 typedef typename _Ht::value_type value_type;
72 typedef typename _Ht::hasher hasher;
73 typedef typename _Ht::key_equal key_equal;
75 typedef typename _Ht::size_type size_type;
76 typedef typename _Ht::difference_type difference_type;
77 typedef typename _Ht::pointer pointer;
78 typedef typename _Ht::const_pointer const_pointer;
79 typedef typename _Ht::reference reference;
80 typedef typename _Ht::const_reference const_reference;
82 typedef typename _Ht::iterator iterator;
83 typedef typename _Ht::const_iterator const_iterator;
85 typedef typename _Ht::allocator_type allocator_type;
87 hasher hash_funct() const { return _M_ht.hash_funct(); }
89 key_equal key_eq() const { return _M_ht.key_eq(); }
91 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
93 HashMap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
95 explicit HashMap(size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
97 HashMap(size_type __n, const hasher& __hf) : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
99 HashMap(size_type __n, const hasher& __hf, const key_equal& __eql,
100 const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a) {}
102 template<class _InputIterator>
103 HashMap(_InputIterator __f, _InputIterator __l) : _M_ht(100, hasher(), key_equal(), allocator_type())
104 { _M_ht.insert_unique(__f, __l); }
106 template<class _InputIterator>
107 HashMap(_InputIterator __f, _InputIterator __l, size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type())
108 { _M_ht.insert_unique(__f, __l); }
110 template<class _InputIterator>
111 HashMap(_InputIterator __f, _InputIterator __l, size_type __n, const hasher& __hf)
112 : _M_ht(__n, __hf, key_equal(), allocator_type())
113 { _M_ht.insert_unique(__f, __l); }
115 template<class _InputIterator>
116 HashMap(_InputIterator __f, _InputIterator __l, size_type __n,
117 const hasher& __hf, const key_equal& __eql,
118 const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a)
119 { _M_ht.insert_unique(__f, __l); }
121 size_type size() const { return _M_ht.size(); }
123 size_type max_size() const { return _M_ht.max_size(); }
125 bool empty() const { return _M_ht.empty(); }
127 void swap(HashMap& __hs) { _M_ht.swap(__hs._M_ht); }
129 template<class _K1, class _T1, class _HF, class _EqK, class _Al>
130 friend bool operator== (const HashMap<_K1, _T1, _HF, _EqK, _Al>&,
131 const HashMap<_K1, _T1, _HF, _EqK, _Al>&);
133 iterator begin() { return _M_ht.begin(); }
135 iterator end() { return _M_ht.end(); }
137 const_iterator begin() const { return _M_ht.begin(); }
139 const_iterator end() const { return _M_ht.end(); }
141 std::pair<iterator, bool> insert(const value_type& __obj) { return _M_ht.insert_unique(__obj); }
143 template<class _InputIterator>
144 void insert(_InputIterator __f, _InputIterator __l) { _M_ht.insert_unique(__f, __l); }
146 std::pair<iterator, bool>
147 insert_noresize(const value_type& __obj) { return _M_ht.insert_unique_noresize(__obj); }
149 iterator find(const key_type& __key) { return _M_ht.find(__key); }
151 const_iterator find(const key_type& __key) const { return _M_ht.find(__key); }
153 _Tp& operator[](const key_type& __key) { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
155 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
157 std::pair<iterator, iterator> equal_range(const key_type& __key) { return _M_ht.equal_range(__key); }
159 std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { return _M_ht.equal_range(__key); }
161 size_type erase(const key_type& __key) { return _M_ht.erase(__key); }
163 void erase(iterator __it) { _M_ht.erase(__it); }
165 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
167 void clear() { _M_ht.clear(); }
169 void resize(size_type __hint) { _M_ht.resize(__hint); }
171 size_type bucket_count() const { return _M_ht.bucket_count(); }
173 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
175 size_type elems_in_bucket(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
178 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
179 inline bool operator==(const HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
180 const HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
181 { return __hm1._M_ht == __hm2._M_ht; }
183 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
184 inline bool operator!=(const HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
185 const HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
186 { return !(__hm1 == __hm2); }
188 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
189 inline void swap(HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
190 HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
191 { __hm1.swap(__hm2); }
193 template<class _Key, class _Tp,
194 class _HashFn = hash<_Key>,
195 class _EqualKey = std::equal_to<_Key>,
196 class _Alloc = std::allocator<_Tp> >
200 typedef hashtable<std::pair<const _Key, _Tp>, _Key, _HashFn,
201 STLEXT::Select1st<std::pair<const _Key, _Tp> >, _EqualKey, _Alloc>
205 typedef typename _Ht::key_type key_type;
206 typedef _Tp data_type;
207 typedef _Tp mapped_type;
208 typedef typename _Ht::value_type value_type;
209 typedef typename _Ht::hasher hasher;
210 typedef typename _Ht::key_equal key_equal;
212 typedef typename _Ht::size_type size_type;
213 typedef typename _Ht::difference_type difference_type;
214 typedef typename _Ht::pointer pointer;
215 typedef typename _Ht::const_pointer const_pointer;
216 typedef typename _Ht::reference reference;
217 typedef typename _Ht::const_reference const_reference;
219 typedef typename _Ht::iterator iterator;
220 typedef typename _Ht::const_iterator const_iterator;
222 typedef typename _Ht::allocator_type allocator_type;
224 hasher hash_funct() const { return _M_ht.hash_funct(); }
226 key_equal key_eq() const { return _M_ht.key_eq(); }
228 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
230 HashMultiMap() : _M_ht(100, hasher(), key_equal(), allocator_type()) { }
232 explicit HashMultiMap(size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
234 HashMultiMap(size_type __n, const hasher& __hf) : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
236 HashMultiMap(size_type __n, const hasher& __hf, const key_equal& __eql,
237 const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a) {}
239 template<class _InputIterator>
240 HashMultiMap(_InputIterator __f, _InputIterator __l) : _M_ht(100, hasher(), key_equal(), allocator_type())
241 { _M_ht.insert_equal(__f, __l); }
243 template<class _InputIterator>
244 HashMultiMap(_InputIterator __f, _InputIterator __l, size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type())
245 { _M_ht.insert_equal(__f, __l); }
247 template<class _InputIterator>
248 HashMultiMap(_InputIterator __f, _InputIterator __l, size_type __n, const hasher& __hf)
249 : _M_ht(__n, __hf, key_equal(), allocator_type())
250 { _M_ht.insert_equal(__f, __l); }
252 template<class _InputIterator>
253 HashMultiMap(_InputIterator __f, _InputIterator __l, size_type __n,
254 const hasher& __hf, const key_equal& __eql,
255 const allocator_type& __a = allocator_type())
256 : _M_ht(__n, __hf, __eql, __a)
257 { _M_ht.insert_equal(__f, __l); }
259 size_type size() const { return _M_ht.size(); }
261 size_type max_size() const { return _M_ht.max_size(); }
263 bool empty() const { return _M_ht.empty(); }
265 void swap(HashMultiMap& __hs) { _M_ht.swap(__hs._M_ht); }
267 template<class _K1, class _T1, class _HF, class _EqK, class _Al>
268 friend bool operator==(const HashMultiMap<_K1, _T1, _HF, _EqK, _Al>&,
269 const HashMultiMap<_K1, _T1, _HF, _EqK, _Al>&);
271 iterator begin() { return _M_ht.begin(); }
273 iterator end() { return _M_ht.end(); }
275 const_iterator begin() const { return _M_ht.begin(); }
277 const_iterator end() const { return _M_ht.end(); }
279 iterator insert(const value_type& __obj) { return _M_ht.insert_equal(__obj); }
281 template<class _InputIterator>
282 void insert(_InputIterator __f, _InputIterator __l) { _M_ht.insert_equal(__f,__l); }
284 iterator insert_noresize(const value_type& __obj) { return _M_ht.insert_equal_noresize(__obj); }
286 iterator find(const key_type& __key) { return _M_ht.find(__key); }
288 const_iterator find(const key_type& __key) const { return _M_ht.find(__key); }
290 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
292 std::pair<iterator, iterator> equal_range(const key_type& __key) { return _M_ht.equal_range(__key); }
294 std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { return _M_ht.equal_range(__key); }
296 size_type erase(const key_type& __key) { return _M_ht.erase(__key); }
298 void erase(iterator __it) { _M_ht.erase(__it); }
300 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
302 void clear() { _M_ht.clear(); }
304 void resize(size_type __hint) { _M_ht.resize(__hint); }
306 size_type bucket_count() const { return _M_ht.bucket_count(); }
308 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
310 size_type elems_in_bucket(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
313 template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
314 inline bool operator==(const HashMultiMap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
315 const HashMultiMap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
316 { return __hm1._M_ht == __hm2._M_ht; }
318 template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
319 inline bool operator!=(const HashMultiMap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
320 const HashMultiMap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
321 { return !(__hm1 == __hm2); }
323 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
324 inline void swap(HashMultiMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
325 HashMultiMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
326 { __hm1.swap(__hm2); }
332 // Specialization of insert_iterator so that it will work for HashMap
334 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
335 class insert_iterator<INTERP_KERNEL::HashMap<_Key, _Tp, _HashFn,
339 typedef INTERP_KERNEL::HashMap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
341 _Container* container;
343 typedef _Container container_type;
344 typedef output_iterator_tag iterator_category;
345 typedef void value_type;
346 typedef void difference_type;
347 typedef void pointer;
348 typedef void reference;
350 insert_iterator(_Container& __x) : container(&__x) {}
352 insert_iterator(_Container& __x, typename _Container::iterator) : container(&__x) {}
354 insert_iterator<_Container>& operator=(const typename _Container::value_type& __value__)
356 container->insert(__value__);
360 insert_iterator<_Container>& operator*() { return *this; }
362 insert_iterator<_Container>& operator++() { return *this; }
364 insert_iterator<_Container>& operator++(int) { return *this; }
367 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
368 class insert_iterator<INTERP_KERNEL::HashMultiMap<_Key, _Tp, _HashFn,
372 typedef INTERP_KERNEL::HashMultiMap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
374 _Container* container;
375 typename _Container::iterator iter;
378 typedef _Container container_type;
379 typedef output_iterator_tag iterator_category;
380 typedef void value_type;
381 typedef void difference_type;
382 typedef void pointer;
383 typedef void reference;
385 insert_iterator(_Container& __x) : container(&__x) {}
387 insert_iterator(_Container& __x, typename _Container::iterator) : container(&__x) {}
389 insert_iterator<_Container>& operator=(const typename _Container::value_type& __value__)
391 container->insert(__value__);
395 insert_iterator<_Container>& operator*() { return *this; }
397 insert_iterator<_Container>& operator++() { return *this; }
399 insert_iterator<_Container>& operator++(int) { return *this; }