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