1 // Debugging map implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004, 2005 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 2, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // You should have received a copy of the GNU General Public License along 18 // with this library; see the file COPYING. If not, write to the Free 19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20 // USA. 21 22 // As a special exception, you may use this file as part of a free software 23 // library without restriction. Specifically, if other files instantiate 24 // templates or use macros or inline functions from this file, or you compile 25 // this file and link it with other files to produce an executable, this 26 // file does not by itself cause the resulting executable to be covered by 27 // the GNU General Public License. This exception does not however 28 // invalidate any other reasons why the executable file might be covered by 29 // the GNU General Public License. 30 31 /** @file debug/map.h 32 * This file is a GNU debug extension to the Standard C++ Library. 33 */ 34 35 #ifndef _GLIBCXX_DEBUG_MAP_H 36 #define _GLIBCXX_DEBUG_MAP_H 1 37 38 #include <debug/safe_sequence.h> 39 #include <debug/safe_iterator.h> 40 #include <utility> 41 42 namespace std 43 { 44 namespace __debug 45 { 46 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 47 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 48 class map 49 : public _GLIBCXX_STD::map<_Key, _Tp, _Compare, _Allocator>, 50 public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> > 51 { 52 typedef _GLIBCXX_STD::map<_Key, _Tp, _Compare, _Allocator> _Base; 53 typedef __gnu_debug::_Safe_sequence<map> _Safe_base; 54 55 public: 56 // types: 57 typedef _Key key_type; 58 typedef _Tp mapped_type; 59 typedef std::pair<const _Key, _Tp> value_type; 60 typedef _Compare key_compare; 61 typedef _Allocator allocator_type; 62 typedef typename _Base::reference reference; 63 typedef typename _Base::const_reference const_reference; 64 65 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map> 66 iterator; 67 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map> 68 const_iterator; 69 70 typedef typename _Base::size_type size_type; 71 typedef typename _Base::difference_type difference_type; 72 typedef typename _Base::pointer pointer; 73 typedef typename _Base::const_pointer const_pointer; 74 typedef std::reverse_iterator<iterator> reverse_iterator; 75 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 76 77 using _Base::value_compare; 78 79 // 23.3.1.1 construct/copy/destroy: 80 explicit map(const _Compare& __comp = _Compare(), 81 const _Allocator& __a = _Allocator()) _Base(__comp,__a)82 : _Base(__comp, __a) { } 83 84 template<typename _InputIterator> 85 map(_InputIterator __first, _InputIterator __last, 86 const _Compare& __comp = _Compare(), 87 const _Allocator& __a = _Allocator()) _Base(__gnu_debug::__check_valid_range (__first,__last),__last,__comp,__a)88 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, 89 __comp, __a), _Safe_base() { } 90 map(const map<_Key,_Tp,_Compare,_Allocator> & __x)91 map(const map<_Key,_Tp,_Compare,_Allocator>& __x) 92 : _Base(__x), _Safe_base() { } 93 map(const _Base & __x)94 map(const _Base& __x) : _Base(__x), _Safe_base() { } 95 ~map()96 ~map() { } 97 98 map<_Key,_Tp,_Compare,_Allocator>& 99 operator=(const map<_Key,_Tp,_Compare,_Allocator>& __x) 100 { 101 *static_cast<_Base*>(this) = __x; 102 this->_M_invalidate_all(); 103 return *this; 104 } 105 106 // _GLIBCXX_RESOLVE_LIB_DEFECTS 107 // 133. map missing get_allocator() 108 using _Base::get_allocator; 109 110 // iterators: 111 iterator begin()112 begin() 113 { return iterator(_Base::begin(), this); } 114 115 const_iterator begin()116 begin() const 117 { return const_iterator(_Base::begin(), this); } 118 119 iterator end()120 end() 121 { return iterator(_Base::end(), this); } 122 123 const_iterator end()124 end() const 125 { return const_iterator(_Base::end(), this); } 126 127 reverse_iterator rbegin()128 rbegin() 129 { return reverse_iterator(end()); } 130 131 const_reverse_iterator rbegin()132 rbegin() const 133 { return const_reverse_iterator(end()); } 134 135 reverse_iterator rend()136 rend() 137 { return reverse_iterator(begin()); } 138 139 const_reverse_iterator rend()140 rend() const 141 { return const_reverse_iterator(begin()); } 142 143 // capacity: 144 using _Base::empty; 145 using _Base::size; 146 using _Base::max_size; 147 148 // 23.3.1.2 element access: 149 using _Base::operator[]; 150 151 // _GLIBCXX_RESOLVE_LIB_DEFECTS 152 // DR 464. Suggestion for new member functions in standard containers. 153 using _Base::at; 154 155 // modifiers: 156 std::pair<iterator, bool> insert(const value_type & __x)157 insert(const value_type& __x) 158 { 159 typedef typename _Base::iterator _Base_iterator; 160 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 161 return std::pair<iterator, bool>(iterator(__res.first, this), 162 __res.second); 163 } 164 165 iterator insert(iterator __position,const value_type & __x)166 insert(iterator __position, const value_type& __x) 167 { 168 __glibcxx_check_insert(__position); 169 return iterator(_Base::insert(__position.base(), __x), this); 170 } 171 172 template<typename _InputIterator> 173 void insert(_InputIterator __first,_InputIterator __last)174 insert(_InputIterator __first, _InputIterator __last) 175 { 176 __glibcxx_check_valid_range(__first, __last); 177 _Base::insert(__first, __last); 178 } 179 180 void erase(iterator __position)181 erase(iterator __position) 182 { 183 __glibcxx_check_erase(__position); 184 __position._M_invalidate(); 185 _Base::erase(__position.base()); 186 } 187 188 size_type erase(const key_type & __x)189 erase(const key_type& __x) 190 { 191 iterator __victim = find(__x); 192 if (__victim == end()) 193 return 0; 194 else 195 { 196 __victim._M_invalidate(); 197 _Base::erase(__victim.base()); 198 return 1; 199 } 200 } 201 202 void erase(iterator __first,iterator __last)203 erase(iterator __first, iterator __last) 204 { 205 // _GLIBCXX_RESOLVE_LIB_DEFECTS 206 // 151. can't currently clear() empty container 207 __glibcxx_check_erase_range(__first, __last); 208 while (__first != __last) 209 this->erase(__first++); 210 } 211 212 void swap(map<_Key,_Tp,_Compare,_Allocator> & __x)213 swap(map<_Key,_Tp,_Compare,_Allocator>& __x) 214 { 215 _Base::swap(__x); 216 this->_M_swap(__x); 217 } 218 219 void clear()220 clear() 221 { this->erase(begin(), end()); } 222 223 // observers: 224 using _Base::key_comp; 225 using _Base::value_comp; 226 227 // 23.3.1.3 map operations: 228 iterator find(const key_type & __x)229 find(const key_type& __x) 230 { return iterator(_Base::find(__x), this); } 231 232 const_iterator find(const key_type & __x)233 find(const key_type& __x) const 234 { return const_iterator(_Base::find(__x), this); } 235 236 using _Base::count; 237 238 iterator lower_bound(const key_type & __x)239 lower_bound(const key_type& __x) 240 { return iterator(_Base::lower_bound(__x), this); } 241 242 const_iterator lower_bound(const key_type & __x)243 lower_bound(const key_type& __x) const 244 { return const_iterator(_Base::lower_bound(__x), this); } 245 246 iterator upper_bound(const key_type & __x)247 upper_bound(const key_type& __x) 248 { return iterator(_Base::upper_bound(__x), this); } 249 250 const_iterator upper_bound(const key_type & __x)251 upper_bound(const key_type& __x) const 252 { return const_iterator(_Base::upper_bound(__x), this); } 253 254 std::pair<iterator,iterator> equal_range(const key_type & __x)255 equal_range(const key_type& __x) 256 { 257 typedef typename _Base::iterator _Base_iterator; 258 std::pair<_Base_iterator, _Base_iterator> __res = 259 _Base::equal_range(__x); 260 return std::make_pair(iterator(__res.first, this), 261 iterator(__res.second, this)); 262 } 263 264 std::pair<const_iterator,const_iterator> equal_range(const key_type & __x)265 equal_range(const key_type& __x) const 266 { 267 typedef typename _Base::const_iterator _Base_const_iterator; 268 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 269 _Base::equal_range(__x); 270 return std::make_pair(const_iterator(__res.first, this), 271 const_iterator(__res.second, this)); 272 } 273 274 _Base& _M_base()275 _M_base() { return *this; } 276 277 const _Base& _M_base()278 _M_base() const { return *this; } 279 280 private: 281 void _M_invalidate_all()282 _M_invalidate_all() 283 { 284 typedef typename _Base::const_iterator _Base_const_iterator; 285 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 286 this->_M_invalidate_if(_Not_equal(_M_base().end())); 287 } 288 }; 289 290 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 291 inline bool 292 operator==(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 293 const map<_Key,_Tp,_Compare,_Allocator>& __rhs) 294 { return __lhs._M_base() == __rhs._M_base(); } 295 296 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 297 inline bool 298 operator!=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 299 const map<_Key,_Tp,_Compare,_Allocator>& __rhs) 300 { return __lhs._M_base() != __rhs._M_base(); } 301 302 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 303 inline bool 304 operator<(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 305 const map<_Key,_Tp,_Compare,_Allocator>& __rhs) 306 { return __lhs._M_base() < __rhs._M_base(); } 307 308 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 309 inline bool 310 operator<=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 311 const map<_Key,_Tp,_Compare,_Allocator>& __rhs) 312 { return __lhs._M_base() <= __rhs._M_base(); } 313 314 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 315 inline bool 316 operator>=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 317 const map<_Key,_Tp,_Compare,_Allocator>& __rhs) 318 { return __lhs._M_base() >= __rhs._M_base(); } 319 320 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 321 inline bool 322 operator>(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 323 const map<_Key,_Tp,_Compare,_Allocator>& __rhs) 324 { return __lhs._M_base() > __rhs._M_base(); } 325 326 template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 327 inline void swap(map<_Key,_Tp,_Compare,_Allocator> & __lhs,map<_Key,_Tp,_Compare,_Allocator> & __rhs)328 swap(map<_Key,_Tp,_Compare,_Allocator>& __lhs, 329 map<_Key,_Tp,_Compare,_Allocator>& __rhs) 330 { __lhs.swap(__rhs); } 331 } // namespace __debug 332 } // namespace std 333 334 #endif 335