OSDN Git Service

b796babd68b1ec3a362b3bf4839674b343111e10
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / ext / hash_set
1 // Hashing set implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
4 //
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)
9 // any later version.
10
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.
15
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,
19 // USA.
20
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.
29
30 /*
31  * Copyright (c) 1996
32  * Silicon Graphics Computer Systems, Inc.
33  *
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.
41  *
42  *
43  * Copyright (c) 1994
44  * Hewlett-Packard Company
45  *
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.
53  *
54  */
55
56 /** @file ext/hash_set
57  *  This file is a GNU extension to the Standard C++ Library (possibly
58  *  containing extensions from the HP/SGI STL subset).
59  */
60
61 #ifndef _HASH_SET
62 #define _HASH_SET 1
63
64 #include <bits/c++config.h>
65 #include <ext/hashtable.h>
66 #include <bits/concept_check.h>
67
68 _GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT_D)
69
70   using std::equal_to;
71   using std::allocator;
72   using std::pair;
73   using std::_Identity;
74
75   /**
76    *  This is an SGI extension.
77    *  @ingroup SGIextensions
78    *  @doctodo
79    */
80   template<class _Value, class _HashFcn  = hash<_Value>,
81            class _EqualKey = equal_to<_Value>,
82            class _Alloc = allocator<_Value> >
83     class hash_set
84     {
85       // concept requirements
86       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
87       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
88       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
89
90     private:
91       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
92                         _EqualKey, _Alloc> _Ht;
93       _Ht _M_ht;
94
95     public:
96       typedef typename _Ht::key_type key_type;
97       typedef typename _Ht::value_type value_type;
98       typedef typename _Ht::hasher hasher;
99       typedef typename _Ht::key_equal key_equal;
100       
101       typedef typename _Ht::size_type size_type;
102       typedef typename _Ht::difference_type difference_type;
103       typedef typename _Alloc::pointer pointer;
104       typedef typename _Alloc::const_pointer const_pointer;
105       typedef typename _Alloc::reference reference;
106       typedef typename _Alloc::const_reference const_reference;
107       
108       typedef typename _Ht::const_iterator iterator;
109       typedef typename _Ht::const_iterator const_iterator;
110       
111       typedef typename _Ht::allocator_type allocator_type;
112       
113       hasher
114       hash_funct() const
115       { return _M_ht.hash_funct(); }
116
117       key_equal
118       key_eq() const
119       { return _M_ht.key_eq(); }
120
121       allocator_type
122       get_allocator() const
123       { return _M_ht.get_allocator(); }
124
125     public:
126       hash_set()
127       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
128
129       explicit
130       hash_set(size_type __n)
131       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
132
133       hash_set(size_type __n, const hasher& __hf)
134       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
135
136       hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
137                const allocator_type& __a = allocator_type())
138       : _M_ht(__n, __hf, __eql, __a) {}
139
140       template<class _InputIterator>
141         hash_set(_InputIterator __f, _InputIterator __l)
142         : _M_ht(100, hasher(), key_equal(), allocator_type())
143         { _M_ht.insert_unique(__f, __l); }
144
145       template<class _InputIterator>
146         hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
147         : _M_ht(__n, hasher(), key_equal(), allocator_type())
148         { _M_ht.insert_unique(__f, __l); }
149
150       template<class _InputIterator>
151         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
152                  const hasher& __hf)
153         : _M_ht(__n, __hf, key_equal(), allocator_type())
154         { _M_ht.insert_unique(__f, __l); }
155
156       template<class _InputIterator>
157         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
158                  const hasher& __hf, const key_equal& __eql,
159                  const allocator_type& __a = allocator_type())
160         : _M_ht(__n, __hf, __eql, __a)
161         { _M_ht.insert_unique(__f, __l); }
162
163     public:
164       size_type
165       size() const
166       { return _M_ht.size(); }
167
168       size_type
169       max_size() const
170       { return _M_ht.max_size(); }
171       
172       bool
173       empty() const
174       { return _M_ht.empty(); }
175       
176       void
177       swap(hash_set& __hs)
178       { _M_ht.swap(__hs._M_ht); }
179
180       template<class _Val, class _HF, class _EqK, class _Al>
181         friend bool
182         operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
183                    const hash_set<_Val, _HF, _EqK, _Al>&);
184
185       iterator
186       begin() const
187       { return _M_ht.begin(); }
188       
189       iterator
190       end() const
191       { return _M_ht.end(); }
192
193     public:
194       pair<iterator, bool>
195       insert(const value_type& __obj)
196       {
197         pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
198         return pair<iterator,bool>(__p.first, __p.second);
199       }
200
201       template<class _InputIterator>
202         void
203         insert(_InputIterator __f, _InputIterator __l)
204         { _M_ht.insert_unique(__f, __l); }
205
206       pair<iterator, bool>
207       insert_noresize(const value_type& __obj)
208       {
209         pair<typename _Ht::iterator, bool> __p
210           = _M_ht.insert_unique_noresize(__obj);
211         return pair<iterator, bool>(__p.first, __p.second);
212       }
213
214       iterator
215       find(const key_type& __key) const
216       { return _M_ht.find(__key); }
217
218       size_type
219       count(const key_type& __key) const
220       { return _M_ht.count(__key); }
221
222       pair<iterator, iterator>
223       equal_range(const key_type& __key) const
224       { return _M_ht.equal_range(__key); }
225
226       size_type
227       erase(const key_type& __key)
228       {return _M_ht.erase(__key); }
229       
230       void
231       erase(iterator __it)
232       { _M_ht.erase(__it); }
233       
234       void
235       erase(iterator __f, iterator __l)
236       { _M_ht.erase(__f, __l); }
237       
238       void
239       clear()
240       { _M_ht.clear(); }
241
242     public:
243       void
244       resize(size_type __hint)
245       { _M_ht.resize(__hint); }
246       
247       size_type
248       bucket_count() const
249       { return _M_ht.bucket_count(); }
250       
251       size_type
252       max_bucket_count() const
253       { return _M_ht.max_bucket_count(); }
254       
255       size_type
256       elems_in_bucket(size_type __n) const
257       { return _M_ht.elems_in_bucket(__n); }
258     };
259
260   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
261     inline bool
262     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
263                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
264     { return __hs1._M_ht == __hs2._M_ht; }
265
266   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
267     inline bool
268     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
269                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
270     { return !(__hs1 == __hs2); }
271
272   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
273     inline void
274     swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
275          hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
276     { __hs1.swap(__hs2); }
277
278
279   /**
280    *  This is an SGI extension.
281    *  @ingroup SGIextensions
282    *  @doctodo
283    */
284   template<class _Value,
285            class _HashFcn = hash<_Value>,
286            class _EqualKey = equal_to<_Value>,
287            class _Alloc = allocator<_Value> >
288     class hash_multiset
289     {
290       // concept requirements
291       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
292       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
293       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
294
295     private:
296       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
297                         _EqualKey, _Alloc> _Ht;
298       _Ht _M_ht;
299
300     public:
301       typedef typename _Ht::key_type key_type;
302       typedef typename _Ht::value_type value_type;
303       typedef typename _Ht::hasher hasher;
304       typedef typename _Ht::key_equal key_equal;
305       
306       typedef typename _Ht::size_type size_type;
307       typedef typename _Ht::difference_type difference_type;
308       typedef typename _Alloc::pointer pointer;
309       typedef typename _Alloc::const_pointer const_pointer;
310       typedef typename _Alloc::reference reference;
311       typedef typename _Alloc::const_reference const_reference;
312
313       typedef typename _Ht::const_iterator iterator;
314       typedef typename _Ht::const_iterator const_iterator;
315       
316       typedef typename _Ht::allocator_type allocator_type;
317       
318       hasher
319       hash_funct() const
320       { return _M_ht.hash_funct(); }
321       
322       key_equal
323       key_eq() const
324       { return _M_ht.key_eq(); }
325       
326       allocator_type
327       get_allocator() const
328       { return _M_ht.get_allocator(); }
329
330     public:
331       hash_multiset()
332       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
333
334       explicit
335       hash_multiset(size_type __n)
336       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
337
338       hash_multiset(size_type __n, const hasher& __hf)
339       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
340       
341       hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
342                     const allocator_type& __a = allocator_type())
343       : _M_ht(__n, __hf, __eql, __a) {}
344
345       template<class _InputIterator>
346         hash_multiset(_InputIterator __f, _InputIterator __l)
347         : _M_ht(100, hasher(), key_equal(), allocator_type())
348         { _M_ht.insert_equal(__f, __l); }
349
350       template<class _InputIterator>
351         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
352         : _M_ht(__n, hasher(), key_equal(), allocator_type())
353         { _M_ht.insert_equal(__f, __l); }
354
355       template<class _InputIterator>
356         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
357                       const hasher& __hf)
358         : _M_ht(__n, __hf, key_equal(), allocator_type())
359         { _M_ht.insert_equal(__f, __l); }
360
361       template<class _InputIterator>
362         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
363                       const hasher& __hf, const key_equal& __eql,
364                       const allocator_type& __a = allocator_type())
365         : _M_ht(__n, __hf, __eql, __a)
366         { _M_ht.insert_equal(__f, __l); }
367
368     public:
369       size_type
370       size() const
371       { return _M_ht.size(); }
372
373       size_type
374       max_size() const
375       { return _M_ht.max_size(); }
376
377       bool
378       empty() const
379       { return _M_ht.empty(); }
380
381       void
382       swap(hash_multiset& hs)
383       { _M_ht.swap(hs._M_ht); }
384
385       template<class _Val, class _HF, class _EqK, class _Al>
386         friend bool
387         operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
388                    const hash_multiset<_Val, _HF, _EqK, _Al>&);
389
390       iterator
391       begin() const
392       { return _M_ht.begin(); }
393       
394       iterator
395       end() const
396       { return _M_ht.end(); }
397
398     public:
399       iterator
400       insert(const value_type& __obj)
401       { return _M_ht.insert_equal(__obj); }
402   
403       template<class _InputIterator>
404         void
405         insert(_InputIterator __f, _InputIterator __l)
406         { _M_ht.insert_equal(__f,__l); }
407   
408       iterator
409       insert_noresize(const value_type& __obj)
410       { return _M_ht.insert_equal_noresize(__obj); }
411
412       iterator
413       find(const key_type& __key) const
414       { return _M_ht.find(__key); }
415
416       size_type
417       count(const key_type& __key) const
418       { return _M_ht.count(__key); }
419
420       pair<iterator, iterator>
421       equal_range(const key_type& __key) const
422       { return _M_ht.equal_range(__key); }
423
424       size_type
425       erase(const key_type& __key)
426       { return _M_ht.erase(__key); }
427   
428       void
429       erase(iterator __it)
430       { _M_ht.erase(__it); }
431   
432       void
433       erase(iterator __f, iterator __l)
434       { _M_ht.erase(__f, __l); }
435   
436       void
437       clear()
438       { _M_ht.clear(); }
439
440     public:
441       void
442       resize(size_type __hint)
443       { _M_ht.resize(__hint); }
444   
445       size_type
446       bucket_count() const
447       { return _M_ht.bucket_count(); }
448
449       size_type
450       max_bucket_count() const
451       { return _M_ht.max_bucket_count(); }
452
453       size_type
454       elems_in_bucket(size_type __n) const
455       { return _M_ht.elems_in_bucket(__n); }
456     };
457
458   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
459     inline bool
460     operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
461                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
462     { return __hs1._M_ht == __hs2._M_ht; }
463
464   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
465     inline bool
466     operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
467                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
468     { return !(__hs1 == __hs2); }
469
470   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
471     inline void
472     swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
473          hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
474     { __hs1.swap(__hs2); }
475
476 _GLIBCXX_END_NESTED_NAMESPACE
477
478 #ifdef _GLIBCXX_DEBUG
479 # include <debug/hash_set>
480 #endif
481
482 _GLIBCXX_BEGIN_NAMESPACE(std)
483
484   // Specialization of insert_iterator so that it will work for hash_set
485   // and hash_multiset.
486   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
487     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
488                                               _EqualKey, _Alloc> >
489     {
490     protected:
491       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
492         _Container;
493       _Container* container;
494
495     public:
496       typedef _Container          container_type;
497       typedef output_iterator_tag iterator_category;
498       typedef void                value_type;
499       typedef void                difference_type;
500       typedef void                pointer;
501       typedef void                reference;
502
503       insert_iterator(_Container& __x)
504       : container(&__x) {}
505       
506       insert_iterator(_Container& __x, typename _Container::iterator)
507       : container(&__x) {}
508
509       insert_iterator<_Container>&
510       operator=(const typename _Container::value_type& __value)
511       {
512         container->insert(__value);
513         return *this;
514       }
515
516       insert_iterator<_Container>&
517       operator*()
518       { return *this; }
519       
520       insert_iterator<_Container>&
521       operator++()
522       { return *this; }
523       
524       insert_iterator<_Container>&
525       operator++(int)
526       { return *this; }
527     };
528
529   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
530     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
531                                                    _EqualKey, _Alloc> >
532     {
533     protected:
534       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
535         _Container;
536       _Container* container;
537       typename _Container::iterator iter;
538
539     public:
540       typedef _Container          container_type;
541       typedef output_iterator_tag iterator_category;
542       typedef void                value_type;
543       typedef void                difference_type;
544       typedef void                pointer;
545       typedef void                reference;
546       
547       insert_iterator(_Container& __x)
548       : container(&__x) {}
549       
550       insert_iterator(_Container& __x, typename _Container::iterator)
551       : container(&__x) {}
552
553       insert_iterator<_Container>&
554       operator=(const typename _Container::value_type& __value)
555       {
556         container->insert(__value);
557         return *this;
558       }
559
560       insert_iterator<_Container>&
561       operator*()
562       { return *this; }
563
564       insert_iterator<_Container>&
565       operator++()
566       { return *this; }
567
568       insert_iterator<_Container>&
569       operator++(int) { return *this; }
570     };
571
572 _GLIBCXX_END_NAMESPACE
573
574 #endif