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