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

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