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