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