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