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

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