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

   1 // Debugging multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2019 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file debug/multiset.h
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_MULTISET_H
  30 #define _GLIBCXX_DEBUG_MULTISET_H 1
  31
  32 #include <debug/safe_sequence.h>
  33 #include <debug/safe_container.h>
  34 #include <debug/safe_iterator.h>
  35 #include <utility>
  36
  37 namespace std _GLIBCXX_VISIBILITY(default)
  38 {
  39 namespace __debug
  40 {
  41   /// Class std::multiset with safety/checking/debug instrumentation.
  42   template<typename _Key, typename _Compare = std::less<_Key>,
  43            typename _Allocator = std::allocator<_Key> >
  44     class multiset
  45     : public __gnu_debug::_Safe_container<
  46         multiset<_Key, _Compare, _Allocator>, _Allocator,
  47         __gnu_debug::_Safe_node_sequence>,
  48       public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
  49     {
  50       typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>      _Base;
  51       typedef __gnu_debug::_Safe_container<
  52         multiset, _Allocator, __gnu_debug::_Safe_node_sequence>         _Safe;
  53
  54       typedef typename _Base::const_iterator    _Base_const_iterator;
  55       typedef typename _Base::iterator          _Base_iterator;
  56       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
  57
  58       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, multiset>
  72                                                         iterator;
  73       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  74                                           multiset>     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       multiset() : _Base() { }
  87
  88       multiset(const multiset& __x)
  89       : _Base(__x) { }
  90
  91       ~multiset() { }
  92 #else
  93       multiset() = default;
  94       multiset(const multiset&) = default;
  95       multiset(multiset&&) = default;
  96
  97       multiset(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       multiset(const allocator_type& __a)
 104       : _Base(__a) { }
 105
 106       multiset(const multiset& __m, const allocator_type& __a)
 107       : _Base(__m, __a) { }
 108
 109       multiset(multiset&& __m, const allocator_type& __a)
 110       noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
 111       : _Safe(std::move(__m._M_safe()), __a),
 112         _Base(std::move(__m._M_base()), __a) { }
 113
 114       multiset(initializer_list<value_type> __l, const allocator_type& __a)
 115         : _Base(__l, __a)
 116       { }
 117
 118       template<typename _InputIterator>
 119         multiset(_InputIterator __first, _InputIterator __last,
 120                  const allocator_type& __a)
 121         : _Base(__gnu_debug::__base(
 122                   __glibcxx_check_valid_constructor_range(__first, __last)),
 123                 __gnu_debug::__base(__last), __a) { }
 124
 125       ~multiset() = default;
 126 #endif
 127
 128       explicit multiset(const _Compare& __comp,
 129                         const _Allocator& __a = _Allocator())
 130       : _Base(__comp, __a) { }
 131
 132       template<typename _InputIterator>
 133         multiset(_InputIterator __first, _InputIterator __last,
 134                  const _Compare& __comp = _Compare(),
 135                  const _Allocator& __a = _Allocator())
 136         : _Base(__gnu_debug::__base(
 137                   __glibcxx_check_valid_constructor_range(__first, __last)),
 138                 __gnu_debug::__base(__last),
 139                 __comp, __a) { }
 140
 141       multiset(const _Base& __x)
 142       : _Base(__x) { }
 143
 144 #if __cplusplus < 201103L
 145       multiset&
 146       operator=(const multiset& __x)
 147       {
 148         this->_M_safe() = __x;
 149         _M_base() = __x;
 150         return *this;
 151       }
 152 #else
 153       multiset&
 154       operator=(const multiset&) = default;
 155
 156       multiset&
 157       operator=(multiset&&) = default;
 158
 159       multiset&
 160       operator=(initializer_list<value_type> __l)
 161       {
 162         _M_base() = __l;
 163         this->_M_invalidate_all();
 164         return *this;
 165       }
 166 #endif
 167
 168       using _Base::get_allocator;
 169
 170       // iterators:
 171       iterator
 172       begin() _GLIBCXX_NOEXCEPT
 173       { return iterator(_Base::begin(), this); }
 174
 175       const_iterator
 176       begin() const _GLIBCXX_NOEXCEPT
 177       { return const_iterator(_Base::begin(), this); }
 178
 179       iterator
 180       end() _GLIBCXX_NOEXCEPT
 181       { return iterator(_Base::end(), this); }
 182
 183       const_iterator
 184       end() const _GLIBCXX_NOEXCEPT
 185       { return const_iterator(_Base::end(), this); }
 186
 187       reverse_iterator
 188       rbegin() _GLIBCXX_NOEXCEPT
 189       { return reverse_iterator(end()); }
 190
 191       const_reverse_iterator
 192       rbegin() const _GLIBCXX_NOEXCEPT
 193       { return const_reverse_iterator(end()); }
 194
 195       reverse_iterator
 196       rend() _GLIBCXX_NOEXCEPT
 197       { return reverse_iterator(begin()); }
 198
 199       const_reverse_iterator
 200       rend() const _GLIBCXX_NOEXCEPT
 201       { return const_reverse_iterator(begin()); }
 202
 203 #if __cplusplus >= 201103L
 204       const_iterator
 205       cbegin() const noexcept
 206       { return const_iterator(_Base::begin(), this); }
 207
 208       const_iterator
 209       cend() const noexcept
 210       { return const_iterator(_Base::end(), this); }
 211
 212       const_reverse_iterator
 213       crbegin() const noexcept
 214       { return const_reverse_iterator(end()); }
 215
 216       const_reverse_iterator
 217       crend() const noexcept
 218       { return const_reverse_iterator(begin()); }
 219 #endif
 220
 221       // capacity:
 222       using _Base::empty;
 223       using _Base::size;
 224       using _Base::max_size;
 225
 226       // modifiers:
 227 #if __cplusplus >= 201103L
 228       template<typename... _Args>
 229         iterator
 230         emplace(_Args&&... __args)
 231         { return { _Base::emplace(std::forward<_Args>(__args)...), this }; }
 232
 233       template<typename... _Args>
 234         iterator
 235         emplace_hint(const_iterator __pos, _Args&&... __args)
 236         {
 237           __glibcxx_check_insert(__pos);
 238           return
 239             {
 240               _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
 241               this
 242             };
 243         }
 244 #endif
 245
 246       iterator
 247       insert(const value_type& __x)
 248       { return iterator(_Base::insert(__x), this); }
 249
 250 #if __cplusplus >= 201103L
 251       iterator
 252       insert(value_type&& __x)
 253       { return { _Base::insert(std::move(__x)), this }; }
 254 #endif
 255
 256       iterator
 257       insert(const_iterator __position, const value_type& __x)
 258       {
 259         __glibcxx_check_insert(__position);
 260         return iterator(_Base::insert(__position.base(), __x), this);
 261       }
 262
 263 #if __cplusplus >= 201103L
 264       iterator
 265       insert(const_iterator __position, value_type&& __x)
 266       {
 267         __glibcxx_check_insert(__position);
 268         return { _Base::insert(__position.base(), std::move(__x)), this };
 269       }
 270 #endif
 271
 272       template<typename _InputIterator>
 273         void
 274         insert(_InputIterator __first, _InputIterator __last)
 275         {
 276           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 277           __glibcxx_check_valid_range2(__first, __last, __dist);
 278
 279           if (__dist.second >= __gnu_debug::__dp_sign)
 280             _Base::insert(__gnu_debug::__unsafe(__first),
 281                           __gnu_debug::__unsafe(__last));
 282           else
 283             _Base::insert(__first, __last);
 284         }
 285
 286 #if __cplusplus >= 201103L
 287       void
 288       insert(initializer_list<value_type> __l)
 289       { _Base::insert(__l); }
 290 #endif
 291
 292 #if __cplusplus > 201402L
 293       using node_type = typename _Base::node_type;
 294
 295       node_type
 296       extract(const_iterator __position)
 297       {
 298         __glibcxx_check_erase(__position);
 299         this->_M_invalidate_if(_Equal(__position.base()));
 300         return _Base::extract(__position.base());
 301       }
 302
 303       node_type
 304       extract(const key_type& __key)
 305       {
 306         const auto __position = find(__key);
 307         if (__position != end())
 308           return extract(__position);
 309         return {};
 310       }
 311
 312       iterator
 313       insert(node_type&& __nh)
 314       { return { _Base::insert(std::move(__nh)), this }; }
 315
 316       iterator
 317       insert(const_iterator __hint, node_type&& __nh)
 318       {
 319         __glibcxx_check_insert(__hint);
 320         return { _Base::insert(__hint.base(), std::move(__nh)), this };
 321       }
 322
 323       using _Base::merge;
 324 #endif // C++17
 325
 326 #if __cplusplus >= 201103L
 327       _GLIBCXX_ABI_TAG_CXX11
 328       iterator
 329       erase(const_iterator __position)
 330       {
 331         __glibcxx_check_erase(__position);
 332         this->_M_invalidate_if(_Equal(__position.base()));
 333         return { _Base::erase(__position.base()), this };
 334       }
 335 #else
 336       void
 337       erase(iterator __position)
 338       {
 339         __glibcxx_check_erase(__position);
 340         this->_M_invalidate_if(_Equal(__position.base()));
 341         _Base::erase(__position.base());
 342       }
 343 #endif
 344
 345       size_type
 346       erase(const key_type& __x)
 347       {
 348         std::pair<_Base_iterator, _Base_iterator> __victims =
 349           _Base::equal_range(__x);
 350         size_type __count = 0;
 351         _Base_iterator __victim = __victims.first;
 352         while (__victim != __victims.second)
 353           {
 354             this->_M_invalidate_if(_Equal(__victim));
 355             _Base::erase(__victim++);
 356             ++__count;
 357           }
 358         return __count;
 359       }
 360
 361 #if __cplusplus >= 201103L
 362       _GLIBCXX_ABI_TAG_CXX11
 363       iterator
 364       erase(const_iterator __first, const_iterator __last)
 365       {
 366         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 367         // 151. can't currently clear() empty container
 368         __glibcxx_check_erase_range(__first, __last);
 369         for (_Base_const_iterator __victim = __first.base();
 370              __victim != __last.base(); ++__victim)
 371           {
 372             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
 373                                   _M_message(__gnu_debug::__msg_valid_range)
 374                                   ._M_iterator(__first, "first")
 375                                   ._M_iterator(__last, "last"));
 376             this->_M_invalidate_if(_Equal(__victim));
 377           }
 378
 379         return { _Base::erase(__first.base(), __last.base()), this };
 380       }
 381 #else
 382       void
 383       erase(iterator __first, iterator __last)
 384       {
 385         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 386         // 151. can't currently clear() empty container
 387         __glibcxx_check_erase_range(__first, __last);
 388         for (_Base_iterator __victim = __first.base();
 389              __victim != __last.base(); ++__victim)
 390           {
 391             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 392                                   _M_message(__gnu_debug::__msg_valid_range)
 393                                   ._M_iterator(__first, "first")
 394                                   ._M_iterator(__last, "last"));
 395             this->_M_invalidate_if(_Equal(__victim));
 396           }
 397         _Base::erase(__first.base(), __last.base());
 398       }
 399 #endif
 400
 401       void
 402       swap(multiset& __x)
 403       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
 404       {
 405         _Safe::_M_swap(__x);
 406         _Base::swap(__x);
 407       }
 408
 409       void
 410       clear() _GLIBCXX_NOEXCEPT
 411       {
 412         this->_M_invalidate_all();
 413         _Base::clear();
 414       }
 415
 416       // observers:
 417       using _Base::key_comp;
 418       using _Base::value_comp;
 419
 420       // multiset operations:
 421       iterator
 422       find(const key_type& __x)
 423       { return iterator(_Base::find(__x), this); }
 424
 425       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 426       // 214. set::find() missing const overload
 427       const_iterator
 428       find(const key_type& __x) const
 429       { return const_iterator(_Base::find(__x), this); }
 430
 431 #if __cplusplus > 201103L
 432       template<typename _Kt,
 433                typename _Req =
 434                  typename __has_is_transparent<_Compare, _Kt>::type>
 435         iterator
 436         find(const _Kt& __x)
 437         { return { _Base::find(__x), this }; }
 438
 439       template<typename _Kt,
 440                typename _Req =
 441                  typename __has_is_transparent<_Compare, _Kt>::type>
 442         const_iterator
 443         find(const _Kt& __x) const
 444         { return { _Base::find(__x), this }; }
 445 #endif
 446
 447       using _Base::count;
 448
 449       iterator
 450       lower_bound(const key_type& __x)
 451       { return iterator(_Base::lower_bound(__x), this); }
 452
 453       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 454       // 214. set::find() missing const overload
 455       const_iterator
 456       lower_bound(const key_type& __x) const
 457       { return const_iterator(_Base::lower_bound(__x), this); }
 458
 459 #if __cplusplus > 201103L
 460       template<typename _Kt,
 461                typename _Req =
 462                  typename __has_is_transparent<_Compare, _Kt>::type>
 463         iterator
 464         lower_bound(const _Kt& __x)
 465         { return { _Base::lower_bound(__x), this }; }
 466
 467       template<typename _Kt,
 468                typename _Req =
 469                  typename __has_is_transparent<_Compare, _Kt>::type>
 470         const_iterator
 471         lower_bound(const _Kt& __x) const
 472         { return { _Base::lower_bound(__x), this }; }
 473 #endif
 474
 475       iterator
 476       upper_bound(const key_type& __x)
 477       { return iterator(_Base::upper_bound(__x), this); }
 478
 479       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 480       // 214. set::find() missing const overload
 481       const_iterator
 482       upper_bound(const key_type& __x) const
 483       { return const_iterator(_Base::upper_bound(__x), this); }
 484
 485 #if __cplusplus > 201103L
 486       template<typename _Kt,
 487                typename _Req =
 488                  typename __has_is_transparent<_Compare, _Kt>::type>
 489         iterator
 490         upper_bound(const _Kt& __x)
 491         { return { _Base::upper_bound(__x), this }; }
 492
 493       template<typename _Kt,
 494                typename _Req =
 495                  typename __has_is_transparent<_Compare, _Kt>::type>
 496         const_iterator
 497         upper_bound(const _Kt& __x) const
 498         { return { _Base::upper_bound(__x), this }; }
 499 #endif
 500
 501       std::pair<iterator,iterator>
 502       equal_range(const key_type& __x)
 503       {
 504         std::pair<_Base_iterator, _Base_iterator> __res =
 505           _Base::equal_range(__x);
 506         return std::make_pair(iterator(__res.first, this),
 507                               iterator(__res.second, this));
 508       }
 509
 510       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 511       // 214. set::find() missing const overload
 512       std::pair<const_iterator,const_iterator>
 513       equal_range(const key_type& __x) const
 514       {
 515         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 516           _Base::equal_range(__x);
 517         return std::make_pair(const_iterator(__res.first, this),
 518                               const_iterator(__res.second, this));
 519       }
 520
 521 #if __cplusplus > 201103L
 522       template<typename _Kt,
 523                typename _Req =
 524                  typename __has_is_transparent<_Compare, _Kt>::type>
 525         std::pair<iterator, iterator>
 526         equal_range(const _Kt& __x)
 527         {
 528           auto __res = _Base::equal_range(__x);
 529           return { { __res.first, this }, { __res.second, this } };
 530         }
 531
 532       template<typename _Kt,
 533                typename _Req =
 534                  typename __has_is_transparent<_Compare, _Kt>::type>
 535         std::pair<const_iterator, const_iterator>
 536         equal_range(const _Kt& __x) const
 537         {
 538           auto __res = _Base::equal_range(__x);
 539           return { { __res.first, this }, { __res.second, this } };
 540         }
 541 #endif
 542
 543       _Base&
 544       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 545
 546       const _Base&
 547       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 548     };
 549
 550 #if __cpp_deduction_guides >= 201606
 551
 552   template<typename _InputIterator,
 553            typename _Compare =
 554              less<typename iterator_traits<_InputIterator>::value_type>,
 555            typename _Allocator =
 556              allocator<typename iterator_traits<_InputIterator>::value_type>,
 557            typename = _RequireInputIter<_InputIterator>,
 558            typename = _RequireNotAllocator<_Compare>,
 559            typename = _RequireAllocator<_Allocator>>
 560     multiset(_InputIterator, _InputIterator,
 561              _Compare = _Compare(), _Allocator = _Allocator())
 562     -> multiset<typename iterator_traits<_InputIterator>::value_type,
 563                 _Compare, _Allocator>;
 564
 565   template<typename _Key,
 566            typename _Compare = less<_Key>,
 567            typename _Allocator = allocator<_Key>,
 568            typename = _RequireNotAllocator<_Compare>,
 569            typename = _RequireAllocator<_Allocator>>
 570     multiset(initializer_list<_Key>,
 571              _Compare = _Compare(), _Allocator = _Allocator())
 572     -> multiset<_Key, _Compare, _Allocator>;
 573
 574   template<typename _InputIterator, typename _Allocator,
 575            typename = _RequireInputIter<_InputIterator>,
 576            typename = _RequireAllocator<_Allocator>>
 577     multiset(_InputIterator, _InputIterator, _Allocator)
 578     -> multiset<typename iterator_traits<_InputIterator>::value_type,
 579                 less<typename iterator_traits<_InputIterator>::value_type>,
 580                 _Allocator>;
 581
 582   template<typename _Key, typename _Allocator,
 583            typename = _RequireAllocator<_Allocator>>
 584     multiset(initializer_list<_Key>, _Allocator)
 585     -> multiset<_Key, less<_Key>, _Allocator>;
 586
 587 #endif
 588
 589   template<typename _Key, typename _Compare, typename _Allocator>
 590     inline bool
 591     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
 592                const multiset<_Key, _Compare, _Allocator>& __rhs)
 593     { return __lhs._M_base() == __rhs._M_base(); }
 594
 595   template<typename _Key, typename _Compare, typename _Allocator>
 596     inline bool
 597     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 598                const multiset<_Key, _Compare, _Allocator>& __rhs)
 599     { return __lhs._M_base() != __rhs._M_base(); }
 600
 601   template<typename _Key, typename _Compare, typename _Allocator>
 602     inline bool
 603     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
 604               const multiset<_Key, _Compare, _Allocator>& __rhs)
 605     { return __lhs._M_base() < __rhs._M_base(); }
 606
 607   template<typename _Key, typename _Compare, typename _Allocator>
 608     inline bool
 609     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 610                const multiset<_Key, _Compare, _Allocator>& __rhs)
 611     { return __lhs._M_base() <= __rhs._M_base(); }
 612
 613   template<typename _Key, typename _Compare, typename _Allocator>
 614     inline bool
 615     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 616                const multiset<_Key, _Compare, _Allocator>& __rhs)
 617     { return __lhs._M_base() >= __rhs._M_base(); }
 618
 619   template<typename _Key, typename _Compare, typename _Allocator>
 620     inline bool
 621     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
 622               const multiset<_Key, _Compare, _Allocator>& __rhs)
 623     { return __lhs._M_base() > __rhs._M_base(); }
 624
 625   template<typename _Key, typename _Compare, typename _Allocator>
 626     void
 627     swap(multiset<_Key, _Compare, _Allocator>& __x,
 628          multiset<_Key, _Compare, _Allocator>& __y)
 629     _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
 630     { return __x.swap(__y); }
 631
 632 } // namespace __debug
 633
 634 #if __cplusplus > 201703L
 635 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 636 namespace ranges::__detail
 637 {
 638   template<typename _Tp> extern inline const bool __enable_view_impl;
 639   template<typename _Key, typename _Compare, typename _Alloc>
 640     inline constexpr bool
 641       __enable_view_impl<std::__debug::multiset<_Key, _Compare, _Alloc>>
 642         = false;
 643 } // namespace ranges::__detail
 644 _GLIBCXX_END_NAMESPACE_VERSION
 645 #endif // C++20
 646 } // namespace std
 647
 648 #endif