contrib/gcc-4.4/libstdc++-v3/include/debug/set.h

   1 // Debugging set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009
   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/set.h
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_SET_H
  31 #define _GLIBCXX_DEBUG_SET_H 1
  32
  33 #include <debug/safe_sequence.h>
  34 #include <debug/safe_iterator.h>
  35 #include <utility>
  36
  37 namespace std
  38 {
  39 namespace __debug
  40 {
  41   template<typename _Key, typename _Compare = std::less<_Key>,
  42            typename _Allocator = std::allocator<_Key> >
  43     class set
  44     : public _GLIBCXX_STD_D::set<_Key,_Compare,_Allocator>,
  45       public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
  46     {
  47       typedef _GLIBCXX_STD_D::set<_Key, _Compare, _Allocator> _Base;
  48       typedef __gnu_debug::_Safe_sequence<set> _Safe_base;
  49
  50     public:
  51       // types:
  52       typedef _Key                                  key_type;
  53       typedef _Key                                  value_type;
  54       typedef _Compare                              key_compare;
  55       typedef _Compare                              value_compare;
  56       typedef _Allocator                            allocator_type;
  57       typedef typename _Base::reference             reference;
  58       typedef typename _Base::const_reference       const_reference;
  59
  60       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, set>
  61                                                     iterator;
  62       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set>
  63                                                     const_iterator;
  64
  65       typedef typename _Base::size_type             size_type;
  66       typedef typename _Base::difference_type       difference_type;
  67       typedef typename _Base::pointer               pointer;
  68       typedef typename _Base::const_pointer         const_pointer;
  69       typedef std::reverse_iterator<iterator>       reverse_iterator;
  70       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  71
  72       // 23.3.3.1 construct/copy/destroy:
  73       explicit set(const _Compare& __comp = _Compare(),
  74                    const _Allocator& __a = _Allocator())
  75       : _Base(__comp, __a) { }
  76
  77       template<typename _InputIterator>
  78         set(_InputIterator __first, _InputIterator __last,
  79             const _Compare& __comp = _Compare(),
  80             const _Allocator& __a = _Allocator())
  81         : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
  82                 __comp, __a) { }
  83
  84       set(const set& __x)
  85       : _Base(__x), _Safe_base() { }
  86
  87       set(const _Base& __x)
  88       : _Base(__x), _Safe_base() { }
  89
  90 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  91       set(set&& __x)
  92       : _Base(std::forward<set>(__x)), _Safe_base()
  93       { this->_M_swap(__x); }
  94
  95       set(initializer_list<value_type> __l,
  96           const _Compare& __comp = _Compare(),
  97           const allocator_type& __a = allocator_type())
  98       : _Base(__l, __comp, __a), _Safe_base() { }
  99 #endif
 100
 101       ~set() { }
 102
 103       set&
 104       operator=(const set& __x)
 105       {
 106         *static_cast<_Base*>(this) = __x;
 107         this->_M_invalidate_all();
 108         return *this;
 109       }
 110
 111 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 112       set&
 113       operator=(set&& __x)
 114       {
 115         // NB: DR 675.
 116         clear();
 117         swap(__x);
 118         return *this;
 119       }
 120
 121       set&
 122       operator=(initializer_list<value_type> __l)
 123       {
 124         this->clear();
 125         this->insert(__l);
 126         return *this;
 127       }
 128 #endif
 129
 130       using _Base::get_allocator;
 131
 132       // iterators:
 133       iterator
 134       begin()
 135       { return iterator(_Base::begin(), this); }
 136
 137       const_iterator
 138       begin() const
 139       { return const_iterator(_Base::begin(), this); }
 140
 141       iterator
 142       end()
 143       { return iterator(_Base::end(), this); }
 144
 145       const_iterator
 146       end() const
 147       { return const_iterator(_Base::end(), this); }
 148
 149       reverse_iterator
 150       rbegin()
 151       { return reverse_iterator(end()); }
 152
 153       const_reverse_iterator
 154       rbegin() const
 155       { return const_reverse_iterator(end()); }
 156
 157       reverse_iterator
 158       rend()
 159       { return reverse_iterator(begin()); }
 160
 161       const_reverse_iterator
 162       rend() const
 163       { return const_reverse_iterator(begin()); }
 164
 165 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 166       const_iterator
 167       cbegin() const
 168       { return const_iterator(_Base::begin(), this); }
 169
 170       const_iterator
 171       cend() const
 172       { return const_iterator(_Base::end(), this); }
 173
 174       const_reverse_iterator
 175       crbegin() const
 176       { return const_reverse_iterator(end()); }
 177
 178       const_reverse_iterator
 179       crend() const
 180       { return const_reverse_iterator(begin()); }
 181 #endif
 182
 183       // capacity:
 184       using _Base::empty;
 185       using _Base::size;
 186       using _Base::max_size;
 187
 188       // modifiers:
 189       std::pair<iterator, bool>
 190       insert(const value_type& __x)
 191       {
 192         typedef typename _Base::iterator _Base_iterator;
 193         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 194         return std::pair<iterator, bool>(iterator(__res.first, this),
 195                                          __res.second);
 196       }
 197
 198       iterator
 199       insert(iterator __position, const value_type& __x)
 200       {
 201         __glibcxx_check_insert(__position);
 202         return iterator(_Base::insert(__position.base(), __x), this);
 203       }
 204
 205       template <typename _InputIterator>
 206         void
 207         insert(_InputIterator __first, _InputIterator __last)
 208         {
 209           __glibcxx_check_valid_range(__first, __last);
 210           _Base::insert(__first, __last);
 211         }
 212
 213 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 214       void
 215       insert(initializer_list<value_type> __l)
 216       { _Base::insert(__l); }
 217 #endif
 218
 219       void
 220       erase(iterator __position)
 221       {
 222         __glibcxx_check_erase(__position);
 223         __position._M_invalidate();
 224         _Base::erase(__position.base());
 225       }
 226
 227       size_type
 228       erase(const key_type& __x)
 229       {
 230         iterator __victim = find(__x);
 231         if (__victim == end())
 232           return 0;
 233         else
 234         {
 235           __victim._M_invalidate();
 236           _Base::erase(__victim.base());
 237           return 1;
 238         }
 239       }
 240
 241       void
 242       erase(iterator __first, iterator __last)
 243       {
 244         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 245         // 151. can't currently clear() empty container
 246         __glibcxx_check_erase_range(__first, __last);
 247
 248         while (__first != __last)
 249         this->erase(__first++);
 250       }
 251
 252       void
 253 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 254       swap(set&& __x)
 255 #else
 256       swap(set& __x)
 257 #endif
 258       {
 259         _Base::swap(__x);
 260         this->_M_swap(__x);
 261       }
 262
 263       void
 264       clear()
 265       { this->erase(begin(), end()); }
 266
 267       // observers:
 268       using _Base::key_comp;
 269       using _Base::value_comp;
 270
 271       // set operations:
 272       iterator
 273       find(const key_type& __x)
 274       { return iterator(_Base::find(__x), this); }
 275
 276       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 277       // 214. set::find() missing const overload
 278       const_iterator
 279       find(const key_type& __x) const
 280       { return const_iterator(_Base::find(__x), this); }
 281
 282       using _Base::count;
 283
 284       iterator
 285       lower_bound(const key_type& __x)
 286       { return iterator(_Base::lower_bound(__x), this); }
 287
 288       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 289       // 214. set::find() missing const overload
 290       const_iterator
 291       lower_bound(const key_type& __x) const
 292       { return const_iterator(_Base::lower_bound(__x), this); }
 293
 294       iterator
 295       upper_bound(const key_type& __x)
 296       { return iterator(_Base::upper_bound(__x), this); }
 297
 298       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 299       // 214. set::find() missing const overload
 300       const_iterator
 301       upper_bound(const key_type& __x) const
 302       { return const_iterator(_Base::upper_bound(__x), this); }
 303
 304       std::pair<iterator,iterator>
 305       equal_range(const key_type& __x)
 306       {
 307         typedef typename _Base::iterator _Base_iterator;
 308         std::pair<_Base_iterator, _Base_iterator> __res =
 309         _Base::equal_range(__x);
 310         return std::make_pair(iterator(__res.first, this),
 311                               iterator(__res.second, this));
 312       }
 313
 314       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 315       // 214. set::find() missing const overload
 316       std::pair<const_iterator,const_iterator>
 317       equal_range(const key_type& __x) const
 318       {
 319         typedef typename _Base::const_iterator _Base_iterator;
 320         std::pair<_Base_iterator, _Base_iterator> __res =
 321         _Base::equal_range(__x);
 322         return std::make_pair(const_iterator(__res.first, this),
 323                               const_iterator(__res.second, this));
 324       }
 325
 326       _Base&
 327       _M_base() { return *this; }
 328
 329       const _Base&
 330       _M_base() const { return *this; }
 331
 332     private:
 333       void
 334       _M_invalidate_all()
 335       {
 336         typedef typename _Base::const_iterator _Base_const_iterator;
 337         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 338         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 339       }
 340     };
 341
 342   template<typename _Key, typename _Compare, typename _Allocator>
 343     inline bool
 344     operator==(const set<_Key, _Compare, _Allocator>& __lhs,
 345                const set<_Key, _Compare, _Allocator>& __rhs)
 346     { return __lhs._M_base() == __rhs._M_base(); }
 347
 348   template<typename _Key, typename _Compare, typename _Allocator>
 349     inline bool
 350     operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
 351                const set<_Key, _Compare, _Allocator>& __rhs)
 352     { return __lhs._M_base() != __rhs._M_base(); }
 353
 354   template<typename _Key, typename _Compare, typename _Allocator>
 355     inline bool
 356     operator<(const set<_Key, _Compare, _Allocator>& __lhs,
 357               const set<_Key, _Compare, _Allocator>& __rhs)
 358     { return __lhs._M_base() < __rhs._M_base(); }
 359
 360   template<typename _Key, typename _Compare, typename _Allocator>
 361     inline bool
 362     operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
 363                const set<_Key, _Compare, _Allocator>& __rhs)
 364     { return __lhs._M_base() <= __rhs._M_base(); }
 365
 366   template<typename _Key, typename _Compare, typename _Allocator>
 367     inline bool
 368     operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
 369                const set<_Key, _Compare, _Allocator>& __rhs)
 370     { return __lhs._M_base() >= __rhs._M_base(); }
 371
 372   template<typename _Key, typename _Compare, typename _Allocator>
 373     inline bool
 374     operator>(const set<_Key, _Compare, _Allocator>& __lhs,
 375               const set<_Key, _Compare, _Allocator>& __rhs)
 376     { return __lhs._M_base() > __rhs._M_base(); }
 377
 378   template<typename _Key, typename _Compare, typename _Allocator>
 379     void
 380     swap(set<_Key, _Compare, _Allocator>& __x,
 381          set<_Key, _Compare, _Allocator>& __y)
 382     { return __x.swap(__y); }
 383
 384 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 385   template<typename _Key, typename _Compare, typename _Allocator>
 386     void
 387     swap(set<_Key, _Compare, _Allocator>&& __x,
 388          set<_Key, _Compare, _Allocator>& __y)
 389     { return __x.swap(__y); }
 390
 391   template<typename _Key, typename _Compare, typename _Allocator>
 392     void
 393     swap(set<_Key, _Compare, _Allocator>& __x,
 394          set<_Key, _Compare, _Allocator>&& __y)
 395     { return __x.swap(__y); }
 396 #endif
 397
 398 } // namespace __debug
 399 } // namespace std
 400
 401 #endif