contrib/gcc-8.0/libstdc++-v3/include/debug/multiset.h

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