libstdc++
|
00001 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2009-2016 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 along 00021 // with this library; see the file COPYING3. If not see 00022 // <http://www.gnu.org/licenses/>. 00023 00024 /** @file profile/unordered_map 00025 * This file is a GNU profile extension to the Standard C++ Library. 00026 */ 00027 00028 #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP 00029 #define _GLIBCXX_PROFILE_UNORDERED_MAP 1 00030 00031 #if __cplusplus < 201103L 00032 # include <bits/c++0x_warning.h> 00033 #else 00034 # include <unordered_map> 00035 00036 #include <profile/base.h> 00037 #include <profile/unordered_base.h> 00038 00039 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 00040 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 00041 00042 namespace std _GLIBCXX_VISIBILITY(default) 00043 { 00044 namespace __profile 00045 { 00046 /// Class std::unordered_map wrapper with performance instrumentation. 00047 template<typename _Key, typename _Tp, 00048 typename _Hash = std::hash<_Key>, 00049 typename _Pred = std::equal_to<_Key>, 00050 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00051 class unordered_map 00052 : public _GLIBCXX_STD_BASE, 00053 public _Unordered_profile<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, 00054 true> 00055 { 00056 typedef typename _GLIBCXX_STD_BASE _Base; 00057 00058 _Base& 00059 _M_base() noexcept { return *this; } 00060 00061 const _Base& 00062 _M_base() const noexcept { return *this; } 00063 00064 public: 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 typedef typename _Base::key_type key_type; 00070 typedef typename _Base::value_type value_type; 00071 typedef typename _Base::difference_type difference_type; 00072 typedef typename _Base::reference reference; 00073 typedef typename _Base::const_reference const_reference; 00074 typedef typename _Base::mapped_type mapped_type; 00075 00076 typedef typename _Base::iterator iterator; 00077 typedef typename _Base::const_iterator const_iterator; 00078 00079 unordered_map() = default; 00080 00081 explicit 00082 unordered_map(size_type __n, 00083 const hasher& __hf = hasher(), 00084 const key_equal& __eql = key_equal(), 00085 const allocator_type& __a = allocator_type()) 00086 : _Base(__n, __hf, __eql, __a) { } 00087 00088 template<typename _InputIterator> 00089 unordered_map(_InputIterator __f, _InputIterator __l, 00090 size_type __n = 0, 00091 const hasher& __hf = hasher(), 00092 const key_equal& __eql = key_equal(), 00093 const allocator_type& __a = allocator_type()) 00094 : _Base(__f, __l, __n, __hf, __eql, __a) { } 00095 00096 unordered_map(const unordered_map&) = default; 00097 00098 unordered_map(const _Base& __x) 00099 : _Base(__x) { } 00100 00101 unordered_map(unordered_map&&) = default; 00102 00103 explicit 00104 unordered_map(const allocator_type& __a) 00105 : _Base(__a) { } 00106 00107 unordered_map(const unordered_map& __umap, 00108 const allocator_type& __a) 00109 : _Base(__umap, __a) { } 00110 00111 unordered_map(unordered_map&& __umap, 00112 const allocator_type& __a) 00113 : _Base(std::move(__umap._M_base()), __a) { } 00114 00115 unordered_map(initializer_list<value_type> __l, 00116 size_type __n = 0, 00117 const hasher& __hf = hasher(), 00118 const key_equal& __eql = key_equal(), 00119 const allocator_type& __a = allocator_type()) 00120 : _Base(__l, __n, __hf, __eql, __a) { } 00121 00122 unordered_map(size_type __n, const allocator_type& __a) 00123 : unordered_map(__n, hasher(), key_equal(), __a) 00124 { } 00125 00126 unordered_map(size_type __n, const hasher& __hf, 00127 const allocator_type& __a) 00128 : unordered_map(__n, __hf, key_equal(), __a) 00129 { } 00130 00131 template<typename _InputIterator> 00132 unordered_map(_InputIterator __first, _InputIterator __last, 00133 size_type __n, 00134 const allocator_type& __a) 00135 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) 00136 { } 00137 00138 template<typename _InputIterator> 00139 unordered_map(_InputIterator __first, _InputIterator __last, 00140 size_type __n, const hasher& __hf, 00141 const allocator_type& __a) 00142 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) 00143 { } 00144 00145 unordered_map(initializer_list<value_type> __l, 00146 size_type __n, 00147 const allocator_type& __a) 00148 : unordered_map(__l, __n, hasher(), key_equal(), __a) 00149 { } 00150 00151 unordered_map(initializer_list<value_type> __l, 00152 size_type __n, const hasher& __hf, 00153 const allocator_type& __a) 00154 : unordered_map(__l, __n, __hf, key_equal(), __a) 00155 { } 00156 00157 unordered_map& 00158 operator=(const unordered_map&) = default; 00159 00160 unordered_map& 00161 operator=(unordered_map&&) = default; 00162 00163 unordered_map& 00164 operator=(initializer_list<value_type> __l) 00165 { 00166 this->_M_profile_destruct(); 00167 _M_base() = __l; 00168 this->_M_profile_construct(); 00169 return *this; 00170 } 00171 00172 void 00173 clear() noexcept 00174 { 00175 this->_M_profile_destruct(); 00176 _Base::clear(); 00177 this->_M_profile_construct(); 00178 } 00179 00180 template<typename... _Args> 00181 std::pair<iterator, bool> 00182 emplace(_Args&&... __args) 00183 { 00184 size_type __old_size = _Base::bucket_count(); 00185 std::pair<iterator, bool> __res 00186 = _Base::emplace(std::forward<_Args>(__args)...); 00187 this->_M_profile_resize(__old_size); 00188 return __res; 00189 } 00190 00191 template<typename... _Args> 00192 iterator 00193 emplace_hint(const_iterator __it, _Args&&... __args) 00194 { 00195 size_type __old_size = _Base::bucket_count(); 00196 iterator __res 00197 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 00198 this->_M_profile_resize(__old_size); 00199 return __res; 00200 } 00201 00202 void 00203 insert(std::initializer_list<value_type> __l) 00204 { 00205 size_type __old_size = _Base::bucket_count(); 00206 _Base::insert(__l); 00207 this->_M_profile_resize(__old_size); 00208 } 00209 00210 std::pair<iterator, bool> 00211 insert(const value_type& __obj) 00212 { 00213 size_type __old_size = _Base::bucket_count(); 00214 std::pair<iterator, bool> __res = _Base::insert(__obj); 00215 this->_M_profile_resize(__old_size); 00216 return __res; 00217 } 00218 00219 iterator 00220 insert(const_iterator __iter, const value_type& __v) 00221 { 00222 size_type __old_size = _Base::bucket_count(); 00223 iterator __res = _Base::insert(__iter, __v); 00224 this->_M_profile_resize(__old_size); 00225 return __res; 00226 } 00227 00228 template<typename _Pair, typename = typename 00229 std::enable_if<std::is_constructible<value_type, 00230 _Pair&&>::value>::type> 00231 std::pair<iterator, bool> 00232 insert(_Pair&& __obj) 00233 { 00234 size_type __old_size = _Base::bucket_count(); 00235 std::pair<iterator, bool> __res 00236 = _Base::insert(std::forward<_Pair>(__obj)); 00237 this->_M_profile_resize(__old_size); 00238 return __res; 00239 } 00240 00241 template<typename _Pair, typename = typename 00242 std::enable_if<std::is_constructible<value_type, 00243 _Pair&&>::value>::type> 00244 iterator 00245 insert(const_iterator __iter, _Pair&& __v) 00246 { 00247 size_type __old_size = _Base::bucket_count(); 00248 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 00249 this->_M_profile_resize(__old_size); 00250 return __res; 00251 } 00252 00253 template<typename _InputIter> 00254 void 00255 insert(_InputIter __first, _InputIter __last) 00256 { 00257 size_type __old_size = _Base::bucket_count(); 00258 _Base::insert(__first, __last); 00259 this->_M_profile_resize(__old_size); 00260 } 00261 00262 // operator[] 00263 mapped_type& 00264 operator[](const _Key& __k) 00265 { 00266 size_type __old_size = _Base::bucket_count(); 00267 mapped_type& __res = _M_base()[__k]; 00268 this->_M_profile_resize(__old_size); 00269 return __res; 00270 } 00271 00272 mapped_type& 00273 operator[](_Key&& __k) 00274 { 00275 size_type __old_size = _Base::bucket_count(); 00276 mapped_type& __res = _M_base()[std::move(__k)]; 00277 this->_M_profile_resize(__old_size); 00278 return __res; 00279 } 00280 00281 void 00282 swap(unordered_map& __x) 00283 noexcept( noexcept(__x._M_base().swap(__x)) ) 00284 { 00285 _Base::swap(__x._M_base()); 00286 this->_M_swap(__x); 00287 } 00288 00289 void rehash(size_type __n) 00290 { 00291 size_type __old_size = _Base::bucket_count(); 00292 _Base::rehash(__n); 00293 this->_M_profile_resize(__old_size); 00294 } 00295 }; 00296 00297 template<typename _Key, typename _Tp, typename _Hash, 00298 typename _Pred, typename _Alloc> 00299 inline void 00300 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00301 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00302 noexcept(noexcept(__x.swap(__y))) 00303 { __x.swap(__y); } 00304 00305 template<typename _Key, typename _Tp, typename _Hash, 00306 typename _Pred, typename _Alloc> 00307 inline bool 00308 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00309 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00310 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00311 00312 template<typename _Key, typename _Tp, typename _Hash, 00313 typename _Pred, typename _Alloc> 00314 inline bool 00315 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00316 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00317 { return !(__x == __y); } 00318 00319 #undef _GLIBCXX_BASE 00320 #undef _GLIBCXX_STD_BASE 00321 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 00322 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 00323 00324 /// Class std::unordered_multimap wrapper with performance instrumentation. 00325 template<typename _Key, typename _Tp, 00326 typename _Hash = std::hash<_Key>, 00327 typename _Pred = std::equal_to<_Key>, 00328 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00329 class unordered_multimap 00330 : public _GLIBCXX_STD_BASE, 00331 public _Unordered_profile<unordered_multimap<_Key, _Tp, 00332 _Hash, _Pred, _Alloc>, 00333 false> 00334 { 00335 typedef typename _GLIBCXX_STD_BASE _Base; 00336 00337 _Base& 00338 _M_base() noexcept { return *this; } 00339 00340 const _Base& 00341 _M_base() const noexcept { return *this; } 00342 00343 public: 00344 typedef typename _Base::size_type size_type; 00345 typedef typename _Base::hasher hasher; 00346 typedef typename _Base::key_equal key_equal; 00347 typedef typename _Base::allocator_type allocator_type; 00348 typedef typename _Base::key_type key_type; 00349 typedef typename _Base::value_type value_type; 00350 typedef typename _Base::difference_type difference_type; 00351 typedef typename _Base::reference reference; 00352 typedef typename _Base::const_reference const_reference; 00353 00354 typedef typename _Base::iterator iterator; 00355 typedef typename _Base::const_iterator const_iterator; 00356 00357 unordered_multimap() = default; 00358 00359 explicit 00360 unordered_multimap(size_type __n, 00361 const hasher& __hf = hasher(), 00362 const key_equal& __eql = key_equal(), 00363 const allocator_type& __a = allocator_type()) 00364 : _Base(__n, __hf, __eql, __a) { } 00365 00366 template<typename _InputIterator> 00367 unordered_multimap(_InputIterator __f, _InputIterator __l, 00368 size_type __n = 0, 00369 const hasher& __hf = hasher(), 00370 const key_equal& __eql = key_equal(), 00371 const allocator_type& __a = allocator_type()) 00372 : _Base(__f, __l, __n, __hf, __eql, __a) { } 00373 00374 unordered_multimap(const unordered_multimap&) = default; 00375 00376 unordered_multimap(const _Base& __x) 00377 : _Base(__x) { } 00378 00379 unordered_multimap(unordered_multimap&&) = default; 00380 00381 explicit 00382 unordered_multimap(const allocator_type& __a) 00383 : _Base(__a) { } 00384 00385 unordered_multimap(const unordered_multimap& __ummap, 00386 const allocator_type& __a) 00387 : _Base(__ummap._M_base(), __a) { } 00388 00389 unordered_multimap(unordered_multimap&& __ummap, 00390 const allocator_type& __a) 00391 : _Base(std::move(__ummap._M_base()), __a) { } 00392 00393 unordered_multimap(initializer_list<value_type> __l, 00394 size_type __n = 0, 00395 const hasher& __hf = hasher(), 00396 const key_equal& __eql = key_equal(), 00397 const allocator_type& __a = allocator_type()) 00398 : _Base(__l, __n, __hf, __eql, __a) { } 00399 00400 unordered_multimap(size_type __n, const allocator_type& __a) 00401 : unordered_multimap(__n, hasher(), key_equal(), __a) 00402 { } 00403 00404 unordered_multimap(size_type __n, const hasher& __hf, 00405 const allocator_type& __a) 00406 : unordered_multimap(__n, __hf, key_equal(), __a) 00407 { } 00408 00409 template<typename _InputIterator> 00410 unordered_multimap(_InputIterator __first, _InputIterator __last, 00411 size_type __n, 00412 const allocator_type& __a) 00413 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 00414 { } 00415 00416 template<typename _InputIterator> 00417 unordered_multimap(_InputIterator __first, _InputIterator __last, 00418 size_type __n, const hasher& __hf, 00419 const allocator_type& __a) 00420 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 00421 { } 00422 00423 unordered_multimap(initializer_list<value_type> __l, 00424 size_type __n, 00425 const allocator_type& __a) 00426 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 00427 { } 00428 00429 unordered_multimap(initializer_list<value_type> __l, 00430 size_type __n, const hasher& __hf, 00431 const allocator_type& __a) 00432 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 00433 { } 00434 00435 unordered_multimap& 00436 operator=(const unordered_multimap&) = default; 00437 00438 unordered_multimap& 00439 operator=(unordered_multimap&&) = default; 00440 00441 unordered_multimap& 00442 operator=(initializer_list<value_type> __l) 00443 { 00444 this->_M_profile_destruct(); 00445 _M_base() = __l; 00446 this->_M_profile_construct(); 00447 return *this; 00448 } 00449 00450 void 00451 clear() noexcept 00452 { 00453 this->_M_profile_destruct(); 00454 _Base::clear(); 00455 this->_M_profile_construct(); 00456 } 00457 00458 template<typename... _Args> 00459 iterator 00460 emplace(_Args&&... __args) 00461 { 00462 size_type __old_size = _Base::bucket_count(); 00463 iterator __res 00464 = _Base::emplace(std::forward<_Args>(__args)...); 00465 this->_M_profile_resize(__old_size); 00466 return __res; 00467 } 00468 00469 template<typename... _Args> 00470 iterator 00471 emplace_hint(const_iterator __it, _Args&&... __args) 00472 { 00473 size_type __old_size = _Base::bucket_count(); 00474 iterator __res 00475 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 00476 this->_M_profile_resize(__old_size); 00477 return __res; 00478 } 00479 00480 void 00481 insert(std::initializer_list<value_type> __l) 00482 { 00483 size_type __old_size = _Base::bucket_count(); 00484 _Base::insert(__l); 00485 this->_M_profile_resize(__old_size); 00486 } 00487 00488 iterator 00489 insert(const value_type& __obj) 00490 { 00491 size_type __old_size = _Base::bucket_count(); 00492 iterator __res = _Base::insert(__obj); 00493 this->_M_profile_resize(__old_size); 00494 return __res; 00495 } 00496 00497 iterator 00498 insert(const_iterator __iter, const value_type& __v) 00499 { 00500 size_type __old_size = _Base::bucket_count(); 00501 iterator __res = _Base::insert(__iter, __v); 00502 this->_M_profile_resize(__old_size); 00503 return __res; 00504 } 00505 00506 template<typename _Pair, typename = typename 00507 std::enable_if<std::is_constructible<value_type, 00508 _Pair&&>::value>::type> 00509 iterator 00510 insert(_Pair&& __obj) 00511 { 00512 size_type __old_size = _Base::bucket_count(); 00513 iterator __res = _Base::insert(std::forward<_Pair>(__obj)); 00514 this->_M_profile_resize(__old_size); 00515 return __res; 00516 } 00517 00518 template<typename _Pair, typename = typename 00519 std::enable_if<std::is_constructible<value_type, 00520 _Pair&&>::value>::type> 00521 iterator 00522 insert(const_iterator __iter, _Pair&& __v) 00523 { 00524 size_type __old_size = _Base::bucket_count(); 00525 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 00526 this->_M_profile_resize(__old_size); 00527 return __res; 00528 } 00529 00530 template<typename _InputIter> 00531 void 00532 insert(_InputIter __first, _InputIter __last) 00533 { 00534 size_type __old_size = _Base::bucket_count(); 00535 _Base::insert(__first, __last); 00536 this->_M_profile_resize(__old_size); 00537 } 00538 00539 void 00540 swap(unordered_multimap& __x) 00541 noexcept( noexcept(__x._M_base().swap(__x)) ) 00542 { 00543 _Base::swap(__x._M_base()); 00544 this->_M_swap(__x); 00545 } 00546 00547 void 00548 rehash(size_type __n) 00549 { 00550 size_type __old_size = _Base::bucket_count(); 00551 _Base::rehash(__n); 00552 this->_M_profile_resize(__old_size); 00553 } 00554 }; 00555 00556 template<typename _Key, typename _Tp, typename _Hash, 00557 typename _Pred, typename _Alloc> 00558 inline void 00559 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00560 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00561 noexcept(noexcept(__x.swap(__y))) 00562 { __x.swap(__y); } 00563 00564 template<typename _Key, typename _Tp, typename _Hash, 00565 typename _Pred, typename _Alloc> 00566 inline bool 00567 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00568 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00569 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00570 00571 template<typename _Key, typename _Tp, typename _Hash, 00572 typename _Pred, typename _Alloc> 00573 inline bool 00574 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00575 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00576 { return !(__x == __y); } 00577 00578 } // namespace __profile 00579 } // namespace std 00580 00581 #undef _GLIBCXX_BASE 00582 #undef _GLIBCXX_STD_BASE 00583 00584 #endif // C++11 00585 00586 #endif