l4/pkg/l4re-core/libstdc++-v3/contrib/libstdc++-v3-4.8/include/debug/multiset.h

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