1 // Debugging multimap implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2016 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_container.h> 34 #include <debug/safe_iterator.h> 35 #include <utility> 36 37 namespace std _GLIBCXX_VISIBILITY(default) 38 { 39 namespace __debug 40 { 41 /// Class std::multimap 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 multimap 45 : public __gnu_debug::_Safe_container< 46 multimap<_Key, _Tp, _Compare, _Allocator>, _Allocator, 47 __gnu_debug::_Safe_node_sequence>, 48 public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> 49 { 50 typedef _GLIBCXX_STD_C::multimap< 51 _Key, _Tp, _Compare, _Allocator> _Base; 52 typedef __gnu_debug::_Safe_container< 53 multimap, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; 54 55 typedef typename _Base::const_iterator _Base_const_iterator; 56 typedef typename _Base::iterator _Base_iterator; 57 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 58 59 public: 60 // types: 61 typedef _Key key_type; 62 typedef _Tp mapped_type; 63 typedef std::pair<const _Key, _Tp> value_type; 64 typedef _Compare key_compare; 65 typedef _Allocator allocator_type; 66 typedef typename _Base::reference reference; 67 typedef typename _Base::const_reference const_reference; 68 69 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap> 70 iterator; 71 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 72 multimap> const_iterator; 73 74 typedef typename _Base::size_type size_type; 75 typedef typename _Base::difference_type difference_type; 76 typedef typename _Base::pointer pointer; 77 typedef typename _Base::const_pointer const_pointer; 78 typedef std::reverse_iterator<iterator> reverse_iterator; 79 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 80 81 // 23.3.1.1 construct/copy/destroy: 82 83 #if __cplusplus < 201103L 84 multimap() : _Base() { } 85 86 multimap(const multimap& __x) 87 : _Base(__x) { } 88 89 ~multimap() { } 90 #else 91 multimap() = default; 92 multimap(const multimap&) = default; 93 multimap(multimap&&) = default; 94 95 multimap(initializer_list<value_type> __l, 96 const _Compare& __c = _Compare(), 97 const allocator_type& __a = allocator_type()) 98 : _Base(__l, __c, __a) { } 99 100 explicit 101 multimap(const allocator_type& __a) 102 : _Base(__a) { } 103 104 multimap(const multimap& __m, const allocator_type& __a) 105 : _Base(__m, __a) { } 106 107 multimap(multimap&& __m, const allocator_type& __a) 108 : _Safe(std::move(__m._M_safe()), __a), 109 _Base(std::move(__m._M_base()), __a) { } 110 111 multimap(initializer_list<value_type> __l, const allocator_type& __a) 112 : _Base(__l, __a) { } 113 114 template<typename _InputIterator> 115 multimap(_InputIterator __first, _InputIterator __last, 116 const allocator_type& __a) 117 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 118 __last)), 119 __gnu_debug::__base(__last), __a) { } 120 121 ~multimap() = default; 122 #endif 123 124 explicit multimap(const _Compare& __comp, 125 const _Allocator& __a = _Allocator()) 126 : _Base(__comp, __a) { } 127 128 template<typename _InputIterator> 129 multimap(_InputIterator __first, _InputIterator __last, 130 const _Compare& __comp = _Compare(), 131 const _Allocator& __a = _Allocator()) 132 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 133 __last)), 134 __gnu_debug::__base(__last), 135 __comp, __a) { } 136 137 multimap(const _Base& __x) 138 : _Base(__x) { } 139 140 #if __cplusplus < 201103L 141 multimap& 142 operator=(const multimap& __x) 143 { 144 this->_M_safe() = __x; 145 _M_base() = __x; 146 return *this; 147 } 148 #else 149 multimap& 150 operator=(const multimap&) = default; 151 152 multimap& 153 operator=(multimap&&) = default; 154 155 multimap& 156 operator=(initializer_list<value_type> __l) 157 { 158 _M_base() = __l; 159 this->_M_invalidate_all(); 160 return *this; 161 } 162 #endif 163 164 using _Base::get_allocator; 165 166 // iterators: 167 iterator 168 begin() _GLIBCXX_NOEXCEPT 169 { return iterator(_Base::begin(), this); } 170 171 const_iterator 172 begin() const _GLIBCXX_NOEXCEPT 173 { return const_iterator(_Base::begin(), this); } 174 175 iterator 176 end() _GLIBCXX_NOEXCEPT 177 { return iterator(_Base::end(), this); } 178 179 const_iterator 180 end() const _GLIBCXX_NOEXCEPT 181 { return const_iterator(_Base::end(), this); } 182 183 reverse_iterator 184 rbegin() _GLIBCXX_NOEXCEPT 185 { return reverse_iterator(end()); } 186 187 const_reverse_iterator 188 rbegin() const _GLIBCXX_NOEXCEPT 189 { return const_reverse_iterator(end()); } 190 191 reverse_iterator 192 rend() _GLIBCXX_NOEXCEPT 193 { return reverse_iterator(begin()); } 194 195 const_reverse_iterator 196 rend() const _GLIBCXX_NOEXCEPT 197 { return const_reverse_iterator(begin()); } 198 199 #if __cplusplus >= 201103L 200 const_iterator 201 cbegin() const noexcept 202 { return const_iterator(_Base::begin(), this); } 203 204 const_iterator 205 cend() const noexcept 206 { return const_iterator(_Base::end(), this); } 207 208 const_reverse_iterator 209 crbegin() const noexcept 210 { return const_reverse_iterator(end()); } 211 212 const_reverse_iterator 213 crend() const noexcept 214 { return const_reverse_iterator(begin()); } 215 #endif 216 217 // capacity: 218 using _Base::empty; 219 using _Base::size; 220 using _Base::max_size; 221 222 // modifiers: 223 #if __cplusplus >= 201103L 224 template<typename... _Args> 225 iterator 226 emplace(_Args&&... __args) 227 { 228 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); 229 } 230 231 template<typename... _Args> 232 iterator 233 emplace_hint(const_iterator __pos, _Args&&... __args) 234 { 235 __glibcxx_check_insert(__pos); 236 return iterator(_Base::emplace_hint(__pos.base(), 237 std::forward<_Args>(__args)...), 238 this); 239 } 240 #endif 241 242 iterator 243 insert(const value_type& __x) 244 { return iterator(_Base::insert(__x), this); } 245 246 #if __cplusplus >= 201103L 247 template<typename _Pair, typename = typename 248 std::enable_if<std::is_constructible<value_type, 249 _Pair&&>::value>::type> 250 iterator 251 insert(_Pair&& __x) 252 { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); } 253 #endif 254 255 #if __cplusplus >= 201103L 256 void 257 insert(std::initializer_list<value_type> __list) 258 { _Base::insert(__list); } 259 #endif 260 261 iterator 262 #if __cplusplus >= 201103L 263 insert(const_iterator __position, const value_type& __x) 264 #else 265 insert(iterator __position, const value_type& __x) 266 #endif 267 { 268 __glibcxx_check_insert(__position); 269 return iterator(_Base::insert(__position.base(), __x), this); 270 } 271 272 #if __cplusplus >= 201103L 273 template<typename _Pair, typename = typename 274 std::enable_if<std::is_constructible<value_type, 275 _Pair&&>::value>::type> 276 iterator 277 insert(const_iterator __position, _Pair&& __x) 278 { 279 __glibcxx_check_insert(__position); 280 return iterator(_Base::insert(__position.base(), 281 std::forward<_Pair>(__x)), this); 282 } 283 #endif 284 285 template<typename _InputIterator> 286 void 287 insert(_InputIterator __first, _InputIterator __last) 288 { 289 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 290 __glibcxx_check_valid_range2(__first, __last, __dist); 291 292 if (__dist.second >= __gnu_debug::__dp_sign) 293 _Base::insert(__gnu_debug::__unsafe(__first), 294 __gnu_debug::__unsafe(__last)); 295 else 296 _Base::insert(__first, __last); 297 } 298 299 #if __cplusplus >= 201103L 300 iterator 301 erase(const_iterator __position) 302 { 303 __glibcxx_check_erase(__position); 304 this->_M_invalidate_if(_Equal(__position.base())); 305 return iterator(_Base::erase(__position.base()), this); 306 } 307 308 iterator 309 erase(iterator __position) 310 { return erase(const_iterator(__position)); } 311 #else 312 void 313 erase(iterator __position) 314 { 315 __glibcxx_check_erase(__position); 316 this->_M_invalidate_if(_Equal(__position.base())); 317 _Base::erase(__position.base()); 318 } 319 #endif 320 321 size_type 322 erase(const key_type& __x) 323 { 324 std::pair<_Base_iterator, _Base_iterator> __victims = 325 _Base::equal_range(__x); 326 size_type __count = 0; 327 _Base_iterator __victim = __victims.first; 328 while (__victim != __victims.second) 329 { 330 this->_M_invalidate_if(_Equal(__victim)); 331 _Base::erase(__victim++); 332 ++__count; 333 } 334 return __count; 335 } 336 337 #if __cplusplus >= 201103L 338 iterator 339 erase(const_iterator __first, const_iterator __last) 340 { 341 // _GLIBCXX_RESOLVE_LIB_DEFECTS 342 // 151. can't currently clear() empty container 343 __glibcxx_check_erase_range(__first, __last); 344 for (_Base_const_iterator __victim = __first.base(); 345 __victim != __last.base(); ++__victim) 346 { 347 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 348 _M_message(__gnu_debug::__msg_valid_range) 349 ._M_iterator(__first, "first") 350 ._M_iterator(__last, "last")); 351 this->_M_invalidate_if(_Equal(__victim)); 352 } 353 return iterator(_Base::erase(__first.base(), __last.base()), this); 354 } 355 #else 356 void 357 erase(iterator __first, iterator __last) 358 { 359 // _GLIBCXX_RESOLVE_LIB_DEFECTS 360 // 151. can't currently clear() empty container 361 __glibcxx_check_erase_range(__first, __last); 362 for (_Base_iterator __victim = __first.base(); 363 __victim != __last.base(); ++__victim) 364 { 365 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 366 _M_message(__gnu_debug::__msg_valid_range) 367 ._M_iterator(__first, "first") 368 ._M_iterator(__last, "last")); 369 this->_M_invalidate_if(_Equal(__victim)); 370 } 371 _Base::erase(__first.base(), __last.base()); 372 } 373 #endif 374 375 void 376 swap(multimap& __x) 377 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 378 { 379 _Safe::_M_swap(__x); 380 _Base::swap(__x); 381 } 382 383 void 384 clear() _GLIBCXX_NOEXCEPT 385 { 386 this->_M_invalidate_all(); 387 _Base::clear(); 388 } 389 390 // observers: 391 using _Base::key_comp; 392 using _Base::value_comp; 393 394 // 23.3.1.3 multimap operations: 395 iterator 396 find(const key_type& __x) 397 { return iterator(_Base::find(__x), this); } 398 399 #if __cplusplus > 201103L 400 template<typename _Kt, 401 typename _Req = 402 typename __has_is_transparent<_Compare, _Kt>::type> 403 iterator 404 find(const _Kt& __x) 405 { return { _Base::find(__x), this }; } 406 #endif 407 408 const_iterator 409 find(const key_type& __x) const 410 { return const_iterator(_Base::find(__x), this); } 411 412 #if __cplusplus > 201103L 413 template<typename _Kt, 414 typename _Req = 415 typename __has_is_transparent<_Compare, _Kt>::type> 416 const_iterator 417 find(const _Kt& __x) const 418 { return { _Base::find(__x), this }; } 419 #endif 420 421 using _Base::count; 422 423 iterator 424 lower_bound(const key_type& __x) 425 { return iterator(_Base::lower_bound(__x), this); } 426 427 #if __cplusplus > 201103L 428 template<typename _Kt, 429 typename _Req = 430 typename __has_is_transparent<_Compare, _Kt>::type> 431 iterator 432 lower_bound(const _Kt& __x) 433 { return { _Base::lower_bound(__x), this }; } 434 #endif 435 436 const_iterator 437 lower_bound(const key_type& __x) const 438 { return const_iterator(_Base::lower_bound(__x), this); } 439 440 #if __cplusplus > 201103L 441 template<typename _Kt, 442 typename _Req = 443 typename __has_is_transparent<_Compare, _Kt>::type> 444 const_iterator 445 lower_bound(const _Kt& __x) const 446 { return { _Base::lower_bound(__x), this }; } 447 #endif 448 449 iterator 450 upper_bound(const key_type& __x) 451 { return iterator(_Base::upper_bound(__x), this); } 452 453 #if __cplusplus > 201103L 454 template<typename _Kt, 455 typename _Req = 456 typename __has_is_transparent<_Compare, _Kt>::type> 457 iterator 458 upper_bound(const _Kt& __x) 459 { return { _Base::upper_bound(__x), this }; } 460 #endif 461 462 const_iterator 463 upper_bound(const key_type& __x) const 464 { return const_iterator(_Base::upper_bound(__x), this); } 465 466 #if __cplusplus > 201103L 467 template<typename _Kt, 468 typename _Req = 469 typename __has_is_transparent<_Compare, _Kt>::type> 470 const_iterator 471 upper_bound(const _Kt& __x) const 472 { return { _Base::upper_bound(__x), this }; } 473 #endif 474 475 std::pair<iterator,iterator> 476 equal_range(const key_type& __x) 477 { 478 std::pair<_Base_iterator, _Base_iterator> __res = 479 _Base::equal_range(__x); 480 return std::make_pair(iterator(__res.first, this), 481 iterator(__res.second, this)); 482 } 483 484 #if __cplusplus > 201103L 485 template<typename _Kt, 486 typename _Req = 487 typename __has_is_transparent<_Compare, _Kt>::type> 488 std::pair<iterator, iterator> 489 equal_range(const _Kt& __x) 490 { 491 auto __res = _Base::equal_range(__x); 492 return { { __res.first, this }, { __res.second, this } }; 493 } 494 #endif 495 496 std::pair<const_iterator,const_iterator> 497 equal_range(const key_type& __x) const 498 { 499 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 500 _Base::equal_range(__x); 501 return std::make_pair(const_iterator(__res.first, this), 502 const_iterator(__res.second, this)); 503 } 504 505 #if __cplusplus > 201103L 506 template<typename _Kt, 507 typename _Req = 508 typename __has_is_transparent<_Compare, _Kt>::type> 509 std::pair<const_iterator, const_iterator> 510 equal_range(const _Kt& __x) const 511 { 512 auto __res = _Base::equal_range(__x); 513 return { { __res.first, this }, { __res.second, this } }; 514 } 515 #endif 516 517 _Base& 518 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 519 520 const _Base& 521 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 522 }; 523 524 template<typename _Key, typename _Tp, 525 typename _Compare, typename _Allocator> 526 inline bool 527 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 528 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 529 { return __lhs._M_base() == __rhs._M_base(); } 530 531 template<typename _Key, typename _Tp, 532 typename _Compare, typename _Allocator> 533 inline bool 534 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 535 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 536 { return __lhs._M_base() != __rhs._M_base(); } 537 538 template<typename _Key, typename _Tp, 539 typename _Compare, typename _Allocator> 540 inline bool 541 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 542 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 543 { return __lhs._M_base() < __rhs._M_base(); } 544 545 template<typename _Key, typename _Tp, 546 typename _Compare, typename _Allocator> 547 inline bool 548 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 549 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 550 { return __lhs._M_base() <= __rhs._M_base(); } 551 552 template<typename _Key, typename _Tp, 553 typename _Compare, typename _Allocator> 554 inline bool 555 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 556 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 557 { return __lhs._M_base() >= __rhs._M_base(); } 558 559 template<typename _Key, typename _Tp, 560 typename _Compare, typename _Allocator> 561 inline bool 562 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 563 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 564 { return __lhs._M_base() > __rhs._M_base(); } 565 566 template<typename _Key, typename _Tp, 567 typename _Compare, typename _Allocator> 568 inline void 569 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 570 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 571 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) 572 { __lhs.swap(__rhs); } 573 574 } // namespace __debug 575 } // namespace std 576 577 #endif 578