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
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       using _Base::value_compare;
00078 
00079       // 23.3.1.1 construct/copy/destroy:
00080       explicit multimap(const _Compare& __comp = _Compare(),
00081             const _Allocator& __a = _Allocator())
00082       : _Base(__comp, __a) { }
00083 
00084       template<typename _InputIterator>
00085       multimap(_InputIterator __first, _InputIterator __last,
00086            const _Compare& __comp = _Compare(),
00087            const _Allocator& __a = _Allocator())
00088     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00089                                      __last)),
00090         __gnu_debug::__base(__last),
00091           __comp, __a) { }
00092 
00093       multimap(const multimap& __x)
00094       : _Base(__x), _Safe_base() { }
00095 
00096       multimap(const _Base& __x)
00097       : _Base(__x), _Safe_base() { }
00098 
00099 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00100       multimap(multimap&& __x)
00101       : _Base(std::move(__x)), _Safe_base()
00102       { this->_M_swap(__x); }
00103 
00104       multimap(initializer_list<value_type> __l,
00105            const _Compare& __c = _Compare(),
00106            const allocator_type& __a = allocator_type())
00107       : _Base(__l, __c, __a), _Safe_base() { }
00108 #endif
00109 
00110       ~multimap() { }
00111 
00112       multimap&
00113       operator=(const multimap& __x)
00114       {
00115     *static_cast<_Base*>(this) = __x;
00116     this->_M_invalidate_all();
00117     return *this;
00118       }
00119 
00120 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00121       multimap&
00122       operator=(multimap&& __x)
00123       {
00124     // NB: DR 1204.
00125     // NB: DR 675.
00126     clear();
00127     swap(__x);
00128     return *this;
00129       }
00130 
00131       multimap&
00132       operator=(initializer_list<value_type> __l)
00133       {
00134     this->clear();
00135     this->insert(__l);
00136     return *this;
00137       }
00138 #endif
00139 
00140       using _Base::get_allocator;
00141 
00142       // iterators:
00143       iterator
00144       begin()
00145       { return iterator(_Base::begin(), this); }
00146 
00147       const_iterator
00148       begin() const
00149       { return const_iterator(_Base::begin(), this); }
00150 
00151       iterator
00152       end()
00153       { return iterator(_Base::end(), this); }
00154 
00155       const_iterator
00156       end() const
00157       { return const_iterator(_Base::end(), this); }
00158 
00159       reverse_iterator
00160       rbegin()
00161       { return reverse_iterator(end()); }
00162 
00163       const_reverse_iterator
00164       rbegin() const
00165       { return const_reverse_iterator(end()); }
00166 
00167       reverse_iterator
00168       rend()
00169       { return reverse_iterator(begin()); }
00170 
00171       const_reverse_iterator
00172       rend() const
00173       { return const_reverse_iterator(begin()); }
00174 
00175 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00176       const_iterator
00177       cbegin() const
00178       { return const_iterator(_Base::begin(), this); }
00179 
00180       const_iterator
00181       cend() const
00182       { return const_iterator(_Base::end(), this); }
00183 
00184       const_reverse_iterator
00185       crbegin() const
00186       { return const_reverse_iterator(end()); }
00187 
00188       const_reverse_iterator
00189       crend() const
00190       { return const_reverse_iterator(begin()); }
00191 #endif
00192 
00193       // capacity:
00194       using _Base::empty;
00195       using _Base::size;
00196       using _Base::max_size;
00197 
00198       // modifiers:
00199       iterator
00200       insert(const value_type& __x)
00201       { return iterator(_Base::insert(__x), this); }
00202 
00203 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00204       template<typename _Pair, typename = typename
00205            std::enable_if<std::is_convertible<_Pair,
00206                           value_type>::value>::type>
00207         iterator
00208         insert(_Pair&& __x)
00209         { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); }
00210 #endif
00211 
00212 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00213       void
00214       insert(std::initializer_list<value_type> __list)
00215       { _Base::insert(__list); }
00216 #endif
00217 
00218       iterator
00219 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00220       insert(const_iterator __position, const value_type& __x)
00221 #else
00222       insert(iterator __position, const value_type& __x)
00223 #endif
00224       {
00225     __glibcxx_check_insert(__position);
00226     return iterator(_Base::insert(__position.base(), __x), this);
00227       }
00228 
00229 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00230       template<typename _Pair, typename = typename
00231            std::enable_if<std::is_convertible<_Pair,
00232                           value_type>::value>::type>
00233         iterator
00234         insert(const_iterator __position, _Pair&& __x)
00235         {
00236       __glibcxx_check_insert(__position);
00237       return iterator(_Base::insert(__position.base(),
00238                     std::forward<_Pair>(__x)), this);
00239     }
00240 #endif
00241 
00242       template<typename _InputIterator>
00243         void
00244         insert(_InputIterator __first, _InputIterator __last)
00245         {
00246       __glibcxx_check_valid_range(__first, __last);
00247       _Base::insert(__gnu_debug::__base(__first),
00248             __gnu_debug::__base(__last));
00249     }
00250 
00251 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00252       iterator
00253       erase(const_iterator __position)
00254       {
00255     __glibcxx_check_erase(__position);
00256     this->_M_invalidate_if(_Equal(__position.base()));
00257     return iterator(_Base::erase(__position.base()), this);
00258       }
00259 #else
00260       void
00261       erase(iterator __position)
00262       {
00263     __glibcxx_check_erase(__position);
00264     this->_M_invalidate_if(_Equal(__position.base()));
00265     _Base::erase(__position.base());
00266       }
00267 #endif
00268 
00269       size_type
00270       erase(const key_type& __x)
00271       {
00272     std::pair<_Base_iterator, _Base_iterator> __victims =
00273       _Base::equal_range(__x);
00274     size_type __count = 0;
00275     _Base_iterator __victim = __victims.first;
00276     while (__victim !=  __victims.second)
00277       {
00278         this->_M_invalidate_if(_Equal(__victim));
00279         _Base::erase(__victim++);
00280         ++__count;
00281       }
00282     return __count;
00283       }
00284 
00285 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00286       iterator
00287       erase(const_iterator __first, const_iterator __last)
00288       {
00289     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00290     // 151. can't currently clear() empty container
00291     __glibcxx_check_erase_range(__first, __last);
00292     for (_Base_const_iterator __victim = __first.base();
00293          __victim != __last.base(); ++__victim)
00294       {
00295         _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00296                   _M_message(__gnu_debug::__msg_valid_range)
00297                   ._M_iterator(__first, "first")
00298                   ._M_iterator(__last, "last"));
00299         this->_M_invalidate_if(_Equal(__victim));
00300       }
00301     return iterator(_Base::erase(__first.base(), __last.base()), this);
00302       }
00303 #else
00304       void
00305       erase(iterator __first, iterator __last)
00306       {
00307     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00308     // 151. can't currently clear() empty container
00309     __glibcxx_check_erase_range(__first, __last);
00310     for (_Base_iterator __victim = __first.base();
00311          __victim != __last.base(); ++__victim)
00312       {
00313         _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00314                   _M_message(__gnu_debug::__msg_valid_range)
00315                   ._M_iterator(__first, "first")
00316                   ._M_iterator(__last, "last"));
00317         this->_M_invalidate_if(_Equal(__victim));
00318       }
00319     _Base::erase(__first.base(), __last.base());
00320       }
00321 #endif
00322 
00323       void
00324       swap(multimap& __x)
00325       {
00326     _Base::swap(__x);
00327     this->_M_swap(__x);
00328       }
00329 
00330       void
00331       clear()
00332       {
00333     this->_M_invalidate_all();
00334     _Base::clear();
00335       }
00336 
00337       // observers:
00338       using _Base::key_comp;
00339       using _Base::value_comp;
00340 
00341       // 23.3.1.3 multimap operations:
00342       iterator
00343       find(const key_type& __x)
00344       { return iterator(_Base::find(__x), this); }
00345 
00346       const_iterator
00347       find(const key_type& __x) const
00348       { return const_iterator(_Base::find(__x), this); }
00349 
00350       using _Base::count;
00351 
00352       iterator
00353       lower_bound(const key_type& __x)
00354       { return iterator(_Base::lower_bound(__x), this); }
00355 
00356       const_iterator
00357       lower_bound(const key_type& __x) const
00358       { return const_iterator(_Base::lower_bound(__x), this); }
00359 
00360       iterator
00361       upper_bound(const key_type& __x)
00362       { return iterator(_Base::upper_bound(__x), this); }
00363 
00364       const_iterator
00365       upper_bound(const key_type& __x) const
00366       { return const_iterator(_Base::upper_bound(__x), this); }
00367 
00368       std::pair<iterator,iterator>
00369       equal_range(const key_type& __x)
00370       {
00371     std::pair<_Base_iterator, _Base_iterator> __res =
00372     _Base::equal_range(__x);
00373     return std::make_pair(iterator(__res.first, this),
00374                   iterator(__res.second, this));
00375       }
00376 
00377       std::pair<const_iterator,const_iterator>
00378       equal_range(const key_type& __x) const
00379       {
00380     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00381       _Base::equal_range(__x);
00382     return std::make_pair(const_iterator(__res.first, this),
00383                   const_iterator(__res.second, this));
00384       }
00385 
00386       _Base&
00387       _M_base() { return *this; }
00388 
00389       const _Base&
00390       _M_base() const { return *this; }
00391 
00392     private:
00393       void
00394       _M_invalidate_all()
00395       {
00396     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00397     this->_M_invalidate_if(_Not_equal(_Base::end()));
00398       }
00399     };
00400 
00401   template<typename _Key, typename _Tp,
00402        typename _Compare, typename _Allocator>
00403     inline bool
00404     operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00405            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00406     { return __lhs._M_base() == __rhs._M_base(); }
00407 
00408   template<typename _Key, typename _Tp,
00409        typename _Compare, typename _Allocator>
00410     inline bool
00411     operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00412            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00413     { return __lhs._M_base() != __rhs._M_base(); }
00414 
00415   template<typename _Key, typename _Tp,
00416        typename _Compare, typename _Allocator>
00417     inline bool
00418     operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00419           const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00420     { return __lhs._M_base() < __rhs._M_base(); }
00421 
00422   template<typename _Key, typename _Tp,
00423        typename _Compare, typename _Allocator>
00424     inline bool
00425     operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00426            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00427     { return __lhs._M_base() <= __rhs._M_base(); }
00428 
00429   template<typename _Key, typename _Tp,
00430        typename _Compare, typename _Allocator>
00431     inline bool
00432     operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00433            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00434     { return __lhs._M_base() >= __rhs._M_base(); }
00435 
00436   template<typename _Key, typename _Tp,
00437        typename _Compare, typename _Allocator>
00438     inline bool
00439     operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00440           const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00441     { return __lhs._M_base() > __rhs._M_base(); }
00442 
00443   template<typename _Key, typename _Tp,
00444        typename _Compare, typename _Allocator>
00445     inline void
00446     swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00447      multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00448     { __lhs.swap(__rhs); }
00449 
00450 } // namespace __debug
00451 } // namespace std
00452 
00453 #endif