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

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