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 = false> 00044 class __unordered_map 00045 : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, 00046 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 00047 _Hash, __detail::_Mod_range_hashing, 00048 __detail::_Default_ranged_hash, 00049 __detail::_Prime_rehash_policy, 00050 __cache_hash_code, false, true> 00051 { 00052 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, 00053 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 00054 _Hash, __detail::_Mod_range_hashing, 00055 __detail::_Default_ranged_hash, 00056 __detail::_Prime_rehash_policy, 00057 __cache_hash_code, false, true> 00058 _Base; 00059 00060 public: 00061 typedef typename _Base::value_type value_type; 00062 typedef typename _Base::size_type size_type; 00063 typedef typename _Base::hasher hasher; 00064 typedef typename _Base::key_equal key_equal; 00065 typedef typename _Base::allocator_type allocator_type; 00066 00067 explicit 00068 __unordered_map(size_type __n = 10, 00069 const hasher& __hf = hasher(), 00070 const key_equal& __eql = key_equal(), 00071 const allocator_type& __a = allocator_type()) 00072 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 00073 __detail::_Default_ranged_hash(), 00074 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00075 { } 00076 00077 template<typename _InputIterator> 00078 __unordered_map(_InputIterator __f, _InputIterator __l, 00079 size_type __n = 0, 00080 const hasher& __hf = hasher(), 00081 const key_equal& __eql = key_equal(), 00082 const allocator_type& __a = allocator_type()) 00083 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 00084 __detail::_Default_ranged_hash(), 00085 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00086 { } 00087 00088 __unordered_map(initializer_list<value_type> __l, 00089 size_type __n = 0, 00090 const hasher& __hf = hasher(), 00091 const key_equal& __eql = key_equal(), 00092 const allocator_type& __a = allocator_type()) 00093 : _Base(__l.begin(), __l.end(), __n, __hf, 00094 __detail::_Mod_range_hashing(), 00095 __detail::_Default_ranged_hash(), 00096 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00097 { } 00098 00099 __unordered_map& 00100 operator=(initializer_list<value_type> __l) 00101 { 00102 this->clear(); 00103 this->insert(__l.begin(), __l.end()); 00104 return *this; 00105 } 00106 }; 00107 00108 template<class _Key, class _Tp, 00109 class _Hash = hash<_Key>, 00110 class _Pred = std::equal_to<_Key>, 00111 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >, 00112 bool __cache_hash_code = false> 00113 class __unordered_multimap 00114 : public _Hashtable<_Key, std::pair<const _Key, _Tp>, 00115 _Alloc, 00116 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 00117 _Hash, __detail::_Mod_range_hashing, 00118 __detail::_Default_ranged_hash, 00119 __detail::_Prime_rehash_policy, 00120 __cache_hash_code, false, false> 00121 { 00122 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, 00123 _Alloc, 00124 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 00125 _Hash, __detail::_Mod_range_hashing, 00126 __detail::_Default_ranged_hash, 00127 __detail::_Prime_rehash_policy, 00128 __cache_hash_code, false, false> 00129 _Base; 00130 00131 public: 00132 typedef typename _Base::value_type value_type; 00133 typedef typename _Base::size_type size_type; 00134 typedef typename _Base::hasher hasher; 00135 typedef typename _Base::key_equal key_equal; 00136 typedef typename _Base::allocator_type allocator_type; 00137 00138 explicit 00139 __unordered_multimap(size_type __n = 10, 00140 const hasher& __hf = hasher(), 00141 const key_equal& __eql = key_equal(), 00142 const allocator_type& __a = allocator_type()) 00143 : _Base(__n, __hf, __detail::_Mod_range_hashing(), 00144 __detail::_Default_ranged_hash(), 00145 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00146 { } 00147 00148 00149 template<typename _InputIterator> 00150 __unordered_multimap(_InputIterator __f, _InputIterator __l, 00151 size_type __n = 0, 00152 const hasher& __hf = hasher(), 00153 const key_equal& __eql = key_equal(), 00154 const allocator_type& __a = allocator_type()) 00155 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), 00156 __detail::_Default_ranged_hash(), 00157 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00158 { } 00159 00160 __unordered_multimap(initializer_list<value_type> __l, 00161 size_type __n = 0, 00162 const hasher& __hf = hasher(), 00163 const key_equal& __eql = key_equal(), 00164 const allocator_type& __a = allocator_type()) 00165 : _Base(__l.begin(), __l.end(), __n, __hf, 00166 __detail::_Mod_range_hashing(), 00167 __detail::_Default_ranged_hash(), 00168 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) 00169 { } 00170 00171 __unordered_multimap& 00172 operator=(initializer_list<value_type> __l) 00173 { 00174 this->clear(); 00175 this->insert(__l.begin(), __l.end()); 00176 return *this; 00177 } 00178 }; 00179 00180 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00181 bool __cache_hash_code> 00182 inline void 00183 swap(__unordered_map<_Key, _Tp, _Hash, _Pred, 00184 _Alloc, __cache_hash_code>& __x, 00185 __unordered_map<_Key, _Tp, _Hash, _Pred, 00186 _Alloc, __cache_hash_code>& __y) 00187 { __x.swap(__y); } 00188 00189 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00190 bool __cache_hash_code> 00191 inline void 00192 swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred, 00193 _Alloc, __cache_hash_code>& __x, 00194 __unordered_multimap<_Key, _Tp, _Hash, _Pred, 00195 _Alloc, __cache_hash_code>& __y) 00196 { __x.swap(__y); } 00197 00198 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00199 bool __cache_hash_code> 00200 inline bool 00201 operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, 00202 __cache_hash_code>& __x, 00203 const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, 00204 __cache_hash_code>& __y) 00205 { return __x._M_equal(__y); } 00206 00207 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00208 bool __cache_hash_code> 00209 inline bool 00210 operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, 00211 __cache_hash_code>& __x, 00212 const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, 00213 __cache_hash_code>& __y) 00214 { return !(__x == __y); } 00215 00216 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00217 bool __cache_hash_code> 00218 inline bool 00219 operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, 00220 __cache_hash_code>& __x, 00221 const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, 00222 __cache_hash_code>& __y) 00223 { return __x._M_equal(__y); } 00224 00225 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, 00226 bool __cache_hash_code> 00227 inline bool 00228 operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, 00229 __cache_hash_code>& __x, 00230 const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, 00231 __cache_hash_code>& __y) 00232 { return !(__x == __y); } 00233 00234 /** 00235 * @brief A standard container composed of unique keys (containing 00236 * at most one of each key value) that associates values of another type 00237 * with the keys. 00238 * 00239 * @ingroup unordered_associative_containers 00240 * 00241 * Meets the requirements of a <a href="tables.html#65">container</a>, and 00242 * <a href="tables.html#xx">unordered associative container</a> 00243 * 00244 * @param Key Type of key objects. 00245 * @param Tp Type of mapped objects. 00246 * @param Hash Hashing function object type, defaults to hash<Value>. 00247 * @param Pred Predicate function object type, defaults to equal_to<Value>. 00248 * @param Alloc Allocator type, defaults to allocator<Key>. 00249 * 00250 * The resulting value type of the container is std::pair<const Key, Tp>. 00251 */ 00252 template<class _Key, class _Tp, 00253 class _Hash = hash<_Key>, 00254 class _Pred = std::equal_to<_Key>, 00255 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00256 class unordered_map 00257 : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 00258 { 00259 typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; 00260 00261 public: 00262 typedef typename _Base::value_type value_type; 00263 typedef typename _Base::size_type size_type; 00264 typedef typename _Base::hasher hasher; 00265 typedef typename _Base::key_equal key_equal; 00266 typedef typename _Base::allocator_type allocator_type; 00267 00268 explicit 00269 unordered_map(size_type __n = 10, 00270 const hasher& __hf = hasher(), 00271 const key_equal& __eql = key_equal(), 00272 const allocator_type& __a = allocator_type()) 00273 : _Base(__n, __hf, __eql, __a) 00274 { } 00275 00276 template<typename _InputIterator> 00277 unordered_map(_InputIterator __f, _InputIterator __l, 00278 size_type __n = 0, 00279 const hasher& __hf = hasher(), 00280 const key_equal& __eql = key_equal(), 00281 const allocator_type& __a = allocator_type()) 00282 : _Base(__f, __l, __n, __hf, __eql, __a) 00283 { } 00284 00285 unordered_map(initializer_list<value_type> __l, 00286 size_type __n = 0, 00287 const hasher& __hf = hasher(), 00288 const key_equal& __eql = key_equal(), 00289 const allocator_type& __a = allocator_type()) 00290 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 00291 { } 00292 00293 unordered_map& 00294 operator=(initializer_list<value_type> __l) 00295 { 00296 this->clear(); 00297 this->insert(__l.begin(), __l.end()); 00298 return *this; 00299 } 00300 }; 00301 00302 /** 00303 * @brief A standard container composed of equivalent keys 00304 * (possibly containing multiple of each key value) that associates 00305 * values of another type with the keys. 00306 * 00307 * @ingroup unordered_associative_containers 00308 * 00309 * Meets the requirements of a <a href="tables.html#65">container</a>, and 00310 * <a href="tables.html#xx">unordered associative container</a> 00311 * 00312 * @param Key Type of key objects. 00313 * @param Tp Type of mapped objects. 00314 * @param Hash Hashing function object type, defaults to hash<Value>. 00315 * @param Pred Predicate function object type, defaults to equal_to<Value>. 00316 * @param Alloc Allocator type, defaults to allocator<Key>. 00317 * 00318 * The resulting value type of the container is std::pair<const Key, Tp>. 00319 */ 00320 template<class _Key, class _Tp, 00321 class _Hash = hash<_Key>, 00322 class _Pred = std::equal_to<_Key>, 00323 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00324 class unordered_multimap 00325 : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 00326 { 00327 typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; 00328 00329 public: 00330 typedef typename _Base::value_type value_type; 00331 typedef typename _Base::size_type size_type; 00332 typedef typename _Base::hasher hasher; 00333 typedef typename _Base::key_equal key_equal; 00334 typedef typename _Base::allocator_type allocator_type; 00335 00336 explicit 00337 unordered_multimap(size_type __n = 10, 00338 const hasher& __hf = hasher(), 00339 const key_equal& __eql = key_equal(), 00340 const allocator_type& __a = allocator_type()) 00341 : _Base(__n, __hf, __eql, __a) 00342 { } 00343 00344 template<typename _InputIterator> 00345 unordered_multimap(_InputIterator __f, _InputIterator __l, 00346 size_type __n = 0, 00347 const hasher& __hf = hasher(), 00348 const key_equal& __eql = key_equal(), 00349 const allocator_type& __a = allocator_type()) 00350 : _Base(__f, __l, __n, __hf, __eql, __a) 00351 { } 00352 00353 unordered_multimap(initializer_list<value_type> __l, 00354 size_type __n = 0, 00355 const hasher& __hf = hasher(), 00356 const key_equal& __eql = key_equal(), 00357 const allocator_type& __a = allocator_type()) 00358 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) 00359 { } 00360 00361 unordered_multimap& 00362 operator=(initializer_list<value_type> __l) 00363 { 00364 this->clear(); 00365 this->insert(__l.begin(), __l.end()); 00366 return *this; 00367 } 00368 }; 00369 00370 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00371 inline void 00372 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00373 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00374 { __x.swap(__y); } 00375 00376 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00377 inline void 00378 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00379 unordered_multimap<_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 bool 00384 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00385 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00386 { return __x._M_equal(__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 == __y); } 00393 00394 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00395 inline bool 00396 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00397 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00398 { return __x._M_equal(__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 == __y); } 00405 00406 _GLIBCXX_END_NAMESPACE_CONTAINER 00407 } // namespace std 00408 00409 #endif /* _UNORDERED_MAP_H */