1 // Profiling multimap implementation -*- C++ -*- 2 3 // Copyright (C) 2009-2015 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 <profile/base.h> 33 #include <profile/ordered_base.h> 34 35 namespace std _GLIBCXX_VISIBILITY(default) 36 { 37 namespace __profile 38 { 39 /// Class std::multimap wrapper with performance instrumentation. 40 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 41 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 42 class multimap 43 : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>, 44 public _Ordered_profile<map<_Key, _Tp, _Compare, _Allocator> > 45 { 46 typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base; 47 48 typedef typename _Base::iterator _Base_iterator; 49 typedef typename _Base::const_iterator _Base_const_iterator; 50 51 public: 52 // types: 53 typedef _Key key_type; 54 typedef _Tp mapped_type; 55 typedef std::pair<const _Key, _Tp> value_type; 56 typedef _Compare key_compare; 57 typedef typename _Base::reference reference; 58 typedef typename _Base::const_reference const_reference; 59 60 typedef __iterator_tracker<_Base_iterator, 61 multimap> iterator; 62 typedef __iterator_tracker<_Base_const_iterator, 63 multimap> const_iterator; 64 typedef std::reverse_iterator<iterator> reverse_iterator; 65 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 66 67 typedef typename _Base::size_type size_type; 68 typedef typename _Base::difference_type difference_type; 69 70 // 23.3.1.1 construct/copy/destroy: 71 72 #if __cplusplus < 201103L 73 multimap() 74 : _Base() { } 75 multimap(const multimap& __x) 76 : _Base(__x) { } 77 ~multimap() { } 78 #else 79 multimap() = default; 80 multimap(const multimap&) = default; 81 multimap(multimap&&) = default; 82 ~multimap() = default; 83 #endif 84 85 explicit multimap(const _Compare& __comp, 86 const _Allocator& __a = _Allocator()) 87 : _Base(__comp, __a) { } 88 89 #if __cplusplus >= 201103L 90 template<typename _InputIterator, 91 typename = std::_RequireInputIter<_InputIterator>> 92 #else 93 template<typename _InputIterator> 94 #endif 95 multimap(_InputIterator __first, _InputIterator __last, 96 const _Compare& __comp = _Compare(), 97 const _Allocator& __a = _Allocator()) 98 : _Base(__first, __last, __comp, __a) { } 99 100 #if __cplusplus >= 201103L 101 multimap(initializer_list<value_type> __l, 102 const _Compare& __c = _Compare(), 103 const _Allocator& __a = _Allocator()) 104 : _Base(__l, __c, __a) { } 105 106 explicit 107 multimap(const _Allocator& __a) 108 : _Base(__a) { } 109 110 multimap(const multimap& __x, const _Allocator& __a) 111 : _Base(__x, __a) { } 112 113 multimap(multimap&& __x, const _Allocator& __a) 114 noexcept( noexcept(_Base(std::move(__x), __a)) ) 115 : _Base(std::move(__x), __a) { } 116 117 multimap(initializer_list<value_type> __l, const _Allocator& __a) 118 : _Base(__l, __a) { } 119 120 template<typename _InputIterator> 121 multimap(_InputIterator __first, _InputIterator __last, 122 const _Allocator& __a) 123 : _Base(__first, __last, __a) { } 124 #endif 125 126 multimap(const _Base& __x) 127 : _Base(__x) { } 128 129 #if __cplusplus < 201103L 130 multimap& 131 operator=(const multimap& __x) 132 { 133 this->_M_profile_destruct(); 134 _M_base() = __x; 135 this->_M_profile_construct(); 136 return *this; 137 } 138 #else 139 multimap& 140 operator=(const multimap&) = default; 141 142 multimap& 143 operator=(multimap&&) = default; 144 145 multimap& 146 operator=(initializer_list<value_type> __l) 147 { 148 this->_M_profile_destruct(); 149 _M_base() = __l; 150 this->_M_profile_construct(); 151 return *this; 152 } 153 #endif 154 155 // iterators 156 iterator 157 begin() _GLIBCXX_NOEXCEPT 158 { return iterator(_Base::begin(), this); } 159 160 const_iterator 161 begin() const _GLIBCXX_NOEXCEPT 162 { return const_iterator(_Base::begin(), this); } 163 164 iterator 165 end() _GLIBCXX_NOEXCEPT 166 { return iterator(_Base::end(), this); } 167 168 const_iterator 169 end() const _GLIBCXX_NOEXCEPT 170 { return const_iterator(_Base::end(), this); } 171 172 #if __cplusplus >= 201103L 173 const_iterator 174 cbegin() const noexcept 175 { return const_iterator(_Base::cbegin(), this); } 176 177 const_iterator 178 cend() const noexcept 179 { return const_iterator(_Base::cend(), this); } 180 #endif 181 182 reverse_iterator 183 rbegin() _GLIBCXX_NOEXCEPT 184 { 185 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 186 return reverse_iterator(end()); 187 } 188 189 const_reverse_iterator 190 rbegin() const _GLIBCXX_NOEXCEPT 191 { 192 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 193 return const_reverse_iterator(end()); 194 } 195 196 reverse_iterator 197 rend() _GLIBCXX_NOEXCEPT 198 { 199 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 200 return reverse_iterator(begin()); 201 } 202 203 const_reverse_iterator 204 rend() const _GLIBCXX_NOEXCEPT 205 { 206 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 207 return const_reverse_iterator(begin()); 208 } 209 210 #if __cplusplus >= 201103L 211 const_reverse_iterator 212 crbegin() const noexcept 213 { 214 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 215 return const_reverse_iterator(cend()); 216 } 217 218 const_reverse_iterator 219 crend() const noexcept 220 { 221 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 222 return const_reverse_iterator(cbegin()); 223 } 224 #endif 225 226 // modifiers: 227 #if __cplusplus >= 201103L 228 template<typename... _Args> 229 iterator 230 emplace(_Args&&... __args) 231 { 232 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 233 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); 234 } 235 236 template<typename... _Args> 237 iterator 238 emplace_hint(const_iterator __pos, _Args&&... __args) 239 { 240 auto size_before = this->size(); 241 auto __res 242 = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...); 243 __profcxx_map2umap_insert(this->_M_map2umap_info, 244 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 245 return iterator(__res, this); 246 } 247 #endif 248 249 iterator 250 insert(const value_type& __x) 251 { 252 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 253 return iterator(_Base::insert(__x), this); 254 } 255 256 #if __cplusplus >= 201103L 257 template<typename _Pair, typename = typename 258 std::enable_if<std::is_constructible<value_type, 259 _Pair&&>::value>::type> 260 iterator 261 insert(_Pair&& __x) 262 { 263 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 264 return iterator(_Base::insert(std::forward<_Pair>(__x)), this); 265 } 266 #endif 267 268 #if __cplusplus >= 201103L 269 void 270 insert(std::initializer_list<value_type> __list) 271 { insert(__list.begin(), __list.end()); } 272 #endif 273 274 iterator 275 #if __cplusplus >= 201103L 276 insert(const_iterator __pos, const value_type& __x) 277 #else 278 insert(iterator __pos, const value_type& __x) 279 #endif 280 { 281 size_type size_before = this->size(); 282 _Base_iterator __res = _Base::insert(__pos.base(), __x); 283 __profcxx_map2umap_insert(this->_M_map2umap_info, 284 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 285 return iterator(__res, this); 286 } 287 288 #if __cplusplus >= 201103L 289 template<typename _Pair, typename = typename 290 std::enable_if<std::is_constructible<value_type, 291 _Pair&&>::value>::type> 292 iterator 293 insert(const_iterator __pos, _Pair&& __x) 294 { 295 size_type size_before = this->size(); 296 auto __res = _Base::insert(__pos.base(), std::forward<_Pair>(__x)); 297 __profcxx_map2umap_insert(this->_M_map2umap_info, 298 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 299 return iterator(__res, this); 300 } 301 #endif 302 303 template<typename _InputIterator> 304 void 305 insert(_InputIterator __first, _InputIterator __last) 306 { 307 for (; __first != __last; ++__first) 308 insert(*__first); 309 } 310 311 #if __cplusplus >= 201103L 312 iterator 313 erase(const_iterator __pos) 314 { 315 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 316 return iterator(_Base::erase(__pos.base()), this); 317 } 318 319 iterator 320 erase(iterator __pos) 321 { 322 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 323 return iterator(_Base::erase(__pos.base()), this); 324 } 325 #else 326 void 327 erase(iterator __pos) 328 { 329 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 330 _Base::erase(__pos.base()); 331 } 332 #endif 333 334 size_type 335 erase(const key_type& __x) 336 { 337 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 338 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 339 return _Base::erase(__x); 340 } 341 342 #if __cplusplus >= 201103L 343 iterator 344 erase(const_iterator __first, const_iterator __last) 345 { 346 if (__first != __last) 347 { 348 iterator __ret; 349 for (; __first != __last;) 350 __ret = erase(__first++); 351 return __ret; 352 } 353 else 354 return iterator(_Base::erase(__first.base(), __last.base()), this); 355 } 356 #else 357 void 358 erase(iterator __first, iterator __last) 359 { 360 for (; __first != __last;) 361 erase(__first++); 362 } 363 #endif 364 365 void 366 swap(multimap& __x) 367 #if __cplusplus >= 201103L 368 noexcept( noexcept(declval<_Base>().swap(__x)) ) 369 #endif 370 { 371 std::swap(this->_M_map2umap_info, __x._M_map2umap_info); 372 _Base::swap(__x); 373 } 374 375 void 376 clear() _GLIBCXX_NOEXCEPT 377 { 378 this->_M_profile_destruct(); 379 _Base::clear(); 380 this->_M_profile_construct(); 381 } 382 383 // 23.3.1.3 multimap operations: 384 iterator 385 find(const key_type& __x) 386 { 387 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 388 return iterator(_Base::find(__x), this); 389 } 390 391 const_iterator 392 find(const key_type& __x) const 393 { 394 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 395 return const_iterator(_Base::find(__x), this); 396 } 397 398 size_type 399 count(const key_type& __x) const 400 { 401 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 402 return _Base::count(__x); 403 } 404 405 iterator 406 lower_bound(const key_type& __x) 407 { 408 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 409 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 410 return iterator(_Base::lower_bound(__x), this); 411 } 412 413 const_iterator 414 lower_bound(const key_type& __x) const 415 { 416 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 417 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 418 return const_iterator(_Base::lower_bound(__x), this); 419 } 420 421 iterator 422 upper_bound(const key_type& __x) 423 { 424 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 425 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 426 return iterator(_Base::upper_bound(__x), this); 427 } 428 429 const_iterator 430 upper_bound(const key_type& __x) const 431 { 432 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 433 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 434 return const_iterator(_Base::upper_bound(__x), this); 435 } 436 437 std::pair<iterator,iterator> 438 equal_range(const key_type& __x) 439 { 440 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 441 std::pair<_Base_iterator, _Base_iterator> __base_ret 442 = _Base::equal_range(__x); 443 return std::make_pair(iterator(__base_ret.first, this), 444 iterator(__base_ret.second, this)); 445 } 446 447 std::pair<const_iterator,const_iterator> 448 equal_range(const key_type& __x) const 449 { 450 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 451 std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret 452 = _Base::equal_range(__x); 453 return std::make_pair(const_iterator(__base_ret.first, this), 454 const_iterator(__base_ret.second, this)); 455 } 456 457 _Base& 458 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 459 460 const _Base& 461 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 462 463 private: 464 /** If hint is used we consider that the map and unordered_map 465 * operations have equivalent insertion cost so we do not update metrics 466 * about it. 467 * Note that to find out if hint has been used is libstdc++ 468 * implementation dependent. 469 */ 470 bool 471 _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res) 472 { 473 return (__hint == __res 474 || (__hint == _M_base().end() && ++__res == _M_base().end()) 475 || (__hint != _M_base().end() && (++__hint == __res 476 || ++__res == --__hint))); 477 } 478 479 template<typename _K1, typename _T1, typename _C1, typename _A1> 480 friend bool 481 operator==(const multimap<_K1, _T1, _C1, _A1>&, 482 const multimap<_K1, _T1, _C1, _A1>&); 483 484 template<typename _K1, typename _T1, typename _C1, typename _A1> 485 friend bool 486 operator<(const multimap<_K1, _T1, _C1, _A1>&, 487 const multimap<_K1, _T1, _C1, _A1>&); 488 }; 489 490 template<typename _Key, typename _Tp, 491 typename _Compare, typename _Allocator> 492 inline bool 493 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 494 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 495 { 496 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 497 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 498 return __lhs._M_base() == __rhs._M_base(); 499 } 500 501 template<typename _Key, typename _Tp, 502 typename _Compare, typename _Allocator> 503 inline bool 504 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 505 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 506 { 507 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 508 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 509 return __lhs._M_base() < __rhs._M_base(); 510 } 511 512 template<typename _Key, typename _Tp, 513 typename _Compare, typename _Allocator> 514 inline bool 515 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 516 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 517 { return !(__lhs == __rhs); } 518 519 template<typename _Key, typename _Tp, 520 typename _Compare, typename _Allocator> 521 inline bool 522 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 523 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 524 { return !(__rhs < __lhs); } 525 526 template<typename _Key, typename _Tp, 527 typename _Compare, typename _Allocator> 528 inline bool 529 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 530 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 531 { return !(__lhs < __rhs); } 532 533 template<typename _Key, typename _Tp, 534 typename _Compare, typename _Allocator> 535 inline bool 536 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 537 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 538 { return __rhs < __lhs; } 539 540 template<typename _Key, typename _Tp, 541 typename _Compare, typename _Allocator> 542 inline void 543 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 544 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 545 { __lhs.swap(__rhs); } 546 547 } // namespace __profile 548 } // namespace std 549 550 #endif 551