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