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

   1 // Debugging map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005
   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 2, 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 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /** @file debug/map.h
  32  *  This file is a GNU debug extension to the Standard C++ Library.
  33  */
  34
  35 #ifndef _GLIBCXX_DEBUG_MAP_H
  36 #define _GLIBCXX_DEBUG_MAP_H 1
  37
  38 #include <debug/safe_sequence.h>
  39 #include <debug/safe_iterator.h>
  40 #include <utility>
  41
  42 namespace std
  43 {
  44 namespace __debug
  45 {
  46   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
  47            typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
  48     class map
  49     : public _GLIBCXX_STD::map<_Key, _Tp, _Compare, _Allocator>,
  50       public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> >
  51     {
  52       typedef _GLIBCXX_STD::map<_Key, _Tp, _Compare, _Allocator> _Base;
  53       typedef __gnu_debug::_Safe_sequence<map> _Safe_base;
  54
  55     public:
  56       // types:
  57       typedef _Key                                  key_type;
  58       typedef _Tp                                   mapped_type;
  59       typedef std::pair<const _Key, _Tp>            value_type;
  60       typedef _Compare                              key_compare;
  61       typedef _Allocator                            allocator_type;
  62       typedef typename _Base::reference             reference;
  63       typedef typename _Base::const_reference       const_reference;
  64
  65       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map>
  66                                                     iterator;
  67       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map>
  68                                                     const_iterator;
  69
  70       typedef typename _Base::size_type             size_type;
  71       typedef typename _Base::difference_type       difference_type;
  72       typedef typename _Base::pointer               pointer;
  73       typedef typename _Base::const_pointer         const_pointer;
  74       typedef std::reverse_iterator<iterator>       reverse_iterator;
  75       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  76
  77       using _Base::value_compare;
  78
  79       // 23.3.1.1 construct/copy/destroy:
  80       explicit map(const _Compare& __comp = _Compare(),
  81                    const _Allocator& __a = _Allocator())
  82       : _Base(__comp, __a) { }
  83
  84       template<typename _InputIterator>
  85         map(_InputIterator __first, _InputIterator __last,
  86             const _Compare& __comp = _Compare(),
  87             const _Allocator& __a = _Allocator())
  88         : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
  89                 __comp, __a), _Safe_base() { }
  90
  91       map(const map<_Key,_Tp,_Compare,_Allocator>& __x)
  92       : _Base(__x), _Safe_base() { }
  93
  94       map(const _Base& __x) : _Base(__x), _Safe_base() { }
  95
  96       ~map() { }
  97
  98       map<_Key,_Tp,_Compare,_Allocator>&
  99       operator=(const map<_Key,_Tp,_Compare,_Allocator>& __x)
 100       {
 101         *static_cast<_Base*>(this) = __x;
 102         this->_M_invalidate_all();
 103         return *this;
 104       }
 105
 106       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 107       // 133. map missing get_allocator()
 108       using _Base::get_allocator;
 109
 110       // iterators:
 111       iterator
 112       begin()
 113       { return iterator(_Base::begin(), this); }
 114
 115       const_iterator
 116       begin() const
 117       { return const_iterator(_Base::begin(), this); }
 118
 119       iterator
 120       end()
 121       { return iterator(_Base::end(), this); }
 122
 123       const_iterator
 124       end() const
 125       { return const_iterator(_Base::end(), this); }
 126
 127       reverse_iterator
 128       rbegin()
 129       { return reverse_iterator(end()); }
 130
 131       const_reverse_iterator
 132       rbegin() const
 133       { return const_reverse_iterator(end()); }
 134
 135       reverse_iterator
 136       rend()
 137       { return reverse_iterator(begin()); }
 138
 139       const_reverse_iterator
 140       rend() const
 141       { return const_reverse_iterator(begin()); }
 142
 143       // capacity:
 144       using _Base::empty;
 145       using _Base::size;
 146       using _Base::max_size;
 147
 148       // 23.3.1.2 element access:
 149       using _Base::operator[];
 150
 151       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 152       // DR 464. Suggestion for new member functions in standard containers.
 153       using _Base::at;
 154
 155       // modifiers:
 156       std::pair<iterator, bool>
 157       insert(const value_type& __x)
 158       {
 159         typedef typename _Base::iterator _Base_iterator;
 160         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 161         return std::pair<iterator, bool>(iterator(__res.first, this),
 162                                          __res.second);
 163       }
 164
 165       iterator
 166       insert(iterator __position, const value_type& __x)
 167       {
 168         __glibcxx_check_insert(__position);
 169         return iterator(_Base::insert(__position.base(), __x), this);
 170       }
 171
 172       template<typename _InputIterator>
 173         void
 174         insert(_InputIterator __first, _InputIterator __last)
 175         {
 176           __glibcxx_check_valid_range(__first, __last);
 177           _Base::insert(__first, __last);
 178         }
 179
 180       void
 181       erase(iterator __position)
 182       {
 183         __glibcxx_check_erase(__position);
 184         __position._M_invalidate();
 185         _Base::erase(__position.base());
 186       }
 187
 188       size_type
 189       erase(const key_type& __x)
 190       {
 191         iterator __victim = find(__x);
 192         if (__victim == end())
 193           return 0;
 194         else
 195         {
 196           __victim._M_invalidate();
 197           _Base::erase(__victim.base());
 198           return 1;
 199         }
 200       }
 201
 202       void
 203       erase(iterator __first, iterator __last)
 204       {
 205         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 206         // 151. can't currently clear() empty container
 207         __glibcxx_check_erase_range(__first, __last);
 208         while (__first != __last)
 209           this->erase(__first++);
 210       }
 211
 212       void
 213       swap(map<_Key,_Tp,_Compare,_Allocator>& __x)
 214       {
 215         _Base::swap(__x);
 216         this->_M_swap(__x);
 217       }
 218
 219       void
 220       clear()
 221       { this->erase(begin(), end()); }
 222
 223       // observers:
 224       using _Base::key_comp;
 225       using _Base::value_comp;
 226
 227       // 23.3.1.3 map operations:
 228       iterator
 229       find(const key_type& __x)
 230       { return iterator(_Base::find(__x), this); }
 231
 232       const_iterator
 233       find(const key_type& __x) const
 234       { return const_iterator(_Base::find(__x), this); }
 235
 236       using _Base::count;
 237
 238       iterator
 239       lower_bound(const key_type& __x)
 240       { return iterator(_Base::lower_bound(__x), this); }
 241
 242       const_iterator
 243       lower_bound(const key_type& __x) const
 244       { return const_iterator(_Base::lower_bound(__x), this); }
 245
 246       iterator
 247       upper_bound(const key_type& __x)
 248       { return iterator(_Base::upper_bound(__x), this); }
 249
 250       const_iterator
 251       upper_bound(const key_type& __x) const
 252       { return const_iterator(_Base::upper_bound(__x), this); }
 253
 254       std::pair<iterator,iterator>
 255       equal_range(const key_type& __x)
 256       {
 257         typedef typename _Base::iterator _Base_iterator;
 258         std::pair<_Base_iterator, _Base_iterator> __res =
 259         _Base::equal_range(__x);
 260         return std::make_pair(iterator(__res.first, this),
 261                               iterator(__res.second, this));
 262       }
 263
 264       std::pair<const_iterator,const_iterator>
 265       equal_range(const key_type& __x) const
 266       {
 267         typedef typename _Base::const_iterator _Base_const_iterator;
 268         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 269         _Base::equal_range(__x);
 270         return std::make_pair(const_iterator(__res.first, this),
 271                               const_iterator(__res.second, this));
 272       }
 273
 274       _Base&
 275       _M_base() { return *this; }
 276
 277       const _Base&
 278       _M_base() const { return *this; }
 279
 280     private:
 281       void
 282       _M_invalidate_all()
 283       {
 284         typedef typename _Base::const_iterator _Base_const_iterator;
 285         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 286         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 287       }
 288     };
 289
 290   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
 291     inline bool
 292     operator==(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
 293                const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
 294     { return __lhs._M_base() == __rhs._M_base(); }
 295
 296   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
 297     inline bool
 298     operator!=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
 299                const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
 300     { return __lhs._M_base() != __rhs._M_base(); }
 301
 302   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
 303     inline bool
 304     operator<(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
 305               const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
 306     { return __lhs._M_base() < __rhs._M_base(); }
 307
 308   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
 309     inline bool
 310     operator<=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
 311                const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
 312     { return __lhs._M_base() <= __rhs._M_base(); }
 313
 314   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
 315     inline bool
 316     operator>=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
 317                const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
 318     { return __lhs._M_base() >= __rhs._M_base(); }
 319
 320   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
 321     inline bool
 322     operator>(const map<_Key,_Tp,_Compare,_Allocator>& __lhs,
 323               const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
 324     { return __lhs._M_base() > __rhs._M_base(); }
 325
 326   template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
 327     inline void
 328     swap(map<_Key,_Tp,_Compare,_Allocator>& __lhs,
 329          map<_Key,_Tp,_Compare,_Allocator>& __rhs)
 330     { __lhs.swap(__rhs); }
 331 } // namespace __debug
 332 } // namespace std
 333
 334 #endif