libstdc++-v3/include/debug/set.h

   1 // Debugging set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2024 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 <bits/stl_pair.h>
  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       template<typename _ItT, typename _SeqT, typename _CatT>
  59         friend class ::__gnu_debug::_Safe_iterator;
  60
  61       // Reference wrapper for base class. Disambiguates set(const _Base&)
  62       // from copy constructor by requiring a user-defined conversion.
  63       // See PR libstdc++/90102.
  64       struct _Base_ref
  65       {
  66         _Base_ref(const _Base& __r) : _M_ref(__r) { }
  67
  68         const _Base& _M_ref;
  69       };
  70
  71     public:
  72       // types:
  73       typedef _Key                                      key_type;
  74       typedef _Key                                      value_type;
  75       typedef _Compare                                  key_compare;
  76       typedef _Compare                                  value_compare;
  77       typedef _Allocator                                allocator_type;
  78       typedef typename _Base::reference                 reference;
  79       typedef typename _Base::const_reference           const_reference;
  80
  81       typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
  82                                                         iterator;
  83       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
  84                                                         const_iterator;
  85
  86       typedef typename _Base::size_type                 size_type;
  87       typedef typename _Base::difference_type           difference_type;
  88       typedef typename _Base::pointer                   pointer;
  89       typedef typename _Base::const_pointer             const_pointer;
  90       typedef std::reverse_iterator<iterator>           reverse_iterator;
  91       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
  92
  93       // 23.3.3.1 construct/copy/destroy:
  94
  95 #if __cplusplus < 201103L
  96       set() : _Base() { }
  97
  98       set(const set& __x)
  99       : _Base(__x) { }
 100
 101       ~set() { }
 102 #else
 103       set() = default;
 104       set(const set&) = default;
 105       set(set&&) = default;
 106
 107       set(initializer_list<value_type> __l,
 108           const _Compare& __comp = _Compare(),
 109           const allocator_type& __a = allocator_type())
 110       : _Base(__l, __comp, __a) { }
 111
 112       explicit
 113       set(const allocator_type& __a)
 114       : _Base(__a) { }
 115
 116       set(const set& __x, const __type_identity_t<allocator_type>& __a)
 117       : _Base(__x, __a) { }
 118
 119       set(set&& __x, const __type_identity_t<allocator_type>& __a)
 120       noexcept( noexcept(_Base(std::move(__x), __a)) )
 121       : _Safe(std::move(__x), __a),
 122         _Base(std::move(__x), __a) { }
 123
 124       set(initializer_list<value_type> __l, const allocator_type& __a)
 125       : _Base(__l, __a) { }
 126
 127       template<typename _InputIterator>
 128         set(_InputIterator __first, _InputIterator __last,
 129             const allocator_type& __a)
 130         : _Base(__gnu_debug::__base(
 131                   __glibcxx_check_valid_constructor_range(__first, __last)),
 132                 __gnu_debug::__base(__last), __a) { }
 133
 134       ~set() = default;
 135 #endif
 136
 137       explicit set(const _Compare& __comp,
 138                    const _Allocator& __a = _Allocator())
 139       : _Base(__comp, __a) { }
 140
 141       template<typename _InputIterator>
 142         set(_InputIterator __first, _InputIterator __last,
 143             const _Compare& __comp = _Compare(),
 144             const _Allocator& __a = _Allocator())
 145         : _Base(__gnu_debug::__base(
 146                   __glibcxx_check_valid_constructor_range(__first, __last)),
 147                 __gnu_debug::__base(__last),
 148                 __comp, __a) { }
 149
 150       set(_Base_ref __x)
 151       : _Base(__x._M_ref) { }
 152
 153 #if __cplusplus >= 201103L
 154       set&
 155       operator=(const set&) = default;
 156
 157       set&
 158       operator=(set&&) = default;
 159
 160       set&
 161       operator=(initializer_list<value_type> __l)
 162       {
 163         _Base::operator=(__l);
 164         this->_M_invalidate_all();
 165         return *this;
 166       }
 167 #endif
 168
 169       using _Base::get_allocator;
 170
 171       // iterators:
 172       iterator
 173       begin() _GLIBCXX_NOEXCEPT
 174       { return iterator(_Base::begin(), this); }
 175
 176       const_iterator
 177       begin() const _GLIBCXX_NOEXCEPT
 178       { return const_iterator(_Base::begin(), this); }
 179
 180       iterator
 181       end() _GLIBCXX_NOEXCEPT
 182       { return iterator(_Base::end(), this); }
 183
 184       const_iterator
 185       end() const _GLIBCXX_NOEXCEPT
 186       { return const_iterator(_Base::end(), this); }
 187
 188       reverse_iterator
 189       rbegin() _GLIBCXX_NOEXCEPT
 190       { return reverse_iterator(end()); }
 191
 192       const_reverse_iterator
 193       rbegin() const _GLIBCXX_NOEXCEPT
 194       { return const_reverse_iterator(end()); }
 195
 196       reverse_iterator
 197       rend() _GLIBCXX_NOEXCEPT
 198       { return reverse_iterator(begin()); }
 199
 200       const_reverse_iterator
 201       rend() const _GLIBCXX_NOEXCEPT
 202       { return const_reverse_iterator(begin()); }
 203
 204 #if __cplusplus >= 201103L
 205       const_iterator
 206       cbegin() const noexcept
 207       { return const_iterator(_Base::begin(), this); }
 208
 209       const_iterator
 210       cend() const noexcept
 211       { return const_iterator(_Base::end(), this); }
 212
 213       const_reverse_iterator
 214       crbegin() const noexcept
 215       { return const_reverse_iterator(end()); }
 216
 217       const_reverse_iterator
 218       crend() const noexcept
 219       { return const_reverse_iterator(begin()); }
 220 #endif
 221
 222       // capacity:
 223       using _Base::empty;
 224       using _Base::size;
 225       using _Base::max_size;
 226
 227       // modifiers:
 228 #if __cplusplus >= 201103L
 229       template<typename... _Args>
 230         std::pair<iterator, bool>
 231         emplace(_Args&&... __args)
 232         {
 233           auto __res = _Base::emplace(std::forward<_Args>(__args)...);
 234           return { { __res.first, this }, __res.second };
 235         }
 236
 237       template<typename... _Args>
 238         iterator
 239         emplace_hint(const_iterator __pos, _Args&&... __args)
 240         {
 241           __glibcxx_check_insert(__pos);
 242           return
 243             {
 244               _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
 245               this
 246             };
 247         }
 248 #endif
 249
 250       std::pair<iterator, bool>
 251       insert(const value_type& __x)
 252       {
 253         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 254         return std::pair<iterator, bool>(iterator(__res.first, this),
 255                                          __res.second);
 256       }
 257
 258 #if __cplusplus >= 201103L
 259       std::pair<iterator, bool>
 260       insert(value_type&& __x)
 261       {
 262         auto __res = _Base::insert(std::move(__x));
 263         return { { __res.first, this }, __res.second };
 264       }
 265 #endif
 266
 267       iterator
 268       insert(const_iterator __position, const value_type& __x)
 269       {
 270         __glibcxx_check_insert(__position);
 271         return iterator(_Base::insert(__position.base(), __x), this);
 272       }
 273
 274 #if __cplusplus >= 201103L
 275       iterator
 276       insert(const_iterator __position, value_type&& __x)
 277       {
 278         __glibcxx_check_insert(__position);
 279         return { _Base::insert(__position.base(), std::move(__x)), this };
 280       }
 281 #endif
 282
 283       template <typename _InputIterator>
 284         void
 285         insert(_InputIterator __first, _InputIterator __last)
 286         {
 287           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 288           __glibcxx_check_valid_range2(__first, __last, __dist);
 289
 290           if (__dist.second >= __gnu_debug::__dp_sign)
 291             _Base::insert(__gnu_debug::__unsafe(__first),
 292                           __gnu_debug::__unsafe(__last));
 293           else
 294             _Base::insert(__first, __last);
 295         }
 296
 297 #if __cplusplus >= 201103L
 298       void
 299       insert(initializer_list<value_type> __l)
 300       { _Base::insert(__l); }
 301 #endif
 302
 303 #if __cplusplus > 201402L
 304       using node_type = typename _Base::node_type;
 305       using insert_return_type = _Node_insert_return<iterator, node_type>;
 306
 307       node_type
 308       extract(const_iterator __position)
 309       {
 310         __glibcxx_check_erase(__position);
 311         this->_M_invalidate_if(_Equal(__position.base()));
 312         return _Base::extract(__position.base());
 313       }
 314
 315       node_type
 316       extract(const key_type& __key)
 317       {
 318         const auto __position = find(__key);
 319         if (__position != end())
 320           return extract(__position);
 321         return {};
 322       }
 323
 324       insert_return_type
 325       insert(node_type&& __nh)
 326       {
 327         auto __ret = _Base::insert(std::move(__nh));
 328         iterator __pos = iterator(__ret.position, this);
 329         return { __pos, __ret.inserted, std::move(__ret.node) };
 330       }
 331
 332       iterator
 333       insert(const_iterator __hint, node_type&& __nh)
 334       {
 335         __glibcxx_check_insert(__hint);
 336         return { _Base::insert(__hint.base(), std::move(__nh)), this };
 337       }
 338
 339       using _Base::merge;
 340 #endif // C++17
 341
 342 #if __cplusplus >= 201103L
 343       _GLIBCXX_ABI_TAG_CXX11
 344       iterator
 345       erase(const_iterator __position)
 346       {
 347         __glibcxx_check_erase(__position);
 348         return { erase(__position.base()), this };
 349       }
 350
 351       _Base_iterator
 352       erase(_Base_const_iterator __position)
 353       {
 354         __glibcxx_check_erase2(__position);
 355         this->_M_invalidate_if(_Equal(__position));
 356         return _Base::erase(__position);
 357       }
 358 #else
 359       void
 360       erase(iterator __position)
 361       {
 362         __glibcxx_check_erase(__position);
 363         this->_M_invalidate_if(_Equal(__position.base()));
 364         _Base::erase(__position.base());
 365       }
 366 #endif
 367
 368       size_type
 369       erase(const key_type& __x)
 370       {
 371         _Base_iterator __victim = _Base::find(__x);
 372         if (__victim == _Base::end())
 373           return 0;
 374         else
 375           {
 376             this->_M_invalidate_if(_Equal(__victim));
 377             _Base::erase(__victim);
 378             return 1;
 379           }
 380       }
 381
 382 #if __cplusplus >= 201103L
 383       _GLIBCXX_ABI_TAG_CXX11
 384       iterator
 385       erase(const_iterator __first, const_iterator __last)
 386       {
 387         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 388         // 151. can't currently clear() empty container
 389         __glibcxx_check_erase_range(__first, __last);
 390         for (_Base_const_iterator __victim = __first.base();
 391              __victim != __last.base(); ++__victim)
 392           {
 393             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
 394                                   _M_message(__gnu_debug::__msg_valid_range)
 395                                   ._M_iterator(__first, "first")
 396                                   ._M_iterator(__last, "last"));
 397             this->_M_invalidate_if(_Equal(__victim));
 398           }
 399
 400         return { _Base::erase(__first.base(), __last.base()), this };
 401       }
 402 #else
 403       void
 404       erase(iterator __first, iterator __last)
 405       {
 406         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 407         // 151. can't currently clear() empty container
 408         __glibcxx_check_erase_range(__first, __last);
 409         for (_Base_iterator __victim = __first.base();
 410              __victim != __last.base(); ++__victim)
 411           {
 412             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 413                                   _M_message(__gnu_debug::__msg_valid_range)
 414                                   ._M_iterator(__first, "first")
 415                                   ._M_iterator(__last, "last"));
 416             this->_M_invalidate_if(_Equal(__victim));
 417           }
 418         _Base::erase(__first.base(), __last.base());
 419       }
 420 #endif
 421
 422       void
 423       swap(set& __x)
 424       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
 425       {
 426         _Safe::_M_swap(__x);
 427         _Base::swap(__x);
 428       }
 429
 430       void
 431       clear() _GLIBCXX_NOEXCEPT
 432       {
 433         this->_M_invalidate_all();
 434         _Base::clear();
 435       }
 436
 437       // observers:
 438       using _Base::key_comp;
 439       using _Base::value_comp;
 440
 441       // set operations:
 442       iterator
 443       find(const key_type& __x)
 444       { return iterator(_Base::find(__x), this); }
 445
 446       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 447       // 214. set::find() missing const overload
 448       const_iterator
 449       find(const key_type& __x) const
 450       { return const_iterator(_Base::find(__x), this); }
 451
 452 #if __cplusplus > 201103L
 453       template<typename _Kt,
 454                typename _Req =
 455                  typename __has_is_transparent<_Compare, _Kt>::type>
 456         iterator
 457         find(const _Kt& __x)
 458         { return { _Base::find(__x), this }; }
 459
 460       template<typename _Kt,
 461                typename _Req =
 462                  typename __has_is_transparent<_Compare, _Kt>::type>
 463         const_iterator
 464         find(const _Kt& __x) const
 465         { return { _Base::find(__x), this }; }
 466 #endif
 467
 468       using _Base::count;
 469
 470       iterator
 471       lower_bound(const key_type& __x)
 472       { return iterator(_Base::lower_bound(__x), this); }
 473
 474       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 475       // 214. set::find() missing const overload
 476       const_iterator
 477       lower_bound(const key_type& __x) const
 478       { return const_iterator(_Base::lower_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         lower_bound(const _Kt& __x)
 486         { return { _Base::lower_bound(__x), this }; }
 487
 488       template<typename _Kt,
 489                typename _Req =
 490                  typename __has_is_transparent<_Compare, _Kt>::type>
 491         const_iterator
 492         lower_bound(const _Kt& __x) const
 493         { return { _Base::lower_bound(__x), this }; }
 494 #endif
 495
 496       iterator
 497       upper_bound(const key_type& __x)
 498       { return iterator(_Base::upper_bound(__x), this); }
 499
 500       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 501       // 214. set::find() missing const overload
 502       const_iterator
 503       upper_bound(const key_type& __x) const
 504       { return const_iterator(_Base::upper_bound(__x), this); }
 505
 506 #if __cplusplus > 201103L
 507       template<typename _Kt,
 508                typename _Req =
 509                  typename __has_is_transparent<_Compare, _Kt>::type>
 510         iterator
 511         upper_bound(const _Kt& __x)
 512         { return { _Base::upper_bound(__x), this }; }
 513
 514       template<typename _Kt,
 515                typename _Req =
 516                  typename __has_is_transparent<_Compare, _Kt>::type>
 517         const_iterator
 518         upper_bound(const _Kt& __x) const
 519         { return { _Base::upper_bound(__x), this }; }
 520 #endif
 521
 522       std::pair<iterator, iterator>
 523       equal_range(const key_type& __x)
 524       {
 525         std::pair<_Base_iterator, _Base_iterator> __res =
 526         _Base::equal_range(__x);
 527         return std::make_pair(iterator(__res.first, this),
 528                               iterator(__res.second, this));
 529       }
 530
 531       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 532       // 214. set::find() missing const overload
 533       std::pair<const_iterator, const_iterator>
 534       equal_range(const key_type& __x) const
 535       {
 536         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 537         _Base::equal_range(__x);
 538         return std::make_pair(const_iterator(__res.first, this),
 539                               const_iterator(__res.second, this));
 540       }
 541
 542 #if __cplusplus > 201103L
 543       template<typename _Kt,
 544                typename _Req =
 545                  typename __has_is_transparent<_Compare, _Kt>::type>
 546         std::pair<iterator, iterator>
 547         equal_range(const _Kt& __x)
 548         {
 549           auto __res = _Base::equal_range(__x);
 550           return { { __res.first, this }, { __res.second, this } };
 551         }
 552
 553       template<typename _Kt,
 554                typename _Req =
 555                  typename __has_is_transparent<_Compare, _Kt>::type>
 556         std::pair<const_iterator, const_iterator>
 557         equal_range(const _Kt& __x) const
 558         {
 559           auto __res = _Base::equal_range(__x);
 560           return { { __res.first, this }, { __res.second, this } };
 561         }
 562 #endif
 563
 564       _Base&
 565       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 566
 567       const _Base&
 568       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 569     };
 570
 571 #if __cpp_deduction_guides >= 201606
 572
 573   template<typename _InputIterator,
 574            typename _Compare =
 575              less<typename iterator_traits<_InputIterator>::value_type>,
 576            typename _Allocator =
 577              allocator<typename iterator_traits<_InputIterator>::value_type>,
 578            typename = _RequireInputIter<_InputIterator>,
 579            typename = _RequireNotAllocator<_Compare>,
 580            typename = _RequireAllocator<_Allocator>>
 581     set(_InputIterator, _InputIterator,
 582         _Compare = _Compare(), _Allocator = _Allocator())
 583     -> set<typename iterator_traits<_InputIterator>::value_type,
 584            _Compare, _Allocator>;
 585
 586   template<typename _Key, typename _Compare = less<_Key>,
 587            typename _Allocator = allocator<_Key>,
 588            typename = _RequireNotAllocator<_Compare>,
 589            typename = _RequireAllocator<_Allocator>>
 590     set(initializer_list<_Key>,
 591         _Compare = _Compare(), _Allocator = _Allocator())
 592     -> set<_Key, _Compare, _Allocator>;
 593
 594   template<typename _InputIterator, typename _Allocator,
 595            typename = _RequireInputIter<_InputIterator>,
 596            typename = _RequireAllocator<_Allocator>>
 597     set(_InputIterator, _InputIterator, _Allocator)
 598     -> set<typename iterator_traits<_InputIterator>::value_type,
 599            less<typename iterator_traits<_InputIterator>::value_type>,
 600            _Allocator>;
 601
 602   template<typename _Key, typename _Allocator,
 603            typename = _RequireAllocator<_Allocator>>
 604     set(initializer_list<_Key>, _Allocator)
 605     -> set<_Key, less<_Key>, _Allocator>;
 606
 607 #endif // deduction guides
 608
 609   template<typename _Key, typename _Compare, typename _Allocator>
 610     inline bool
 611     operator==(const set<_Key, _Compare, _Allocator>& __lhs,
 612                const set<_Key, _Compare, _Allocator>& __rhs)
 613     { return __lhs._M_base() == __rhs._M_base(); }
 614
 615 #if __cpp_lib_three_way_comparison
 616   template<typename _Key, typename _Compare, typename _Alloc>
 617     inline __detail::__synth3way_t<_Key>
 618     operator<=>(const set<_Key, _Compare, _Alloc>& __lhs,
 619                 const set<_Key, _Compare, _Alloc>& __rhs)
 620     { return __lhs._M_base() <=> __rhs._M_base(); }
 621 #else
 622   template<typename _Key, typename _Compare, typename _Allocator>
 623     inline bool
 624     operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
 625                const set<_Key, _Compare, _Allocator>& __rhs)
 626     { return __lhs._M_base() != __rhs._M_base(); }
 627
 628   template<typename _Key, typename _Compare, typename _Allocator>
 629     inline bool
 630     operator<(const set<_Key, _Compare, _Allocator>& __lhs,
 631               const set<_Key, _Compare, _Allocator>& __rhs)
 632     { return __lhs._M_base() < __rhs._M_base(); }
 633
 634   template<typename _Key, typename _Compare, typename _Allocator>
 635     inline bool
 636     operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
 637                const set<_Key, _Compare, _Allocator>& __rhs)
 638     { return __lhs._M_base() <= __rhs._M_base(); }
 639
 640   template<typename _Key, typename _Compare, typename _Allocator>
 641     inline bool
 642     operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
 643                const set<_Key, _Compare, _Allocator>& __rhs)
 644     { return __lhs._M_base() >= __rhs._M_base(); }
 645
 646   template<typename _Key, typename _Compare, typename _Allocator>
 647     inline bool
 648     operator>(const set<_Key, _Compare, _Allocator>& __lhs,
 649               const set<_Key, _Compare, _Allocator>& __rhs)
 650     { return __lhs._M_base() > __rhs._M_base(); }
 651 #endif // three-way comparison
 652
 653   template<typename _Key, typename _Compare, typename _Allocator>
 654     void
 655     swap(set<_Key, _Compare, _Allocator>& __x,
 656          set<_Key, _Compare, _Allocator>& __y)
 657     _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
 658     { return __x.swap(__y); }
 659
 660 } // namespace __debug
 661 } // namespace std
 662
 663 #endif