Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4680 | right-hear | 1 | /* |
2 | * Copyright (c) 1996 |
||
3 | * Silicon Graphics Computer Systems, Inc. |
||
4 | * |
||
5 | * Permission to use, copy, modify, distribute and sell this software |
||
6 | * and its documentation for any purpose is hereby granted without fee, |
||
7 | * provided that the above copyright notice appear in all copies and |
||
8 | * that both that copyright notice and this permission notice appear |
||
9 | * in supporting documentation. Silicon Graphics makes no |
||
10 | * representations about the suitability of this software for any |
||
11 | * purpose. It is provided "as is" without express or implied warranty. |
||
12 | * |
||
13 | * |
||
14 | * Copyright (c) 1994 |
||
15 | * Hewlett-Packard Company |
||
16 | * |
||
17 | * Permission to use, copy, modify, distribute and sell this software |
||
18 | * and its documentation for any purpose is hereby granted without fee, |
||
19 | * provided that the above copyright notice appear in all copies and |
||
20 | * that both that copyright notice and this permission notice appear |
||
21 | * in supporting documentation. Hewlett-Packard Company makes no |
||
22 | * representations about the suitability of this software for any |
||
23 | * purpose. It is provided "as is" without express or implied warranty. |
||
24 | * |
||
25 | */ |
||
26 | |||
27 | /* NOTE: This is an internal header file, included by other STL headers. |
||
28 | * You should not attempt to use it directly. |
||
29 | */ |
||
30 | |||
31 | #ifndef __SGI_STL_INTERNAL_HASH_MAP_H |
||
32 | #define __SGI_STL_INTERNAL_HASH_MAP_H |
||
33 | |||
34 | #include |
||
35 | #include |
||
36 | |||
37 | namespace std |
||
38 | { |
||
39 | |||
40 | // Forward declaration of equality operator; needed for friend declaration. |
||
41 | |||
42 | template |
||
43 | class _HashFcn = hash<_Key>, |
||
44 | class _EqualKey = equal_to<_Key>, |
||
45 | class _Alloc = allocator<_Tp> > |
||
46 | class hash_map; |
||
47 | |||
48 | template |
||
49 | inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&, |
||
50 | const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&); |
||
51 | |||
52 | template |
||
53 | class _Alloc> |
||
54 | class hash_map |
||
55 | { |
||
56 | private: |
||
57 | typedef hashtable |
||
58 | _Select1st |
||
59 | _Ht _M_ht; |
||
60 | |||
61 | public: |
||
62 | typedef typename _Ht::key_type key_type; |
||
63 | typedef _Tp data_type; |
||
64 | typedef _Tp mapped_type; |
||
65 | typedef typename _Ht::value_type value_type; |
||
66 | typedef typename _Ht::hasher hasher; |
||
67 | typedef typename _Ht::key_equal key_equal; |
||
68 | |||
69 | typedef typename _Ht::size_type size_type; |
||
70 | typedef typename _Ht::difference_type difference_type; |
||
71 | typedef typename _Ht::pointer pointer; |
||
72 | typedef typename _Ht::const_pointer const_pointer; |
||
73 | typedef typename _Ht::reference reference; |
||
74 | typedef typename _Ht::const_reference const_reference; |
||
75 | |||
76 | typedef typename _Ht::iterator iterator; |
||
77 | typedef typename _Ht::const_iterator const_iterator; |
||
78 | |||
79 | typedef typename _Ht::allocator_type allocator_type; |
||
80 | |||
81 | hasher hash_funct() const { return _M_ht.hash_funct(); } |
||
82 | key_equal key_eq() const { return _M_ht.key_eq(); } |
||
83 | allocator_type get_allocator() const { return _M_ht.get_allocator(); } |
||
84 | |||
85 | public: |
||
86 | hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} |
||
87 | explicit hash_map(size_type __n) |
||
88 | : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} |
||
89 | hash_map(size_type __n, const hasher& __hf) |
||
90 | : _M_ht(__n, __hf, key_equal(), allocator_type()) {} |
||
91 | hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, |
||
92 | const allocator_type& __a = allocator_type()) |
||
93 | : _M_ht(__n, __hf, __eql, __a) {} |
||
94 | |||
95 | template |
||
96 | hash_map(_InputIterator __f, _InputIterator __l) |
||
97 | : _M_ht(100, hasher(), key_equal(), allocator_type()) |
||
98 | { _M_ht.insert_unique(__f, __l); } |
||
99 | template |
||
100 | hash_map(_InputIterator __f, _InputIterator __l, size_type __n) |
||
101 | : _M_ht(__n, hasher(), key_equal(), allocator_type()) |
||
102 | { _M_ht.insert_unique(__f, __l); } |
||
103 | template |
||
104 | hash_map(_InputIterator __f, _InputIterator __l, size_type __n, |
||
105 | const hasher& __hf) |
||
106 | : _M_ht(__n, __hf, key_equal(), allocator_type()) |
||
107 | { _M_ht.insert_unique(__f, __l); } |
||
108 | template |
||
109 | hash_map(_InputIterator __f, _InputIterator __l, size_type __n, |
||
110 | const hasher& __hf, const key_equal& __eql, |
||
111 | const allocator_type& __a = allocator_type()) |
||
112 | : _M_ht(__n, __hf, __eql, __a) |
||
113 | { _M_ht.insert_unique(__f, __l); } |
||
114 | |||
115 | public: |
||
116 | size_type size() const { return _M_ht.size(); } |
||
117 | size_type max_size() const { return _M_ht.max_size(); } |
||
118 | bool empty() const { return _M_ht.empty(); } |
||
119 | void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); } |
||
120 | |||
121 | template |
||
122 | friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&, |
||
123 | const hash_map<_K1, _T1, _HF, _EqK, _Al>&); |
||
124 | |||
125 | iterator begin() { return _M_ht.begin(); } |
||
126 | iterator end() { return _M_ht.end(); } |
||
127 | const_iterator begin() const { return _M_ht.begin(); } |
||
128 | const_iterator end() const { return _M_ht.end(); } |
||
129 | |||
130 | public: |
||
131 | pair |
||
132 | { return _M_ht.insert_unique(__obj); } |
||
133 | template |
||
134 | void insert(_InputIterator __f, _InputIterator __l) |
||
135 | { _M_ht.insert_unique(__f,__l); } |
||
136 | pair |
||
137 | { return _M_ht.insert_unique_noresize(__obj); } |
||
138 | |||
139 | iterator find(const key_type& __key) { return _M_ht.find(__key); } |
||
140 | const_iterator find(const key_type& __key) const |
||
141 | { return _M_ht.find(__key); } |
||
142 | |||
143 | _Tp& operator[](const key_type& __key) { |
||
144 | return _M_ht.find_or_insert(value_type(__key, _Tp())).second; |
||
145 | } |
||
146 | |||
147 | size_type count(const key_type& __key) const { return _M_ht.count(__key); } |
||
148 | |||
149 | pair |
||
150 | { return _M_ht.equal_range(__key); } |
||
151 | pair |
||
152 | equal_range(const key_type& __key) const |
||
153 | { return _M_ht.equal_range(__key); } |
||
154 | |||
155 | size_type erase(const key_type& __key) {return _M_ht.erase(__key); } |
||
156 | void erase(iterator __it) { _M_ht.erase(__it); } |
||
157 | void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } |
||
158 | void clear() { _M_ht.clear(); } |
||
159 | |||
160 | void resize(size_type __hint) { _M_ht.resize(__hint); } |
||
161 | size_type bucket_count() const { return _M_ht.bucket_count(); } |
||
162 | size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } |
||
163 | size_type elems_in_bucket(size_type __n) const |
||
164 | { return _M_ht.elems_in_bucket(__n); } |
||
165 | }; |
||
166 | |||
167 | template |
||
168 | inline bool |
||
169 | operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, |
||
170 | const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) |
||
171 | { |
||
172 | return __hm1._M_ht == __hm2._M_ht; |
||
173 | } |
||
174 | |||
175 | template |
||
176 | inline bool |
||
177 | operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, |
||
178 | const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) { |
||
179 | return !(__hm1 == __hm2); |
||
180 | } |
||
181 | |||
182 | template |
||
183 | inline void |
||
184 | swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, |
||
185 | hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) |
||
186 | { |
||
187 | __hm1.swap(__hm2); |
||
188 | } |
||
189 | |||
190 | // Forward declaration of equality operator; needed for friend declaration. |
||
191 | |||
192 | template |
||
193 | class _HashFcn = hash<_Key>, |
||
194 | class _EqualKey = equal_to<_Key>, |
||
195 | class _Alloc = allocator<_Tp> > |
||
196 | class hash_multimap; |
||
197 | |||
198 | template |
||
199 | inline bool |
||
200 | operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, |
||
201 | const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2); |
||
202 | |||
203 | template |
||
204 | class hash_multimap |
||
205 | { |
||
206 | // concept requirements |
||
207 | __glibcpp_class_requires(_Key, _SGIAssignableConcept); |
||
208 | __glibcpp_class_requires(_Tp, _SGIAssignableConcept); |
||
209 | __glibcpp_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept); |
||
210 | __glibcpp_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept); |
||
211 | |||
212 | private: |
||
213 | typedef hashtable |
||
214 | _Select1st |
||
215 | _Ht; |
||
216 | _Ht _M_ht; |
||
217 | |||
218 | public: |
||
219 | typedef typename _Ht::key_type key_type; |
||
220 | typedef _Tp data_type; |
||
221 | typedef _Tp mapped_type; |
||
222 | typedef typename _Ht::value_type value_type; |
||
223 | typedef typename _Ht::hasher hasher; |
||
224 | typedef typename _Ht::key_equal key_equal; |
||
225 | |||
226 | typedef typename _Ht::size_type size_type; |
||
227 | typedef typename _Ht::difference_type difference_type; |
||
228 | typedef typename _Ht::pointer pointer; |
||
229 | typedef typename _Ht::const_pointer const_pointer; |
||
230 | typedef typename _Ht::reference reference; |
||
231 | typedef typename _Ht::const_reference const_reference; |
||
232 | |||
233 | typedef typename _Ht::iterator iterator; |
||
234 | typedef typename _Ht::const_iterator const_iterator; |
||
235 | |||
236 | typedef typename _Ht::allocator_type allocator_type; |
||
237 | |||
238 | hasher hash_funct() const { return _M_ht.hash_funct(); } |
||
239 | key_equal key_eq() const { return _M_ht.key_eq(); } |
||
240 | allocator_type get_allocator() const { return _M_ht.get_allocator(); } |
||
241 | |||
242 | public: |
||
243 | hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} |
||
244 | explicit hash_multimap(size_type __n) |
||
245 | : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} |
||
246 | hash_multimap(size_type __n, const hasher& __hf) |
||
247 | : _M_ht(__n, __hf, key_equal(), allocator_type()) {} |
||
248 | hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, |
||
249 | const allocator_type& __a = allocator_type()) |
||
250 | : _M_ht(__n, __hf, __eql, __a) {} |
||
251 | |||
252 | template |
||
253 | hash_multimap(_InputIterator __f, _InputIterator __l) |
||
254 | : _M_ht(100, hasher(), key_equal(), allocator_type()) |
||
255 | { _M_ht.insert_equal(__f, __l); } |
||
256 | template |
||
257 | hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) |
||
258 | : _M_ht(__n, hasher(), key_equal(), allocator_type()) |
||
259 | { _M_ht.insert_equal(__f, __l); } |
||
260 | template |
||
261 | hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, |
||
262 | const hasher& __hf) |
||
263 | : _M_ht(__n, __hf, key_equal(), allocator_type()) |
||
264 | { _M_ht.insert_equal(__f, __l); } |
||
265 | template |
||
266 | hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, |
||
267 | const hasher& __hf, const key_equal& __eql, |
||
268 | const allocator_type& __a = allocator_type()) |
||
269 | : _M_ht(__n, __hf, __eql, __a) |
||
270 | { _M_ht.insert_equal(__f, __l); } |
||
271 | |||
272 | public: |
||
273 | size_type size() const { return _M_ht.size(); } |
||
274 | size_type max_size() const { return _M_ht.max_size(); } |
||
275 | bool empty() const { return _M_ht.empty(); } |
||
276 | void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); } |
||
277 | |||
278 | template |
||
279 | friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&, |
||
280 | const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&); |
||
281 | |||
282 | iterator begin() { return _M_ht.begin(); } |
||
283 | iterator end() { return _M_ht.end(); } |
||
284 | const_iterator begin() const { return _M_ht.begin(); } |
||
285 | const_iterator end() const { return _M_ht.end(); } |
||
286 | |||
287 | public: |
||
288 | iterator insert(const value_type& __obj) |
||
289 | { return _M_ht.insert_equal(__obj); } |
||
290 | template |
||
291 | void insert(_InputIterator __f, _InputIterator __l) |
||
292 | { _M_ht.insert_equal(__f,__l); } |
||
293 | iterator insert_noresize(const value_type& __obj) |
||
294 | { return _M_ht.insert_equal_noresize(__obj); } |
||
295 | |||
296 | iterator find(const key_type& __key) { return _M_ht.find(__key); } |
||
297 | const_iterator find(const key_type& __key) const |
||
298 | { return _M_ht.find(__key); } |
||
299 | |||
300 | size_type count(const key_type& __key) const { return _M_ht.count(__key); } |
||
301 | |||
302 | pair |
||
303 | { return _M_ht.equal_range(__key); } |
||
304 | pair |
||
305 | equal_range(const key_type& __key) const |
||
306 | { return _M_ht.equal_range(__key); } |
||
307 | |||
308 | size_type erase(const key_type& __key) {return _M_ht.erase(__key); } |
||
309 | void erase(iterator __it) { _M_ht.erase(__it); } |
||
310 | void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } |
||
311 | void clear() { _M_ht.clear(); } |
||
312 | |||
313 | public: |
||
314 | void resize(size_type __hint) { _M_ht.resize(__hint); } |
||
315 | size_type bucket_count() const { return _M_ht.bucket_count(); } |
||
316 | size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } |
||
317 | size_type elems_in_bucket(size_type __n) const |
||
318 | { return _M_ht.elems_in_bucket(__n); } |
||
319 | }; |
||
320 | |||
321 | template |
||
322 | inline bool |
||
323 | operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, |
||
324 | const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) |
||
325 | { |
||
326 | return __hm1._M_ht == __hm2._M_ht; |
||
327 | } |
||
328 | |||
329 | template |
||
330 | inline bool |
||
331 | operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, |
||
332 | const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) { |
||
333 | return !(__hm1 == __hm2); |
||
334 | } |
||
335 | |||
336 | template |
||
337 | inline void |
||
338 | swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, |
||
339 | hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) |
||
340 | { |
||
341 | __hm1.swap(__hm2); |
||
342 | } |
||
343 | |||
344 | |||
345 | // Specialization of insert_iterator so that it will work for hash_map |
||
346 | // and hash_multimap. |
||
347 | |||
348 | template |
||
349 | class insert_iterator |
||
350 | protected: |
||
351 | typedef hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; |
||
352 | _Container* container; |
||
353 | public: |
||
354 | typedef _Container container_type; |
||
355 | typedef output_iterator_tag iterator_category; |
||
356 | typedef void value_type; |
||
357 | typedef void difference_type; |
||
358 | typedef void pointer; |
||
359 | typedef void reference; |
||
360 | |||
361 | insert_iterator(_Container& __x) : container(&__x) {} |
||
362 | insert_iterator(_Container& __x, typename _Container::iterator) |
||
363 | : container(&__x) {} |
||
364 | insert_iterator<_Container>& |
||
365 | operator=(const typename _Container::value_type& __value) { |
||
366 | container->insert(__value); |
||
367 | return *this; |
||
368 | } |
||
369 | insert_iterator<_Container>& operator*() { return *this; } |
||
370 | insert_iterator<_Container>& operator++() { return *this; } |
||
371 | insert_iterator<_Container>& operator++(int) { return *this; } |
||
372 | }; |
||
373 | |||
374 | template |
||
375 | class insert_iterator |
||
376 | protected: |
||
377 | typedef hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; |
||
378 | _Container* container; |
||
379 | typename _Container::iterator iter; |
||
380 | public: |
||
381 | typedef _Container container_type; |
||
382 | typedef output_iterator_tag iterator_category; |
||
383 | typedef void value_type; |
||
384 | typedef void difference_type; |
||
385 | typedef void pointer; |
||
386 | typedef void reference; |
||
387 | |||
388 | insert_iterator(_Container& __x) : container(&__x) {} |
||
389 | insert_iterator(_Container& __x, typename _Container::iterator) |
||
390 | : container(&__x) {} |
||
391 | insert_iterator<_Container>& |
||
392 | operator=(const typename _Container::value_type& __value) { |
||
393 | container->insert(__value); |
||
394 | return *this; |
||
395 | } |
||
396 | insert_iterator<_Container>& operator*() { return *this; } |
||
397 | insert_iterator<_Container>& operator++() { return *this; } |
||
398 | insert_iterator<_Container>& operator++(int) { return *this; } |
||
399 | }; |
||
400 | |||
401 | } // namespace std |
||
402 | |||
403 | #endif /* __SGI_STL_INTERNAL_HASH_MAP_H */ |
||
404 | |||
405 | // Local Variables: |
||
406 | // mode:C++ |
||
407 | // End: |