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