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