xref: /netbsd-src/external/gpl3/gcc.old/dist/libstdc++-v3/include/tr1/unordered_set.h (revision b7b7574d3bf8eeb51a1fa3977b59142ec6434a55)
1 // TR1 unordered_set implementation -*- C++ -*-
2 
3 // Copyright (C) 2010 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /** @file tr1/unordered_set.h
26  *  This is an internal header file, included by other library headers.
27  *  You should not attempt to use it directly.
28  */
29 
30 namespace std
31 {
32 namespace tr1
33 {
34   // XXX When we get typedef templates these class definitions
35   // will be unnecessary.
36   template<class _Value,
37 	   class _Hash = hash<_Value>,
38 	   class _Pred = std::equal_to<_Value>,
39 	   class _Alloc = std::allocator<_Value>,
40 	   bool __cache_hash_code = false>
41     class __unordered_set
42     : public _Hashtable<_Value, _Value, _Alloc,
43 			std::_Identity<_Value>, _Pred,
44 			_Hash, __detail::_Mod_range_hashing,
45 			__detail::_Default_ranged_hash,
46 			__detail::_Prime_rehash_policy,
47 			__cache_hash_code, true, true>
48     {
49       typedef _Hashtable<_Value, _Value, _Alloc,
50 			 std::_Identity<_Value>, _Pred,
51 			 _Hash, __detail::_Mod_range_hashing,
52 			 __detail::_Default_ranged_hash,
53 			 __detail::_Prime_rehash_policy,
54 			 __cache_hash_code, true, true>
55         _Base;
56 
57     public:
58       typedef typename _Base::size_type       size_type;
59       typedef typename _Base::hasher          hasher;
60       typedef typename _Base::key_equal       key_equal;
61       typedef typename _Base::allocator_type  allocator_type;
62 
63       explicit
64       __unordered_set(size_type __n = 10,
65 		      const hasher& __hf = hasher(),
66 		      const key_equal& __eql = key_equal(),
67 		      const allocator_type& __a = allocator_type())
68       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
69 	      __detail::_Default_ranged_hash(), __eql,
70 	      std::_Identity<_Value>(), __a)
71       { }
72 
73       template<typename _InputIterator>
74         __unordered_set(_InputIterator __f, _InputIterator __l,
75 			size_type __n = 10,
76 			const hasher& __hf = hasher(),
77 			const key_equal& __eql = key_equal(),
78 			const allocator_type& __a = allocator_type())
79 	: _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
80 		__detail::_Default_ranged_hash(), __eql,
81 		std::_Identity<_Value>(), __a)
82         { }
83     };
84 
85   template<class _Value,
86 	   class _Hash = hash<_Value>,
87 	   class _Pred = std::equal_to<_Value>,
88 	   class _Alloc = std::allocator<_Value>,
89 	   bool __cache_hash_code = false>
90     class __unordered_multiset
91     : public _Hashtable<_Value, _Value, _Alloc,
92 			std::_Identity<_Value>, _Pred,
93 			_Hash, __detail::_Mod_range_hashing,
94 			__detail::_Default_ranged_hash,
95 			__detail::_Prime_rehash_policy,
96 			__cache_hash_code, true, false>
97     {
98       typedef _Hashtable<_Value, _Value, _Alloc,
99 			 std::_Identity<_Value>, _Pred,
100 			 _Hash, __detail::_Mod_range_hashing,
101 			 __detail::_Default_ranged_hash,
102 			 __detail::_Prime_rehash_policy,
103 			 __cache_hash_code, true, false>
104         _Base;
105 
106     public:
107       typedef typename _Base::size_type       size_type;
108       typedef typename _Base::hasher          hasher;
109       typedef typename _Base::key_equal       key_equal;
110       typedef typename _Base::allocator_type  allocator_type;
111 
112       explicit
113       __unordered_multiset(size_type __n = 10,
114 			   const hasher& __hf = hasher(),
115 			   const key_equal& __eql = key_equal(),
116 			   const allocator_type& __a = allocator_type())
117       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
118 	      __detail::_Default_ranged_hash(), __eql,
119 	      std::_Identity<_Value>(), __a)
120       { }
121 
122 
123       template<typename _InputIterator>
124         __unordered_multiset(_InputIterator __f, _InputIterator __l,
125 			     typename _Base::size_type __n = 0,
126 			     const hasher& __hf = hasher(),
127 			     const key_equal& __eql = key_equal(),
128 			     const allocator_type& __a = allocator_type())
129 	: _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
130 		__detail::_Default_ranged_hash(), __eql,
131 		std::_Identity<_Value>(), __a)
132         { }
133     };
134 
135   template<class _Value, class _Hash, class _Pred, class _Alloc,
136 	   bool __cache_hash_code>
137     inline void
138     swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x,
139 	 __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y)
140     { __x.swap(__y); }
141 
142   template<class _Value, class _Hash, class _Pred, class _Alloc,
143 	   bool __cache_hash_code>
144     inline void
145     swap(__unordered_multiset<_Value, _Hash, _Pred,
146 	 _Alloc, __cache_hash_code>& __x,
147 	 __unordered_multiset<_Value, _Hash, _Pred,
148 	 _Alloc, __cache_hash_code>& __y)
149     { __x.swap(__y); }
150 
151 
152   /**
153    *  @brief A standard container composed of unique keys (containing
154    *  at most one of each key value) in which the elements' keys are
155    *  the elements themselves.
156    *
157    *  @ingroup unordered_associative_containers
158    *
159    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
160    *  <a href="tables.html#xx">unordered associative container</a>
161    *
162    *  @param  Value  Type of key objects.
163    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
164    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
165    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
166    */
167   template<class _Value,
168 	   class _Hash = hash<_Value>,
169 	   class _Pred = std::equal_to<_Value>,
170 	   class _Alloc = std::allocator<_Value> >
171     class unordered_set
172     : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
173     {
174       typedef __unordered_set<_Value, _Hash, _Pred, _Alloc>  _Base;
175 
176     public:
177       typedef typename _Base::value_type      value_type;
178       typedef typename _Base::size_type       size_type;
179       typedef typename _Base::hasher          hasher;
180       typedef typename _Base::key_equal       key_equal;
181       typedef typename _Base::allocator_type  allocator_type;
182 
183       explicit
184       unordered_set(size_type __n = 10,
185 		    const hasher& __hf = hasher(),
186 		    const key_equal& __eql = key_equal(),
187 		    const allocator_type& __a = allocator_type())
188       : _Base(__n, __hf, __eql, __a)
189       { }
190 
191       template<typename _InputIterator>
192         unordered_set(_InputIterator __f, _InputIterator __l,
193 		      size_type __n = 10,
194 		      const hasher& __hf = hasher(),
195 		      const key_equal& __eql = key_equal(),
196 		      const allocator_type& __a = allocator_type())
197 	: _Base(__f, __l, __n, __hf, __eql, __a)
198         { }
199     };
200 
201   /**
202    *  @brief A standard container composed of equivalent keys
203    *  (possibly containing multiple of each key value) in which the
204    *  elements' keys are the elements themselves.
205    *
206    *  @ingroup unordered_associative_containers
207    *
208    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
209    *  <a href="tables.html#xx">unordered associative container</a>
210    *
211    *  @param  Value  Type of key objects.
212    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
213    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
214    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
215    */
216   template<class _Value,
217 	   class _Hash = hash<_Value>,
218 	   class _Pred = std::equal_to<_Value>,
219 	   class _Alloc = std::allocator<_Value> >
220     class unordered_multiset
221     : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc>
222     {
223       typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc>  _Base;
224 
225     public:
226       typedef typename _Base::value_type      value_type;
227       typedef typename _Base::size_type       size_type;
228       typedef typename _Base::hasher          hasher;
229       typedef typename _Base::key_equal       key_equal;
230       typedef typename _Base::allocator_type  allocator_type;
231 
232       explicit
233       unordered_multiset(size_type __n = 10,
234 			 const hasher& __hf = hasher(),
235 			 const key_equal& __eql = key_equal(),
236 			 const allocator_type& __a = allocator_type())
237       : _Base(__n, __hf, __eql, __a)
238       { }
239 
240 
241       template<typename _InputIterator>
242         unordered_multiset(_InputIterator __f, _InputIterator __l,
243 			   typename _Base::size_type __n = 0,
244 			   const hasher& __hf = hasher(),
245 			   const key_equal& __eql = key_equal(),
246 			   const allocator_type& __a = allocator_type())
247 	: _Base(__f, __l, __n, __hf, __eql, __a)
248         { }
249     };
250 
251   template<class _Value, class _Hash, class _Pred, class _Alloc>
252     inline void
253     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
254 	 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
255     { __x.swap(__y); }
256 
257   template<class _Value, class _Hash, class _Pred, class _Alloc>
258     inline void
259     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
260 	 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
261     { __x.swap(__y); }
262 }
263 }
264