libstdc++
map.h
Go to the documentation of this file.
00001 // Debugging map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2013 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file debug/map.h
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_MAP_H
00030 #define _GLIBCXX_DEBUG_MAP_H 1
00031 
00032 #include <debug/safe_sequence.h>
00033 #include <debug/safe_iterator.h>
00034 #include <utility>
00035 
00036 namespace std _GLIBCXX_VISIBILITY(default)
00037 {
00038 namespace __debug
00039 {
00040   /// Class std::map with safety/checking/debug instrumentation.
00041   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
00042        typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
00043     class map
00044     : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>,
00045       public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> >
00046     {
00047       typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;
00048 
00049       typedef typename _Base::const_iterator _Base_const_iterator;
00050       typedef typename _Base::iterator _Base_iterator;
00051       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00052     public:
00053       // types:
00054       typedef _Key                                  key_type;
00055       typedef _Tp                                   mapped_type;
00056       typedef std::pair<const _Key, _Tp>            value_type;
00057       typedef _Compare                              key_compare;
00058       typedef _Allocator                            allocator_type;
00059       typedef typename _Base::reference             reference;
00060       typedef typename _Base::const_reference       const_reference;
00061 
00062       typedef __gnu_debug::_Safe_iterator<_Base_iterator, map>
00063                                                     iterator;
00064       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, map>
00065                                                     const_iterator;
00066 
00067       typedef typename _Base::size_type             size_type;
00068       typedef typename _Base::difference_type       difference_type;
00069       typedef typename _Base::pointer               pointer;
00070       typedef typename _Base::const_pointer         const_pointer;
00071       typedef std::reverse_iterator<iterator>       reverse_iterator;
00072       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00073 
00074       // 23.3.1.1 construct/copy/destroy:
00075       explicit map(const _Compare& __comp = _Compare(),
00076            const _Allocator& __a = _Allocator())
00077       : _Base(__comp, __a) { }
00078 
00079       template<typename _InputIterator>
00080         map(_InputIterator __first, _InputIterator __last,
00081         const _Compare& __comp = _Compare(),
00082         const _Allocator& __a = _Allocator())
00083     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00084                                      __last)),
00085         __gnu_debug::__base(__last),
00086         __comp, __a) { }
00087 
00088       map(const map& __x)
00089       : _Base(__x) { }
00090 
00091       map(const _Base& __x)
00092       : _Base(__x) { }
00093 
00094 #if __cplusplus >= 201103L
00095       map(map&& __x)
00096       noexcept(is_nothrow_copy_constructible<_Compare>::value)
00097       : _Base(std::move(__x))
00098       { this->_M_swap(__x); }
00099 
00100       map(initializer_list<value_type> __l,
00101       const _Compare& __c = _Compare(),
00102       const allocator_type& __a = allocator_type())
00103       : _Base(__l, __c, __a) { }
00104 #endif
00105 
00106       ~map() _GLIBCXX_NOEXCEPT { }
00107 
00108       map&
00109       operator=(const map& __x)
00110       {
00111     *static_cast<_Base*>(this) = __x;
00112     this->_M_invalidate_all();
00113     return *this;
00114       }
00115 
00116 #if __cplusplus >= 201103L
00117       map&
00118       operator=(map&& __x)
00119       {
00120     // NB: DR 1204.
00121     // NB: DR 675.
00122     __glibcxx_check_self_move_assign(__x);
00123     clear();
00124     swap(__x);
00125     return *this;
00126       }
00127 
00128       map&
00129       operator=(initializer_list<value_type> __l)
00130       {
00131     this->clear();
00132     this->insert(__l);
00133     return *this;
00134       }
00135 #endif
00136 
00137       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00138       // 133. map missing get_allocator()
00139       using _Base::get_allocator;
00140 
00141       // iterators:
00142       iterator 
00143       begin() _GLIBCXX_NOEXCEPT
00144       { return iterator(_Base::begin(), this); }
00145 
00146       const_iterator
00147       begin() const _GLIBCXX_NOEXCEPT
00148       { return const_iterator(_Base::begin(), this); }
00149 
00150       iterator
00151       end() _GLIBCXX_NOEXCEPT
00152       { return iterator(_Base::end(), this); }
00153 
00154       const_iterator
00155       end() const _GLIBCXX_NOEXCEPT
00156       { return const_iterator(_Base::end(), this); }
00157 
00158       reverse_iterator
00159       rbegin() _GLIBCXX_NOEXCEPT
00160       { return reverse_iterator(end()); }
00161 
00162       const_reverse_iterator
00163       rbegin() const _GLIBCXX_NOEXCEPT
00164       { return const_reverse_iterator(end()); }
00165 
00166       reverse_iterator
00167       rend() _GLIBCXX_NOEXCEPT
00168       { return reverse_iterator(begin()); }
00169 
00170       const_reverse_iterator
00171       rend() const _GLIBCXX_NOEXCEPT
00172       { return const_reverse_iterator(begin()); }
00173 
00174 #if __cplusplus >= 201103L
00175       const_iterator
00176       cbegin() const noexcept
00177       { return const_iterator(_Base::begin(), this); }
00178 
00179       const_iterator
00180       cend() const noexcept
00181       { return const_iterator(_Base::end(), this); }
00182 
00183       const_reverse_iterator
00184       crbegin() const noexcept
00185       { return const_reverse_iterator(end()); }
00186 
00187       const_reverse_iterator
00188       crend() const noexcept
00189       { return const_reverse_iterator(begin()); }
00190 #endif
00191 
00192       // capacity:
00193       using _Base::empty;
00194       using _Base::size;
00195       using _Base::max_size;
00196 
00197       // 23.3.1.2 element access:
00198       using _Base::operator[];
00199 
00200       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00201       // DR 464. Suggestion for new member functions in standard containers.
00202       using _Base::at;
00203 
00204       // modifiers:
00205 #if __cplusplus >= 201103L
00206       template<typename... _Args>
00207     std::pair<iterator, bool>
00208     emplace(_Args&&... __args)
00209     {
00210       auto __res = _Base::emplace(std::forward<_Args>(__args)...);
00211       return std::pair<iterator, bool>(iterator(__res.first, this),
00212                        __res.second);
00213     }
00214 
00215       template<typename... _Args>
00216     iterator
00217     emplace_hint(const_iterator __pos, _Args&&... __args)
00218     {
00219       __glibcxx_check_insert(__pos);
00220       return iterator(_Base::emplace_hint(__pos.base(),
00221                           std::forward<_Args>(__args)...),
00222               this);
00223     }
00224 #endif
00225 
00226       std::pair<iterator, bool>
00227       insert(const value_type& __x)
00228       {
00229     std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
00230     return std::pair<iterator, bool>(iterator(__res.first, this),
00231                      __res.second);
00232       }
00233 
00234 #if __cplusplus >= 201103L
00235       template<typename _Pair, typename = typename
00236            std::enable_if<std::is_constructible<value_type,
00237                             _Pair&&>::value>::type>
00238         std::pair<iterator, bool>
00239         insert(_Pair&& __x)
00240         {
00241       std::pair<_Base_iterator, bool> __res
00242         = _Base::insert(std::forward<_Pair>(__x));
00243       return std::pair<iterator, bool>(iterator(__res.first, this),
00244                        __res.second);
00245     }
00246 #endif
00247 
00248 #if __cplusplus >= 201103L
00249       void
00250       insert(std::initializer_list<value_type> __list)
00251       { _Base::insert(__list); }
00252 #endif
00253 
00254       iterator
00255 #if __cplusplus >= 201103L
00256       insert(const_iterator __position, const value_type& __x)
00257 #else
00258       insert(iterator __position, const value_type& __x)
00259 #endif
00260       {
00261     __glibcxx_check_insert(__position);
00262     return iterator(_Base::insert(__position.base(), __x), this);
00263       }
00264 
00265 #if __cplusplus >= 201103L
00266       template<typename _Pair, typename = typename
00267            std::enable_if<std::is_constructible<value_type,
00268                             _Pair&&>::value>::type>
00269         iterator
00270         insert(const_iterator __position, _Pair&& __x)
00271         {
00272       __glibcxx_check_insert(__position);
00273       return iterator(_Base::insert(__position.base(),
00274                     std::forward<_Pair>(__x)), this);
00275     }
00276 #endif
00277 
00278       template<typename _InputIterator>
00279         void
00280         insert(_InputIterator __first, _InputIterator __last)
00281         {
00282       __glibcxx_check_valid_range(__first, __last);
00283       _Base::insert(__gnu_debug::__base(__first),
00284             __gnu_debug::__base(__last));
00285     }
00286 
00287 #if __cplusplus >= 201103L
00288       iterator
00289       erase(const_iterator __position)
00290       {
00291     __glibcxx_check_erase(__position);
00292     this->_M_invalidate_if(_Equal(__position.base()));
00293     return iterator(_Base::erase(__position.base()), this);
00294       }
00295 
00296       iterator
00297       erase(iterator __position)
00298       { return erase(const_iterator(__position)); }
00299 #else
00300       void
00301       erase(iterator __position)
00302       {
00303     __glibcxx_check_erase(__position);
00304     this->_M_invalidate_if(_Equal(__position.base()));
00305     _Base::erase(__position.base());
00306       }
00307 #endif
00308 
00309       size_type
00310       erase(const key_type& __x)
00311       {
00312     _Base_iterator __victim = _Base::find(__x);
00313     if (__victim == _Base::end())
00314       return 0;
00315     else
00316       {
00317         this->_M_invalidate_if(_Equal(__victim));
00318         _Base::erase(__victim);
00319         return 1;
00320       }
00321       }
00322 
00323 #if __cplusplus >= 201103L
00324       iterator
00325       erase(const_iterator __first, const_iterator __last)
00326       {
00327     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00328     // 151. can't currently clear() empty container
00329     __glibcxx_check_erase_range(__first, __last);
00330     for (_Base_const_iterator __victim = __first.base();
00331          __victim != __last.base(); ++__victim)
00332       {
00333         _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00334                   _M_message(__gnu_debug::__msg_valid_range)
00335                   ._M_iterator(__first, "first")
00336                   ._M_iterator(__last, "last"));
00337         this->_M_invalidate_if(_Equal(__victim));
00338       }
00339     return iterator(_Base::erase(__first.base(), __last.base()), this);
00340       }
00341 #else
00342       void
00343       erase(iterator __first, iterator __last)
00344       {
00345     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00346     // 151. can't currently clear() empty container
00347     __glibcxx_check_erase_range(__first, __last);
00348     for (_Base_iterator __victim = __first.base();
00349          __victim != __last.base(); ++__victim)
00350       {
00351         _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00352                   _M_message(__gnu_debug::__msg_valid_range)
00353                   ._M_iterator(__first, "first")
00354                   ._M_iterator(__last, "last"));
00355         this->_M_invalidate_if(_Equal(__victim));
00356       }
00357     _Base::erase(__first.base(), __last.base());
00358       }
00359 #endif
00360 
00361       void
00362       swap(map& __x)
00363       {
00364     _Base::swap(__x);
00365     this->_M_swap(__x);
00366       }
00367 
00368       void
00369       clear() _GLIBCXX_NOEXCEPT
00370       {
00371     this->_M_invalidate_all();
00372     _Base::clear();
00373       }
00374 
00375       // observers:
00376       using _Base::key_comp;
00377       using _Base::value_comp;
00378 
00379       // 23.3.1.3 map operations:
00380       iterator
00381       find(const key_type& __x)
00382       { return iterator(_Base::find(__x), this); }
00383 
00384       const_iterator
00385       find(const key_type& __x) const
00386       { return const_iterator(_Base::find(__x), this); }
00387 
00388       using _Base::count;
00389 
00390       iterator
00391       lower_bound(const key_type& __x)
00392       { return iterator(_Base::lower_bound(__x), this); }
00393 
00394       const_iterator
00395       lower_bound(const key_type& __x) const
00396       { return const_iterator(_Base::lower_bound(__x), this); }
00397 
00398       iterator
00399       upper_bound(const key_type& __x)
00400       { return iterator(_Base::upper_bound(__x), this); }
00401 
00402       const_iterator
00403       upper_bound(const key_type& __x) const
00404       { return const_iterator(_Base::upper_bound(__x), this); }
00405 
00406       std::pair<iterator,iterator>
00407       equal_range(const key_type& __x)
00408       {
00409     std::pair<_Base_iterator, _Base_iterator> __res =
00410     _Base::equal_range(__x);
00411     return std::make_pair(iterator(__res.first, this),
00412                   iterator(__res.second, this));
00413       }
00414 
00415       std::pair<const_iterator,const_iterator>
00416       equal_range(const key_type& __x) const
00417       {
00418     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00419     _Base::equal_range(__x);
00420     return std::make_pair(const_iterator(__res.first, this),
00421                   const_iterator(__res.second, this));
00422       }
00423 
00424       _Base&
00425       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00426 
00427       const _Base&
00428       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00429 
00430     private:
00431       void
00432       _M_invalidate_all()
00433       {
00434     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00435     this->_M_invalidate_if(_Not_equal(_M_base().end()));
00436       }
00437     };
00438 
00439   template<typename _Key, typename _Tp,
00440        typename _Compare, typename _Allocator>
00441     inline bool
00442     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00443            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00444     { return __lhs._M_base() == __rhs._M_base(); }
00445 
00446   template<typename _Key, typename _Tp,
00447        typename _Compare, typename _Allocator>
00448     inline bool
00449     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00450            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00451     { return __lhs._M_base() != __rhs._M_base(); }
00452 
00453   template<typename _Key, typename _Tp,
00454        typename _Compare, typename _Allocator>
00455     inline bool
00456     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00457           const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00458     { return __lhs._M_base() < __rhs._M_base(); }
00459 
00460   template<typename _Key, typename _Tp,
00461        typename _Compare, typename _Allocator>
00462     inline bool
00463     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00464            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00465     { return __lhs._M_base() <= __rhs._M_base(); }
00466 
00467   template<typename _Key, typename _Tp,
00468        typename _Compare, typename _Allocator>
00469     inline bool
00470     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00471            const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00472     { return __lhs._M_base() >= __rhs._M_base(); }
00473 
00474   template<typename _Key, typename _Tp,
00475        typename _Compare, typename _Allocator>
00476     inline bool
00477     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00478           const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00479     { return __lhs._M_base() > __rhs._M_base(); }
00480 
00481   template<typename _Key, typename _Tp,
00482        typename _Compare, typename _Allocator>
00483     inline void
00484     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00485      map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00486     { __lhs.swap(__rhs); }
00487 
00488 } // namespace __debug
00489 } // namespace std
00490 
00491 #endif