libstdc++
|
00001 // unordered_map implementation -*- C++ -*- 00002 00003 // Copyright (C) 2010, 2011 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file bits/unordered_map.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{unordered_map} 00028 */ 00029 00030 #ifndef _UNORDERED_MAP_H 00031 #define _UNORDERED_MAP_H 00032 00033 namespace std _GLIBCXX_VISIBILITY(default) 00034 { 00035 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00036 00037 // NB: When we get typedef templates these class definitions 00038 // will be unnecessary. 00039 template<class _Key, class _Tp, 00040 class _Hash = hash<_Key>, 00041 class _Pred = std::equal_to<_Key>, 00042 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >, 00043 bool __cache_hash_code = 00044 __not_<__and_<is_integral<_Key>, is_empty<_Hash>, 00045 integral_constant<bool, !__is_final(_Hash)>, 00046 __detail::__is_noexcept_hash<_Key, _Hash>>>::value> 00047 class __unordered_map 00048 : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, 00049 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 00050 _Hash, __detail::_Mod_range_hashing, 00051 __detail::_Default_ranged_hash, 00052 __detail::_Prime_rehash_policy, 00053 __cache_hash_code, false, true> 00054 { 00055 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, 00056 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 00057 _Hash, __detail::_Mod_range_hashing, 00058 __detail::_Default_ranged_hash, 00059 __detail::_Prime_rehash_policy, 00060 __cache_hash_code, false, true> 00061 _Base; 00062 00063 public: 00064 typedef typename _Base::value_type value_type; 00065 typedef typename _Base::size_type size_type; 00066 typedef typename _Base::hasher hasher; 00067 typedef typename _Base::key_equal key_equal; 00068 typedef typename _Base::allocator_type allocator_type; 00069 00070 explicit 00071 __unordered_map(size_type __n = 10, 00072 const hasher& __hf = hasher(), 00073 const key_equal& __eql = key_equal(), 00074 const allocator_type& __a = allocator_type()) 00075 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 00076 __detail::_Default_ranged_hash(), 00077 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00078 { } 00079 00080 template<typename _InputIterator> 00081 __unordered_map(_InputIterator __f, _InputIterator __l, 00082 size_type __n = 0, 00083 const hasher& __hf = hasher(), 00084 const key_equal& __eql = key_equal(), 00085 const allocator_type& __a = allocator_type()) 00086 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 00087 __detail::_Default_ranged_hash(), 00088 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00089 { } 00090 00091 __unordered_map(initializer_list<value_type> __l, 00092 size_type __n = 0, 00093 const hasher& __hf = hasher(), 00094 const key_equal& __eql = key_equal(), 00095 const allocator_type& __a = allocator_type()) 00096 : _Base(__l.begin(), __l.end(), __n, __hf, 00097 __detail::_Mod_range_hashing(), 00098 __detail::_Default_ranged_hash(), 00099 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00100 { } 00101 00102 __unordered_map& 00103 operator=(initializer_list<value_type> __l) 00104 { 00105 this->clear(); 00106 this->insert(__l.begin(), __l.end()); 00107 return *this; 00108 } 00109 }; 00110 00111 template<class _Key, class _Tp, 00112 class _Hash = hash<_Key>, 00113 class _Pred = std::equal_to<_Key>, 00114 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >, 00115 bool __cache_hash_code = 00116 __not_<__and_<is_integral<_Key>, is_empty<_Hash>, 00117 integral_constant<bool, !__is_final(_Hash)>, 00118 __detail::__is_noexcept_hash<_Key, _Hash>>>::value> 00119 class __unordered_multimap 00120 : public _Hashtable<_Key, std::pair<const _Key, _Tp>, 00121 _Alloc, 00122 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 00123 _Hash, __detail::_Mod_range_hashing, 00124 __detail::_Default_ranged_hash, 00125 __detail::_Prime_rehash_policy, 00126 __cache_hash_code, false, false> 00127 { 00128 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, 00129 _Alloc, 00130 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 00131 _Hash, __detail::_Mod_range_hashing, 00132 __detail::_Default_ranged_hash, 00133 __detail::_Prime_rehash_policy, 00134 __cache_hash_code, false, false> 00135 _Base; 00136 00137 public: 00138 typedef typename _Base::value_type value_type; 00139 typedef typename _Base::size_type size_type; 00140 typedef typename _Base::hasher hasher; 00141 typedef typename _Base::key_equal key_equal; 00142 typedef typename _Base::allocator_type allocator_type; 00143 00144 explicit 00145 __unordered_multimap(size_type __n = 10, 00146 const hasher& __hf = hasher(), 00147 const key_equal& __eql = key_equal(), 00148 const allocator_type& __a = allocator_type()) 00149 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 00150 __detail::_Default_ranged_hash(), 00151 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00152 { } 00153 00154 00155 template<typename _InputIterator> 00156 __unordered_multimap(_InputIterator __f, _InputIterator __l, 00157 size_type __n = 0, 00158 const hasher& __hf = hasher(), 00159 const key_equal& __eql = key_equal(), 00160 const allocator_type& __a = allocator_type()) 00161 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 00162 __detail::_Default_ranged_hash(), 00163 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00164 { } 00165 00166 __unordered_multimap(initializer_list<value_type> __l, 00167 size_type __n = 0, 00168 const hasher& __hf = hasher(), 00169 const key_equal& __eql = key_equal(), 00170 const allocator_type& __a = allocator_type()) 00171 : _Base(__l.begin(), __l.end(), __n, __hf, 00172 __detail::_Mod_range_hashing(), 00173 __detail::_Default_ranged_hash(), 00174 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00175 { } 00176 00177 __unordered_multimap& 00178 operator=(initializer_list<value_type> __l) 00179 { 00180 this->clear(); 00181 this->insert(__l.begin(), __l.end()); 00182 return *this; 00183 } 00184 }; 00185 00186 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00187 bool __cache_hash_code> 00188 inline void 00189 swap(__unordered_map<_Key, _Tp, _Hash, _Pred, 00190 _Alloc, __cache_hash_code>& __x, 00191 __unordered_map<_Key, _Tp, _Hash, _Pred, 00192 _Alloc, __cache_hash_code>& __y) 00193 { __x.swap(__y); } 00194 00195 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00196 bool __cache_hash_code> 00197 inline void 00198 swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred, 00199 _Alloc, __cache_hash_code>& __x, 00200 __unordered_multimap<_Key, _Tp, _Hash, _Pred, 00201 _Alloc, __cache_hash_code>& __y) 00202 { __x.swap(__y); } 00203 00204 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00205 bool __cache_hash_code> 00206 inline bool 00207 operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, 00208 __cache_hash_code>& __x, 00209 const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, 00210 __cache_hash_code>& __y) 00211 { return __x._M_equal(__y); } 00212 00213 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00214 bool __cache_hash_code> 00215 inline bool 00216 operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, 00217 __cache_hash_code>& __x, 00218 const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, 00219 __cache_hash_code>& __y) 00220 { return !(__x == __y); } 00221 00222 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00223 bool __cache_hash_code> 00224 inline bool 00225 operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, 00226 __cache_hash_code>& __x, 00227 const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, 00228 __cache_hash_code>& __y) 00229 { return __x._M_equal(__y); } 00230 00231 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00232 bool __cache_hash_code> 00233 inline bool 00234 operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, 00235 __cache_hash_code>& __x, 00236 const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, 00237 __cache_hash_code>& __y) 00238 { return !(__x == __y); } 00239 00240 /** 00241 * @brief A standard container composed of unique keys (containing 00242 * at most one of each key value) that associates values of another type 00243 * with the keys. 00244 * 00245 * @ingroup unordered_associative_containers 00246 * 00247 * Meets the requirements of a <a href="tables.html#65">container</a>, and 00248 * <a href="tables.html#xx">unordered associative container</a> 00249 * 00250 * @param Key Type of key objects. 00251 * @param Tp Type of mapped objects. 00252 * @param Hash Hashing function object type, defaults to hash<Value>. 00253 * @param Pred Predicate function object type, defaults to equal_to<Value>. 00254 * @param Alloc Allocator type, defaults to allocator<Key>. 00255 * 00256 * The resulting value type of the container is std::pair<const Key, Tp>. 00257 */ 00258 template<class _Key, class _Tp, 00259 class _Hash = hash<_Key>, 00260 class _Pred = std::equal_to<_Key>, 00261 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00262 class unordered_map 00263 : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 00264 { 00265 typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; 00266 00267 public: 00268 typedef typename _Base::value_type value_type; 00269 typedef typename _Base::size_type size_type; 00270 typedef typename _Base::hasher hasher; 00271 typedef typename _Base::key_equal key_equal; 00272 typedef typename _Base::allocator_type allocator_type; 00273 00274 explicit 00275 unordered_map(size_type __n = 10, 00276 const hasher& __hf = hasher(), 00277 const key_equal& __eql = key_equal(), 00278 const allocator_type& __a = allocator_type()) 00279 : _Base(__n, __hf, __eql, __a) 00280 { } 00281 00282 template<typename _InputIterator> 00283 unordered_map(_InputIterator __f, _InputIterator __l, 00284 size_type __n = 0, 00285 const hasher& __hf = hasher(), 00286 const key_equal& __eql = key_equal(), 00287 const allocator_type& __a = allocator_type()) 00288 : _Base(__f, __l, __n, __hf, __eql, __a) 00289 { } 00290 00291 unordered_map(initializer_list<value_type> __l, 00292 size_type __n = 0, 00293 const hasher& __hf = hasher(), 00294 const key_equal& __eql = key_equal(), 00295 const allocator_type& __a = allocator_type()) 00296 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 00297 { } 00298 00299 unordered_map& 00300 operator=(initializer_list<value_type> __l) 00301 { 00302 this->clear(); 00303 this->insert(__l.begin(), __l.end()); 00304 return *this; 00305 } 00306 }; 00307 00308 /** 00309 * @brief A standard container composed of equivalent keys 00310 * (possibly containing multiple of each key value) that associates 00311 * values of another type with the keys. 00312 * 00313 * @ingroup unordered_associative_containers 00314 * 00315 * Meets the requirements of a <a href="tables.html#65">container</a>, and 00316 * <a href="tables.html#xx">unordered associative container</a> 00317 * 00318 * @param Key Type of key objects. 00319 * @param Tp Type of mapped objects. 00320 * @param Hash Hashing function object type, defaults to hash<Value>. 00321 * @param Pred Predicate function object type, defaults to equal_to<Value>. 00322 * @param Alloc Allocator type, defaults to allocator<Key>. 00323 * 00324 * The resulting value type of the container is std::pair<const Key, Tp>. 00325 */ 00326 template<class _Key, class _Tp, 00327 class _Hash = hash<_Key>, 00328 class _Pred = std::equal_to<_Key>, 00329 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00330 class unordered_multimap 00331 : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 00332 { 00333 typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; 00334 00335 public: 00336 typedef typename _Base::value_type value_type; 00337 typedef typename _Base::size_type size_type; 00338 typedef typename _Base::hasher hasher; 00339 typedef typename _Base::key_equal key_equal; 00340 typedef typename _Base::allocator_type allocator_type; 00341 00342 explicit 00343 unordered_multimap(size_type __n = 10, 00344 const hasher& __hf = hasher(), 00345 const key_equal& __eql = key_equal(), 00346 const allocator_type& __a = allocator_type()) 00347 : _Base(__n, __hf, __eql, __a) 00348 { } 00349 00350 template<typename _InputIterator> 00351 unordered_multimap(_InputIterator __f, _InputIterator __l, 00352 size_type __n = 0, 00353 const hasher& __hf = hasher(), 00354 const key_equal& __eql = key_equal(), 00355 const allocator_type& __a = allocator_type()) 00356 : _Base(__f, __l, __n, __hf, __eql, __a) 00357 { } 00358 00359 unordered_multimap(initializer_list<value_type> __l, 00360 size_type __n = 0, 00361 const hasher& __hf = hasher(), 00362 const key_equal& __eql = key_equal(), 00363 const allocator_type& __a = allocator_type()) 00364 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 00365 { } 00366 00367 unordered_multimap& 00368 operator=(initializer_list<value_type> __l) 00369 { 00370 this->clear(); 00371 this->insert(__l.begin(), __l.end()); 00372 return *this; 00373 } 00374 }; 00375 00376 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00377 inline void 00378 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00379 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00380 { __x.swap(__y); } 00381 00382 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00383 inline void 00384 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00385 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00386 { __x.swap(__y); } 00387 00388 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00389 inline bool 00390 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00391 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00392 { return __x._M_equal(__y); } 00393 00394 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00395 inline bool 00396 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00397 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00398 { return !(__x == __y); } 00399 00400 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00401 inline bool 00402 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00403 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00404 { return __x._M_equal(__y); } 00405 00406 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00407 inline bool 00408 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00409 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00410 { return !(__x == __y); } 00411 00412 _GLIBCXX_END_NAMESPACE_CONTAINER 00413 } // namespace std 00414 00415 #endif /* _UNORDERED_MAP_H */