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