1 // TR1 unordered_set implementation -*- C++ -*-
3 // Copyright (C) 2010 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 3, 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 // 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.
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/>.
25 /** @file tr1/unordered_set.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{tr1/unordered_set}
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>
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>
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>
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
;
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
)
73 template<typename _InputIterator
>
74 __unordered_set(_InputIterator __f
, _InputIterator __l
,
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
)
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>
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>
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
;
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
)
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
)
135 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
136 bool __cache_hash_code
>
138 swap(__unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
, __cache_hash_code
>& __x
,
139 __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
, __cache_hash_code
>& __y
)
142 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
143 bool __cache_hash_code
>
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
)
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.
157 * @ingroup unordered_associative_containers
159 * Meets the requirements of a <a href="tables.html#65">container</a>, and
160 * <a href="tables.html#xx">unordered associative container</a>
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>.
167 template<class _Value
,
168 class _Hash
= hash
<_Value
>,
169 class _Pred
= std::equal_to
<_Value
>,
170 class _Alloc
= std::allocator
<_Value
> >
172 : public __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>
174 typedef __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
> _Base
;
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
;
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
)
191 template<typename _InputIterator
>
192 unordered_set(_InputIterator __f
, _InputIterator __l
,
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
)
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.
206 * @ingroup unordered_associative_containers
208 * Meets the requirements of a <a href="tables.html#65">container</a>, and
209 * <a href="tables.html#xx">unordered associative container</a>
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>.
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
>
223 typedef __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
> _Base
;
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
;
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
)
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
)
251 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
253 swap(unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
254 unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
257 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
259 swap(unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
260 unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)