1// Debugging map implementation -*- C++ -*- 2 3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011 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 37namespace std _GLIBCXX_VISIBILITY(default) 38{ 39namespace __debug 40{ 41 /// Class std::map with safety/checking/debug instrumentation. 42 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 43 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 44 class map 45 : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>, 46 public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> > 47 { 48 typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base; 49 typedef __gnu_debug::_Safe_sequence<map> _Safe_base; 50 51 typedef typename _Base::const_iterator _Base_const_iterator; 52 typedef typename _Base::iterator _Base_iterator; 53 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 54 public: 55 // types: 56 typedef _Key key_type; 57 typedef _Tp mapped_type; 58 typedef std::pair<const _Key, _Tp> value_type; 59 typedef _Compare key_compare; 60 typedef _Allocator allocator_type; 61 typedef typename _Base::reference reference; 62 typedef typename _Base::const_reference const_reference; 63 64 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map> 65 iterator; 66 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map> 67 const_iterator; 68 69 typedef typename _Base::size_type size_type; 70 typedef typename _Base::difference_type difference_type; 71 typedef typename _Base::pointer pointer; 72 typedef typename _Base::const_pointer const_pointer; 73 typedef std::reverse_iterator<iterator> reverse_iterator; 74 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 75 76 // 23.3.1.1 construct/copy/destroy: 77 explicit map(const _Compare& __comp = _Compare(), 78 const _Allocator& __a = _Allocator()) 79 : _Base(__comp, __a) { } 80 81 template<typename _InputIterator> 82 map(_InputIterator __first, _InputIterator __last, 83 const _Compare& __comp = _Compare(), 84 const _Allocator& __a = _Allocator()) 85 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 86 __last)), 87 __gnu_debug::__base(__last), 88 __comp, __a), _Safe_base() { } 89 90 map(const map& __x) 91 : _Base(__x), _Safe_base() { } 92 93 map(const _Base& __x) 94 : _Base(__x), _Safe_base() { } 95 96#ifdef __GXX_EXPERIMENTAL_CXX0X__ 97 map(map&& __x) 98 : _Base(std::move(__x)), _Safe_base() 99 { this->_M_swap(__x); } 100 101 map(initializer_list<value_type> __l, 102 const _Compare& __c = _Compare(), 103 const allocator_type& __a = allocator_type()) 104 : _Base(__l, __c, __a), _Safe_base() { } 105#endif 106 107 ~map() { } 108 109 map& 110 operator=(const map& __x) 111 { 112 *static_cast<_Base*>(this) = __x; 113 this->_M_invalidate_all(); 114 return *this; 115 } 116 117#ifdef __GXX_EXPERIMENTAL_CXX0X__ 118 map& 119 operator=(map&& __x) 120 { 121 // NB: DR 1204. 122 // NB: DR 675. 123 clear(); 124 swap(__x); 125 return *this; 126 } 127 128 map& 129 operator=(initializer_list<value_type> __l) 130 { 131 this->clear(); 132 this->insert(__l); 133 return *this; 134 } 135#endif 136 137 // _GLIBCXX_RESOLVE_LIB_DEFECTS 138 // 133. map missing get_allocator() 139 using _Base::get_allocator; 140 141 // iterators: 142 iterator 143 begin() 144 { return iterator(_Base::begin(), this); } 145 146 const_iterator 147 begin() const 148 { return const_iterator(_Base::begin(), this); } 149 150 iterator 151 end() 152 { return iterator(_Base::end(), this); } 153 154 const_iterator 155 end() const 156 { return const_iterator(_Base::end(), this); } 157 158 reverse_iterator 159 rbegin() 160 { return reverse_iterator(end()); } 161 162 const_reverse_iterator 163 rbegin() const 164 { return const_reverse_iterator(end()); } 165 166 reverse_iterator 167 rend() 168 { return reverse_iterator(begin()); } 169 170 const_reverse_iterator 171 rend() const 172 { return const_reverse_iterator(begin()); } 173 174#ifdef __GXX_EXPERIMENTAL_CXX0X__ 175 const_iterator 176 cbegin() const 177 { return const_iterator(_Base::begin(), this); } 178 179 const_iterator 180 cend() const 181 { return const_iterator(_Base::end(), this); } 182 183 const_reverse_iterator 184 crbegin() const 185 { return const_reverse_iterator(end()); } 186 187 const_reverse_iterator 188 crend() const 189 { return const_reverse_iterator(begin()); } 190#endif 191 192 // capacity: 193 using _Base::empty; 194 using _Base::size; 195 using _Base::max_size; 196 197 // 23.3.1.2 element access: 198 using _Base::operator[]; 199 200 // _GLIBCXX_RESOLVE_LIB_DEFECTS 201 // DR 464. Suggestion for new member functions in standard containers. 202 using _Base::at; 203 204 // modifiers: 205 std::pair<iterator, bool> 206 insert(const value_type& __x) 207 { 208 typedef typename _Base::iterator _Base_iterator; 209 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 210 return std::pair<iterator, bool>(iterator(__res.first, this), 211 __res.second); 212 } 213 214#ifdef __GXX_EXPERIMENTAL_CXX0X__ 215 template<typename _Pair, typename = typename 216 std::enable_if<std::is_convertible<_Pair, 217 value_type>::value>::type> 218 std::pair<iterator, bool> 219 insert(_Pair&& __x) 220 { 221 typedef typename _Base::iterator _Base_iterator; 222 std::pair<_Base_iterator, bool> __res 223 = _Base::insert(std::forward<_Pair>(__x)); 224 return std::pair<iterator, bool>(iterator(__res.first, this), 225 __res.second); 226 } 227#endif 228 229#ifdef __GXX_EXPERIMENTAL_CXX0X__ 230 void 231 insert(std::initializer_list<value_type> __list) 232 { _Base::insert(__list); } 233#endif 234 235 iterator 236#ifdef __GXX_EXPERIMENTAL_CXX0X__ 237 insert(const_iterator __position, const value_type& __x) 238#else 239 insert(iterator __position, const value_type& __x) 240#endif 241 { 242 __glibcxx_check_insert(__position); 243 return iterator(_Base::insert(__position.base(), __x), this); 244 } 245 246#ifdef __GXX_EXPERIMENTAL_CXX0X__ 247 template<typename _Pair, typename = typename 248 std::enable_if<std::is_convertible<_Pair, 249 value_type>::value>::type> 250 iterator 251 insert(const_iterator __position, _Pair&& __x) 252 { 253 __glibcxx_check_insert(__position); 254 return iterator(_Base::insert(__position.base(), 255 std::forward<_Pair>(__x)), this); 256 } 257#endif 258 259 template<typename _InputIterator> 260 void 261 insert(_InputIterator __first, _InputIterator __last) 262 { 263 __glibcxx_check_valid_range(__first, __last); 264 _Base::insert(__gnu_debug::__base(__first), 265 __gnu_debug::__base(__last)); 266 } 267 268#ifdef __GXX_EXPERIMENTAL_CXX0X__ 269 iterator 270 erase(const_iterator __position) 271 { 272 __glibcxx_check_erase(__position); 273 this->_M_invalidate_if(_Equal(__position.base())); 274 return iterator(_Base::erase(__position.base()), this); 275 } 276#else 277 void 278 erase(iterator __position) 279 { 280 __glibcxx_check_erase(__position); 281 this->_M_invalidate_if(_Equal(__position.base())); 282 _Base::erase(__position.base()); 283 } 284#endif 285 286 size_type 287 erase(const key_type& __x) 288 { 289 _Base_iterator __victim = _Base::find(__x); 290 if (__victim == _Base::end()) 291 return 0; 292 else 293 { 294 this->_M_invalidate_if(_Equal(__victim)); 295 _Base::erase(__victim); 296 return 1; 297 } 298 } 299 300#ifdef __GXX_EXPERIMENTAL_CXX0X__ 301 iterator 302 erase(const_iterator __first, const_iterator __last) 303 { 304 // _GLIBCXX_RESOLVE_LIB_DEFECTS 305 // 151. can't currently clear() empty container 306 __glibcxx_check_erase_range(__first, __last); 307 for (_Base_const_iterator __victim = __first.base(); 308 __victim != __last.base(); ++__victim) 309 { 310 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 311 _M_message(__gnu_debug::__msg_valid_range) 312 ._M_iterator(__first, "first") 313 ._M_iterator(__last, "last")); 314 this->_M_invalidate_if(_Equal(__victim)); 315 } 316 return iterator(_Base::erase(__first.base(), __last.base()), this); 317 } 318#else 319 void 320 erase(iterator __first, iterator __last) 321 { 322 // _GLIBCXX_RESOLVE_LIB_DEFECTS 323 // 151. can't currently clear() empty container 324 __glibcxx_check_erase_range(__first, __last); 325 for (_Base_iterator __victim = __first.base(); 326 __victim != __last.base(); ++__victim) 327 { 328 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 329 _M_message(__gnu_debug::__msg_valid_range) 330 ._M_iterator(__first, "first") 331 ._M_iterator(__last, "last")); 332 this->_M_invalidate_if(_Equal(__victim)); 333 } 334 _Base::erase(__first.base(), __last.base()); 335 } 336#endif 337 338 void 339 swap(map& __x) 340 { 341 _Base::swap(__x); 342 this->_M_swap(__x); 343 } 344 345 void 346 clear() 347 { 348 this->_M_invalidate_all(); 349 _Base::clear(); 350 } 351 352 // observers: 353 using _Base::key_comp; 354 using _Base::value_comp; 355 356 // 23.3.1.3 map operations: 357 iterator 358 find(const key_type& __x) 359 { return iterator(_Base::find(__x), this); } 360 361 const_iterator 362 find(const key_type& __x) const 363 { return const_iterator(_Base::find(__x), this); } 364 365 using _Base::count; 366 367 iterator 368 lower_bound(const key_type& __x) 369 { return iterator(_Base::lower_bound(__x), this); } 370 371 const_iterator 372 lower_bound(const key_type& __x) const 373 { return const_iterator(_Base::lower_bound(__x), this); } 374 375 iterator 376 upper_bound(const key_type& __x) 377 { return iterator(_Base::upper_bound(__x), this); } 378 379 const_iterator 380 upper_bound(const key_type& __x) const 381 { return const_iterator(_Base::upper_bound(__x), this); } 382 383 std::pair<iterator,iterator> 384 equal_range(const key_type& __x) 385 { 386 typedef typename _Base::iterator _Base_iterator; 387 std::pair<_Base_iterator, _Base_iterator> __res = 388 _Base::equal_range(__x); 389 return std::make_pair(iterator(__res.first, this), 390 iterator(__res.second, this)); 391 } 392 393 std::pair<const_iterator,const_iterator> 394 equal_range(const key_type& __x) const 395 { 396 typedef typename _Base::const_iterator _Base_const_iterator; 397 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 398 _Base::equal_range(__x); 399 return std::make_pair(const_iterator(__res.first, this), 400 const_iterator(__res.second, this)); 401 } 402 403 _Base& 404 _M_base() { return *this; } 405 406 const _Base& 407 _M_base() const { return *this; } 408 409 private: 410 void 411 _M_invalidate_all() 412 { 413 typedef typename _Base::const_iterator _Base_const_iterator; 414 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 415 this->_M_invalidate_if(_Not_equal(_M_base().end())); 416 } 417 }; 418 419 template<typename _Key, typename _Tp, 420 typename _Compare, typename _Allocator> 421 inline bool 422 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 423 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 424 { return __lhs._M_base() == __rhs._M_base(); } 425 426 template<typename _Key, typename _Tp, 427 typename _Compare, typename _Allocator> 428 inline bool 429 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 430 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 431 { return __lhs._M_base() != __rhs._M_base(); } 432 433 template<typename _Key, typename _Tp, 434 typename _Compare, typename _Allocator> 435 inline bool 436 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 437 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 438 { return __lhs._M_base() < __rhs._M_base(); } 439 440 template<typename _Key, typename _Tp, 441 typename _Compare, typename _Allocator> 442 inline bool 443 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 444 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 445 { return __lhs._M_base() <= __rhs._M_base(); } 446 447 template<typename _Key, typename _Tp, 448 typename _Compare, typename _Allocator> 449 inline bool 450 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 451 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 452 { return __lhs._M_base() >= __rhs._M_base(); } 453 454 template<typename _Key, typename _Tp, 455 typename _Compare, typename _Allocator> 456 inline bool 457 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 458 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 459 { return __lhs._M_base() > __rhs._M_base(); } 460 461 template<typename _Key, typename _Tp, 462 typename _Compare, typename _Allocator> 463 inline void 464 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 465 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 466 { __lhs.swap(__rhs); } 467 468} // namespace __debug 469} // namespace std 470 471#endif 472