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

   1 // Debugging multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2014 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_iterator.h>
  34 #include <utility>
  35
  36 namespace std _GLIBCXX_VISIBILITY(default)
  37 {
  38 namespace __debug
  39 {
  40   /// Class std::multiset with safety/checking/debug instrumentation.
  41   template<typename _Key, typename _Compare = std::less<_Key>,
  42            typename _Allocator = std::allocator<_Key> >
  43     class multiset
  44     : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
  45       public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
  46     {
  47       typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
  48
  49       typedef typename _Base::const_iterator _Base_const_iterator;
  50       typedef typename _Base::iterator _Base_iterator;
  51       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
  52
  53 #if __cplusplus >= 201103L
  54       typedef __gnu_cxx::__alloc_traits<typename
  55                                         _Base::allocator_type> _Alloc_traits;
  56 #endif
  57     public:
  58       // types:
  59       typedef _Key                                   key_type;
  60       typedef _Key                                   value_type;
  61       typedef _Compare                               key_compare;
  62       typedef _Compare                               value_compare;
  63       typedef _Allocator                             allocator_type;
  64       typedef typename _Base::reference              reference;
  65       typedef typename _Base::const_reference        const_reference;
  66
  67       typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
  68       iterator;
  69       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  70                                           multiset> const_iterator;
  71
  72       typedef typename _Base::size_type              size_type;
  73       typedef typename _Base::difference_type        difference_type;
  74       typedef typename _Base::pointer                pointer;
  75       typedef typename _Base::const_pointer          const_pointer;
  76       typedef std::reverse_iterator<iterator>        reverse_iterator;
  77       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
  78
  79       // 23.3.3.1 construct/copy/destroy:
  80       explicit multiset(const _Compare& __comp = _Compare(),
  81                         const _Allocator& __a = _Allocator())
  82       : _Base(__comp, __a) { }
  83
  84       template<typename _InputIterator>
  85         multiset(_InputIterator __first, _InputIterator __last,
  86                  const _Compare& __comp = _Compare(),
  87                  const _Allocator& __a = _Allocator())
  88         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  89                                                                      __last)),
  90                 __gnu_debug::__base(__last),
  91                 __comp, __a) { }
  92
  93       multiset(const multiset& __x)
  94       : _Base(__x) { }
  95
  96       multiset(const _Base& __x)
  97       : _Base(__x) { }
  98
  99 #if __cplusplus >= 201103L
 100       multiset(multiset&& __x)
 101       noexcept(is_nothrow_copy_constructible<_Compare>::value)
 102       : _Base(std::move(__x))
 103       { this->_M_swap(__x); }
 104
 105       multiset(initializer_list<value_type> __l,
 106                const _Compare& __comp = _Compare(),
 107                const allocator_type& __a = allocator_type())
 108       : _Base(__l, __comp, __a) { }
 109
 110       explicit
 111       multiset(const allocator_type& __a)
 112       : _Base(__a) { }
 113
 114       multiset(const multiset& __m, const allocator_type& __a)
 115       : _Base(__m, __a) { }
 116
 117       multiset(multiset&& __m, const allocator_type& __a)
 118       : _Base(std::move(__m._M_base()), __a) { }
 119
 120       multiset(initializer_list<value_type> __l, const allocator_type& __a)
 121         : _Base(__l, __a)
 122       { }
 123
 124       template<typename _InputIterator>
 125         multiset(_InputIterator __first, _InputIterator __last,
 126                  const allocator_type& __a)
 127           : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 128                                                                        __last)),
 129                   __gnu_debug::__base(__last), __a)
 130         { }
 131 #endif
 132
 133       ~multiset() _GLIBCXX_NOEXCEPT { }
 134
 135       multiset&
 136       operator=(const multiset& __x)
 137       {
 138         _M_base() = __x;
 139         this->_M_invalidate_all();
 140         return *this;
 141       }
 142
 143 #if __cplusplus >= 201103L
 144       multiset&
 145       operator=(multiset&& __x)
 146       noexcept(_Alloc_traits::_S_nothrow_move())
 147       {
 148         __glibcxx_check_self_move_assign(__x);
 149         bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
 150             || __x.get_allocator() == this->get_allocator();
 151         _M_base() = std::move(__x._M_base());
 152         if (xfer_memory)
 153           this->_M_swap(__x);
 154         else
 155           this->_M_invalidate_all();
 156         __x._M_invalidate_all();
 157         return *this;
 158       }
 159
 160       multiset&
 161       operator=(initializer_list<value_type> __l)
 162       {
 163         _M_base() = __l;
 164         this->_M_invalidate_all();
 165         return *this;
 166       }
 167 #endif
 168
 169       using _Base::get_allocator;
 170
 171       // iterators:
 172       iterator
 173       begin() _GLIBCXX_NOEXCEPT
 174       { return iterator(_Base::begin(), this); }
 175
 176       const_iterator
 177       begin() const _GLIBCXX_NOEXCEPT
 178       { return const_iterator(_Base::begin(), this); }
 179
 180       iterator
 181       end() _GLIBCXX_NOEXCEPT
 182       { return iterator(_Base::end(), this); }
 183
 184       const_iterator
 185       end() const _GLIBCXX_NOEXCEPT
 186       { return const_iterator(_Base::end(), this); }
 187
 188       reverse_iterator
 189       rbegin() _GLIBCXX_NOEXCEPT
 190       { return reverse_iterator(end()); }
 191
 192       const_reverse_iterator
 193       rbegin() const _GLIBCXX_NOEXCEPT
 194       { return const_reverse_iterator(end()); }
 195
 196       reverse_iterator
 197       rend() _GLIBCXX_NOEXCEPT
 198       { return reverse_iterator(begin()); }
 199
 200       const_reverse_iterator
 201       rend() const _GLIBCXX_NOEXCEPT
 202       { return const_reverse_iterator(begin()); }
 203
 204 #if __cplusplus >= 201103L
 205       const_iterator
 206       cbegin() const noexcept
 207       { return const_iterator(_Base::begin(), this); }
 208
 209       const_iterator
 210       cend() const noexcept
 211       { return const_iterator(_Base::end(), this); }
 212
 213       const_reverse_iterator
 214       crbegin() const noexcept
 215       { return const_reverse_iterator(end()); }
 216
 217       const_reverse_iterator
 218       crend() const noexcept
 219       { return const_reverse_iterator(begin()); }
 220 #endif
 221
 222       // capacity:
 223       using _Base::empty;
 224       using _Base::size;
 225       using _Base::max_size;
 226
 227       // modifiers:
 228 #if __cplusplus >= 201103L
 229       template<typename... _Args>
 230         iterator
 231         emplace(_Args&&... __args)
 232         {
 233           return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
 234         }
 235
 236       template<typename... _Args>
 237         iterator
 238         emplace_hint(const_iterator __pos, _Args&&... __args)
 239         {
 240           __glibcxx_check_insert(__pos);
 241           return iterator(_Base::emplace_hint(__pos.base(),
 242                                               std::forward<_Args>(__args)...),
 243                           this);
 244         }
 245 #endif
 246
 247       iterator
 248       insert(const value_type& __x)
 249       { return iterator(_Base::insert(__x), this); }
 250
 251 #if __cplusplus >= 201103L
 252       iterator
 253       insert(value_type&& __x)
 254       { return iterator(_Base::insert(std::move(__x)), this); }
 255 #endif
 256
 257       iterator
 258       insert(const_iterator __position, const value_type& __x)
 259       {
 260         __glibcxx_check_insert(__position);
 261         return iterator(_Base::insert(__position.base(), __x), this);
 262       }
 263
 264 #if __cplusplus >= 201103L
 265       iterator
 266       insert(const_iterator __position, value_type&& __x)
 267       {
 268         __glibcxx_check_insert(__position);
 269         return iterator(_Base::insert(__position.base(), std::move(__x)),
 270                         this);
 271       }
 272 #endif
 273
 274       template<typename _InputIterator>
 275         void
 276         insert(_InputIterator __first, _InputIterator __last)
 277         {
 278           __glibcxx_check_valid_range(__first, __last);
 279           _Base::insert(__gnu_debug::__base(__first),
 280                         __gnu_debug::__base(__last));
 281         }
 282
 283 #if __cplusplus >= 201103L
 284       void
 285       insert(initializer_list<value_type> __l)
 286       { _Base::insert(__l); }
 287 #endif
 288
 289 #if __cplusplus >= 201103L
 290       iterator
 291       erase(const_iterator __position)
 292       {
 293         __glibcxx_check_erase(__position);
 294         this->_M_invalidate_if(_Equal(__position.base()));
 295         return iterator(_Base::erase(__position.base()), this);
 296       }
 297 #else
 298       void
 299       erase(iterator __position)
 300       {
 301         __glibcxx_check_erase(__position);
 302         this->_M_invalidate_if(_Equal(__position.base()));
 303         _Base::erase(__position.base());
 304       }
 305 #endif
 306
 307       size_type
 308       erase(const key_type& __x)
 309       {
 310         std::pair<_Base_iterator, _Base_iterator> __victims =
 311           _Base::equal_range(__x);
 312         size_type __count = 0;
 313         _Base_iterator __victim = __victims.first;
 314         while (__victim != __victims.second)
 315           {
 316             this->_M_invalidate_if(_Equal(__victim));
 317             _Base::erase(__victim++);
 318             ++__count;
 319           }
 320         return __count;
 321       }
 322
 323 #if __cplusplus >= 201103L
 324       iterator
 325       erase(const_iterator __first, const_iterator __last)
 326       {
 327         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 328         // 151. can't currently clear() empty container
 329         __glibcxx_check_erase_range(__first, __last);
 330         for (_Base_const_iterator __victim = __first.base();
 331              __victim != __last.base(); ++__victim)
 332           {
 333             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 334                                   _M_message(__gnu_debug::__msg_valid_range)
 335                                   ._M_iterator(__first, "first")
 336                                   ._M_iterator(__last, "last"));
 337             this->_M_invalidate_if(_Equal(__victim));
 338           }
 339         return iterator(_Base::erase(__first.base(), __last.base()), this);
 340       }
 341 #else
 342       void
 343       erase(iterator __first, iterator __last)
 344       {
 345         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 346         // 151. can't currently clear() empty container
 347         __glibcxx_check_erase_range(__first, __last);
 348         for (_Base_iterator __victim = __first.base();
 349              __victim != __last.base(); ++__victim)
 350           {
 351             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 352                                   _M_message(__gnu_debug::__msg_valid_range)
 353                                   ._M_iterator(__first, "first")
 354                                   ._M_iterator(__last, "last"));
 355             this->_M_invalidate_if(_Equal(__victim));
 356           }
 357         _Base::erase(__first.base(), __last.base());
 358       }
 359 #endif
 360
 361       void
 362       swap(multiset& __x)
 363 #if __cplusplus >= 201103L
 364       noexcept(_Alloc_traits::_S_nothrow_swap())
 365 #endif
 366       {
 367 #if __cplusplus >= 201103L
 368         if (!_Alloc_traits::_S_propagate_on_swap())
 369           __glibcxx_check_equal_allocs(__x);
 370 #endif
 371         _Base::swap(__x);
 372         this->_M_swap(__x);
 373       }
 374
 375       void
 376       clear() _GLIBCXX_NOEXCEPT
 377       {
 378         this->_M_invalidate_all();
 379         _Base::clear();
 380       }
 381
 382       // observers:
 383       using _Base::key_comp;
 384       using _Base::value_comp;
 385
 386       // multiset operations:
 387       iterator
 388       find(const key_type& __x)
 389       { return iterator(_Base::find(__x), this); }
 390
 391       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 392       // 214. set::find() missing const overload
 393       const_iterator
 394       find(const key_type& __x) const
 395       { return const_iterator(_Base::find(__x), this); }
 396
 397       using _Base::count;
 398
 399       iterator
 400       lower_bound(const key_type& __x)
 401       { return iterator(_Base::lower_bound(__x), this); }
 402
 403       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 404       // 214. set::find() missing const overload
 405       const_iterator
 406       lower_bound(const key_type& __x) const
 407       { return const_iterator(_Base::lower_bound(__x), this); }
 408
 409       iterator
 410       upper_bound(const key_type& __x)
 411       { return iterator(_Base::upper_bound(__x), this); }
 412
 413       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 414       // 214. set::find() missing const overload
 415       const_iterator
 416       upper_bound(const key_type& __x) const
 417       { return const_iterator(_Base::upper_bound(__x), this); }
 418
 419       std::pair<iterator,iterator>
 420       equal_range(const key_type& __x)
 421       {
 422         std::pair<_Base_iterator, _Base_iterator> __res =
 423           _Base::equal_range(__x);
 424         return std::make_pair(iterator(__res.first, this),
 425                               iterator(__res.second, this));
 426       }
 427
 428       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 429       // 214. set::find() missing const overload
 430       std::pair<const_iterator,const_iterator>
 431       equal_range(const key_type& __x) const
 432       {
 433         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 434           _Base::equal_range(__x);
 435         return std::make_pair(const_iterator(__res.first, this),
 436                               const_iterator(__res.second, this));
 437       }
 438
 439       _Base&
 440       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 441
 442       const _Base&
 443       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 444
 445     private:
 446       void
 447       _M_invalidate_all()
 448       {
 449         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 450         this->_M_invalidate_if(_Not_equal(_Base::end()));
 451       }
 452     };
 453
 454   template<typename _Key, typename _Compare, typename _Allocator>
 455     inline bool
 456     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
 457                const multiset<_Key, _Compare, _Allocator>& __rhs)
 458     { return __lhs._M_base() == __rhs._M_base(); }
 459
 460   template<typename _Key, typename _Compare, typename _Allocator>
 461     inline bool
 462     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 463                const multiset<_Key, _Compare, _Allocator>& __rhs)
 464     { return __lhs._M_base() != __rhs._M_base(); }
 465
 466   template<typename _Key, typename _Compare, typename _Allocator>
 467     inline bool
 468     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
 469               const multiset<_Key, _Compare, _Allocator>& __rhs)
 470     { return __lhs._M_base() < __rhs._M_base(); }
 471
 472   template<typename _Key, typename _Compare, typename _Allocator>
 473     inline bool
 474     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 475                const multiset<_Key, _Compare, _Allocator>& __rhs)
 476     { return __lhs._M_base() <= __rhs._M_base(); }
 477
 478   template<typename _Key, typename _Compare, typename _Allocator>
 479     inline bool
 480     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 481                const multiset<_Key, _Compare, _Allocator>& __rhs)
 482     { return __lhs._M_base() >= __rhs._M_base(); }
 483
 484   template<typename _Key, typename _Compare, typename _Allocator>
 485     inline bool
 486     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
 487               const multiset<_Key, _Compare, _Allocator>& __rhs)
 488     { return __lhs._M_base() > __rhs._M_base(); }
 489
 490   template<typename _Key, typename _Compare, typename _Allocator>
 491     void
 492     swap(multiset<_Key, _Compare, _Allocator>& __x,
 493          multiset<_Key, _Compare, _Allocator>& __y)
 494     { return __x.swap(__y); }
 495
 496 } // namespace __debug
 497 } // namespace std
 498
 499 #endif