multimap.h

Go to the documentation of this file.
00001 // Debugging multimap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007
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 2, 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 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /** @file debug/multimap.h
00032  *  This file is a GNU debug extension to the Standard C++ Library.
00033  */
00034 
00035 #ifndef _GLIBCXX_DEBUG_MULTIMAP_H
00036 #define _GLIBCXX_DEBUG_MULTIMAP_H 1
00037 
00038 #include <debug/safe_sequence.h>
00039 #include <debug/safe_iterator.h>
00040 #include <utility>
00041 
00042 namespace std
00043 {
00044 namespace __debug
00045 {
00046   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
00047        typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
00048     class multimap
00049     : public _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator>,
00050       public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp,
00051                           _Compare, _Allocator> >
00052     {
00053       typedef _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
00054       typedef __gnu_debug::_Safe_sequence<multimap> _Safe_base;
00055 
00056     public:
00057       // types:
00058       typedef _Key                   key_type;
00059       typedef _Tp                    mapped_type;
00060       typedef std::pair<const _Key, _Tp>             value_type;
00061       typedef _Compare                               key_compare;
00062       typedef _Allocator                             allocator_type;
00063       typedef typename _Base::reference              reference;
00064       typedef typename _Base::const_reference        const_reference;
00065 
00066       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multimap>
00067                                                      iterator;
00068       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00069                                            multimap> const_iterator;
00070 
00071       typedef typename _Base::size_type              size_type;
00072       typedef typename _Base::difference_type        difference_type;
00073       typedef typename _Base::pointer                pointer;
00074       typedef typename _Base::const_pointer          const_pointer;
00075       typedef std::reverse_iterator<iterator>        reverse_iterator;
00076       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
00077 
00078       using _Base::value_compare;
00079 
00080       // 23.3.1.1 construct/copy/destroy:
00081       explicit multimap(const _Compare& __comp = _Compare(),
00082             const _Allocator& __a = _Allocator())
00083       : _Base(__comp, __a) { }
00084 
00085       template<typename _InputIterator>
00086       multimap(_InputIterator __first, _InputIterator __last,
00087            const _Compare& __comp = _Compare(),
00088            const _Allocator& __a = _Allocator())
00089       : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
00090           __comp, __a) { }
00091 
00092       multimap(const multimap& __x)
00093       : _Base(__x), _Safe_base() { }
00094 
00095       multimap(const _Base& __x)
00096       : _Base(__x), _Safe_base() { }
00097 
00098 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00099       multimap(multimap&& __x)
00100       : _Base(std::forward<multimap>(__x)), _Safe_base()
00101       { this->_M_swap(__x); }
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 #endif
00124 
00125       using _Base::get_allocator;
00126 
00127       // iterators:
00128       iterator
00129       begin()
00130       { return iterator(_Base::begin(), this); }
00131 
00132       const_iterator
00133       begin() const
00134       { return const_iterator(_Base::begin(), this); }
00135 
00136       iterator
00137       end()
00138       { return iterator(_Base::end(), this); }
00139 
00140       const_iterator
00141       end() const
00142       { return const_iterator(_Base::end(), this); }
00143 
00144       reverse_iterator
00145       rbegin()
00146       { return reverse_iterator(end()); }
00147 
00148       const_reverse_iterator
00149       rbegin() const
00150       { return const_reverse_iterator(end()); }
00151 
00152       reverse_iterator
00153       rend()
00154       { return reverse_iterator(begin()); }
00155 
00156       const_reverse_iterator
00157       rend() const
00158       { return const_reverse_iterator(begin()); }
00159 
00160 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00161       const_iterator
00162       cbegin() const
00163       { return const_iterator(_Base::begin(), this); }
00164 
00165       const_iterator
00166       cend() const
00167       { return const_iterator(_Base::end(), this); }
00168 
00169       const_reverse_iterator
00170       crbegin() const
00171       { return const_reverse_iterator(end()); }
00172 
00173       const_reverse_iterator
00174       crend() const
00175       { return const_reverse_iterator(begin()); }
00176 #endif
00177 
00178       // capacity:
00179       using _Base::empty;
00180       using _Base::size;
00181       using _Base::max_size;
00182 
00183       // modifiers:
00184       iterator
00185       insert(const value_type& __x)
00186       { return iterator(_Base::insert(__x), this); }
00187 
00188       iterator
00189       insert(iterator __position, const value_type& __x)
00190       {
00191     __glibcxx_check_insert(__position);
00192     return iterator(_Base::insert(__position.base(), __x), this);
00193       }
00194 
00195       template<typename _InputIterator>
00196         void
00197         insert(_InputIterator __first, _InputIterator __last)
00198         {
00199       __glibcxx_check_valid_range(__first, __last);
00200       _Base::insert(__first, __last);
00201     }
00202 
00203       void
00204       erase(iterator __position)
00205       {
00206     __glibcxx_check_erase(__position);
00207     __position._M_invalidate();
00208     _Base::erase(__position.base());
00209       }
00210 
00211       size_type
00212       erase(const key_type& __x)
00213       {
00214     std::pair<iterator, iterator> __victims = this->equal_range(__x);
00215     size_type __count = 0;
00216     while (__victims.first != __victims.second)
00217     {
00218       iterator __victim = __victims.first++;
00219       __victim._M_invalidate();
00220       _Base::erase(__victim.base());
00221       ++__count;
00222     }
00223     return __count;
00224       }
00225 
00226       void
00227       erase(iterator __first, iterator __last)
00228       {
00229     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00230     // 151. can't currently clear() empty container
00231     __glibcxx_check_erase_range(__first, __last);
00232     while (__first != __last)
00233     this->erase(__first++);
00234       }
00235 
00236       void
00237 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00238       swap(multimap&& __x)
00239 #else
00240       swap(multimap& __x)
00241 #endif
00242       {
00243     _Base::swap(__x);
00244     this->_M_swap(__x);
00245       }
00246 
00247       void
00248       clear()
00249       { this->erase(begin(), end()); }
00250 
00251       // observers:
00252       using _Base::key_comp;
00253       using _Base::value_comp;
00254 
00255       // 23.3.1.3 multimap operations:
00256       iterator
00257       find(const key_type& __x)
00258       { return iterator(_Base::find(__x), this); }
00259 
00260       const_iterator
00261       find(const key_type& __x) const
00262       { return const_iterator(_Base::find(__x), this); }
00263 
00264       using _Base::count;
00265 
00266       iterator
00267       lower_bound(const key_type& __x)
00268       { return iterator(_Base::lower_bound(__x), this); }
00269 
00270       const_iterator
00271       lower_bound(const key_type& __x) const
00272       { return const_iterator(_Base::lower_bound(__x), this); }
00273 
00274       iterator
00275       upper_bound(const key_type& __x)
00276       { return iterator(_Base::upper_bound(__x), this); }
00277 
00278       const_iterator
00279       upper_bound(const key_type& __x) const
00280       { return const_iterator(_Base::upper_bound(__x), this); }
00281 
00282       std::pair<iterator,iterator>
00283       equal_range(const key_type& __x)
00284       {
00285     typedef typename _Base::iterator _Base_iterator;
00286     std::pair<_Base_iterator, _Base_iterator> __res =
00287     _Base::equal_range(__x);
00288     return std::make_pair(iterator(__res.first, this),
00289                   iterator(__res.second, this));
00290       }
00291 
00292       std::pair<const_iterator,const_iterator>
00293       equal_range(const key_type& __x) const
00294       {
00295     typedef typename _Base::const_iterator _Base_const_iterator;
00296     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00297     _Base::equal_range(__x);
00298     return std::make_pair(const_iterator(__res.first, this),
00299                   const_iterator(__res.second, this));
00300       }
00301 
00302       _Base&
00303       _M_base() { return *this; }
00304 
00305       const _Base&
00306       _M_base() const { return *this; }
00307 
00308     private:
00309       void
00310       _M_invalidate_all()
00311       {
00312     typedef typename _Base::const_iterator _Base_const_iterator;
00313     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00314     this->_M_invalidate_if(_Not_equal(_M_base().end()));
00315       }
00316     };
00317 
00318   template<typename _Key, typename _Tp,
00319        typename _Compare, typename _Allocator>
00320     inline bool
00321     operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00322            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00323     { return __lhs._M_base() == __rhs._M_base(); }
00324 
00325   template<typename _Key, typename _Tp,
00326        typename _Compare, typename _Allocator>
00327     inline bool
00328     operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00329            const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00330     { return __lhs._M_base() != __rhs._M_base(); }
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 void
00363     swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00364      multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00365     { __lhs.swap(__rhs); }
00366 
00367 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00368   template<typename _Key, typename _Tp,
00369        typename _Compare, typename _Allocator>
00370     inline void
00371     swap(multimap<_Key, _Tp, _Compare, _Allocator>&& __lhs,
00372      multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00373     { __lhs.swap(__rhs); }
00374 
00375   template<typename _Key, typename _Tp,
00376        typename _Compare, typename _Allocator>
00377     inline void
00378     swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00379      multimap<_Key, _Tp, _Compare, _Allocator>&& __rhs)
00380     { __lhs.swap(__rhs); }
00381 #endif
00382 
00383 } // namespace __debug
00384 } // namespace std
00385 
00386 #endif

Generated on Wed Mar 26 00:43:03 2008 for libstdc++ by  doxygen 1.5.1