libstdc++
|
00001 // Profiling set 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 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 #if __cplusplus >= 201103L 00227 noexcept( noexcept(declval<_Base>().swap(__x)) ) 00228 #endif 00229 { 00230 _Base::swap(__x); 00231 this->_M_swap(__x); 00232 } 00233 00234 // modifiers: 00235 #if __cplusplus >= 201103L 00236 template<typename... _Args> 00237 std::pair<iterator, bool> 00238 emplace(_Args&&... __args) 00239 { 00240 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 00241 auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...); 00242 return std::make_pair(iterator(__base_ret.first, this), 00243 __base_ret.second); 00244 } 00245 00246 template<typename... _Args> 00247 iterator 00248 emplace_hint(const_iterator __pos, _Args&&... __args) 00249 { 00250 auto size_before = this->size(); 00251 auto __res 00252 = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...); 00253 __profcxx_map2umap_insert(this->_M_map2umap_info, 00254 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 00255 return iterator(__res, this); 00256 } 00257 #endif 00258 00259 std::pair<iterator, bool> 00260 insert(const value_type& __x) 00261 { 00262 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 00263 std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x); 00264 return std::make_pair(iterator(__base_ret.first, this), 00265 __base_ret.second); 00266 } 00267 00268 #if __cplusplus >= 201103L 00269 std::pair<iterator, bool> 00270 insert(value_type&& __x) 00271 { 00272 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 00273 std::pair<_Base_iterator, bool> __base_ret 00274 = _Base::insert(std::move(__x)); 00275 return std::make_pair(iterator(__base_ret.first, this), 00276 __base_ret.second); 00277 } 00278 #endif 00279 00280 iterator 00281 insert(const_iterator __pos, const value_type& __x) 00282 { 00283 size_type size_before = this->size(); 00284 _Base_iterator __res = _Base::insert(__pos.base(), __x); 00285 __profcxx_map2umap_insert(this->_M_map2umap_info, 00286 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 00287 return iterator(__res, this); 00288 } 00289 00290 #if __cplusplus >= 201103L 00291 iterator 00292 insert(const_iterator __pos, value_type&& __x) 00293 { return iterator(_Base::insert(__pos.base(), std::move(__x)), this); } 00294 #endif 00295 00296 template<typename _InputIterator> 00297 void 00298 insert(_InputIterator __first, _InputIterator __last) 00299 { 00300 for (; __first != __last; ++__first) 00301 insert(*__first); 00302 } 00303 00304 #if __cplusplus >= 201103L 00305 void 00306 insert(initializer_list<value_type> __l) 00307 { insert(__l.begin(), __l.end()); } 00308 #endif 00309 00310 #if __cplusplus >= 201103L 00311 iterator 00312 erase(const_iterator __pos) 00313 { 00314 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 00315 return iterator(_Base::erase(__pos.base()), this); 00316 } 00317 #else 00318 void 00319 erase(iterator __pos) 00320 { 00321 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 00322 _Base::erase(__pos.base()); 00323 } 00324 #endif 00325 00326 size_type 00327 erase(const key_type& __x) 00328 { 00329 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00330 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 00331 return _Base::erase(__x); 00332 } 00333 00334 #if __cplusplus >= 201103L 00335 iterator 00336 erase(const_iterator __first, const_iterator __last) 00337 { 00338 if (__first != __last) 00339 { 00340 iterator __ret; 00341 for (; __first != __last;) 00342 __ret = erase(__first++); 00343 return __ret; 00344 } 00345 00346 return iterator(_Base::erase(__first.base(), __last.base()), this); 00347 } 00348 #else 00349 void 00350 erase(iterator __first, iterator __last) 00351 { 00352 for (; __first != __last;) 00353 erase(__first++); 00354 } 00355 #endif 00356 00357 void 00358 clear() _GLIBCXX_NOEXCEPT 00359 { 00360 this->_M_profile_destruct(); 00361 _Base::clear(); 00362 this->_M_profile_construct(); 00363 } 00364 00365 size_type 00366 count(const key_type& __x) const 00367 { 00368 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00369 return _Base::count(__x); 00370 } 00371 00372 // set operations: 00373 iterator 00374 find(const key_type& __x) 00375 { 00376 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00377 return iterator(_Base::find(__x), this); 00378 } 00379 00380 const_iterator 00381 find(const key_type& __x) const 00382 { 00383 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00384 return const_iterator(_Base::find(__x), this); 00385 } 00386 00387 iterator 00388 lower_bound(const key_type& __x) 00389 { 00390 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00391 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00392 return iterator(_Base::lower_bound(__x), this); 00393 } 00394 00395 const_iterator 00396 lower_bound(const key_type& __x) const 00397 { 00398 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00399 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00400 return const_iterator(_Base::lower_bound(__x), this); 00401 } 00402 00403 iterator 00404 upper_bound(const key_type& __x) 00405 { 00406 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00407 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00408 return iterator(_Base::upper_bound(__x), this); 00409 } 00410 00411 const_iterator 00412 upper_bound(const key_type& __x) const 00413 { 00414 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00415 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 00416 return const_iterator(_Base::upper_bound(__x), this); 00417 } 00418 00419 std::pair<iterator, iterator> 00420 equal_range(const key_type& __x) 00421 { 00422 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00423 std::pair<_Base_iterator, _Base_iterator> __base_ret 00424 = _Base::equal_range(__x); 00425 return std::make_pair(iterator(__base_ret.first, this), 00426 iterator(__base_ret.second, this)); 00427 } 00428 00429 std::pair<const_iterator, const_iterator> 00430 equal_range(const key_type& __x) const 00431 { 00432 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 00433 std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret 00434 = _Base::equal_range(__x); 00435 return std::make_pair(const_iterator(__base_ret.first, this), 00436 const_iterator(__base_ret.second, this)); 00437 } 00438 00439 _Base& 00440 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00441 00442 const _Base& 00443 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00444 00445 private: 00446 /** If hint is used we consider that the map and unordered_map 00447 * operations have equivalent insertion cost so we do not update metrics 00448 * about it. 00449 * Note that to find out if hint has been used is libstdc++ 00450 * implementation dependent. 00451 */ 00452 bool 00453 _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res) 00454 { 00455 return (__hint == __res 00456 || (__hint == _M_base().end() && ++__res == _M_base().end()) 00457 || (__hint != _M_base().end() && (++__hint == __res 00458 || ++__res == --__hint))); 00459 } 00460 00461 template<typename _K1, typename _C1, typename _A1> 00462 friend bool 00463 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 00464 00465 template<typename _K1, typename _C1, typename _A1> 00466 friend bool 00467 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 00468 }; 00469 00470 template<typename _Key, typename _Compare, typename _Allocator> 00471 inline bool 00472 operator==(const set<_Key, _Compare, _Allocator>& __lhs, 00473 const set<_Key, _Compare, _Allocator>& __rhs) 00474 { 00475 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 00476 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 00477 return __lhs._M_base() == __rhs._M_base(); 00478 } 00479 00480 template<typename _Key, typename _Compare, typename _Allocator> 00481 inline bool 00482 operator<(const set<_Key, _Compare, _Allocator>& __lhs, 00483 const set<_Key, _Compare, _Allocator>& __rhs) 00484 { 00485 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 00486 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 00487 return __lhs._M_base() < __rhs._M_base(); 00488 } 00489 00490 template<typename _Key, typename _Compare, typename _Allocator> 00491 inline bool 00492 operator!=(const set<_Key, _Compare, _Allocator>& __lhs, 00493 const set<_Key, _Compare, _Allocator>& __rhs) 00494 { return !(__lhs == __rhs); } 00495 00496 template<typename _Key, typename _Compare, typename _Allocator> 00497 inline bool 00498 operator<=(const set<_Key, _Compare, _Allocator>& __lhs, 00499 const set<_Key, _Compare, _Allocator>& __rhs) 00500 { return !(__rhs < __lhs); } 00501 00502 template<typename _Key, typename _Compare, typename _Allocator> 00503 inline bool 00504 operator>=(const set<_Key, _Compare, _Allocator>& __lhs, 00505 const set<_Key, _Compare, _Allocator>& __rhs) 00506 { return !(__lhs < __rhs); } 00507 00508 template<typename _Key, typename _Compare, typename _Allocator> 00509 inline bool 00510 operator>(const set<_Key, _Compare, _Allocator>& __lhs, 00511 const set<_Key, _Compare, _Allocator>& __rhs) 00512 { return __rhs < __lhs; } 00513 00514 template<typename _Key, typename _Compare, typename _Allocator> 00515 void 00516 swap(set<_Key, _Compare, _Allocator>& __x, 00517 set<_Key, _Compare, _Allocator>& __y) 00518 { return __x.swap(__y); } 00519 00520 } // namespace __profile 00521 } // namespace std 00522 00523 #endif