l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/include/debug/multiset.h

   1 // Debugging multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /** @file debug/multiset.h
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_MULTISET_H
  31 #define _GLIBCXX_DEBUG_MULTISET_H 1
  32
  33 #include <debug/safe_sequence.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 _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
  46       public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
  47     {
  48       typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
  49       typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
  50
  51       typedef typename _Base::const_iterator _Base_const_iterator;
  52       typedef typename _Base::iterator _Base_iterator;
  53       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
  54     public:
  55       // types:
  56       typedef _Key                                   key_type;
  57       typedef _Key                                   value_type;
  58       typedef _Compare                               key_compare;
  59       typedef _Compare                               value_compare;
  60       typedef _Allocator                             allocator_type;
  61       typedef typename _Base::reference              reference;
  62       typedef typename _Base::const_reference        const_reference;
  63
  64       typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
  65       iterator;
  66       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  67                                           multiset> const_iterator;
  68
  69       typedef typename _Base::size_type              size_type;
  70       typedef typename _Base::difference_type        difference_type;
  71       typedef typename _Base::pointer                pointer;
  72       typedef typename _Base::const_pointer          const_pointer;
  73       typedef std::reverse_iterator<iterator>        reverse_iterator;
  74       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
  75
  76       // 23.3.3.1 construct/copy/destroy:
  77       explicit multiset(const _Compare& __comp = _Compare(),
  78                         const _Allocator& __a = _Allocator())
  79       : _Base(__comp, __a) { }
  80
  81       template<typename _InputIterator>
  82         multiset(_InputIterator __first, _InputIterator __last,
  83                  const _Compare& __comp = _Compare(),
  84                  const _Allocator& __a = _Allocator())
  85         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  86                                                                      __last)),
  87                 __gnu_debug::__base(__last),
  88                 __comp, __a) { }
  89
  90       multiset(const multiset& __x)
  91       : _Base(__x), _Safe_base() { }
  92
  93       multiset(const _Base& __x)
  94       : _Base(__x), _Safe_base() { }
  95
  96 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  97       multiset(multiset&& __x)
  98       : _Base(std::move(__x)), _Safe_base()
  99       { this->_M_swap(__x); }
 100
 101       multiset(initializer_list<value_type> __l,
 102                const _Compare& __comp = _Compare(),
 103                const allocator_type& __a = allocator_type())
 104       : _Base(__l, __comp, __a), _Safe_base() { }
 105 #endif
 106
 107       ~multiset() { }
 108
 109       multiset&
 110       operator=(const multiset& __x)
 111       {
 112         *static_cast<_Base*>(this) = __x;
 113         this->_M_invalidate_all();
 114         return *this;
 115       }
 116
 117 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 118       multiset&
 119       operator=(multiset&& __x)
 120       {
 121         // NB: DR 1204.
 122         // NB: DR 675.
 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()
 142       { return iterator(_Base::begin(), this); }
 143
 144       const_iterator
 145       begin() const
 146       { return const_iterator(_Base::begin(), this); }
 147
 148       iterator
 149       end()
 150       { return iterator(_Base::end(), this); }
 151
 152       const_iterator
 153       end() const
 154       { return const_iterator(_Base::end(), this); }
 155
 156       reverse_iterator
 157       rbegin()
 158       { return reverse_iterator(end()); }
 159
 160       const_reverse_iterator
 161       rbegin() const
 162       { return const_reverse_iterator(end()); }
 163
 164       reverse_iterator
 165       rend()
 166       { return reverse_iterator(begin()); }
 167
 168       const_reverse_iterator
 169       rend() const
 170       { return const_reverse_iterator(begin()); }
 171
 172 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 173       const_iterator
 174       cbegin() const
 175       { return const_iterator(_Base::begin(), this); }
 176
 177       const_iterator
 178       cend() const
 179       { return const_iterator(_Base::end(), this); }
 180
 181       const_reverse_iterator
 182       crbegin() const
 183       { return const_reverse_iterator(end()); }
 184
 185       const_reverse_iterator
 186       crend() const
 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       iterator
 197       insert(const value_type& __x)
 198       { return iterator(_Base::insert(__x), this); }
 199
 200 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 201       iterator
 202       insert(value_type&& __x)
 203       { return iterator(_Base::insert(std::move(__x)), this); }
 204 #endif
 205
 206       iterator
 207       insert(const_iterator __position, const value_type& __x)
 208       {
 209         __glibcxx_check_insert(__position);
 210         return iterator(_Base::insert(__position.base(), __x), this);
 211       }
 212
 213 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 214       iterator
 215       insert(const_iterator __position, value_type&& __x)
 216       {
 217         __glibcxx_check_insert(__position);
 218         return iterator(_Base::insert(__position.base(), std::move(__x)),
 219                         this);
 220       }
 221 #endif
 222
 223       template<typename _InputIterator>
 224         void
 225         insert(_InputIterator __first, _InputIterator __last)
 226         {
 227           __glibcxx_check_valid_range(__first, __last);
 228           _Base::insert(__gnu_debug::__base(__first),
 229                         __gnu_debug::__base(__last));
 230         }
 231
 232 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 233       void
 234       insert(initializer_list<value_type> __l)
 235       { _Base::insert(__l); }
 236 #endif
 237
 238 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 239       iterator
 240       erase(const_iterator __position)
 241       {
 242         __glibcxx_check_erase(__position);
 243         this->_M_invalidate_if(_Equal(__position.base()));
 244         return iterator(_Base::erase(__position.base()), this);
 245       }
 246 #else
 247       void
 248       erase(iterator __position)
 249       {
 250         __glibcxx_check_erase(__position);
 251         this->_M_invalidate_if(_Equal(__position.base()));
 252         _Base::erase(__position.base());
 253       }
 254 #endif
 255
 256       size_type
 257       erase(const key_type& __x)
 258       {
 259         std::pair<_Base_iterator, _Base_iterator> __victims =
 260           _Base::equal_range(__x);
 261         size_type __count = 0;
 262         _Base_iterator __victim = __victims.first;
 263         while (__victim != __victims.second)
 264           {
 265             this->_M_invalidate_if(_Equal(__victim));
 266             _Base::erase(__victim++);
 267             ++__count;
 268           }
 269         return __count;
 270       }
 271
 272 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 273       iterator
 274       erase(const_iterator __first, const_iterator __last)
 275       {
 276         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 277         // 151. can't currently clear() empty container
 278         __glibcxx_check_erase_range(__first, __last);
 279         for (_Base_const_iterator __victim = __first.base();
 280              __victim != __last.base(); ++__victim)
 281           {
 282             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 283                                   _M_message(__gnu_debug::__msg_valid_range)
 284                                   ._M_iterator(__first, "first")
 285                                   ._M_iterator(__last, "last"));
 286             this->_M_invalidate_if(_Equal(__victim));
 287           }
 288         return iterator(_Base::erase(__first.base(), __last.base()), this);
 289       }
 290 #else
 291       void
 292       erase(iterator __first, iterator __last)
 293       {
 294         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 295         // 151. can't currently clear() empty container
 296         __glibcxx_check_erase_range(__first, __last);
 297         for (_Base_iterator __victim = __first.base();
 298              __victim != __last.base(); ++__victim)
 299           {
 300             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 301                                   _M_message(__gnu_debug::__msg_valid_range)
 302                                   ._M_iterator(__first, "first")
 303                                   ._M_iterator(__last, "last"));
 304             this->_M_invalidate_if(_Equal(__victim));
 305           }
 306         _Base::erase(__first.base(), __last.base());
 307       }
 308 #endif
 309
 310       void
 311       swap(multiset& __x)
 312       {
 313         _Base::swap(__x);
 314         this->_M_swap(__x);
 315       }
 316
 317       void
 318       clear()
 319       {
 320         this->_M_invalidate_all();
 321         _Base::clear();
 322       }
 323
 324       // observers:
 325       using _Base::key_comp;
 326       using _Base::value_comp;
 327
 328       // multiset operations:
 329       iterator
 330       find(const key_type& __x)
 331       { return iterator(_Base::find(__x), this); }
 332
 333       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 334       // 214. set::find() missing const overload
 335       const_iterator
 336       find(const key_type& __x) const
 337       { return const_iterator(_Base::find(__x), this); }
 338
 339       using _Base::count;
 340
 341       iterator
 342       lower_bound(const key_type& __x)
 343       { return iterator(_Base::lower_bound(__x), this); }
 344
 345       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 346       // 214. set::find() missing const overload
 347       const_iterator
 348       lower_bound(const key_type& __x) const
 349       { return const_iterator(_Base::lower_bound(__x), this); }
 350
 351       iterator
 352       upper_bound(const key_type& __x)
 353       { return iterator(_Base::upper_bound(__x), this); }
 354
 355       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 356       // 214. set::find() missing const overload
 357       const_iterator
 358       upper_bound(const key_type& __x) const
 359       { return const_iterator(_Base::upper_bound(__x), this); }
 360
 361       std::pair<iterator,iterator>
 362       equal_range(const key_type& __x)
 363       {
 364         std::pair<_Base_iterator, _Base_iterator> __res =
 365           _Base::equal_range(__x);
 366         return std::make_pair(iterator(__res.first, this),
 367                               iterator(__res.second, this));
 368       }
 369
 370       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 371       // 214. set::find() missing const overload
 372       std::pair<const_iterator,const_iterator>
 373       equal_range(const key_type& __x) const
 374       {
 375         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 376           _Base::equal_range(__x);
 377         return std::make_pair(const_iterator(__res.first, this),
 378                               const_iterator(__res.second, this));
 379       }
 380
 381       _Base&
 382       _M_base() { return *this; }
 383
 384       const _Base&
 385       _M_base() const { return *this; }
 386
 387     private:
 388       void
 389       _M_invalidate_all()
 390       {
 391         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 392         this->_M_invalidate_if(_Not_equal(_Base::end()));
 393       }
 394     };
 395
 396   template<typename _Key, typename _Compare, typename _Allocator>
 397     inline bool
 398     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
 399                const multiset<_Key, _Compare, _Allocator>& __rhs)
 400     { return __lhs._M_base() == __rhs._M_base(); }
 401
 402   template<typename _Key, typename _Compare, typename _Allocator>
 403     inline bool
 404     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 405                const multiset<_Key, _Compare, _Allocator>& __rhs)
 406     { return __lhs._M_base() != __rhs._M_base(); }
 407
 408   template<typename _Key, typename _Compare, typename _Allocator>
 409     inline bool
 410     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
 411               const multiset<_Key, _Compare, _Allocator>& __rhs)
 412     { return __lhs._M_base() < __rhs._M_base(); }
 413
 414   template<typename _Key, typename _Compare, typename _Allocator>
 415     inline bool
 416     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 417                const multiset<_Key, _Compare, _Allocator>& __rhs)
 418     { return __lhs._M_base() <= __rhs._M_base(); }
 419
 420   template<typename _Key, typename _Compare, typename _Allocator>
 421     inline bool
 422     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
 423                const multiset<_Key, _Compare, _Allocator>& __rhs)
 424     { return __lhs._M_base() >= __rhs._M_base(); }
 425
 426   template<typename _Key, typename _Compare, typename _Allocator>
 427     inline bool
 428     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
 429               const multiset<_Key, _Compare, _Allocator>& __rhs)
 430     { return __lhs._M_base() > __rhs._M_base(); }
 431
 432   template<typename _Key, typename _Compare, typename _Allocator>
 433     void
 434     swap(multiset<_Key, _Compare, _Allocator>& __x,
 435          multiset<_Key, _Compare, _Allocator>& __y)
 436     { return __x.swap(__y); }
 437
 438 } // namespace __debug
 439 } // namespace std
 440
 441 #endif