1 // Debugging multimap implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2014 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file debug/multimap.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_MULTIMAP_H 30 #define _GLIBCXX_DEBUG_MULTIMAP_H 1 31 32 #include <debug/safe_sequence.h> 33 #include <debug/safe_iterator.h> 34 #include <utility> 35 36 namespace std _GLIBCXX_VISIBILITY(default) 37 { 38 namespace __debug 39 { 40 /// Class std::multimap with safety/checking/debug instrumentation. 41 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 42 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 43 class multimap 44 : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>, 45 public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp, 46 _Compare, _Allocator> > 47 { 48 typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base; 49 50 typedef typename _Base::const_iterator _Base_const_iterator; 51 typedef typename _Base::iterator _Base_iterator; 52 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 53 54 #if __cplusplus >= 201103L 55 typedef __gnu_cxx::__alloc_traits<typename 56 _Base::allocator_type> _Alloc_traits; 57 #endif 58 public: 59 // types: 60 typedef _Key key_type; 61 typedef _Tp mapped_type; 62 typedef std::pair<const _Key, _Tp> value_type; 63 typedef _Compare key_compare; 64 typedef _Allocator allocator_type; 65 typedef typename _Base::reference reference; 66 typedef typename _Base::const_reference const_reference; 67 68 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap> 69 iterator; 70 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 71 multimap> const_iterator; 72 73 typedef typename _Base::size_type size_type; 74 typedef typename _Base::difference_type difference_type; 75 typedef typename _Base::pointer pointer; 76 typedef typename _Base::const_pointer const_pointer; 77 typedef std::reverse_iterator<iterator> reverse_iterator; 78 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 79 80 // 23.3.1.1 construct/copy/destroy: 81 82 multimap() : _Base() { } 83 84 explicit multimap(const _Compare& __comp, 85 const _Allocator& __a = _Allocator()) 86 : _Base(__comp, __a) { } 87 88 template<typename _InputIterator> 89 multimap(_InputIterator __first, _InputIterator __last, 90 const _Compare& __comp = _Compare(), 91 const _Allocator& __a = _Allocator()) 92 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 93 __last)), 94 __gnu_debug::__base(__last), 95 __comp, __a) { } 96 97 multimap(const multimap& __x) 98 : _Base(__x) { } 99 100 multimap(const _Base& __x) 101 : _Base(__x) { } 102 103 #if __cplusplus >= 201103L 104 multimap(multimap&& __x) 105 noexcept(is_nothrow_copy_constructible<_Compare>::value) 106 : _Base(std::move(__x)) 107 { this->_M_swap(__x); } 108 109 multimap(initializer_list<value_type> __l, 110 const _Compare& __c = _Compare(), 111 const allocator_type& __a = allocator_type()) 112 : _Base(__l, __c, __a) { } 113 114 explicit 115 multimap(const allocator_type& __a) 116 : _Base(__a) { } 117 118 multimap(const multimap& __m, const allocator_type& __a) 119 : _Base(__m, __a) { } 120 121 multimap(multimap&& __m, const allocator_type& __a) 122 : _Base(std::move(__m._M_base()), __a) { } 123 124 multimap(initializer_list<value_type> __l, const allocator_type& __a) 125 : _Base(__l, __a) 126 { } 127 128 template<typename _InputIterator> 129 multimap(_InputIterator __first, _InputIterator __last, 130 const allocator_type& __a) 131 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 132 __last)), 133 __gnu_debug::__base(__last), __a) 134 { } 135 #endif 136 137 ~multimap() _GLIBCXX_NOEXCEPT { } 138 139 multimap& 140 operator=(const multimap& __x) 141 { 142 _M_base() = __x; 143 this->_M_invalidate_all(); 144 return *this; 145 } 146 147 #if __cplusplus >= 201103L 148 multimap& 149 operator=(multimap&& __x) 150 noexcept(_Alloc_traits::_S_nothrow_move()) 151 { 152 __glibcxx_check_self_move_assign(__x); 153 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 154 || __x.get_allocator() == this->get_allocator(); 155 _M_base() = std::move(__x._M_base()); 156 if (__xfer_memory) 157 this->_M_swap(__x); 158 else 159 this->_M_invalidate_all(); 160 __x._M_invalidate_all(); 161 return *this; 162 } 163 164 multimap& 165 operator=(initializer_list<value_type> __l) 166 { 167 _M_base() = __l; 168 this->_M_invalidate_all(); 169 return *this; 170 } 171 #endif 172 173 using _Base::get_allocator; 174 175 // iterators: 176 iterator 177 begin() _GLIBCXX_NOEXCEPT 178 { return iterator(_Base::begin(), this); } 179 180 const_iterator 181 begin() const _GLIBCXX_NOEXCEPT 182 { return const_iterator(_Base::begin(), this); } 183 184 iterator 185 end() _GLIBCXX_NOEXCEPT 186 { return iterator(_Base::end(), this); } 187 188 const_iterator 189 end() const _GLIBCXX_NOEXCEPT 190 { return const_iterator(_Base::end(), this); } 191 192 reverse_iterator 193 rbegin() _GLIBCXX_NOEXCEPT 194 { return reverse_iterator(end()); } 195 196 const_reverse_iterator 197 rbegin() const _GLIBCXX_NOEXCEPT 198 { return const_reverse_iterator(end()); } 199 200 reverse_iterator 201 rend() _GLIBCXX_NOEXCEPT 202 { return reverse_iterator(begin()); } 203 204 const_reverse_iterator 205 rend() const _GLIBCXX_NOEXCEPT 206 { return const_reverse_iterator(begin()); } 207 208 #if __cplusplus >= 201103L 209 const_iterator 210 cbegin() const noexcept 211 { return const_iterator(_Base::begin(), this); } 212 213 const_iterator 214 cend() const noexcept 215 { return const_iterator(_Base::end(), this); } 216 217 const_reverse_iterator 218 crbegin() const noexcept 219 { return const_reverse_iterator(end()); } 220 221 const_reverse_iterator 222 crend() const noexcept 223 { return const_reverse_iterator(begin()); } 224 #endif 225 226 // capacity: 227 using _Base::empty; 228 using _Base::size; 229 using _Base::max_size; 230 231 // modifiers: 232 #if __cplusplus >= 201103L 233 template<typename... _Args> 234 iterator 235 emplace(_Args&&... __args) 236 { 237 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); 238 } 239 240 template<typename... _Args> 241 iterator 242 emplace_hint(const_iterator __pos, _Args&&... __args) 243 { 244 __glibcxx_check_insert(__pos); 245 return iterator(_Base::emplace_hint(__pos.base(), 246 std::forward<_Args>(__args)...), 247 this); 248 } 249 #endif 250 251 iterator 252 insert(const value_type& __x) 253 { return iterator(_Base::insert(__x), this); } 254 255 #if __cplusplus >= 201103L 256 template<typename _Pair, typename = typename 257 std::enable_if<std::is_constructible<value_type, 258 _Pair&&>::value>::type> 259 iterator 260 insert(_Pair&& __x) 261 { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); } 262 #endif 263 264 #if __cplusplus >= 201103L 265 void 266 insert(std::initializer_list<value_type> __list) 267 { _Base::insert(__list); } 268 #endif 269 270 iterator 271 #if __cplusplus >= 201103L 272 insert(const_iterator __position, const value_type& __x) 273 #else 274 insert(iterator __position, const value_type& __x) 275 #endif 276 { 277 __glibcxx_check_insert(__position); 278 return iterator(_Base::insert(__position.base(), __x), this); 279 } 280 281 #if __cplusplus >= 201103L 282 template<typename _Pair, typename = typename 283 std::enable_if<std::is_constructible<value_type, 284 _Pair&&>::value>::type> 285 iterator 286 insert(const_iterator __position, _Pair&& __x) 287 { 288 __glibcxx_check_insert(__position); 289 return iterator(_Base::insert(__position.base(), 290 std::forward<_Pair>(__x)), this); 291 } 292 #endif 293 294 template<typename _InputIterator> 295 void 296 insert(_InputIterator __first, _InputIterator __last) 297 { 298 __glibcxx_check_valid_range(__first, __last); 299 _Base::insert(__gnu_debug::__base(__first), 300 __gnu_debug::__base(__last)); 301 } 302 303 #if __cplusplus >= 201103L 304 iterator 305 erase(const_iterator __position) 306 { 307 __glibcxx_check_erase(__position); 308 this->_M_invalidate_if(_Equal(__position.base())); 309 return iterator(_Base::erase(__position.base()), this); 310 } 311 312 iterator 313 erase(iterator __position) 314 { return erase(const_iterator(__position)); } 315 #else 316 void 317 erase(iterator __position) 318 { 319 __glibcxx_check_erase(__position); 320 this->_M_invalidate_if(_Equal(__position.base())); 321 _Base::erase(__position.base()); 322 } 323 #endif 324 325 size_type 326 erase(const key_type& __x) 327 { 328 std::pair<_Base_iterator, _Base_iterator> __victims = 329 _Base::equal_range(__x); 330 size_type __count = 0; 331 _Base_iterator __victim = __victims.first; 332 while (__victim != __victims.second) 333 { 334 this->_M_invalidate_if(_Equal(__victim)); 335 _Base::erase(__victim++); 336 ++__count; 337 } 338 return __count; 339 } 340 341 #if __cplusplus >= 201103L 342 iterator 343 erase(const_iterator __first, const_iterator __last) 344 { 345 // _GLIBCXX_RESOLVE_LIB_DEFECTS 346 // 151. can't currently clear() empty container 347 __glibcxx_check_erase_range(__first, __last); 348 for (_Base_const_iterator __victim = __first.base(); 349 __victim != __last.base(); ++__victim) 350 { 351 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 352 _M_message(__gnu_debug::__msg_valid_range) 353 ._M_iterator(__first, "first") 354 ._M_iterator(__last, "last")); 355 this->_M_invalidate_if(_Equal(__victim)); 356 } 357 return iterator(_Base::erase(__first.base(), __last.base()), this); 358 } 359 #else 360 void 361 erase(iterator __first, iterator __last) 362 { 363 // _GLIBCXX_RESOLVE_LIB_DEFECTS 364 // 151. can't currently clear() empty container 365 __glibcxx_check_erase_range(__first, __last); 366 for (_Base_iterator __victim = __first.base(); 367 __victim != __last.base(); ++__victim) 368 { 369 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 370 _M_message(__gnu_debug::__msg_valid_range) 371 ._M_iterator(__first, "first") 372 ._M_iterator(__last, "last")); 373 this->_M_invalidate_if(_Equal(__victim)); 374 } 375 _Base::erase(__first.base(), __last.base()); 376 } 377 #endif 378 379 void 380 swap(multimap& __x) 381 #if __cplusplus >= 201103L 382 noexcept(_Alloc_traits::_S_nothrow_swap()) 383 #endif 384 { 385 #if __cplusplus >= 201103L 386 if (!_Alloc_traits::_S_propagate_on_swap()) 387 __glibcxx_check_equal_allocs(__x); 388 #endif 389 _Base::swap(__x); 390 this->_M_swap(__x); 391 } 392 393 void 394 clear() _GLIBCXX_NOEXCEPT 395 { 396 this->_M_invalidate_all(); 397 _Base::clear(); 398 } 399 400 // observers: 401 using _Base::key_comp; 402 using _Base::value_comp; 403 404 // 23.3.1.3 multimap operations: 405 iterator 406 find(const key_type& __x) 407 { return iterator(_Base::find(__x), this); } 408 409 const_iterator 410 find(const key_type& __x) const 411 { return const_iterator(_Base::find(__x), this); } 412 413 using _Base::count; 414 415 iterator 416 lower_bound(const key_type& __x) 417 { return iterator(_Base::lower_bound(__x), this); } 418 419 const_iterator 420 lower_bound(const key_type& __x) const 421 { return const_iterator(_Base::lower_bound(__x), this); } 422 423 iterator 424 upper_bound(const key_type& __x) 425 { return iterator(_Base::upper_bound(__x), this); } 426 427 const_iterator 428 upper_bound(const key_type& __x) const 429 { return const_iterator(_Base::upper_bound(__x), this); } 430 431 std::pair<iterator,iterator> 432 equal_range(const key_type& __x) 433 { 434 std::pair<_Base_iterator, _Base_iterator> __res = 435 _Base::equal_range(__x); 436 return std::make_pair(iterator(__res.first, this), 437 iterator(__res.second, this)); 438 } 439 440 std::pair<const_iterator,const_iterator> 441 equal_range(const key_type& __x) const 442 { 443 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 444 _Base::equal_range(__x); 445 return std::make_pair(const_iterator(__res.first, this), 446 const_iterator(__res.second, this)); 447 } 448 449 _Base& 450 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 451 452 const _Base& 453 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 454 455 private: 456 void 457 _M_invalidate_all() 458 { 459 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 460 this->_M_invalidate_if(_Not_equal(_Base::end())); 461 } 462 }; 463 464 template<typename _Key, typename _Tp, 465 typename _Compare, typename _Allocator> 466 inline bool 467 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 468 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 469 { return __lhs._M_base() == __rhs._M_base(); } 470 471 template<typename _Key, typename _Tp, 472 typename _Compare, typename _Allocator> 473 inline bool 474 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 475 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 476 { return __lhs._M_base() != __rhs._M_base(); } 477 478 template<typename _Key, typename _Tp, 479 typename _Compare, typename _Allocator> 480 inline bool 481 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 482 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 483 { return __lhs._M_base() < __rhs._M_base(); } 484 485 template<typename _Key, typename _Tp, 486 typename _Compare, typename _Allocator> 487 inline bool 488 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 489 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 490 { return __lhs._M_base() <= __rhs._M_base(); } 491 492 template<typename _Key, typename _Tp, 493 typename _Compare, typename _Allocator> 494 inline bool 495 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 496 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 497 { return __lhs._M_base() >= __rhs._M_base(); } 498 499 template<typename _Key, typename _Tp, 500 typename _Compare, typename _Allocator> 501 inline bool 502 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 503 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 504 { return __lhs._M_base() > __rhs._M_base(); } 505 506 template<typename _Key, typename _Tp, 507 typename _Compare, typename _Allocator> 508 inline void 509 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 510 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 511 { __lhs.swap(__rhs); } 512 513 } // namespace __debug 514 } // namespace std 515 516 #endif 517
