libstdc++
|
00001 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2009-2015 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 { __x.swap(__y); } 00303 00304 template<typename _Key, typename _Tp, typename _Hash, 00305 typename _Pred, typename _Alloc> 00306 inline bool 00307 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00308 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00309 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00310 00311 template<typename _Key, typename _Tp, typename _Hash, 00312 typename _Pred, typename _Alloc> 00313 inline bool 00314 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00315 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00316 { return !(__x == __y); } 00317 00318 #undef _GLIBCXX_BASE 00319 #undef _GLIBCXX_STD_BASE 00320 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 00321 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 00322 00323 /// Class std::unordered_multimap wrapper with performance instrumentation. 00324 template<typename _Key, typename _Tp, 00325 typename _Hash = std::hash<_Key>, 00326 typename _Pred = std::equal_to<_Key>, 00327 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00328 class unordered_multimap 00329 : public _GLIBCXX_STD_BASE, 00330 public _Unordered_profile<unordered_multimap<_Key, _Tp, 00331 _Hash, _Pred, _Alloc>, 00332 false> 00333 { 00334 typedef typename _GLIBCXX_STD_BASE _Base; 00335 00336 _Base& 00337 _M_base() noexcept { return *this; } 00338 00339 const _Base& 00340 _M_base() const noexcept { return *this; } 00341 00342 public: 00343 typedef typename _Base::size_type size_type; 00344 typedef typename _Base::hasher hasher; 00345 typedef typename _Base::key_equal key_equal; 00346 typedef typename _Base::allocator_type allocator_type; 00347 typedef typename _Base::key_type key_type; 00348 typedef typename _Base::value_type value_type; 00349 typedef typename _Base::difference_type difference_type; 00350 typedef typename _Base::reference reference; 00351 typedef typename _Base::const_reference const_reference; 00352 00353 typedef typename _Base::iterator iterator; 00354 typedef typename _Base::const_iterator const_iterator; 00355 00356 unordered_multimap() = default; 00357 00358 explicit 00359 unordered_multimap(size_type __n, 00360 const hasher& __hf = hasher(), 00361 const key_equal& __eql = key_equal(), 00362 const allocator_type& __a = allocator_type()) 00363 : _Base(__n, __hf, __eql, __a) { } 00364 00365 template<typename _InputIterator> 00366 unordered_multimap(_InputIterator __f, _InputIterator __l, 00367 size_type __n = 0, 00368 const hasher& __hf = hasher(), 00369 const key_equal& __eql = key_equal(), 00370 const allocator_type& __a = allocator_type()) 00371 : _Base(__f, __l, __n, __hf, __eql, __a) { } 00372 00373 unordered_multimap(const unordered_multimap&) = default; 00374 00375 unordered_multimap(const _Base& __x) 00376 : _Base(__x) { } 00377 00378 unordered_multimap(unordered_multimap&&) = default; 00379 00380 explicit 00381 unordered_multimap(const allocator_type& __a) 00382 : _Base(__a) { } 00383 00384 unordered_multimap(const unordered_multimap& __ummap, 00385 const allocator_type& __a) 00386 : _Base(__ummap._M_base(), __a) { } 00387 00388 unordered_multimap(unordered_multimap&& __ummap, 00389 const allocator_type& __a) 00390 : _Base(std::move(__ummap._M_base()), __a) { } 00391 00392 unordered_multimap(initializer_list<value_type> __l, 00393 size_type __n = 0, 00394 const hasher& __hf = hasher(), 00395 const key_equal& __eql = key_equal(), 00396 const allocator_type& __a = allocator_type()) 00397 : _Base(__l, __n, __hf, __eql, __a) { } 00398 00399 unordered_multimap(size_type __n, const allocator_type& __a) 00400 : unordered_multimap(__n, hasher(), key_equal(), __a) 00401 { } 00402 00403 unordered_multimap(size_type __n, const hasher& __hf, 00404 const allocator_type& __a) 00405 : unordered_multimap(__n, __hf, key_equal(), __a) 00406 { } 00407 00408 template<typename _InputIterator> 00409 unordered_multimap(_InputIterator __first, _InputIterator __last, 00410 size_type __n, 00411 const allocator_type& __a) 00412 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 00413 { } 00414 00415 template<typename _InputIterator> 00416 unordered_multimap(_InputIterator __first, _InputIterator __last, 00417 size_type __n, const hasher& __hf, 00418 const allocator_type& __a) 00419 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 00420 { } 00421 00422 unordered_multimap(initializer_list<value_type> __l, 00423 size_type __n, 00424 const allocator_type& __a) 00425 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 00426 { } 00427 00428 unordered_multimap(initializer_list<value_type> __l, 00429 size_type __n, const hasher& __hf, 00430 const allocator_type& __a) 00431 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 00432 { } 00433 00434 unordered_multimap& 00435 operator=(const unordered_multimap&) = default; 00436 00437 unordered_multimap& 00438 operator=(unordered_multimap&&) = default; 00439 00440 unordered_multimap& 00441 operator=(initializer_list<value_type> __l) 00442 { 00443 this->_M_profile_destruct(); 00444 _M_base() = __l; 00445 this->_M_profile_construct(); 00446 return *this; 00447 } 00448 00449 void 00450 clear() noexcept 00451 { 00452 this->_M_profile_destruct(); 00453 _Base::clear(); 00454 this->_M_profile_construct(); 00455 } 00456 00457 template<typename... _Args> 00458 iterator 00459 emplace(_Args&&... __args) 00460 { 00461 size_type __old_size = _Base::bucket_count(); 00462 iterator __res 00463 = _Base::emplace(std::forward<_Args>(__args)...); 00464 this->_M_profile_resize(__old_size); 00465 return __res; 00466 } 00467 00468 template<typename... _Args> 00469 iterator 00470 emplace_hint(const_iterator __it, _Args&&... __args) 00471 { 00472 size_type __old_size = _Base::bucket_count(); 00473 iterator __res 00474 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 00475 this->_M_profile_resize(__old_size); 00476 return __res; 00477 } 00478 00479 void 00480 insert(std::initializer_list<value_type> __l) 00481 { 00482 size_type __old_size = _Base::bucket_count(); 00483 _Base::insert(__l); 00484 this->_M_profile_resize(__old_size); 00485 } 00486 00487 iterator 00488 insert(const value_type& __obj) 00489 { 00490 size_type __old_size = _Base::bucket_count(); 00491 iterator __res = _Base::insert(__obj); 00492 this->_M_profile_resize(__old_size); 00493 return __res; 00494 } 00495 00496 iterator 00497 insert(const_iterator __iter, const value_type& __v) 00498 { 00499 size_type __old_size = _Base::bucket_count(); 00500 iterator __res = _Base::insert(__iter, __v); 00501 this->_M_profile_resize(__old_size); 00502 return __res; 00503 } 00504 00505 template<typename _Pair, typename = typename 00506 std::enable_if<std::is_constructible<value_type, 00507 _Pair&&>::value>::type> 00508 iterator 00509 insert(_Pair&& __obj) 00510 { 00511 size_type __old_size = _Base::bucket_count(); 00512 iterator __res = _Base::insert(std::forward<_Pair>(__obj)); 00513 this->_M_profile_resize(__old_size); 00514 return __res; 00515 } 00516 00517 template<typename _Pair, typename = typename 00518 std::enable_if<std::is_constructible<value_type, 00519 _Pair&&>::value>::type> 00520 iterator 00521 insert(const_iterator __iter, _Pair&& __v) 00522 { 00523 size_type __old_size = _Base::bucket_count(); 00524 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 00525 this->_M_profile_resize(__old_size); 00526 return __res; 00527 } 00528 00529 template<typename _InputIter> 00530 void 00531 insert(_InputIter __first, _InputIter __last) 00532 { 00533 size_type __old_size = _Base::bucket_count(); 00534 _Base::insert(__first, __last); 00535 this->_M_profile_resize(__old_size); 00536 } 00537 00538 void 00539 swap(unordered_multimap& __x) 00540 noexcept( noexcept(__x._M_base().swap(__x)) ) 00541 { 00542 _Base::swap(__x._M_base()); 00543 this->_M_swap(__x); 00544 } 00545 00546 void 00547 rehash(size_type __n) 00548 { 00549 size_type __old_size = _Base::bucket_count(); 00550 _Base::rehash(__n); 00551 this->_M_profile_resize(__old_size); 00552 } 00553 }; 00554 00555 template<typename _Key, typename _Tp, typename _Hash, 00556 typename _Pred, typename _Alloc> 00557 inline void 00558 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00559 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00560 { __x.swap(__y); } 00561 00562 template<typename _Key, typename _Tp, typename _Hash, 00563 typename _Pred, typename _Alloc> 00564 inline bool 00565 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00566 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00567 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00568 00569 template<typename _Key, typename _Tp, typename _Hash, 00570 typename _Pred, typename _Alloc> 00571 inline bool 00572 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00573 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00574 { return !(__x == __y); } 00575 00576 } // namespace __profile 00577 } // namespace std 00578 00579 #undef _GLIBCXX_BASE 00580 #undef _GLIBCXX_STD_BASE 00581 00582 #endif // C++11 00583 00584 #endif