libstdc++
|
00001 // Profiling multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2009, 2010 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 public: 00047 // types: 00048 typedef _Key key_type; 00049 typedef _Tp mapped_type; 00050 typedef std::pair<const _Key, _Tp> value_type; 00051 typedef _Compare key_compare; 00052 typedef _Allocator allocator_type; 00053 typedef typename _Base::reference reference; 00054 typedef typename _Base::const_reference const_reference; 00055 00056 typedef typename _Base::iterator iterator; 00057 typedef typename _Base::const_iterator const_iterator; 00058 typedef typename _Base::reverse_iterator reverse_iterator; 00059 typedef typename _Base::const_reverse_iterator const_reverse_iterator; 00060 00061 typedef typename _Base::size_type size_type; 00062 typedef typename _Base::difference_type difference_type; 00063 typedef typename _Base::pointer pointer; 00064 typedef typename _Base::const_pointer const_pointer; 00065 00066 using _Base::value_compare; 00067 00068 // 23.3.1.1 construct/copy/destroy: 00069 explicit multimap(const _Compare& __comp = _Compare(), 00070 const _Allocator& __a = _Allocator()) 00071 : _Base(__comp, __a) { } 00072 00073 template<typename _InputIterator> 00074 multimap(_InputIterator __first, _InputIterator __last, 00075 const _Compare& __comp = _Compare(), 00076 const _Allocator& __a = _Allocator()) 00077 : _Base(__first, __last, __comp, __a) { } 00078 00079 multimap(const multimap& __x) 00080 : _Base(__x) { } 00081 00082 multimap(const _Base& __x) 00083 : _Base(__x) { } 00084 00085 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00086 multimap(multimap&& __x) 00087 : _Base(std::move(__x)) 00088 { } 00089 00090 multimap(initializer_list<value_type> __l, 00091 const _Compare& __c = _Compare(), 00092 const allocator_type& __a = allocator_type()) 00093 : _Base(__l, __c, __a) { } 00094 #endif 00095 00096 ~multimap() { } 00097 00098 multimap& 00099 operator=(const multimap& __x) 00100 { 00101 *static_cast<_Base*>(this) = __x; 00102 return *this; 00103 } 00104 00105 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00106 multimap& 00107 operator=(multimap&& __x) 00108 { 00109 // NB: DR 1204. 00110 // NB: DR 675. 00111 this->clear(); 00112 this->swap(__x); 00113 return *this; 00114 } 00115 00116 multimap& 00117 operator=(initializer_list<value_type> __l) 00118 { 00119 this->clear(); 00120 this->insert(__l); 00121 return *this; 00122 } 00123 #endif 00124 00125 using _Base::get_allocator; 00126 00127 // iterators: 00128 iterator 00129 begin() 00130 { return iterator(_Base::begin()); } 00131 00132 const_iterator 00133 begin() const 00134 { return const_iterator(_Base::begin()); } 00135 00136 iterator 00137 end() 00138 { return iterator(_Base::end()); } 00139 00140 const_iterator 00141 end() const 00142 { return const_iterator(_Base::end()); } 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()); } 00164 00165 const_iterator 00166 cend() const 00167 { return const_iterator(_Base::end()); } 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)); } 00187 00188 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00189 template<typename _Pair, typename = typename 00190 std::enable_if<std::is_convertible<_Pair, 00191 value_type>::value>::type> 00192 iterator 00193 insert(_Pair&& __x) 00194 { return iterator(_Base::insert(std::forward<_Pair>(__x))); } 00195 #endif 00196 00197 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00198 void 00199 insert(std::initializer_list<value_type> __list) 00200 { _Base::insert(__list); } 00201 #endif 00202 00203 iterator 00204 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00205 insert(const_iterator __position, const value_type& __x) 00206 #else 00207 insert(iterator __position, const value_type& __x) 00208 #endif 00209 { return iterator(_Base::insert(__position, __x)); } 00210 00211 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00212 template<typename _Pair, typename = typename 00213 std::enable_if<std::is_convertible<_Pair, 00214 value_type>::value>::type> 00215 iterator 00216 insert(const_iterator __position, _Pair&& __x) 00217 { return iterator(_Base::insert(__position, 00218 std::forward<_Pair>(__x))); } 00219 #endif 00220 00221 template<typename _InputIterator> 00222 void 00223 insert(_InputIterator __first, _InputIterator __last) 00224 { _Base::insert(__first, __last); } 00225 00226 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00227 iterator 00228 erase(const_iterator __position) 00229 { return iterator(_Base::erase(__position)); } 00230 #else 00231 void 00232 erase(iterator __position) 00233 { _Base::erase(__position); } 00234 #endif 00235 00236 size_type 00237 erase(const key_type& __x) 00238 { 00239 std::pair<iterator, iterator> __victims = this->equal_range(__x); 00240 size_type __count = 0; 00241 while (__victims.first != __victims.second) 00242 { 00243 iterator __victim = __victims.first++; 00244 _Base::erase(__victim); 00245 ++__count; 00246 } 00247 return __count; 00248 } 00249 00250 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00251 iterator 00252 erase(const_iterator __first, const_iterator __last) 00253 { return iterator(_Base::erase(__first, __last)); } 00254 #else 00255 void 00256 erase(iterator __first, iterator __last) 00257 { _Base::erase(__first, __last); } 00258 #endif 00259 00260 void 00261 swap(multimap& __x) 00262 { _Base::swap(__x); } 00263 00264 void 00265 clear() 00266 { this->erase(begin(), end()); } 00267 00268 // observers: 00269 using _Base::key_comp; 00270 using _Base::value_comp; 00271 00272 // 23.3.1.3 multimap operations: 00273 iterator 00274 find(const key_type& __x) 00275 { return iterator(_Base::find(__x)); } 00276 00277 const_iterator 00278 find(const key_type& __x) const 00279 { return const_iterator(_Base::find(__x)); } 00280 00281 using _Base::count; 00282 00283 iterator 00284 lower_bound(const key_type& __x) 00285 { return iterator(_Base::lower_bound(__x)); } 00286 00287 const_iterator 00288 lower_bound(const key_type& __x) const 00289 { return const_iterator(_Base::lower_bound(__x)); } 00290 00291 iterator 00292 upper_bound(const key_type& __x) 00293 { return iterator(_Base::upper_bound(__x)); } 00294 00295 const_iterator 00296 upper_bound(const key_type& __x) const 00297 { return const_iterator(_Base::upper_bound(__x)); } 00298 00299 std::pair<iterator,iterator> 00300 equal_range(const key_type& __x) 00301 { 00302 typedef typename _Base::iterator _Base_iterator; 00303 std::pair<_Base_iterator, _Base_iterator> __res = 00304 _Base::equal_range(__x); 00305 return std::make_pair(iterator(__res.first), 00306 iterator(__res.second)); 00307 } 00308 00309 std::pair<const_iterator,const_iterator> 00310 equal_range(const key_type& __x) const 00311 { 00312 typedef typename _Base::const_iterator _Base_const_iterator; 00313 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00314 _Base::equal_range(__x); 00315 return std::make_pair(const_iterator(__res.first), 00316 const_iterator(__res.second)); 00317 } 00318 00319 _Base& 00320 _M_base() { return *this; } 00321 00322 const _Base& 00323 _M_base() const { return *this; } 00324 }; 00325 00326 template<typename _Key, typename _Tp, 00327 typename _Compare, typename _Allocator> 00328 inline bool 00329 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00330 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00331 { return __lhs._M_base() == __rhs._M_base(); } 00332 00333 template<typename _Key, typename _Tp, 00334 typename _Compare, typename _Allocator> 00335 inline bool 00336 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00337 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00338 { return __lhs._M_base() != __rhs._M_base(); } 00339 00340 template<typename _Key, typename _Tp, 00341 typename _Compare, typename _Allocator> 00342 inline bool 00343 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00344 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00345 { return __lhs._M_base() < __rhs._M_base(); } 00346 00347 template<typename _Key, typename _Tp, 00348 typename _Compare, typename _Allocator> 00349 inline bool 00350 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00351 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00352 { return __lhs._M_base() <= __rhs._M_base(); } 00353 00354 template<typename _Key, typename _Tp, 00355 typename _Compare, typename _Allocator> 00356 inline bool 00357 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00358 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00359 { return __lhs._M_base() >= __rhs._M_base(); } 00360 00361 template<typename _Key, typename _Tp, 00362 typename _Compare, typename _Allocator> 00363 inline bool 00364 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00365 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00366 { return __lhs._M_base() > __rhs._M_base(); } 00367 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 } // namespace __profile 00376 } // namespace std 00377 00378 #endif