1 // TR1 unordered_map -*- C++ -*- 2 3 // Copyright (C) 2007, 2009 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_impl/unordered_map 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 _GLIBCXX_BEGIN_NAMESPACE_TR1 33 34 // XXX When we get typedef templates these class definitions 35 // will be unnecessary. 36 template<class _Key, class _Tp, 37 class _Hash = hash<_Key>, 38 class _Pred = std::equal_to<_Key>, 39 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >, 40 bool __cache_hash_code = false> 41 class __unordered_map 42 : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, 43 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 44 _Hash, __detail::_Mod_range_hashing, 45 __detail::_Default_ranged_hash, 46 __detail::_Prime_rehash_policy, 47 __cache_hash_code, false, true> 48 { 49 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, 50 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 51 _Hash, __detail::_Mod_range_hashing, 52 __detail::_Default_ranged_hash, 53 __detail::_Prime_rehash_policy, 54 __cache_hash_code, false, 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_map(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(), 70 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 71 { } 72 73 template<typename _InputIterator> 74 __unordered_map(_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(), 81 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 82 { } 83 84 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 85 __unordered_map(__unordered_map&& __x) 86 : _Base(std::forward<_Base>(__x)) { } 87 #endif 88 }; 89 90 template<class _Key, class _Tp, 91 class _Hash = hash<_Key>, 92 class _Pred = std::equal_to<_Key>, 93 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >, 94 bool __cache_hash_code = false> 95 class __unordered_multimap 96 : public _Hashtable<_Key, std::pair<const _Key, _Tp>, 97 _Alloc, 98 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 99 _Hash, __detail::_Mod_range_hashing, 100 __detail::_Default_ranged_hash, 101 __detail::_Prime_rehash_policy, 102 __cache_hash_code, false, false> 103 { 104 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, 105 _Alloc, 106 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 107 _Hash, __detail::_Mod_range_hashing, 108 __detail::_Default_ranged_hash, 109 __detail::_Prime_rehash_policy, 110 __cache_hash_code, false, false> 111 _Base; 112 113 public: 114 typedef typename _Base::size_type size_type; 115 typedef typename _Base::hasher hasher; 116 typedef typename _Base::key_equal key_equal; 117 typedef typename _Base::allocator_type allocator_type; 118 119 explicit 120 __unordered_multimap(size_type __n = 10, 121 const hasher& __hf = hasher(), 122 const key_equal& __eql = key_equal(), 123 const allocator_type& __a = allocator_type()) 124 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 125 __detail::_Default_ranged_hash(), 126 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 127 { } 128 129 130 template<typename _InputIterator> 131 __unordered_multimap(_InputIterator __f, _InputIterator __l, 132 typename _Base::size_type __n = 0, 133 const hasher& __hf = hasher(), 134 const key_equal& __eql = key_equal(), 135 const allocator_type& __a = allocator_type()) 136 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 137 __detail::_Default_ranged_hash(), 138 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 139 { } 140 141 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 142 __unordered_multimap(__unordered_multimap&& __x) 143 : _Base(std::forward<_Base>(__x)) { } 144 #endif 145 }; 146 147 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 148 bool __cache_hash_code> 149 inline void 150 swap(__unordered_map<_Key, _Tp, _Hash, _Pred, 151 _Alloc, __cache_hash_code>& __x, 152 __unordered_map<_Key, _Tp, _Hash, _Pred, 153 _Alloc, __cache_hash_code>& __y) 154 { __x.swap(__y); } 155 156 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 157 bool __cache_hash_code> 158 inline void 159 swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred, 160 _Alloc, __cache_hash_code>& __x, 161 __unordered_multimap<_Key, _Tp, _Hash, _Pred, 162 _Alloc, __cache_hash_code>& __y) 163 { __x.swap(__y); } 164 165 166 /** 167 * @brief A standard container composed of unique keys (containing 168 * at most one of each key value) that associates values of another type 169 * with the keys. 170 * 171 * @ingroup unordered_associative_containers 172 * 173 * Meets the requirements of a <a href="tables.html#65">container</a>, and 174 * <a href="tables.html#xx">unordered associative container</a> 175 * 176 * @param Key Type of key objects. 177 * @param Tp Type of mapped objects. 178 * @param Hash Hashing function object type, defaults to hash<Value>. 179 * @param Pred Predicate function object type, defaults to equal_to<Value>. 180 * @param Alloc Allocator type, defaults to allocator<Key>. 181 * 182 * The resulting value type of the container is std::pair<const Key, Tp>. 183 */ 184 template<class _Key, class _Tp, 185 class _Hash = hash<_Key>, 186 class _Pred = std::equal_to<_Key>, 187 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 188 class unordered_map 189 : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 190 { 191 typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; 192 193 public: 194 typedef typename _Base::value_type value_type; 195 typedef typename _Base::size_type size_type; 196 typedef typename _Base::hasher hasher; 197 typedef typename _Base::key_equal key_equal; 198 typedef typename _Base::allocator_type allocator_type; 199 200 explicit 201 unordered_map(size_type __n = 10, 202 const hasher& __hf = hasher(), 203 const key_equal& __eql = key_equal(), 204 const allocator_type& __a = allocator_type()) 205 : _Base(__n, __hf, __eql, __a) 206 { } 207 208 template<typename _InputIterator> 209 unordered_map(_InputIterator __f, _InputIterator __l, 210 size_type __n = 10, 211 const hasher& __hf = hasher(), 212 const key_equal& __eql = key_equal(), 213 const allocator_type& __a = allocator_type()) 214 : _Base(__f, __l, __n, __hf, __eql, __a) 215 { } 216 217 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 218 unordered_map(unordered_map&& __x) 219 : _Base(std::forward<_Base>(__x)) { } 220 221 unordered_map(initializer_list<value_type> __l, 222 size_type __n = 10, 223 const hasher& __hf = hasher(), 224 const key_equal& __eql = key_equal(), 225 const allocator_type& __a = allocator_type()) 226 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 227 { } 228 229 unordered_map& 230 operator=(unordered_map&& __x) 231 { 232 // NB: DR 675. 233 this->clear(); 234 this->swap(__x); 235 return *this; 236 } 237 238 unordered_map& 239 operator=(initializer_list<value_type> __l) 240 { 241 this->clear(); 242 this->insert(__l.begin(), __l.end()); 243 return *this; 244 } 245 #endif 246 }; 247 248 /** 249 * @brief A standard container composed of equivalent keys 250 * (possibly containing multiple of each key value) that associates 251 * values of another type with the keys. 252 * 253 * @ingroup unordered_associative_containers 254 * 255 * Meets the requirements of a <a href="tables.html#65">container</a>, and 256 * <a href="tables.html#xx">unordered associative container</a> 257 * 258 * @param Key Type of key objects. 259 * @param Tp Type of mapped objects. 260 * @param Hash Hashing function object type, defaults to hash<Value>. 261 * @param Pred Predicate function object type, defaults to equal_to<Value>. 262 * @param Alloc Allocator type, defaults to allocator<Key>. 263 * 264 * The resulting value type of the container is std::pair<const Key, Tp>. 265 */ 266 template<class _Key, class _Tp, 267 class _Hash = hash<_Key>, 268 class _Pred = std::equal_to<_Key>, 269 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 270 class unordered_multimap 271 : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 272 { 273 typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; 274 275 public: 276 typedef typename _Base::value_type value_type; 277 typedef typename _Base::size_type size_type; 278 typedef typename _Base::hasher hasher; 279 typedef typename _Base::key_equal key_equal; 280 typedef typename _Base::allocator_type allocator_type; 281 282 explicit 283 unordered_multimap(size_type __n = 10, 284 const hasher& __hf = hasher(), 285 const key_equal& __eql = key_equal(), 286 const allocator_type& __a = allocator_type()) 287 : _Base(__n, __hf, __eql, __a) 288 { } 289 290 291 template<typename _InputIterator> 292 unordered_multimap(_InputIterator __f, _InputIterator __l, 293 typename _Base::size_type __n = 0, 294 const hasher& __hf = hasher(), 295 const key_equal& __eql = key_equal(), 296 const allocator_type& __a = allocator_type()) 297 : _Base(__f, __l, __n, __hf, __eql, __a) 298 { } 299 300 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 301 unordered_multimap(unordered_multimap&& __x) 302 : _Base(std::forward<_Base>(__x)) { } 303 304 unordered_multimap(initializer_list<value_type> __l, 305 size_type __n = 10, 306 const hasher& __hf = hasher(), 307 const key_equal& __eql = key_equal(), 308 const allocator_type& __a = allocator_type()) 309 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 310 { } 311 312 unordered_multimap& 313 operator=(unordered_multimap&& __x) 314 { 315 // NB: DR 675. 316 this->clear(); 317 this->swap(__x); 318 return *this; 319 } 320 321 unordered_multimap& 322 operator=(initializer_list<value_type> __l) 323 { 324 this->clear(); 325 this->insert(__l.begin(), __l.end()); 326 return *this; 327 } 328 #endif 329 }; 330 331 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 332 inline void 333 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 334 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 335 { __x.swap(__y); } 336 337 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 338 inline void 339 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 340 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 341 { __x.swap(__y); } 342 343 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 344 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 345 inline void 346 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x, 347 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 348 { __x.swap(__y); } 349 350 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 351 inline void 352 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 353 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y) 354 { __x.swap(__y); } 355 356 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 357 inline void 358 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __x, 359 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 360 { __x.swap(__y); } 361 362 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 363 inline void 364 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 365 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&& __y) 366 { __x.swap(__y); } 367 #endif 368 369 _GLIBCXX_END_NAMESPACE_TR1 370 } 371