1// Profiling multimap implementation -*- C++ -*- 2 3// Copyright (C) 2009, 2010 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/** @file profile/multimap.h 26 * This file is a GNU profile extension to the Standard C++ Library. 27 */ 28 29#ifndef _GLIBCXX_PROFILE_MULTIMAP_H 30#define _GLIBCXX_PROFILE_MULTIMAP_H 1 31 32#include <utility> 33 34namespace std 35{ 36namespace __profile 37{ 38 /// Class std::multimap wrapper with performance instrumentation. 39 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 40 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 41 class multimap 42 : public _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator> 43 { 44 typedef _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator> _Base; 45 46 public: 47 // types: 48 typedef _Key key_type; 49 typedef _Tp mapped_type; 50 typedef std::pair<const _Key, _Tp> value_type; 51 typedef _Compare key_compare; 52 typedef _Allocator allocator_type; 53 typedef typename _Base::reference reference; 54 typedef typename _Base::const_reference const_reference; 55 56 typedef typename _Base::iterator iterator; 57 typedef typename _Base::const_iterator const_iterator; 58 typedef typename _Base::reverse_iterator reverse_iterator; 59 typedef typename _Base::const_reverse_iterator const_reverse_iterator; 60 61 typedef typename _Base::size_type size_type; 62 typedef typename _Base::difference_type difference_type; 63 typedef typename _Base::pointer pointer; 64 typedef typename _Base::const_pointer const_pointer; 65 66 using _Base::value_compare; 67 68 // 23.3.1.1 construct/copy/destroy: 69 explicit multimap(const _Compare& __comp = _Compare(), 70 const _Allocator& __a = _Allocator()) 71 : _Base(__comp, __a) { } 72 73 template<typename _InputIterator> 74 multimap(_InputIterator __first, _InputIterator __last, 75 const _Compare& __comp = _Compare(), 76 const _Allocator& __a = _Allocator()) 77 : _Base(__first, __last, __comp, __a) { } 78 79 multimap(const multimap& __x) 80 : _Base(__x) { } 81 82 multimap(const _Base& __x) 83 : _Base(__x) { } 84 85#ifdef __GXX_EXPERIMENTAL_CXX0X__ 86 multimap(multimap&& __x) 87 : _Base(std::forward<multimap>(__x)) 88 { } 89 90 multimap(initializer_list<value_type> __l, 91 const _Compare& __c = _Compare(), 92 const allocator_type& __a = allocator_type()) 93 : _Base(__l, __c, __a) { } 94#endif 95 96 ~multimap() { } 97 98 multimap& 99 operator=(const multimap& __x) 100 { 101 *static_cast<_Base*>(this) = __x; 102 return *this; 103 } 104 105#ifdef __GXX_EXPERIMENTAL_CXX0X__ 106 multimap& 107 operator=(multimap&& __x) 108 { 109 // NB: DR 1204. 110 // NB: DR 675. 111 this->clear(); 112 this->swap(__x); 113 return *this; 114 } 115 116 multimap& 117 operator=(initializer_list<value_type> __l) 118 { 119 this->clear(); 120 this->insert(__l); 121 return *this; 122 } 123#endif 124 125 using _Base::get_allocator; 126 127 // iterators: 128 iterator 129 begin() 130 { return iterator(_Base::begin()); } 131 132 const_iterator 133 begin() const 134 { return const_iterator(_Base::begin()); } 135 136 iterator 137 end() 138 { return iterator(_Base::end()); } 139 140 const_iterator 141 end() const 142 { return const_iterator(_Base::end()); } 143 144 reverse_iterator 145 rbegin() 146 { return reverse_iterator(end()); } 147 148 const_reverse_iterator 149 rbegin() const 150 { return const_reverse_iterator(end()); } 151 152 reverse_iterator 153 rend() 154 { return reverse_iterator(begin()); } 155 156 const_reverse_iterator 157 rend() const 158 { return const_reverse_iterator(begin()); } 159 160#ifdef __GXX_EXPERIMENTAL_CXX0X__ 161 const_iterator 162 cbegin() const 163 { return const_iterator(_Base::begin()); } 164 165 const_iterator 166 cend() const 167 { return const_iterator(_Base::end()); } 168 169 const_reverse_iterator 170 crbegin() const 171 { return const_reverse_iterator(end()); } 172 173 const_reverse_iterator 174 crend() const 175 { return const_reverse_iterator(begin()); } 176#endif 177 178 // capacity: 179 using _Base::empty; 180 using _Base::size; 181 using _Base::max_size; 182 183 // modifiers: 184 iterator 185 insert(const value_type& __x) 186 { return iterator(_Base::insert(__x)); } 187 188#ifdef __GXX_EXPERIMENTAL_CXX0X__ 189 void 190 insert(std::initializer_list<value_type> __list) 191 { _Base::insert(__list); } 192#endif 193 194 iterator 195 insert(iterator __position, const value_type& __x) 196 { 197 return iterator(_Base::insert(__position, __x)); 198 } 199 200 template<typename _InputIterator> 201 void 202 insert(_InputIterator __first, _InputIterator __last) 203 { 204 _Base::insert(__first, __last); 205 } 206 207#ifdef __GXX_EXPERIMENTAL_CXX0X__ 208 iterator 209 erase(iterator __position) 210 { return _Base::erase(__position); } 211#else 212 void 213 erase(iterator __position) 214 { _Base::erase(__position); } 215#endif 216 217 size_type 218 erase(const key_type& __x) 219 { 220 std::pair<iterator, iterator> __victims = this->equal_range(__x); 221 size_type __count = 0; 222 while (__victims.first != __victims.second) 223 { 224 iterator __victim = __victims.first++; 225 _Base::erase(__victim); 226 ++__count; 227 } 228 return __count; 229 } 230 231#ifdef __GXX_EXPERIMENTAL_CXX0X__ 232 iterator 233 erase(iterator __first, iterator __last) 234 { 235 // _GLIBCXX_RESOLVE_LIB_DEFECTS 236 // 151. can't currently clear() empty container 237 while (__first != __last) 238 this->erase(__first++); 239 return __last; 240 } 241#else 242 void 243 erase(iterator __first, iterator __last) 244 { 245 // _GLIBCXX_RESOLVE_LIB_DEFECTS 246 // 151. can't currently clear() empty container 247 while (__first != __last) 248 this->erase(__first++); 249 } 250#endif 251 252 void 253 swap(multimap& __x) 254 { 255 _Base::swap(__x); 256 } 257 258 void 259 clear() 260 { this->erase(begin(), end()); } 261 262 // observers: 263 using _Base::key_comp; 264 using _Base::value_comp; 265 266 // 23.3.1.3 multimap operations: 267 iterator 268 find(const key_type& __x) 269 { return iterator(_Base::find(__x)); } 270 271 const_iterator 272 find(const key_type& __x) const 273 { return const_iterator(_Base::find(__x)); } 274 275 using _Base::count; 276 277 iterator 278 lower_bound(const key_type& __x) 279 { return iterator(_Base::lower_bound(__x)); } 280 281 const_iterator 282 lower_bound(const key_type& __x) const 283 { return const_iterator(_Base::lower_bound(__x)); } 284 285 iterator 286 upper_bound(const key_type& __x) 287 { return iterator(_Base::upper_bound(__x)); } 288 289 const_iterator 290 upper_bound(const key_type& __x) const 291 { return const_iterator(_Base::upper_bound(__x)); } 292 293 std::pair<iterator,iterator> 294 equal_range(const key_type& __x) 295 { 296 typedef typename _Base::iterator _Base_iterator; 297 std::pair<_Base_iterator, _Base_iterator> __res = 298 _Base::equal_range(__x); 299 return std::make_pair(iterator(__res.first), 300 iterator(__res.second)); 301 } 302 303 std::pair<const_iterator,const_iterator> 304 equal_range(const key_type& __x) const 305 { 306 typedef typename _Base::const_iterator _Base_const_iterator; 307 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 308 _Base::equal_range(__x); 309 return std::make_pair(const_iterator(__res.first), 310 const_iterator(__res.second)); 311 } 312 313 _Base& 314 _M_base() { return *this; } 315 316 const _Base& 317 _M_base() const { return *this; } 318 }; 319 320 template<typename _Key, typename _Tp, 321 typename _Compare, typename _Allocator> 322 inline bool 323 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 324 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 325 { return __lhs._M_base() == __rhs._M_base(); } 326 327 template<typename _Key, typename _Tp, 328 typename _Compare, typename _Allocator> 329 inline bool 330 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 331 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 332 { return __lhs._M_base() != __rhs._M_base(); } 333 334 template<typename _Key, typename _Tp, 335 typename _Compare, typename _Allocator> 336 inline bool 337 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 338 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 339 { return __lhs._M_base() < __rhs._M_base(); } 340 341 template<typename _Key, typename _Tp, 342 typename _Compare, typename _Allocator> 343 inline bool 344 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 345 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 346 { return __lhs._M_base() <= __rhs._M_base(); } 347 348 template<typename _Key, typename _Tp, 349 typename _Compare, typename _Allocator> 350 inline bool 351 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 352 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 353 { return __lhs._M_base() >= __rhs._M_base(); } 354 355 template<typename _Key, typename _Tp, 356 typename _Compare, typename _Allocator> 357 inline bool 358 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 359 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 360 { return __lhs._M_base() > __rhs._M_base(); } 361 362 template<typename _Key, typename _Tp, 363 typename _Compare, typename _Allocator> 364 inline void 365 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 366 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 367 { __lhs.swap(__rhs); } 368 369} // namespace __profile 370} // namespace std 371 372#endif 373