multimap.h

Go to the documentation of this file.
00001 // Debugging multimap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009
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
00038 {
00039 namespace __debug
00040 {
00041   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
00042        typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
00043     class multimap
00044     : public _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator>,
00045       public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp,
00046                           _Compare, _Allocator> >
00047     {
00048       typedef _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
00049       typedef __gnu_debug::_Safe_sequence<multimap> _Safe_base;
00050 
00051     public:
00052       // types:
00053       typedef _Key                   key_type;
00054       typedef _Tp                    mapped_type;
00055       typedef std::pair<const _Key, _Tp>             value_type;
00056       typedef _Compare                               key_compare;
00057       typedef _Allocator                             allocator_type;
00058       typedef typename _Base::reference              reference;
00059       typedef typename _Base::const_reference        const_reference;
00060 
00061       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multimap>
00062                                                      iterator;
00063       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00064                                            multimap> const_iterator;
00065 
00066       typedef typename _Base::size_type              size_type;
00067       typedef typename _Base::difference_type        difference_type;
00068       typedef typename _Base::pointer                pointer;
00069       typedef typename _Base::const_pointer          const_pointer;
00070       typedef std::reverse_iterator<iterator>        reverse_iterator;
00071       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
00072 
00073       using _Base::value_compare;
00074 
00075       // 23.3.1.1 construct/copy/destroy:
00076       explicit multimap(const _Compare& __comp = _Compare(),
00077             const _Allocator& __a = _Allocator())
00078       : _Base(__comp, __a) { }
00079 
00080       template<typename _InputIterator>
00081       multimap(_InputIterator __first, _InputIterator __last,
00082            const _Compare& __comp = _Compare(),
00083            const _Allocator& __a = _Allocator())
00084       : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
00085           __comp, __a) { }
00086 
00087       multimap(const multimap& __x)
00088       : _Base(__x), _Safe_base() { }
00089 
00090       multimap(const _Base& __x)
00091       : _Base(__x), _Safe_base() { }
00092 
00093 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00094       multimap(multimap&& __x)
00095       : _Base(std::forward<multimap>(__x)), _Safe_base()
00096       { this->_M_swap(__x); }
00097 
00098       multimap(initializer_list<value_type> __l,
00099            const _Compare& __c = _Compare(),
00100            const allocator_type& __a = allocator_type())
00101       : _Base(__l, __c, __a), _Safe_base() { }
00102 #endif
00103 
00104       ~multimap() { }
00105 
00106       multimap&
00107       operator=(const multimap& __x)
00108       {
00109     *static_cast<_Base*>(this) = __x;
00110     this->_M_invalidate_all();
00111     return *this;
00112       }
00113 
00114 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00115       multimap&
00116       operator=(multimap&& __x)
00117       {
00118         // NB: DR 675.
00119     clear();
00120     swap(__x);
00121     return *this;
00122       }
00123 
00124       multimap&
00125       operator=(initializer_list<value_type> __l)
00126       {
00127     this->clear();
00128     this->insert(__l);
00129     return *this;
00130       }
00131 #endif
00132 
00133       using _Base::get_allocator;
00134 
00135       // iterators:
00136       iterator
00137       begin()
00138       { return iterator(_Base::begin(), this); }
00139 
00140       const_iterator
00141       begin() const
00142       { return const_iterator(_Base::begin(), this); }
00143 
00144       iterator
00145       end()
00146       { return iterator(_Base::end(), this); }
00147 
00148       const_iterator
00149       end() const
00150       { return const_iterator(_Base::end(), this); }
00151 
00152       reverse_iterator
00153       rbegin()
00154       { return reverse_iterator(end()); }
00155 
00156       const_reverse_iterator
00157       rbegin() const
00158       { return const_reverse_iterator(end()); }
00159 
00160       reverse_iterator
00161       rend()
00162       { return reverse_iterator(begin()); }
00163 
00164       const_reverse_iterator
00165       rend() const
00166       { return const_reverse_iterator(begin()); }
00167 
00168 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00169       const_iterator
00170       cbegin() const
00171       { return const_iterator(_Base::begin(), this); }
00172 
00173       const_iterator
00174       cend() const
00175       { return const_iterator(_Base::end(), this); }
00176 
00177       const_reverse_iterator
00178       crbegin() const
00179       { return const_reverse_iterator(end()); }
00180 
00181       const_reverse_iterator
00182       crend() const
00183       { return const_reverse_iterator(begin()); }
00184 #endif
00185 
00186       // capacity:
00187       using _Base::empty;
00188       using _Base::size;
00189       using _Base::max_size;
00190 
00191       // modifiers:
00192       iterator
00193       insert(const value_type& __x)
00194       { return iterator(_Base::insert(__x), this); }
00195 
00196 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00197       void
00198       insert(std::initializer_list<value_type> __list)
00199       { _Base::insert(__list); }
00200 #endif
00201 
00202       iterator
00203       insert(iterator __position, const value_type& __x)
00204       {
00205     __glibcxx_check_insert(__position);
00206     return iterator(_Base::insert(__position.base(), __x), this);
00207       }
00208 
00209       template<typename _InputIterator>
00210         void
00211         insert(_InputIterator __first, _InputIterator __last)
00212         {
00213       __glibcxx_check_valid_range(__first, __last);
00214       _Base::insert(__first, __last);
00215     }
00216 
00217       void
00218       erase(iterator __position)
00219       {
00220     __glibcxx_check_erase(__position);
00221     __position._M_invalidate();
00222     _Base::erase(__position.base());
00223       }
00224 
00225       size_type
00226       erase(const key_type& __x)
00227       {
00228     std::pair<iterator, iterator> __victims = this->equal_range(__x);
00229     size_type __count = 0;
00230     while (__victims.first != __victims.second)
00231     {
00232       iterator __victim = __victims.first++;
00233       __victim._M_invalidate();
00234       _Base::erase(__victim.base());
00235       ++__count;
00236     }
00237     return __count;
00238       }
00239 
00240       void
00241       erase(iterator __first, iterator __last)
00242       {
00243     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00244     // 151. can't currently clear() empty container
00245     __glibcxx_check_erase_range(__first, __last);
00246     while (__first != __last)
00247     this->erase(__first++);
00248       }
00249 
00250       void
00251 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00252       swap(multimap&& __x)
00253 #else
00254       swap(multimap& __x)
00255 #endif
00256       {
00257     _Base::swap(__x);
00258     this->_M_swap(__x);
00259       }
00260 
00261       void
00262       clear()
00263       { this->erase(begin(), end()); }
00264 
00265       // observers:
00266       using _Base::key_comp;
00267       using _Base::value_comp;
00268 
00269       // 23.3.1.3 multimap operations:
00270       iterator
00271       find(const key_type& __x)
00272       { return iterator(_Base::find(__x), this); }
00273 
00274       const_iterator
00275       find(const key_type& __x) const
00276       { return const_iterator(_Base::find(__x), this); }
00277 
00278       using _Base::count;
00279 
00280       iterator
00281       lower_bound(const key_type& __x)
00282       { return iterator(_Base::lower_bound(__x), this); }
00283 
00284       const_iterator
00285       lower_bound(const key_type& __x) const
00286       { return const_iterator(_Base::lower_bound(__x), this); }
00287 
00288       iterator
00289       upper_bound(const key_type& __x)
00290       { return iterator(_Base::upper_bound(__x), this); }
00291 
00292       const_iterator
00293       upper_bound(const key_type& __x) const
00294       { return const_iterator(_Base::upper_bound(__x), this); }
00295 
00296       std::pair<iterator,iterator>
00297       equal_range(const key_type& __x)
00298       {
00299     typedef typename _Base::iterator _Base_iterator;
00300     std::pair<_Base_iterator, _Base_iterator> __res =
00301     _Base::equal_range(__x);
00302     return std::make_pair(iterator(__res.first, this),
00303                   iterator(__res.second, this));
00304       }
00305 
00306       std::pair<const_iterator,const_iterator>
00307       equal_range(const key_type& __x) const
00308       {
00309     typedef typename _Base::const_iterator _Base_const_iterator;
00310     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00311     _Base::equal_range(__x);
00312     return std::make_pair(const_iterator(__res.first, this),
00313                   const_iterator(__res.second, this));
00314       }
00315 
00316       _Base&
00317       _M_base() { return *this; }
00318 
00319       const _Base&
00320       _M_base() const { return *this; }
00321 
00322     private:
00323       void
00324       _M_invalidate_all()
00325       {
00326     typedef typename _Base::const_iterator _Base_const_iterator;
00327     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00328     this->_M_invalidate_if(_Not_equal(_M_base().end()));
00329       }
00330     };
00331 
00332   template<typename _Key, typename _Tp,
00333        typename _Compare, typename _Allocator>
00334     inline bool
00335     operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00336            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00337     { return __lhs._M_base() == __rhs._M_base(); }
00338 
00339   template<typename _Key, typename _Tp,
00340        typename _Compare, typename _Allocator>
00341     inline bool
00342     operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00343            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00344     { return __lhs._M_base() != __rhs._M_base(); }
00345 
00346   template<typename _Key, typename _Tp,
00347        typename _Compare, typename _Allocator>
00348     inline bool
00349     operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00350           const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00351     { return __lhs._M_base() < __rhs._M_base(); }
00352 
00353   template<typename _Key, typename _Tp,
00354        typename _Compare, typename _Allocator>
00355     inline bool
00356     operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00357            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00358     { return __lhs._M_base() <= __rhs._M_base(); }
00359 
00360   template<typename _Key, typename _Tp,
00361        typename _Compare, typename _Allocator>
00362     inline bool
00363     operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00364            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00365     { return __lhs._M_base() >= __rhs._M_base(); }
00366 
00367   template<typename _Key, typename _Tp,
00368        typename _Compare, typename _Allocator>
00369     inline bool
00370     operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00371           const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00372     { return __lhs._M_base() > __rhs._M_base(); }
00373 
00374   template<typename _Key, typename _Tp,
00375        typename _Compare, typename _Allocator>
00376     inline void
00377     swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00378      multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00379     { __lhs.swap(__rhs); }
00380 
00381 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00382   template<typename _Key, typename _Tp,
00383        typename _Compare, typename _Allocator>
00384     inline void
00385     swap(multimap<_Key, _Tp, _Compare, _Allocator>&& __lhs,
00386      multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00387     { __lhs.swap(__rhs); }
00388 
00389   template<typename _Key, typename _Tp,
00390        typename _Compare, typename _Allocator>
00391     inline void
00392     swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00393      multimap<_Key, _Tp, _Compare, _Allocator>&& __rhs)
00394     { __lhs.swap(__rhs); }
00395 #endif
00396 
00397 } // namespace __debug
00398 } // namespace std
00399 
00400 #endif

Generated on Thu Jul 23 21:16:11 2009 for libstdc++ by  doxygen 1.5.8