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