libstdc++
|
00001 // Profiling set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2009-2019 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 profile/set.h 00026 * This file is a GNU profile extension to the Standard C++ Library. 00027 */ 00028 00029 #ifndef _GLIBCXX_PROFILE_SET_H 00030 #define _GLIBCXX_PROFILE_SET_H 1 00031 00032 #include <profile/base.h> 00033 #include <profile/ordered_base.h> 00034 00035 namespace std _GLIBCXX_VISIBILITY(default) 00036 { 00037 namespace __profile 00038 { 00039 /// Class std::set wrapper with performance instrumentation. 00040 template<typename _Key, typename _Compare = std::less<_Key>, 00041 typename _Allocator = std::allocator<_Key> > 00042 class set 00043 : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>, 00044 public _Ordered_profile<set<_Key, _Compare, _Allocator> > 00045 { 00046 typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base; 00047 00048 typedef typename _Base::iterator _Base_iterator; 00049 typedef typename _Base::const_iterator _Base_const_iterator; 00050 00051 public: 00052 // types: 00053 typedef _Key key_type; 00054 typedef _Key value_type; 00055 typedef _Compare key_compare; 00056 typedef _Compare value_compare; 00057 typedef typename _Base::reference reference; 00058 typedef typename _Base::const_reference const_reference; 00059 00060 typedef __iterator_tracker<_Base_iterator, set> iterator; 00061 typedef __iterator_tracker<_Base_const_iterator, 00062 set> const_iterator; 00063 typedef std::reverse_iterator<iterator> reverse_iterator; 00064 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00065 00066 typedef typename _Base::size_type size_type; 00067 typedef typename _Base::difference_type difference_type; 00068 00069 // 23.3.3.1 construct/copy/destroy: 00070 #if __cplusplus < 201103L 00071 set() 00072 : _Base() { } 00073 set(const set& __x) 00074 : _Base(__x) { } 00075 ~set() { } 00076 #else 00077 set() = default; 00078 set(const set&) = default; 00079 set(set&&) = default; 00080 ~set() = default; 00081 #endif 00082 00083 explicit set(const _Compare& __comp, 00084 const _Allocator& __a = _Allocator()) 00085 : _Base(__comp, __a) { } 00086 00087 #if __cplusplus >= 201103L 00088 template<typename _InputIterator, 00089 typename = std::_RequireInputIter<_InputIterator>> 00090 #else 00091 template<typename _InputIterator> 00092 #endif 00093 set(_InputIterator __first, _InputIterator __last, 00094 const _Compare& __comp = _Compare(), 00095 const _Allocator& __a = _Allocator()) 00096 : _Base(__first, __last, __comp, __a) { } 00097 00098 #if __cplusplus >= 201103L 00099 set(initializer_list<value_type> __l, 00100 const _Compare& __comp = _Compare(), 00101 const _Allocator& __a = _Allocator()) 00102 : _Base(__l, __comp, __a) { } 00103 00104 explicit 00105 set(const _Allocator& __a) 00106 : _Base(__a) { } 00107 00108 set(const set& __x, const _Allocator& __a) 00109 : _Base(__x, __a) { } 00110 00111 set(set&& __x, const _Allocator& __a) 00112 noexcept( noexcept(_Base(std::move(__x), __a)) ) 00113 : _Base(std::move(__x), __a) { } 00114 00115 set(initializer_list<value_type> __l, const _Allocator& __a) 00116 : _Base(__l, __a) { } 00117 00118 template<typename _InputIterator> 00119 set(_InputIterator __first, _InputIterator __last, 00120 const _Allocator& __a) 00121 : _Base(__first, __last, __a) { } 00122 #endif 00123 00124 set(const _Base& __x) 00125 : _Base(__x) { } 00126 00127 #if __cplusplus < 201103L 00128 set& 00129 operator=(const set& __x) 00130 { 00131 this->_M_profile_destruct(); 00132 _M_base() = __x; 00133 this->_M_profile_construct(); 00134 return *this; 00135 } 00136 #else 00137 set& 00138 operator=(const set&) = default; 00139 00140 set& 00141 operator=(set&&) = default; 00142 00143 set& 00144 operator=(initializer_list<value_type> __l) 00145 { 00146 this->_M_profile_destruct(); 00147 _M_base() = __l; 00148 this->_M_profile_construct(); 00149 return *this; 00150 } 00151 #endif 00152 00153 // iterators 00154 iterator 00155 begin() _GLIBCXX_NOEXCEPT 00156 { return iterator(_Base::begin(), this); } 00157 00158 const_iterator 00159 begin() const _GLIBCXX_NOEXCEPT 00160 { return const_iterator(_Base::begin(), this); } 00161 00162 iterator 00163 end() _GLIBCXX_NOEXCEPT 00164 { return iterator(_Base::end(), this); } 00165 00166 const_iterator 00167 end() const _GLIBCXX_NOEXCEPT 00168 { return const_iterator(_Base::end(), this); } 00169 00170 #if __cplusplus >= 201103L 00171 const_iterator 00172 cbegin() const noexcept 00173 { return const_iterator(_Base::cbegin(), this); } 00174 00175 const_iterator 00176 cend() const noexcept 00177 { return const_iterator(_Base::cend(), this); } 00178 #endif 00179 00180 reverse_iterator 00181 rbegin() _GLIBCXX_NOEXCEPT 00182 { 00183 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00184 return reverse_iterator(end()); 00185 } 00186 00187 const_reverse_iterator 00188 rbegin() const _GLIBCXX_NOEXCEPT 00189 { 00190 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00191 return const_reverse_iterator(end()); 00192 } 00193 00194 reverse_iterator 00195 rend() _GLIBCXX_NOEXCEPT 00196 { 00197 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00198 return reverse_iterator(begin()); 00199 } 00200 00201 const_reverse_iterator 00202 rend() const _GLIBCXX_NOEXCEPT 00203 { 00204 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00205 return const_reverse_iterator(begin()); 00206 } 00207 00208 #if __cplusplus >= 201103L 00209 const_reverse_iterator 00210 crbegin() const noexcept 00211 { 00212 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00213 return const_reverse_iterator(cend()); 00214 } 00215 00216 const_reverse_iterator 00217 crend() const noexcept 00218 { 00219 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00220 return const_reverse_iterator(cbegin()); 00221 } 00222 #endif 00223 00224 void 00225 swap(set& __x) 00226 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 00227 { 00228 _Base::swap(__x); 00229 this->_M_swap(__x); 00230 } 00231 00232 // modifiers: 00233 #if __cplusplus >= 201103L 00234 template<typename... _Args> 00235 std::pair<iterator, bool> 00236 emplace(_Args&&... __args) 00237 { 00238 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 00239 auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...); 00240 return std::make_pair(iterator(__base_ret.first, this), 00241 __base_ret.second); 00242 } 00243 00244 template<typename... _Args> 00245 iterator 00246 emplace_hint(const_iterator __pos, _Args&&... __args) 00247 { 00248 auto size_before = this->size(); 00249 auto __res 00250 = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...); 00251 __profcxx_map2umap_insert(this->_M_map2umap_info, 00252 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 00253 return iterator(__res, this); 00254 } 00255 #endif 00256 00257 std::pair<iterator, bool> 00258 insert(const value_type& __x) 00259 { 00260 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 00261 std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x); 00262 return std::make_pair(iterator(__base_ret.first, this), 00263 __base_ret.second); 00264 } 00265 00266 #if __cplusplus >= 201103L 00267 std::pair<iterator, bool> 00268 insert(value_type&& __x) 00269 { 00270 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 00271 std::pair<_Base_iterator, bool> __base_ret 00272 = _Base::insert(std::move(__x)); 00273 return std::make_pair(iterator(__base_ret.first, this), 00274 __base_ret.second); 00275 } 00276 #endif 00277 00278 iterator 00279 insert(const_iterator __pos, const value_type& __x) 00280 { 00281 size_type size_before = this->size(); 00282 _Base_iterator __res = _Base::insert(__pos.base(), __x); 00283 __profcxx_map2umap_insert(this->_M_map2umap_info, 00284 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 00285 return iterator(__res, this); 00286 } 00287 00288 #if __cplusplus >= 201103L 00289 iterator 00290 insert(const_iterator __pos, value_type&& __x) 00291 { return iterator(_Base::insert(__pos.base(), std::move(__x)), this); } 00292 #endif 00293 00294 template<typename _InputIterator> 00295 void 00296 insert(_InputIterator __first, _InputIterator __last) 00297 { 00298 for (; __first != __last; ++__first) 00299 insert(*__first); 00300 } 00301 00302 #if __cplusplus >= 201103L 00303 void 00304 insert(initializer_list<value_type> __l) 00305 { insert(__l.begin(), __l.end()); } 00306 #endif 00307 00308 #if __cplusplus >= 201103L 00309 iterator 00310 erase(const_iterator __pos) 00311 { 00312 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 00313 return iterator(_Base::erase(__pos.base()), this); 00314 } 00315 #else 00316 void 00317 erase(iterator __pos) 00318 { 00319 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 00320 _Base::erase(__pos.base()); 00321 } 00322 #endif 00323 00324 size_type 00325 erase(const key_type& __x) 00326 { 00327 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00328 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 00329 return _Base::erase(__x); 00330 } 00331 00332 #if __cplusplus >= 201103L 00333 iterator 00334 erase(const_iterator __first, const_iterator __last) 00335 { 00336 if (__first != __last) 00337 { 00338 iterator __ret; 00339 for (; __first != __last;) 00340 __ret = erase(__first++); 00341 return __ret; 00342 } 00343 00344 return iterator(_Base::erase(__first.base(), __last.base()), this); 00345 } 00346 #else 00347 void 00348 erase(iterator __first, iterator __last) 00349 { 00350 for (; __first != __last;) 00351 erase(__first++); 00352 } 00353 #endif 00354 00355 void 00356 clear() _GLIBCXX_NOEXCEPT 00357 { 00358 this->_M_profile_destruct(); 00359 _Base::clear(); 00360 this->_M_profile_construct(); 00361 } 00362 00363 size_type 00364 count(const key_type& __x) const 00365 { 00366 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00367 return _Base::count(__x); 00368 } 00369 00370 #if __cplusplus > 201103L 00371 template<typename _Kt, 00372 typename _Req = 00373 typename __has_is_transparent<_Compare, _Kt>::type> 00374 size_type 00375 count(const _Kt& __x) const 00376 { 00377 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00378 return _Base::count(__x); 00379 } 00380 #endif 00381 00382 // set operations: 00383 iterator 00384 find(const key_type& __x) 00385 { 00386 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00387 return iterator(_Base::find(__x), this); 00388 } 00389 00390 const_iterator 00391 find(const key_type& __x) const 00392 { 00393 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00394 return const_iterator(_Base::find(__x), this); 00395 } 00396 00397 #if __cplusplus > 201103L 00398 template<typename _Kt, 00399 typename _Req = 00400 typename __has_is_transparent<_Compare, _Kt>::type> 00401 iterator 00402 find(const _Kt& __x) 00403 { 00404 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00405 return { _Base::find(__x), this }; 00406 } 00407 00408 template<typename _Kt, 00409 typename _Req = 00410 typename __has_is_transparent<_Compare, _Kt>::type> 00411 const_iterator 00412 find(const _Kt& __x) const 00413 { 00414 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00415 return { _Base::find(__x), this }; 00416 } 00417 #endif 00418 00419 iterator 00420 lower_bound(const key_type& __x) 00421 { 00422 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00423 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00424 return iterator(_Base::lower_bound(__x), this); 00425 } 00426 00427 const_iterator 00428 lower_bound(const key_type& __x) const 00429 { 00430 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00431 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00432 return const_iterator(_Base::lower_bound(__x), this); 00433 } 00434 00435 #if __cplusplus > 201103L 00436 template<typename _Kt, 00437 typename _Req = 00438 typename __has_is_transparent<_Compare, _Kt>::type> 00439 iterator 00440 lower_bound(const _Kt& __x) 00441 { 00442 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00443 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00444 return { _Base::lower_bound(__x), this }; 00445 } 00446 00447 template<typename _Kt, 00448 typename _Req = 00449 typename __has_is_transparent<_Compare, _Kt>::type> 00450 const_iterator 00451 lower_bound(const _Kt& __x) const 00452 { 00453 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00454 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00455 return { _Base::lower_bound(__x), this }; 00456 } 00457 #endif 00458 00459 iterator 00460 upper_bound(const key_type& __x) 00461 { 00462 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00463 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00464 return iterator(_Base::upper_bound(__x), this); 00465 } 00466 00467 const_iterator 00468 upper_bound(const key_type& __x) const 00469 { 00470 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00471 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00472 return const_iterator(_Base::upper_bound(__x), this); 00473 } 00474 00475 #if __cplusplus > 201103L 00476 template<typename _Kt, 00477 typename _Req = 00478 typename __has_is_transparent<_Compare, _Kt>::type> 00479 iterator 00480 upper_bound(const _Kt& __x) 00481 { 00482 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00483 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00484 return { _Base::upper_bound(__x), this }; 00485 } 00486 00487 template<typename _Kt, 00488 typename _Req = 00489 typename __has_is_transparent<_Compare, _Kt>::type> 00490 const_iterator 00491 upper_bound(const _Kt& __x) const 00492 { 00493 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00494 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00495 return { _Base::upper_bound(__x), this }; 00496 } 00497 #endif 00498 00499 std::pair<iterator, iterator> 00500 equal_range(const key_type& __x) 00501 { 00502 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00503 std::pair<_Base_iterator, _Base_iterator> __base_ret 00504 = _Base::equal_range(__x); 00505 return std::make_pair(iterator(__base_ret.first, this), 00506 iterator(__base_ret.second, this)); 00507 } 00508 00509 std::pair<const_iterator, const_iterator> 00510 equal_range(const key_type& __x) const 00511 { 00512 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00513 std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret 00514 = _Base::equal_range(__x); 00515 return std::make_pair(const_iterator(__base_ret.first, this), 00516 const_iterator(__base_ret.second, this)); 00517 } 00518 00519 #if __cplusplus > 201103L 00520 template<typename _Kt, 00521 typename _Req = 00522 typename __has_is_transparent<_Compare, _Kt>::type> 00523 std::pair<iterator, iterator> 00524 equal_range(const _Kt& __x) 00525 { 00526 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00527 auto __res = _Base::equal_range(__x); 00528 return { { __res.first, this }, { __res.second, this } }; 00529 } 00530 00531 template<typename _Kt, 00532 typename _Req = 00533 typename __has_is_transparent<_Compare, _Kt>::type> 00534 std::pair<const_iterator, const_iterator> 00535 equal_range(const _Kt& __x) const 00536 { 00537 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00538 auto __res = _Base::equal_range(__x); 00539 return { { __res.first, this }, { __res.second, this } }; 00540 } 00541 #endif 00542 00543 _Base& 00544 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00545 00546 const _Base& 00547 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00548 00549 private: 00550 /** If hint is used we consider that the map and unordered_map 00551 * operations have equivalent insertion cost so we do not update metrics 00552 * about it. 00553 * Note that to find out if hint has been used is libstdc++ 00554 * implementation dependent. 00555 */ 00556 bool 00557 _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res) 00558 { 00559 return (__hint == __res 00560 || (__hint == _M_base().end() && ++__res == _M_base().end()) 00561 || (__hint != _M_base().end() && (++__hint == __res 00562 || ++__res == --__hint))); 00563 } 00564 00565 template<typename _K1, typename _C1, typename _A1> 00566 friend bool 00567 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 00568 00569 template<typename _K1, typename _C1, typename _A1> 00570 friend bool 00571 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 00572 }; 00573 00574 template<typename _Key, typename _Compare, typename _Allocator> 00575 inline bool 00576 operator==(const set<_Key, _Compare, _Allocator>& __lhs, 00577 const set<_Key, _Compare, _Allocator>& __rhs) 00578 { 00579 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 00580 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 00581 return __lhs._M_base() == __rhs._M_base(); 00582 } 00583 00584 template<typename _Key, typename _Compare, typename _Allocator> 00585 inline bool 00586 operator<(const set<_Key, _Compare, _Allocator>& __lhs, 00587 const set<_Key, _Compare, _Allocator>& __rhs) 00588 { 00589 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 00590 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 00591 return __lhs._M_base() < __rhs._M_base(); 00592 } 00593 00594 template<typename _Key, typename _Compare, typename _Allocator> 00595 inline bool 00596 operator!=(const set<_Key, _Compare, _Allocator>& __lhs, 00597 const set<_Key, _Compare, _Allocator>& __rhs) 00598 { return !(__lhs == __rhs); } 00599 00600 template<typename _Key, typename _Compare, typename _Allocator> 00601 inline bool 00602 operator<=(const set<_Key, _Compare, _Allocator>& __lhs, 00603 const set<_Key, _Compare, _Allocator>& __rhs) 00604 { return !(__rhs < __lhs); } 00605 00606 template<typename _Key, typename _Compare, typename _Allocator> 00607 inline bool 00608 operator>=(const set<_Key, _Compare, _Allocator>& __lhs, 00609 const set<_Key, _Compare, _Allocator>& __rhs) 00610 { return !(__lhs < __rhs); } 00611 00612 template<typename _Key, typename _Compare, typename _Allocator> 00613 inline bool 00614 operator>(const set<_Key, _Compare, _Allocator>& __lhs, 00615 const set<_Key, _Compare, _Allocator>& __rhs) 00616 { return __rhs < __lhs; } 00617 00618 template<typename _Key, typename _Compare, typename _Allocator> 00619 void 00620 swap(set<_Key, _Compare, _Allocator>& __x, 00621 set<_Key, _Compare, _Allocator>& __y) 00622 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 00623 { return __x.swap(__y); } 00624 00625 } // namespace __profile 00626 } // namespace std 00627 00628 #endif