1 // Debugging multiset implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2018 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/multiset.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_MULTISET_H 30 #define _GLIBCXX_DEBUG_MULTISET_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::multiset with safety/checking/debug instrumentation. 42 template<typename _Key, typename _Compare = std::less<_Key>, 43 typename _Allocator = std::allocator<_Key> > 44 class multiset 45 : public __gnu_debug::_Safe_container< 46 multiset<_Key, _Compare, _Allocator>, _Allocator, 47 __gnu_debug::_Safe_node_sequence>, 48 public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> 49 { 50 typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base; 51 typedef __gnu_debug::_Safe_container< 52 multiset, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; 53 54 typedef typename _Base::const_iterator _Base_const_iterator; 55 typedef typename _Base::iterator _Base_iterator; 56 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 57 58 public: 59 // types: 60 typedef _Key key_type; 61 typedef _Key value_type; 62 typedef _Compare key_compare; 63 typedef _Compare value_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, multiset> 69 iterator; 70 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 71 multiset> 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.3.1 construct/copy/destroy: 81 82 #if __cplusplus < 201103L 83 multiset() : _Base() { } 84 85 multiset(const multiset& __x) 86 : _Base(__x) { } 87 88 ~multiset() { } 89 #else 90 multiset() = default; 91 multiset(const multiset&) = default; 92 multiset(multiset&&) = default; 93 94 multiset(initializer_list<value_type> __l, 95 const _Compare& __comp = _Compare(), 96 const allocator_type& __a = allocator_type()) 97 : _Base(__l, __comp, __a) { } 98 99 explicit 100 multiset(const allocator_type& __a) 101 : _Base(__a) { } 102 103 multiset(const multiset& __m, const allocator_type& __a) 104 : _Base(__m, __a) { } 105 106 multiset(multiset&& __m, const allocator_type& __a) 107 : _Safe(std::move(__m._M_safe()), __a), 108 _Base(std::move(__m._M_base()), __a) { } 109 110 multiset(initializer_list<value_type> __l, const allocator_type& __a) 111 : _Base(__l, __a) 112 { } 113 114 template<typename _InputIterator> 115 multiset(_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 ~multiset() = default; 122 #endif 123 124 explicit multiset(const _Compare& __comp, 125 const _Allocator& __a = _Allocator()) 126 : _Base(__comp, __a) { } 127 128 template<typename _InputIterator> 129 multiset(_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 multiset(const _Base& __x) 138 : _Base(__x) { } 139 140 #if __cplusplus < 201103L 141 multiset& 142 operator=(const multiset& __x) 143 { 144 this->_M_safe() = __x; 145 _M_base() = __x; 146 return *this; 147 } 148 #else 149 multiset& 150 operator=(const multiset&) = default; 151 152 multiset& 153 operator=(multiset&&) = default; 154 155 multiset& 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)...), 229 this); 230 } 231 232 template<typename... _Args> 233 iterator 234 emplace_hint(const_iterator __pos, _Args&&... __args) 235 { 236 __glibcxx_check_insert(__pos); 237 return iterator(_Base::emplace_hint(__pos.base(), 238 std::forward<_Args>(__args)...), 239 this); 240 } 241 #endif 242 243 iterator 244 insert(const value_type& __x) 245 { return iterator(_Base::insert(__x), this); } 246 247 #if __cplusplus >= 201103L 248 iterator 249 insert(value_type&& __x) 250 { return iterator(_Base::insert(std::move(__x)), this); } 251 #endif 252 253 iterator 254 insert(const_iterator __position, const value_type& __x) 255 { 256 __glibcxx_check_insert(__position); 257 return iterator(_Base::insert(__position.base(), __x), this); 258 } 259 260 #if __cplusplus >= 201103L 261 iterator 262 insert(const_iterator __position, value_type&& __x) 263 { 264 __glibcxx_check_insert(__position); 265 return iterator(_Base::insert(__position.base(), std::move(__x)), 266 this); 267 } 268 #endif 269 270 template<typename _InputIterator> 271 void 272 insert(_InputIterator __first, _InputIterator __last) 273 { 274 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 275 __glibcxx_check_valid_range2(__first, __last, __dist); 276 277 if (__dist.second >= __gnu_debug::__dp_sign) 278 _Base::insert(__gnu_debug::__unsafe(__first), 279 __gnu_debug::__unsafe(__last)); 280 else 281 _Base::insert(__first, __last); 282 } 283 284 #if __cplusplus >= 201103L 285 void 286 insert(initializer_list<value_type> __l) 287 { _Base::insert(__l); } 288 #endif 289 290 #if __cplusplus > 201402L 291 using node_type = typename _Base::node_type; 292 293 node_type 294 extract(const_iterator __position) 295 { 296 __glibcxx_check_erase(__position); 297 this->_M_invalidate_if(_Equal(__position.base())); 298 return _Base::extract(__position.base()); 299 } 300 301 node_type 302 extract(const key_type& __key) 303 { 304 const auto __position = find(__key); 305 if (__position != end()) 306 return extract(__position); 307 return {}; 308 } 309 310 iterator 311 insert(node_type&& __nh) 312 { return iterator(_Base::insert(std::move(__nh)), this); } 313 314 iterator 315 insert(const_iterator __hint, node_type&& __nh) 316 { 317 __glibcxx_check_insert(__hint); 318 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); 319 } 320 321 using _Base::merge; 322 #endif // C++17 323 324 #if __cplusplus >= 201103L 325 iterator 326 erase(const_iterator __position) 327 { 328 __glibcxx_check_erase(__position); 329 this->_M_invalidate_if(_Equal(__position.base())); 330 return iterator(_Base::erase(__position.base()), this); 331 } 332 #else 333 void 334 erase(iterator __position) 335 { 336 __glibcxx_check_erase(__position); 337 this->_M_invalidate_if(_Equal(__position.base())); 338 _Base::erase(__position.base()); 339 } 340 #endif 341 342 size_type 343 erase(const key_type& __x) 344 { 345 std::pair<_Base_iterator, _Base_iterator> __victims = 346 _Base::equal_range(__x); 347 size_type __count = 0; 348 _Base_iterator __victim = __victims.first; 349 while (__victim != __victims.second) 350 { 351 this->_M_invalidate_if(_Equal(__victim)); 352 _Base::erase(__victim++); 353 ++__count; 354 } 355 return __count; 356 } 357 358 #if __cplusplus >= 201103L 359 iterator 360 erase(const_iterator __first, const_iterator __last) 361 { 362 // _GLIBCXX_RESOLVE_LIB_DEFECTS 363 // 151. can't currently clear() empty container 364 __glibcxx_check_erase_range(__first, __last); 365 for (_Base_const_iterator __victim = __first.base(); 366 __victim != __last.base(); ++__victim) 367 { 368 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 369 _M_message(__gnu_debug::__msg_valid_range) 370 ._M_iterator(__first, "first") 371 ._M_iterator(__last, "last")); 372 this->_M_invalidate_if(_Equal(__victim)); 373 } 374 return iterator(_Base::erase(__first.base(), __last.base()), this); 375 } 376 #else 377 void 378 erase(iterator __first, iterator __last) 379 { 380 // _GLIBCXX_RESOLVE_LIB_DEFECTS 381 // 151. can't currently clear() empty container 382 __glibcxx_check_erase_range(__first, __last); 383 for (_Base_iterator __victim = __first.base(); 384 __victim != __last.base(); ++__victim) 385 { 386 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 387 _M_message(__gnu_debug::__msg_valid_range) 388 ._M_iterator(__first, "first") 389 ._M_iterator(__last, "last")); 390 this->_M_invalidate_if(_Equal(__victim)); 391 } 392 _Base::erase(__first.base(), __last.base()); 393 } 394 #endif 395 396 void 397 swap(multiset& __x) 398 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 399 { 400 _Safe::_M_swap(__x); 401 _Base::swap(__x); 402 } 403 404 void 405 clear() _GLIBCXX_NOEXCEPT 406 { 407 this->_M_invalidate_all(); 408 _Base::clear(); 409 } 410 411 // observers: 412 using _Base::key_comp; 413 using _Base::value_comp; 414 415 // multiset operations: 416 iterator 417 find(const key_type& __x) 418 { return iterator(_Base::find(__x), this); } 419 420 // _GLIBCXX_RESOLVE_LIB_DEFECTS 421 // 214. set::find() missing const overload 422 const_iterator 423 find(const key_type& __x) const 424 { return const_iterator(_Base::find(__x), this); } 425 426 #if __cplusplus > 201103L 427 template<typename _Kt, 428 typename _Req = 429 typename __has_is_transparent<_Compare, _Kt>::type> 430 iterator 431 find(const _Kt& __x) 432 { return { _Base::find(__x), this }; } 433 434 template<typename _Kt, 435 typename _Req = 436 typename __has_is_transparent<_Compare, _Kt>::type> 437 const_iterator 438 find(const _Kt& __x) const 439 { return { _Base::find(__x), this }; } 440 #endif 441 442 using _Base::count; 443 444 iterator 445 lower_bound(const key_type& __x) 446 { return iterator(_Base::lower_bound(__x), this); } 447 448 // _GLIBCXX_RESOLVE_LIB_DEFECTS 449 // 214. set::find() missing const overload 450 const_iterator 451 lower_bound(const key_type& __x) const 452 { return const_iterator(_Base::lower_bound(__x), this); } 453 454 #if __cplusplus > 201103L 455 template<typename _Kt, 456 typename _Req = 457 typename __has_is_transparent<_Compare, _Kt>::type> 458 iterator 459 lower_bound(const _Kt& __x) 460 { return { _Base::lower_bound(__x), this }; } 461 462 template<typename _Kt, 463 typename _Req = 464 typename __has_is_transparent<_Compare, _Kt>::type> 465 const_iterator 466 lower_bound(const _Kt& __x) const 467 { return { _Base::lower_bound(__x), this }; } 468 #endif 469 470 iterator 471 upper_bound(const key_type& __x) 472 { return iterator(_Base::upper_bound(__x), this); } 473 474 // _GLIBCXX_RESOLVE_LIB_DEFECTS 475 // 214. set::find() missing const overload 476 const_iterator 477 upper_bound(const key_type& __x) const 478 { return const_iterator(_Base::upper_bound(__x), this); } 479 480 #if __cplusplus > 201103L 481 template<typename _Kt, 482 typename _Req = 483 typename __has_is_transparent<_Compare, _Kt>::type> 484 iterator 485 upper_bound(const _Kt& __x) 486 { return { _Base::upper_bound(__x), this }; } 487 488 template<typename _Kt, 489 typename _Req = 490 typename __has_is_transparent<_Compare, _Kt>::type> 491 const_iterator 492 upper_bound(const _Kt& __x) const 493 { return { _Base::upper_bound(__x), this }; } 494 #endif 495 496 std::pair<iterator,iterator> 497 equal_range(const key_type& __x) 498 { 499 std::pair<_Base_iterator, _Base_iterator> __res = 500 _Base::equal_range(__x); 501 return std::make_pair(iterator(__res.first, this), 502 iterator(__res.second, this)); 503 } 504 505 // _GLIBCXX_RESOLVE_LIB_DEFECTS 506 // 214. set::find() missing const overload 507 std::pair<const_iterator,const_iterator> 508 equal_range(const key_type& __x) const 509 { 510 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 511 _Base::equal_range(__x); 512 return std::make_pair(const_iterator(__res.first, this), 513 const_iterator(__res.second, this)); 514 } 515 516 #if __cplusplus > 201103L 517 template<typename _Kt, 518 typename _Req = 519 typename __has_is_transparent<_Compare, _Kt>::type> 520 std::pair<iterator, iterator> 521 equal_range(const _Kt& __x) 522 { 523 auto __res = _Base::equal_range(__x); 524 return { { __res.first, this }, { __res.second, this } }; 525 } 526 527 template<typename _Kt, 528 typename _Req = 529 typename __has_is_transparent<_Compare, _Kt>::type> 530 std::pair<const_iterator, const_iterator> 531 equal_range(const _Kt& __x) const 532 { 533 auto __res = _Base::equal_range(__x); 534 return { { __res.first, this }, { __res.second, this } }; 535 } 536 #endif 537 538 _Base& 539 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 540 541 const _Base& 542 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 543 }; 544 545 #if __cpp_deduction_guides >= 201606 546 547 template<typename _InputIterator, 548 typename _Compare = 549 less<typename iterator_traits<_InputIterator>::value_type>, 550 typename _Allocator = 551 allocator<typename iterator_traits<_InputIterator>::value_type>, 552 typename = _RequireInputIter<_InputIterator>, 553 typename = _RequireAllocator<_Allocator>> 554 multiset(_InputIterator, _InputIterator, 555 _Compare = _Compare(), _Allocator = _Allocator()) 556 -> multiset<typename iterator_traits<_InputIterator>::value_type, 557 _Compare, _Allocator>; 558 559 template<typename _Key, 560 typename _Compare = less<_Key>, 561 typename _Allocator = allocator<_Key>, 562 typename = _RequireAllocator<_Allocator>> 563 multiset(initializer_list<_Key>, 564 _Compare = _Compare(), _Allocator = _Allocator()) 565 -> multiset<_Key, _Compare, _Allocator>; 566 567 template<typename _InputIterator, typename _Allocator, 568 typename = _RequireInputIter<_InputIterator>, 569 typename = _RequireAllocator<_Allocator>> 570 multiset(_InputIterator, _InputIterator, _Allocator) 571 -> multiset<typename iterator_traits<_InputIterator>::value_type, 572 less<typename iterator_traits<_InputIterator>::value_type>, 573 _Allocator>; 574 575 template<typename _Key, typename _Allocator, 576 typename = _RequireAllocator<_Allocator>> 577 multiset(initializer_list<_Key>, _Allocator) 578 -> multiset<_Key, less<_Key>, _Allocator>; 579 580 #endif 581 582 template<typename _Key, typename _Compare, typename _Allocator> 583 inline bool 584 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs, 585 const multiset<_Key, _Compare, _Allocator>& __rhs) 586 { return __lhs._M_base() == __rhs._M_base(); } 587 588 template<typename _Key, typename _Compare, typename _Allocator> 589 inline bool 590 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs, 591 const multiset<_Key, _Compare, _Allocator>& __rhs) 592 { return __lhs._M_base() != __rhs._M_base(); } 593 594 template<typename _Key, typename _Compare, typename _Allocator> 595 inline bool 596 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs, 597 const multiset<_Key, _Compare, _Allocator>& __rhs) 598 { return __lhs._M_base() < __rhs._M_base(); } 599 600 template<typename _Key, typename _Compare, typename _Allocator> 601 inline bool 602 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs, 603 const multiset<_Key, _Compare, _Allocator>& __rhs) 604 { return __lhs._M_base() <= __rhs._M_base(); } 605 606 template<typename _Key, typename _Compare, typename _Allocator> 607 inline bool 608 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs, 609 const multiset<_Key, _Compare, _Allocator>& __rhs) 610 { return __lhs._M_base() >= __rhs._M_base(); } 611 612 template<typename _Key, typename _Compare, typename _Allocator> 613 inline bool 614 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs, 615 const multiset<_Key, _Compare, _Allocator>& __rhs) 616 { return __lhs._M_base() > __rhs._M_base(); } 617 618 template<typename _Key, typename _Compare, typename _Allocator> 619 void 620 swap(multiset<_Key, _Compare, _Allocator>& __x, 621 multiset<_Key, _Compare, _Allocator>& __y) 622 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 623 { return __x.swap(__y); } 624 625 } // namespace __debug 626 } // namespace std 627 628 #endif 629