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