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

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