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