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

   1 // Debugging multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2015 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 >= 201103L
 291       iterator
 292       erase(const_iterator __position)
 293       {
 294         __glibcxx_check_erase(__position);
 295         this->_M_invalidate_if(_Equal(__position.base()));
 296         return iterator(_Base::erase(__position.base()), this);
 297       }
 298 #else
 299       void
 300       erase(iterator __position)
 301       {
 302         __glibcxx_check_erase(__position);
 303         this->_M_invalidate_if(_Equal(__position.base()));
 304         _Base::erase(__position.base());
 305       }
 306 #endif
 307
 308       size_type
 309       erase(const key_type& __x)
 310       {
 311         std::pair<_Base_iterator, _Base_iterator> __victims =
 312           _Base::equal_range(__x);
 313         size_type __count = 0;
 314         _Base_iterator __victim = __victims.first;
 315         while (__victim != __victims.second)
 316           {
 317             this->_M_invalidate_if(_Equal(__victim));
 318             _Base::erase(__victim++);
 319             ++__count;
 320           }
 321         return __count;
 322       }
 323
 324 #if __cplusplus >= 201103L
 325       iterator
 326       erase(const_iterator __first, const_iterator __last)
 327       {
 328         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 329         // 151. can't currently clear() empty container
 330         __glibcxx_check_erase_range(__first, __last);
 331         for (_Base_const_iterator __victim = __first.base();
 332              __victim != __last.base(); ++__victim)
 333           {
 334             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 335                                   _M_message(__gnu_debug::__msg_valid_range)
 336                                   ._M_iterator(__first, "first")
 337                                   ._M_iterator(__last, "last"));
 338             this->_M_invalidate_if(_Equal(__victim));
 339           }
 340         return iterator(_Base::erase(__first.base(), __last.base()), this);
 341       }
 342 #else
 343       void
 344       erase(iterator __first, iterator __last)
 345       {
 346         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 347         // 151. can't currently clear() empty container
 348         __glibcxx_check_erase_range(__first, __last);
 349         for (_Base_iterator __victim = __first.base();
 350              __victim != __last.base(); ++__victim)
 351           {
 352             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 353                                   _M_message(__gnu_debug::__msg_valid_range)
 354                                   ._M_iterator(__first, "first")
 355                                   ._M_iterator(__last, "last"));
 356             this->_M_invalidate_if(_Equal(__victim));
 357           }
 358         _Base::erase(__first.base(), __last.base());
 359       }
 360 #endif
 361
 362       void
 363       swap(multiset& __x)
 364 #if __cplusplus >= 201103L
 365         noexcept( noexcept(declval<_Base>().swap(__x)) )
 366 #endif
 367       {
 368         _Safe::_M_swap(__x);
 369         _Base::swap(__x);
 370       }
 371
 372       void
 373       clear() _GLIBCXX_NOEXCEPT
 374       {
 375         this->_M_invalidate_all();
 376         _Base::clear();
 377       }
 378
 379       // observers:
 380       using _Base::key_comp;
 381       using _Base::value_comp;
 382
 383       // multiset operations:
 384       iterator
 385       find(const key_type& __x)
 386       { return iterator(_Base::find(__x), this); }
 387
 388       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 389       // 214. set::find() missing const overload
 390       const_iterator
 391       find(const key_type& __x) const
 392       { return const_iterator(_Base::find(__x), this); }
 393
 394 #if __cplusplus > 201103L
 395       template<typename _Kt,
 396                typename _Req =
 397                  typename __has_is_transparent<_Compare, _Kt>::type>
 398         iterator
 399         find(const _Kt& __x)
 400         { return { _Base::find(__x), this }; }
 401
 402       template<typename _Kt,
 403                typename _Req =
 404                  typename __has_is_transparent<_Compare, _Kt>::type>
 405         const_iterator
 406         find(const _Kt& __x) const
 407         { return { _Base::find(__x), this }; }
 408 #endif
 409
 410       using _Base::count;
 411
 412       iterator
 413       lower_bound(const key_type& __x)
 414       { return iterator(_Base::lower_bound(__x), this); }
 415
 416       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 417       // 214. set::find() missing const overload
 418       const_iterator
 419       lower_bound(const key_type& __x) const
 420       { return const_iterator(_Base::lower_bound(__x), this); }
 421
 422 #if __cplusplus > 201103L
 423       template<typename _Kt,
 424                typename _Req =
 425                  typename __has_is_transparent<_Compare, _Kt>::type>
 426         iterator
 427         lower_bound(const _Kt& __x)
 428         { return { _Base::lower_bound(__x), this }; }
 429
 430       template<typename _Kt,
 431                typename _Req =
 432                  typename __has_is_transparent<_Compare, _Kt>::type>
 433         const_iterator
 434         lower_bound(const _Kt& __x) const
 435         { return { _Base::lower_bound(__x), this }; }
 436 #endif
 437
 438       iterator
 439       upper_bound(const key_type& __x)
 440       { return iterator(_Base::upper_bound(__x), this); }
 441
 442       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 443       // 214. set::find() missing const overload
 444       const_iterator
 445       upper_bound(const key_type& __x) const
 446       { return const_iterator(_Base::upper_bound(__x), this); }
 447
 448 #if __cplusplus > 201103L
 449       template<typename _Kt,
 450                typename _Req =
 451                  typename __has_is_transparent<_Compare, _Kt>::type>
 452         iterator
 453         upper_bound(const _Kt& __x)
 454         { return { _Base::upper_bound(__x), this }; }
 455
 456       template<typename _Kt,
 457                typename _Req =
 458                  typename __has_is_transparent<_Compare, _Kt>::type>
 459         const_iterator
 460         upper_bound(const _Kt& __x) const
 461         { return { _Base::upper_bound(__x), this }; }
 462 #endif
 463
 464       std::pair<iterator,iterator>
 465       equal_range(const key_type& __x)
 466       {
 467         std::pair<_Base_iterator, _Base_iterator> __res =
 468           _Base::equal_range(__x);
 469         return std::make_pair(iterator(__res.first, this),
 470                               iterator(__res.second, this));
 471       }
 472
 473       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 474       // 214. set::find() missing const overload
 475       std::pair<const_iterator,const_iterator>
 476       equal_range(const key_type& __x) const
 477       {
 478         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 479           _Base::equal_range(__x);
 480         return std::make_pair(const_iterator(__res.first, this),
 481                               const_iterator(__res.second, this));
 482       }
 483
 484 #if __cplusplus > 201103L
 485       template<typename _Kt,
 486                typename _Req =
 487                  typename __has_is_transparent<_Compare, _Kt>::type>
 488         std::pair<iterator, iterator>
 489         equal_range(const _Kt& __x)
 490         {
 491           auto __res = _Base::equal_range(__x);
 492           return { { __res.first, this }, { __res.second, this } };
 493         }
 494
 495       template<typename _Kt,
 496                typename _Req =
 497                  typename __has_is_transparent<_Compare, _Kt>::type>
 498         std::pair<const_iterator, const_iterator>
 499         equal_range(const _Kt& __x) const
 500         {
 501           auto __res = _Base::equal_range(__x);
 502           return { { __res.first, this }, { __res.second, this } };
 503         }
 504 #endif
 505
 506       _Base&
 507       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 508
 509       const _Base&
 510       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 511     };
 512
 513   template<typename _Key, typename _Compare, typename _Allocator>
 514     inline bool
 515     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
 516                const multiset<_Key, _Compare, _Allocator>& __rhs)
 517     { return __lhs._M_base() == __rhs._M_base(); }
 518
 519   template<typename _Key, typename _Compare, typename _Allocator>
 520     inline bool
 521     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 522                const multiset<_Key, _Compare, _Allocator>& __rhs)
 523     { return __lhs._M_base() != __rhs._M_base(); }
 524
 525   template<typename _Key, typename _Compare, typename _Allocator>
 526     inline bool
 527     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
 528               const multiset<_Key, _Compare, _Allocator>& __rhs)
 529     { return __lhs._M_base() < __rhs._M_base(); }
 530
 531   template<typename _Key, typename _Compare, typename _Allocator>
 532     inline bool
 533     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 534                const multiset<_Key, _Compare, _Allocator>& __rhs)
 535     { return __lhs._M_base() <= __rhs._M_base(); }
 536
 537   template<typename _Key, typename _Compare, typename _Allocator>
 538     inline bool
 539     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 540                const multiset<_Key, _Compare, _Allocator>& __rhs)
 541     { return __lhs._M_base() >= __rhs._M_base(); }
 542
 543   template<typename _Key, typename _Compare, typename _Allocator>
 544     inline bool
 545     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
 546               const multiset<_Key, _Compare, _Allocator>& __rhs)
 547     { return __lhs._M_base() > __rhs._M_base(); }
 548
 549   template<typename _Key, typename _Compare, typename _Allocator>
 550     void
 551     swap(multiset<_Key, _Compare, _Allocator>& __x,
 552          multiset<_Key, _Compare, _Allocator>& __y)
 553     { return __x.swap(__y); }
 554
 555 } // namespace __debug
 556 } // namespace std
 557
 558 #endif