1 // Debugging map implementation -*- C++ -*- 2 3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /** @file debug/map.h 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30 #ifndef _GLIBCXX_DEBUG_MAP_H 31 #define _GLIBCXX_DEBUG_MAP_H 1 32 33 #include <debug/safe_sequence.h> 34 #include <debug/safe_iterator.h> 35 #include <utility> 36 37 namespace std 38 { 39 namespace __debug 40 { 41 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 42 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 43 class map 44 : public _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator>, 45 public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> > 46 { 47 typedef _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator> _Base; 48 typedef __gnu_debug::_Safe_sequence<map> _Safe_base; 49 50 public: 51 // types: 52 typedef _Key key_type; 53 typedef _Tp mapped_type; 54 typedef std::pair<const _Key, _Tp> value_type; 55 typedef _Compare key_compare; 56 typedef _Allocator allocator_type; 57 typedef typename _Base::reference reference; 58 typedef typename _Base::const_reference const_reference; 59 60 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map> 61 iterator; 62 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map> 63 const_iterator; 64 65 typedef typename _Base::size_type size_type; 66 typedef typename _Base::difference_type difference_type; 67 typedef typename _Base::pointer pointer; 68 typedef typename _Base::const_pointer const_pointer; 69 typedef std::reverse_iterator<iterator> reverse_iterator; 70 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 71 72 using _Base::value_compare; 73 74 // 23.3.1.1 construct/copy/destroy: 75 explicit map(const _Compare& __comp = _Compare(), 76 const _Allocator& __a = _Allocator()) 77 : _Base(__comp, __a) { } 78 79 template<typename _InputIterator> 80 map(_InputIterator __first, _InputIterator __last, 81 const _Compare& __comp = _Compare(), 82 const _Allocator& __a = _Allocator()) 83 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, 84 __comp, __a), _Safe_base() { } 85 86 map(const map& __x) 87 : _Base(__x), _Safe_base() { } 88 89 map(const _Base& __x) 90 : _Base(__x), _Safe_base() { } 91 92 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 93 map(map&& __x) 94 : _Base(std::forward<map>(__x)), _Safe_base() 95 { this->_M_swap(__x); } 96 97 map(initializer_list<value_type> __l, 98 const _Compare& __c = _Compare(), 99 const allocator_type& __a = allocator_type()) 100 : _Base(__l, __c, __a), _Safe_base() { } 101 #endif 102 103 ~map() { } 104 105 map& 106 operator=(const map& __x) 107 { 108 *static_cast<_Base*>(this) = __x; 109 this->_M_invalidate_all(); 110 return *this; 111 } 112 113 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 114 map& 115 operator=(map&& __x) 116 { 117 // NB: DR 675. 118 clear(); 119 swap(__x); 120 return *this; 121 } 122 123 map& 124 operator=(initializer_list<value_type> __l) 125 { 126 this->clear(); 127 this->insert(__l); 128 return *this; 129 } 130 #endif 131 132 // _GLIBCXX_RESOLVE_LIB_DEFECTS 133 // 133. map missing get_allocator() 134 using _Base::get_allocator; 135 136 // iterators: 137 iterator 138 begin() 139 { return iterator(_Base::begin(), this); } 140 141 const_iterator 142 begin() const 143 { return const_iterator(_Base::begin(), this); } 144 145 iterator 146 end() 147 { return iterator(_Base::end(), this); } 148 149 const_iterator 150 end() const 151 { return const_iterator(_Base::end(), this); } 152 153 reverse_iterator 154 rbegin() 155 { return reverse_iterator(end()); } 156 157 const_reverse_iterator 158 rbegin() const 159 { return const_reverse_iterator(end()); } 160 161 reverse_iterator 162 rend() 163 { return reverse_iterator(begin()); } 164 165 const_reverse_iterator 166 rend() const 167 { return const_reverse_iterator(begin()); } 168 169 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 170 const_iterator 171 cbegin() const 172 { return const_iterator(_Base::begin(), this); } 173 174 const_iterator 175 cend() const 176 { return const_iterator(_Base::end(), this); } 177 178 const_reverse_iterator 179 crbegin() const 180 { return const_reverse_iterator(end()); } 181 182 const_reverse_iterator 183 crend() const 184 { return const_reverse_iterator(begin()); } 185 #endif 186 187 // capacity: 188 using _Base::empty; 189 using _Base::size; 190 using _Base::max_size; 191 192 // 23.3.1.2 element access: 193 using _Base::operator[]; 194 195 // _GLIBCXX_RESOLVE_LIB_DEFECTS 196 // DR 464. Suggestion for new member functions in standard containers. 197 using _Base::at; 198 199 // modifiers: 200 std::pair<iterator, bool> 201 insert(const value_type& __x) 202 { 203 typedef typename _Base::iterator _Base_iterator; 204 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 205 return std::pair<iterator, bool>(iterator(__res.first, this), 206 __res.second); 207 } 208 209 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 210 void 211 insert(std::initializer_list<value_type> __list) 212 { _Base::insert(__list); } 213 #endif 214 215 iterator 216 insert(iterator __position, const value_type& __x) 217 { 218 __glibcxx_check_insert(__position); 219 return iterator(_Base::insert(__position.base(), __x), this); 220 } 221 222 template<typename _InputIterator> 223 void 224 insert(_InputIterator __first, _InputIterator __last) 225 { 226 __glibcxx_check_valid_range(__first, __last); 227 _Base::insert(__first, __last); 228 } 229 230 void 231 erase(iterator __position) 232 { 233 __glibcxx_check_erase(__position); 234 __position._M_invalidate(); 235 _Base::erase(__position.base()); 236 } 237 238 size_type 239 erase(const key_type& __x) 240 { 241 iterator __victim = find(__x); 242 if (__victim == end()) 243 return 0; 244 else 245 { 246 __victim._M_invalidate(); 247 _Base::erase(__victim.base()); 248 return 1; 249 } 250 } 251 252 void 253 erase(iterator __first, iterator __last) 254 { 255 // _GLIBCXX_RESOLVE_LIB_DEFECTS 256 // 151. can't currently clear() empty container 257 __glibcxx_check_erase_range(__first, __last); 258 while (__first != __last) 259 this->erase(__first++); 260 } 261 262 void 263 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 264 swap(map&& __x) 265 #else 266 swap(map& __x) 267 #endif 268 { 269 _Base::swap(__x); 270 this->_M_swap(__x); 271 } 272 273 void 274 clear() 275 { this->erase(begin(), end()); } 276 277 // observers: 278 using _Base::key_comp; 279 using _Base::value_comp; 280 281 // 23.3.1.3 map operations: 282 iterator 283 find(const key_type& __x) 284 { return iterator(_Base::find(__x), this); } 285 286 const_iterator 287 find(const key_type& __x) const 288 { return const_iterator(_Base::find(__x), this); } 289 290 using _Base::count; 291 292 iterator 293 lower_bound(const key_type& __x) 294 { return iterator(_Base::lower_bound(__x), this); } 295 296 const_iterator 297 lower_bound(const key_type& __x) const 298 { return const_iterator(_Base::lower_bound(__x), this); } 299 300 iterator 301 upper_bound(const key_type& __x) 302 { return iterator(_Base::upper_bound(__x), this); } 303 304 const_iterator 305 upper_bound(const key_type& __x) const 306 { return const_iterator(_Base::upper_bound(__x), this); } 307 308 std::pair<iterator,iterator> 309 equal_range(const key_type& __x) 310 { 311 typedef typename _Base::iterator _Base_iterator; 312 std::pair<_Base_iterator, _Base_iterator> __res = 313 _Base::equal_range(__x); 314 return std::make_pair(iterator(__res.first, this), 315 iterator(__res.second, this)); 316 } 317 318 std::pair<const_iterator,const_iterator> 319 equal_range(const key_type& __x) const 320 { 321 typedef typename _Base::const_iterator _Base_const_iterator; 322 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 323 _Base::equal_range(__x); 324 return std::make_pair(const_iterator(__res.first, this), 325 const_iterator(__res.second, this)); 326 } 327 328 _Base& 329 _M_base() { return *this; } 330 331 const _Base& 332 _M_base() const { return *this; } 333 334 private: 335 void 336 _M_invalidate_all() 337 { 338 typedef typename _Base::const_iterator _Base_const_iterator; 339 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 340 this->_M_invalidate_if(_Not_equal(_M_base().end())); 341 } 342 }; 343 344 template<typename _Key, typename _Tp, 345 typename _Compare, typename _Allocator> 346 inline bool 347 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 348 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 349 { return __lhs._M_base() == __rhs._M_base(); } 350 351 template<typename _Key, typename _Tp, 352 typename _Compare, typename _Allocator> 353 inline bool 354 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 355 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 356 { return __lhs._M_base() != __rhs._M_base(); } 357 358 template<typename _Key, typename _Tp, 359 typename _Compare, typename _Allocator> 360 inline bool 361 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 362 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 363 { return __lhs._M_base() < __rhs._M_base(); } 364 365 template<typename _Key, typename _Tp, 366 typename _Compare, typename _Allocator> 367 inline bool 368 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 369 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 370 { return __lhs._M_base() <= __rhs._M_base(); } 371 372 template<typename _Key, typename _Tp, 373 typename _Compare, typename _Allocator> 374 inline bool 375 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 376 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 377 { return __lhs._M_base() >= __rhs._M_base(); } 378 379 template<typename _Key, typename _Tp, 380 typename _Compare, typename _Allocator> 381 inline bool 382 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 383 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 384 { return __lhs._M_base() > __rhs._M_base(); } 385 386 template<typename _Key, typename _Tp, 387 typename _Compare, typename _Allocator> 388 inline void 389 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 390 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 391 { __lhs.swap(__rhs); } 392 393 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 394 template<typename _Key, typename _Tp, 395 typename _Compare, typename _Allocator> 396 inline void 397 swap(map<_Key, _Tp, _Compare, _Allocator>&& __lhs, 398 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 399 { __lhs.swap(__rhs); } 400 401 template<typename _Key, typename _Tp, 402 typename _Compare, typename _Allocator> 403 inline void 404 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 405 map<_Key, _Tp, _Compare, _Allocator>&& __rhs) 406 { __lhs.swap(__rhs); } 407 #endif 408 409 } // namespace __debug 410 } // namespace std 411 412 #endif 413
