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 * Do not attempt to use it directly. @headername{tr1/unordered_set} 28 */ 29 30 namespace std _GLIBCXX_VISIBILITY(default) 31 { 32 namespace tr1 33 { 34 _GLIBCXX_BEGIN_NAMESPACE_VERSION 35 36 // NB: When we get typedef templates these class definitions 37 // will be unnecessary. 38 template<class _Value, 39 class _Hash = hash<_Value>, 40 class _Pred = std::equal_to<_Value>, 41 class _Alloc = std::allocator<_Value>, 42 bool __cache_hash_code = false> 43 class __unordered_set 44 : public _Hashtable<_Value, _Value, _Alloc, 45 std::_Identity<_Value>, _Pred, 46 _Hash, __detail::_Mod_range_hashing, 47 __detail::_Default_ranged_hash, 48 __detail::_Prime_rehash_policy, 49 __cache_hash_code, true, true> 50 { 51 typedef _Hashtable<_Value, _Value, _Alloc, 52 std::_Identity<_Value>, _Pred, 53 _Hash, __detail::_Mod_range_hashing, 54 __detail::_Default_ranged_hash, 55 __detail::_Prime_rehash_policy, 56 __cache_hash_code, true, true> 57 _Base; 58 59 public: 60 typedef typename _Base::size_type size_type; 61 typedef typename _Base::hasher hasher; 62 typedef typename _Base::key_equal key_equal; 63 typedef typename _Base::allocator_type allocator_type; 64 65 explicit 66 __unordered_set(size_type __n = 10, 67 const hasher& __hf = hasher(), 68 const key_equal& __eql = key_equal(), 69 const allocator_type& __a = allocator_type()) 70 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 71 __detail::_Default_ranged_hash(), __eql, 72 std::_Identity<_Value>(), __a) 73 { } 74 75 template<typename _InputIterator> 76 __unordered_set(_InputIterator __f, _InputIterator __l, 77 size_type __n = 10, 78 const hasher& __hf = hasher(), 79 const key_equal& __eql = key_equal(), 80 const allocator_type& __a = allocator_type()) 81 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 82 __detail::_Default_ranged_hash(), __eql, 83 std::_Identity<_Value>(), __a) 84 { } 85 }; 86 87 template<class _Value, 88 class _Hash = hash<_Value>, 89 class _Pred = std::equal_to<_Value>, 90 class _Alloc = std::allocator<_Value>, 91 bool __cache_hash_code = false> 92 class __unordered_multiset 93 : public _Hashtable<_Value, _Value, _Alloc, 94 std::_Identity<_Value>, _Pred, 95 _Hash, __detail::_Mod_range_hashing, 96 __detail::_Default_ranged_hash, 97 __detail::_Prime_rehash_policy, 98 __cache_hash_code, true, false> 99 { 100 typedef _Hashtable<_Value, _Value, _Alloc, 101 std::_Identity<_Value>, _Pred, 102 _Hash, __detail::_Mod_range_hashing, 103 __detail::_Default_ranged_hash, 104 __detail::_Prime_rehash_policy, 105 __cache_hash_code, true, false> 106 _Base; 107 108 public: 109 typedef typename _Base::size_type size_type; 110 typedef typename _Base::hasher hasher; 111 typedef typename _Base::key_equal key_equal; 112 typedef typename _Base::allocator_type allocator_type; 113 114 explicit 115 __unordered_multiset(size_type __n = 10, 116 const hasher& __hf = hasher(), 117 const key_equal& __eql = key_equal(), 118 const allocator_type& __a = allocator_type()) 119 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 120 __detail::_Default_ranged_hash(), __eql, 121 std::_Identity<_Value>(), __a) 122 { } 123 124 125 template<typename _InputIterator> 126 __unordered_multiset(_InputIterator __f, _InputIterator __l, 127 typename _Base::size_type __n = 0, 128 const hasher& __hf = hasher(), 129 const key_equal& __eql = key_equal(), 130 const allocator_type& __a = allocator_type()) 131 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 132 __detail::_Default_ranged_hash(), __eql, 133 std::_Identity<_Value>(), __a) 134 { } 135 }; 136 137 template<class _Value, class _Hash, class _Pred, class _Alloc, 138 bool __cache_hash_code> 139 inline void 140 swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x, 141 __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y) 142 { __x.swap(__y); } 143 144 template<class _Value, class _Hash, class _Pred, class _Alloc, 145 bool __cache_hash_code> 146 inline void 147 swap(__unordered_multiset<_Value, _Hash, _Pred, 148 _Alloc, __cache_hash_code>& __x, 149 __unordered_multiset<_Value, _Hash, _Pred, 150 _Alloc, __cache_hash_code>& __y) 151 { __x.swap(__y); } 152 153 154 /** 155 * @brief A standard container composed of unique keys (containing 156 * at most one of each key value) in which the elements' keys are 157 * the elements themselves. 158 * 159 * @ingroup unordered_associative_containers 160 * 161 * Meets the requirements of a <a href="tables.html#65">container</a>, and 162 * <a href="tables.html#xx">unordered associative container</a> 163 * 164 * @param Value Type of key objects. 165 * @param Hash Hashing function object type, defaults to hash<Value>. 166 * @param Pred Predicate function object type, defaults to equal_to<Value>. 167 * @param Alloc Allocator type, defaults to allocator<Key>. 168 */ 169 template<class _Value, 170 class _Hash = hash<_Value>, 171 class _Pred = std::equal_to<_Value>, 172 class _Alloc = std::allocator<_Value> > 173 class unordered_set 174 : public __unordered_set<_Value, _Hash, _Pred, _Alloc> 175 { 176 typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base; 177 178 public: 179 typedef typename _Base::value_type value_type; 180 typedef typename _Base::size_type size_type; 181 typedef typename _Base::hasher hasher; 182 typedef typename _Base::key_equal key_equal; 183 typedef typename _Base::allocator_type allocator_type; 184 185 explicit 186 unordered_set(size_type __n = 10, 187 const hasher& __hf = hasher(), 188 const key_equal& __eql = key_equal(), 189 const allocator_type& __a = allocator_type()) 190 : _Base(__n, __hf, __eql, __a) 191 { } 192 193 template<typename _InputIterator> 194 unordered_set(_InputIterator __f, _InputIterator __l, 195 size_type __n = 10, 196 const hasher& __hf = hasher(), 197 const key_equal& __eql = key_equal(), 198 const allocator_type& __a = allocator_type()) 199 : _Base(__f, __l, __n, __hf, __eql, __a) 200 { } 201 }; 202 203 /** 204 * @brief A standard container composed of equivalent keys 205 * (possibly containing multiple of each key value) in which the 206 * elements' keys are the elements themselves. 207 * 208 * @ingroup unordered_associative_containers 209 * 210 * Meets the requirements of a <a href="tables.html#65">container</a>, and 211 * <a href="tables.html#xx">unordered associative container</a> 212 * 213 * @param Value Type of key objects. 214 * @param Hash Hashing function object type, defaults to hash<Value>. 215 * @param Pred Predicate function object type, defaults to equal_to<Value>. 216 * @param Alloc Allocator type, defaults to allocator<Key>. 217 */ 218 template<class _Value, 219 class _Hash = hash<_Value>, 220 class _Pred = std::equal_to<_Value>, 221 class _Alloc = std::allocator<_Value> > 222 class unordered_multiset 223 : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc> 224 { 225 typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base; 226 227 public: 228 typedef typename _Base::value_type value_type; 229 typedef typename _Base::size_type size_type; 230 typedef typename _Base::hasher hasher; 231 typedef typename _Base::key_equal key_equal; 232 typedef typename _Base::allocator_type allocator_type; 233 234 explicit 235 unordered_multiset(size_type __n = 10, 236 const hasher& __hf = hasher(), 237 const key_equal& __eql = key_equal(), 238 const allocator_type& __a = allocator_type()) 239 : _Base(__n, __hf, __eql, __a) 240 { } 241 242 243 template<typename _InputIterator> 244 unordered_multiset(_InputIterator __f, _InputIterator __l, 245 typename _Base::size_type __n = 0, 246 const hasher& __hf = hasher(), 247 const key_equal& __eql = key_equal(), 248 const allocator_type& __a = allocator_type()) 249 : _Base(__f, __l, __n, __hf, __eql, __a) 250 { } 251 }; 252 253 template<class _Value, class _Hash, class _Pred, class _Alloc> 254 inline void 255 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 256 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 257 { __x.swap(__y); } 258 259 template<class _Value, class _Hash, class _Pred, class _Alloc> 260 inline void 261 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 262 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 263 { __x.swap(__y); } 264 265 _GLIBCXX_END_NAMESPACE_VERSION 266 } 267 } 268