libstdc++
|
00001 // Debugging map implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /** @file debug/map.h 00027 * This file is a GNU debug extension to the Standard C++ Library. 00028 */ 00029 00030 #ifndef _GLIBCXX_DEBUG_MAP_H 00031 #define _GLIBCXX_DEBUG_MAP_H 1 00032 00033 #include <debug/safe_sequence.h> 00034 #include <debug/safe_iterator.h> 00035 #include <utility> 00036 00037 namespace std 00038 { 00039 namespace __debug 00040 { 00041 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 00042 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 00043 class map 00044 : public _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator>, 00045 public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> > 00046 { 00047 typedef _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator> _Base; 00048 typedef __gnu_debug::_Safe_sequence<map> _Safe_base; 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 __gnu_debug::_Safe_iterator<typename _Base::iterator, map> 00061 iterator; 00062 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map> 00063 const_iterator; 00064 00065 typedef typename _Base::size_type size_type; 00066 typedef typename _Base::difference_type difference_type; 00067 typedef typename _Base::pointer pointer; 00068 typedef typename _Base::const_pointer const_pointer; 00069 typedef std::reverse_iterator<iterator> reverse_iterator; 00070 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00071 00072 using _Base::value_compare; 00073 00074 // 23.3.1.1 construct/copy/destroy: 00075 explicit map(const _Compare& __comp = _Compare(), 00076 const _Allocator& __a = _Allocator()) 00077 : _Base(__comp, __a) { } 00078 00079 template<typename _InputIterator> 00080 map(_InputIterator __first, _InputIterator __last, 00081 const _Compare& __comp = _Compare(), 00082 const _Allocator& __a = _Allocator()) 00083 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, 00084 __comp, __a), _Safe_base() { } 00085 00086 map(const map& __x) 00087 : _Base(__x), _Safe_base() { } 00088 00089 map(const _Base& __x) 00090 : _Base(__x), _Safe_base() { } 00091 00092 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00093 map(map&& __x) 00094 : _Base(std::forward<map>(__x)), _Safe_base() 00095 { this->_M_swap(__x); } 00096 00097 map(initializer_list<value_type> __l, 00098 const _Compare& __c = _Compare(), 00099 const allocator_type& __a = allocator_type()) 00100 : _Base(__l, __c, __a), _Safe_base() { } 00101 #endif 00102 00103 ~map() { } 00104 00105 map& 00106 operator=(const map& __x) 00107 { 00108 *static_cast<_Base*>(this) = __x; 00109 this->_M_invalidate_all(); 00110 return *this; 00111 } 00112 00113 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00114 map& 00115 operator=(map&& __x) 00116 { 00117 // NB: DR 675. 00118 clear(); 00119 swap(__x); 00120 return *this; 00121 } 00122 00123 map& 00124 operator=(initializer_list<value_type> __l) 00125 { 00126 this->clear(); 00127 this->insert(__l); 00128 return *this; 00129 } 00130 #endif 00131 00132 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00133 // 133. map missing get_allocator() 00134 using _Base::get_allocator; 00135 00136 // iterators: 00137 iterator 00138 begin() 00139 { return iterator(_Base::begin(), this); } 00140 00141 const_iterator 00142 begin() const 00143 { return const_iterator(_Base::begin(), this); } 00144 00145 iterator 00146 end() 00147 { return iterator(_Base::end(), this); } 00148 00149 const_iterator 00150 end() const 00151 { return const_iterator(_Base::end(), this); } 00152 00153 reverse_iterator 00154 rbegin() 00155 { return reverse_iterator(end()); } 00156 00157 const_reverse_iterator 00158 rbegin() const 00159 { return const_reverse_iterator(end()); } 00160 00161 reverse_iterator 00162 rend() 00163 { return reverse_iterator(begin()); } 00164 00165 const_reverse_iterator 00166 rend() const 00167 { return const_reverse_iterator(begin()); } 00168 00169 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00170 const_iterator 00171 cbegin() const 00172 { return const_iterator(_Base::begin(), this); } 00173 00174 const_iterator 00175 cend() const 00176 { return const_iterator(_Base::end(), this); } 00177 00178 const_reverse_iterator 00179 crbegin() const 00180 { return const_reverse_iterator(end()); } 00181 00182 const_reverse_iterator 00183 crend() const 00184 { return const_reverse_iterator(begin()); } 00185 #endif 00186 00187 // capacity: 00188 using _Base::empty; 00189 using _Base::size; 00190 using _Base::max_size; 00191 00192 // 23.3.1.2 element access: 00193 using _Base::operator[]; 00194 00195 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00196 // DR 464. Suggestion for new member functions in standard containers. 00197 using _Base::at; 00198 00199 // modifiers: 00200 std::pair<iterator, bool> 00201 insert(const value_type& __x) 00202 { 00203 typedef typename _Base::iterator _Base_iterator; 00204 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 00205 return std::pair<iterator, bool>(iterator(__res.first, this), 00206 __res.second); 00207 } 00208 00209 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00210 void 00211 insert(std::initializer_list<value_type> __list) 00212 { _Base::insert(__list); } 00213 #endif 00214 00215 iterator 00216 insert(iterator __position, const value_type& __x) 00217 { 00218 __glibcxx_check_insert(__position); 00219 return iterator(_Base::insert(__position.base(), __x), this); 00220 } 00221 00222 template<typename _InputIterator> 00223 void 00224 insert(_InputIterator __first, _InputIterator __last) 00225 { 00226 __glibcxx_check_valid_range(__first, __last); 00227 _Base::insert(__first, __last); 00228 } 00229 00230 void 00231 erase(iterator __position) 00232 { 00233 __glibcxx_check_erase(__position); 00234 __position._M_invalidate(); 00235 _Base::erase(__position.base()); 00236 } 00237 00238 size_type 00239 erase(const key_type& __x) 00240 { 00241 iterator __victim = find(__x); 00242 if (__victim == end()) 00243 return 0; 00244 else 00245 { 00246 __victim._M_invalidate(); 00247 _Base::erase(__victim.base()); 00248 return 1; 00249 } 00250 } 00251 00252 void 00253 erase(iterator __first, iterator __last) 00254 { 00255 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00256 // 151. can't currently clear() empty container 00257 __glibcxx_check_erase_range(__first, __last); 00258 while (__first != __last) 00259 this->erase(__first++); 00260 } 00261 00262 void 00263 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00264 swap(map&& __x) 00265 #else 00266 swap(map& __x) 00267 #endif 00268 { 00269 _Base::swap(__x); 00270 this->_M_swap(__x); 00271 } 00272 00273 void 00274 clear() 00275 { this->erase(begin(), end()); } 00276 00277 // observers: 00278 using _Base::key_comp; 00279 using _Base::value_comp; 00280 00281 // 23.3.1.3 map operations: 00282 iterator 00283 find(const key_type& __x) 00284 { return iterator(_Base::find(__x), this); } 00285 00286 const_iterator 00287 find(const key_type& __x) const 00288 { return const_iterator(_Base::find(__x), this); } 00289 00290 using _Base::count; 00291 00292 iterator 00293 lower_bound(const key_type& __x) 00294 { return iterator(_Base::lower_bound(__x), this); } 00295 00296 const_iterator 00297 lower_bound(const key_type& __x) const 00298 { return const_iterator(_Base::lower_bound(__x), this); } 00299 00300 iterator 00301 upper_bound(const key_type& __x) 00302 { return iterator(_Base::upper_bound(__x), this); } 00303 00304 const_iterator 00305 upper_bound(const key_type& __x) const 00306 { return const_iterator(_Base::upper_bound(__x), this); } 00307 00308 std::pair<iterator,iterator> 00309 equal_range(const key_type& __x) 00310 { 00311 typedef typename _Base::iterator _Base_iterator; 00312 std::pair<_Base_iterator, _Base_iterator> __res = 00313 _Base::equal_range(__x); 00314 return std::make_pair(iterator(__res.first, this), 00315 iterator(__res.second, this)); 00316 } 00317 00318 std::pair<const_iterator,const_iterator> 00319 equal_range(const key_type& __x) const 00320 { 00321 typedef typename _Base::const_iterator _Base_const_iterator; 00322 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00323 _Base::equal_range(__x); 00324 return std::make_pair(const_iterator(__res.first, this), 00325 const_iterator(__res.second, this)); 00326 } 00327 00328 _Base& 00329 _M_base() { return *this; } 00330 00331 const _Base& 00332 _M_base() const { return *this; } 00333 00334 private: 00335 void 00336 _M_invalidate_all() 00337 { 00338 typedef typename _Base::const_iterator _Base_const_iterator; 00339 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00340 this->_M_invalidate_if(_Not_equal(_M_base().end())); 00341 } 00342 }; 00343 00344 template<typename _Key, typename _Tp, 00345 typename _Compare, typename _Allocator> 00346 inline bool 00347 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 00348 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 00349 { return __lhs._M_base() == __rhs._M_base(); } 00350 00351 template<typename _Key, typename _Tp, 00352 typename _Compare, typename _Allocator> 00353 inline bool 00354 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 00355 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 00356 { return __lhs._M_base() != __rhs._M_base(); } 00357 00358 template<typename _Key, typename _Tp, 00359 typename _Compare, typename _Allocator> 00360 inline bool 00361 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 00362 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 00363 { return __lhs._M_base() < __rhs._M_base(); } 00364 00365 template<typename _Key, typename _Tp, 00366 typename _Compare, typename _Allocator> 00367 inline bool 00368 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 00369 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 00370 { return __lhs._M_base() <= __rhs._M_base(); } 00371 00372 template<typename _Key, typename _Tp, 00373 typename _Compare, typename _Allocator> 00374 inline bool 00375 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 00376 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 00377 { return __lhs._M_base() >= __rhs._M_base(); } 00378 00379 template<typename _Key, typename _Tp, 00380 typename _Compare, typename _Allocator> 00381 inline bool 00382 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 00383 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 00384 { return __lhs._M_base() > __rhs._M_base(); } 00385 00386 template<typename _Key, typename _Tp, 00387 typename _Compare, typename _Allocator> 00388 inline void 00389 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 00390 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 00391 { __lhs.swap(__rhs); } 00392 00393 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00394 template<typename _Key, typename _Tp, 00395 typename _Compare, typename _Allocator> 00396 inline void 00397 swap(map<_Key, _Tp, _Compare, _Allocator>&& __lhs, 00398 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 00399 { __lhs.swap(__rhs); } 00400 00401 template<typename _Key, typename _Tp, 00402 typename _Compare, typename _Allocator> 00403 inline void 00404 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 00405 map<_Key, _Tp, _Compare, _Allocator>&& __rhs) 00406 { __lhs.swap(__rhs); } 00407 #endif 00408 00409 } // namespace __debug 00410 } // namespace std 00411 00412 #endif