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 noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) ) 108 : _Safe(std::move(__m._M_safe()), __a), 109 _Base(std::move(__m._M_base()), __a) { } 110 111 multiset(initializer_list<value_type> __l, const allocator_type& __a) 112 : _Base(__l, __a) 113 { } 114 115 template<typename _InputIterator> 116 multiset(_InputIterator __first, _InputIterator __last, 117 const allocator_type& __a) 118 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 119 __last)), 120 __gnu_debug::__base(__last), __a) { } 121 122 ~multiset() = default; 123 #endif 124 125 explicit multiset(const _Compare& __comp, 126 const _Allocator& __a = _Allocator()) 127 : _Base(__comp, __a) { } 128 129 template<typename _InputIterator> 130 multiset(_InputIterator __first, _InputIterator __last, 131 const _Compare& __comp = _Compare(), 132 const _Allocator& __a = _Allocator()) 133 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 134 __last)), 135 __gnu_debug::__base(__last), 136 __comp, __a) { } 137 138 multiset(const _Base& __x) 139 : _Base(__x) { } 140 141 #if __cplusplus < 201103L 142 multiset& 143 operator=(const multiset& __x) 144 { 145 this->_M_safe() = __x; 146 _M_base() = __x; 147 return *this; 148 } 149 #else 150 multiset& 151 operator=(const multiset&) = default; 152 153 multiset& 154 operator=(multiset&&) = default; 155 156 multiset& 157 operator=(initializer_list<value_type> __l) 158 { 159 _M_base() = __l; 160 this->_M_invalidate_all(); 161 return *this; 162 } 163 #endif 164 165 using _Base::get_allocator; 166 167 // iterators: 168 iterator 169 begin() _GLIBCXX_NOEXCEPT 170 { return iterator(_Base::begin(), this); } 171 172 const_iterator 173 begin() const _GLIBCXX_NOEXCEPT 174 { return const_iterator(_Base::begin(), this); } 175 176 iterator 177 end() _GLIBCXX_NOEXCEPT 178 { return iterator(_Base::end(), this); } 179 180 const_iterator 181 end() const _GLIBCXX_NOEXCEPT 182 { return const_iterator(_Base::end(), this); } 183 184 reverse_iterator 185 rbegin() _GLIBCXX_NOEXCEPT 186 { return reverse_iterator(end()); } 187 188 const_reverse_iterator 189 rbegin() const _GLIBCXX_NOEXCEPT 190 { return const_reverse_iterator(end()); } 191 192 reverse_iterator 193 rend() _GLIBCXX_NOEXCEPT 194 { return reverse_iterator(begin()); } 195 196 const_reverse_iterator 197 rend() const _GLIBCXX_NOEXCEPT 198 { return const_reverse_iterator(begin()); } 199 200 #if __cplusplus >= 201103L 201 const_iterator 202 cbegin() const noexcept 203 { return const_iterator(_Base::begin(), this); } 204 205 const_iterator 206 cend() const noexcept 207 { return const_iterator(_Base::end(), this); } 208 209 const_reverse_iterator 210 crbegin() const noexcept 211 { return const_reverse_iterator(end()); } 212 213 const_reverse_iterator 214 crend() const noexcept 215 { return const_reverse_iterator(begin()); } 216 #endif 217 218 // capacity: 219 using _Base::empty; 220 using _Base::size; 221 using _Base::max_size; 222 223 // modifiers: 224 #if __cplusplus >= 201103L 225 template<typename... _Args> 226 iterator 227 emplace(_Args&&... __args) 228 { 229 return iterator(_Base::emplace(std::forward<_Args>(__args)...), 230 this); 231 } 232 233 template<typename... _Args> 234 iterator 235 emplace_hint(const_iterator __pos, _Args&&... __args) 236 { 237 __glibcxx_check_insert(__pos); 238 return iterator(_Base::emplace_hint(__pos.base(), 239 std::forward<_Args>(__args)...), 240 this); 241 } 242 #endif 243 244 iterator 245 insert(const value_type& __x) 246 { return iterator(_Base::insert(__x), this); } 247 248 #if __cplusplus >= 201103L 249 iterator 250 insert(value_type&& __x) 251 { return iterator(_Base::insert(std::move(__x)), this); } 252 #endif 253 254 iterator 255 insert(const_iterator __position, const value_type& __x) 256 { 257 __glibcxx_check_insert(__position); 258 return iterator(_Base::insert(__position.base(), __x), this); 259 } 260 261 #if __cplusplus >= 201103L 262 iterator 263 insert(const_iterator __position, value_type&& __x) 264 { 265 __glibcxx_check_insert(__position); 266 return iterator(_Base::insert(__position.base(), std::move(__x)), 267 this); 268 } 269 #endif 270 271 template<typename _InputIterator> 272 void 273 insert(_InputIterator __first, _InputIterator __last) 274 { 275 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 276 __glibcxx_check_valid_range2(__first, __last, __dist); 277 278 if (__dist.second >= __gnu_debug::__dp_sign) 279 _Base::insert(__gnu_debug::__unsafe(__first), 280 __gnu_debug::__unsafe(__last)); 281 else 282 _Base::insert(__first, __last); 283 } 284 285 #if __cplusplus >= 201103L 286 void 287 insert(initializer_list<value_type> __l) 288 { _Base::insert(__l); } 289 #endif 290 291 #if __cplusplus > 201402L 292 using node_type = typename _Base::node_type; 293 294 node_type 295 extract(const_iterator __position) 296 { 297 __glibcxx_check_erase(__position); 298 this->_M_invalidate_if(_Equal(__position.base())); 299 return _Base::extract(__position.base()); 300 } 301 302 node_type 303 extract(const key_type& __key) 304 { 305 const auto __position = find(__key); 306 if (__position != end()) 307 return extract(__position); 308 return {}; 309 } 310 311 iterator 312 insert(node_type&& __nh) 313 { return iterator(_Base::insert(std::move(__nh)), this); } 314 315 iterator 316 insert(const_iterator __hint, node_type&& __nh) 317 { 318 __glibcxx_check_insert(__hint); 319 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); 320 } 321 322 using _Base::merge; 323 #endif // C++17 324 325 #if __cplusplus >= 201103L 326 iterator 327 erase(const_iterator __position) 328 { 329 __glibcxx_check_erase(__position); 330 this->_M_invalidate_if(_Equal(__position.base())); 331 return iterator(_Base::erase(__position.base()), this); 332 } 333 #else 334 void 335 erase(iterator __position) 336 { 337 __glibcxx_check_erase(__position); 338 this->_M_invalidate_if(_Equal(__position.base())); 339 _Base::erase(__position.base()); 340 } 341 #endif 342 343 size_type 344 erase(const key_type& __x) 345 { 346 std::pair<_Base_iterator, _Base_iterator> __victims = 347 _Base::equal_range(__x); 348 size_type __count = 0; 349 _Base_iterator __victim = __victims.first; 350 while (__victim != __victims.second) 351 { 352 this->_M_invalidate_if(_Equal(__victim)); 353 _Base::erase(__victim++); 354 ++__count; 355 } 356 return __count; 357 } 358 359 #if __cplusplus >= 201103L 360 iterator 361 erase(const_iterator __first, const_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_const_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 return iterator(_Base::erase(__first.base(), __last.base()), this); 376 } 377 #else 378 void 379 erase(iterator __first, iterator __last) 380 { 381 // _GLIBCXX_RESOLVE_LIB_DEFECTS 382 // 151. can't currently clear() empty container 383 __glibcxx_check_erase_range(__first, __last); 384 for (_Base_iterator __victim = __first.base(); 385 __victim != __last.base(); ++__victim) 386 { 387 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 388 _M_message(__gnu_debug::__msg_valid_range) 389 ._M_iterator(__first, "first") 390 ._M_iterator(__last, "last")); 391 this->_M_invalidate_if(_Equal(__victim)); 392 } 393 _Base::erase(__first.base(), __last.base()); 394 } 395 #endif 396 397 void 398 swap(multiset& __x) 399 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 400 { 401 _Safe::_M_swap(__x); 402 _Base::swap(__x); 403 } 404 405 void 406 clear() _GLIBCXX_NOEXCEPT 407 { 408 this->_M_invalidate_all(); 409 _Base::clear(); 410 } 411 412 // observers: 413 using _Base::key_comp; 414 using _Base::value_comp; 415 416 // multiset operations: 417 iterator 418 find(const key_type& __x) 419 { return iterator(_Base::find(__x), this); } 420 421 // _GLIBCXX_RESOLVE_LIB_DEFECTS 422 // 214. set::find() missing const overload 423 const_iterator 424 find(const key_type& __x) const 425 { return const_iterator(_Base::find(__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 find(const _Kt& __x) 433 { return { _Base::find(__x), this }; } 434 435 template<typename _Kt, 436 typename _Req = 437 typename __has_is_transparent<_Compare, _Kt>::type> 438 const_iterator 439 find(const _Kt& __x) const 440 { return { _Base::find(__x), this }; } 441 #endif 442 443 using _Base::count; 444 445 iterator 446 lower_bound(const key_type& __x) 447 { return iterator(_Base::lower_bound(__x), this); } 448 449 // _GLIBCXX_RESOLVE_LIB_DEFECTS 450 // 214. set::find() missing const overload 451 const_iterator 452 lower_bound(const key_type& __x) const 453 { return const_iterator(_Base::lower_bound(__x), this); } 454 455 #if __cplusplus > 201103L 456 template<typename _Kt, 457 typename _Req = 458 typename __has_is_transparent<_Compare, _Kt>::type> 459 iterator 460 lower_bound(const _Kt& __x) 461 { return { _Base::lower_bound(__x), this }; } 462 463 template<typename _Kt, 464 typename _Req = 465 typename __has_is_transparent<_Compare, _Kt>::type> 466 const_iterator 467 lower_bound(const _Kt& __x) const 468 { return { _Base::lower_bound(__x), this }; } 469 #endif 470 471 iterator 472 upper_bound(const key_type& __x) 473 { return iterator(_Base::upper_bound(__x), this); } 474 475 // _GLIBCXX_RESOLVE_LIB_DEFECTS 476 // 214. set::find() missing const overload 477 const_iterator 478 upper_bound(const key_type& __x) const 479 { return const_iterator(_Base::upper_bound(__x), this); } 480 481 #if __cplusplus > 201103L 482 template<typename _Kt, 483 typename _Req = 484 typename __has_is_transparent<_Compare, _Kt>::type> 485 iterator 486 upper_bound(const _Kt& __x) 487 { return { _Base::upper_bound(__x), this }; } 488 489 template<typename _Kt, 490 typename _Req = 491 typename __has_is_transparent<_Compare, _Kt>::type> 492 const_iterator 493 upper_bound(const _Kt& __x) const 494 { return { _Base::upper_bound(__x), this }; } 495 #endif 496 497 std::pair<iterator,iterator> 498 equal_range(const key_type& __x) 499 { 500 std::pair<_Base_iterator, _Base_iterator> __res = 501 _Base::equal_range(__x); 502 return std::make_pair(iterator(__res.first, this), 503 iterator(__res.second, this)); 504 } 505 506 // _GLIBCXX_RESOLVE_LIB_DEFECTS 507 // 214. set::find() missing const overload 508 std::pair<const_iterator,const_iterator> 509 equal_range(const key_type& __x) const 510 { 511 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 512 _Base::equal_range(__x); 513 return std::make_pair(const_iterator(__res.first, this), 514 const_iterator(__res.second, this)); 515 } 516 517 #if __cplusplus > 201103L 518 template<typename _Kt, 519 typename _Req = 520 typename __has_is_transparent<_Compare, _Kt>::type> 521 std::pair<iterator, iterator> 522 equal_range(const _Kt& __x) 523 { 524 auto __res = _Base::equal_range(__x); 525 return { { __res.first, this }, { __res.second, this } }; 526 } 527 528 template<typename _Kt, 529 typename _Req = 530 typename __has_is_transparent<_Compare, _Kt>::type> 531 std::pair<const_iterator, const_iterator> 532 equal_range(const _Kt& __x) const 533 { 534 auto __res = _Base::equal_range(__x); 535 return { { __res.first, this }, { __res.second, this } }; 536 } 537 #endif 538 539 _Base& 540 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 541 542 const _Base& 543 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 544 }; 545 546 #if __cpp_deduction_guides >= 201606 547 548 template<typename _InputIterator, 549 typename _Compare = 550 less<typename iterator_traits<_InputIterator>::value_type>, 551 typename _Allocator = 552 allocator<typename iterator_traits<_InputIterator>::value_type>, 553 typename = _RequireInputIter<_InputIterator>, 554 typename = _RequireAllocator<_Allocator>> 555 multiset(_InputIterator, _InputIterator, 556 _Compare = _Compare(), _Allocator = _Allocator()) 557 -> multiset<typename iterator_traits<_InputIterator>::value_type, 558 _Compare, _Allocator>; 559 560 template<typename _Key, 561 typename _Compare = less<_Key>, 562 typename _Allocator = allocator<_Key>, 563 typename = _RequireAllocator<_Allocator>> 564 multiset(initializer_list<_Key>, 565 _Compare = _Compare(), _Allocator = _Allocator()) 566 -> multiset<_Key, _Compare, _Allocator>; 567 568 template<typename _InputIterator, typename _Allocator, 569 typename = _RequireInputIter<_InputIterator>, 570 typename = _RequireAllocator<_Allocator>> 571 multiset(_InputIterator, _InputIterator, _Allocator) 572 -> multiset<typename iterator_traits<_InputIterator>::value_type, 573 less<typename iterator_traits<_InputIterator>::value_type>, 574 _Allocator>; 575 576 template<typename _Key, typename _Allocator, 577 typename = _RequireAllocator<_Allocator>> 578 multiset(initializer_list<_Key>, _Allocator) 579 -> multiset<_Key, less<_Key>, _Allocator>; 580 581 #endif 582 583 template<typename _Key, typename _Compare, typename _Allocator> 584 inline bool 585 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs, 586 const multiset<_Key, _Compare, _Allocator>& __rhs) 587 { return __lhs._M_base() == __rhs._M_base(); } 588 589 template<typename _Key, typename _Compare, typename _Allocator> 590 inline bool 591 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs, 592 const multiset<_Key, _Compare, _Allocator>& __rhs) 593 { return __lhs._M_base() != __rhs._M_base(); } 594 595 template<typename _Key, typename _Compare, typename _Allocator> 596 inline bool 597 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs, 598 const multiset<_Key, _Compare, _Allocator>& __rhs) 599 { return __lhs._M_base() < __rhs._M_base(); } 600 601 template<typename _Key, typename _Compare, typename _Allocator> 602 inline bool 603 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs, 604 const multiset<_Key, _Compare, _Allocator>& __rhs) 605 { return __lhs._M_base() <= __rhs._M_base(); } 606 607 template<typename _Key, typename _Compare, typename _Allocator> 608 inline bool 609 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs, 610 const multiset<_Key, _Compare, _Allocator>& __rhs) 611 { return __lhs._M_base() >= __rhs._M_base(); } 612 613 template<typename _Key, typename _Compare, typename _Allocator> 614 inline bool 615 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs, 616 const multiset<_Key, _Compare, _Allocator>& __rhs) 617 { return __lhs._M_base() > __rhs._M_base(); } 618 619 template<typename _Key, typename _Compare, typename _Allocator> 620 void 621 swap(multiset<_Key, _Compare, _Allocator>& __x, 622 multiset<_Key, _Compare, _Allocator>& __y) 623 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 624 { return __x.swap(__y); } 625 626 } // namespace __debug 627 } // namespace std 628 629 #endif 630