multimap.h revision 1.6
1// Profiling multimap implementation -*- C++ -*- 2 3// Copyright (C) 2009-2016 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 35namespace std _GLIBCXX_VISIBILITY(default) 36{ 37namespace __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 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 368 { 369 std::swap(this->_M_map2umap_info, __x._M_map2umap_info); 370 _Base::swap(__x); 371 } 372 373 void 374 clear() _GLIBCXX_NOEXCEPT 375 { 376 this->_M_profile_destruct(); 377 _Base::clear(); 378 this->_M_profile_construct(); 379 } 380 381 // 23.3.1.3 multimap operations: 382 iterator 383 find(const key_type& __x) 384 { 385 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 386 return iterator(_Base::find(__x), this); 387 } 388 389#if __cplusplus > 201103L 390 template<typename _Kt, 391 typename _Req = 392 typename __has_is_transparent<_Compare, _Kt>::type> 393 iterator 394 find(const _Kt& __x) 395 { 396 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 397 return { _Base::find(__x), this }; 398 } 399#endif 400 401 const_iterator 402 find(const key_type& __x) const 403 { 404 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 405 return const_iterator(_Base::find(__x), this); 406 } 407 408#if __cplusplus > 201103L 409 template<typename _Kt, 410 typename _Req = 411 typename __has_is_transparent<_Compare, _Kt>::type> 412 const_iterator 413 find(const _Kt& __x) const 414 { 415 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 416 return { _Base::find(__x), this }; 417 } 418#endif 419 420 size_type 421 count(const key_type& __x) const 422 { 423 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 424 return _Base::count(__x); 425 } 426 427#if __cplusplus > 201103L 428 template<typename _Kt, 429 typename _Req = 430 typename __has_is_transparent<_Compare, _Kt>::type> 431 size_type 432 count(const _Kt& __x) const 433 { 434 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 435 return _Base::count(__x); 436 } 437#endif 438 439 iterator 440 lower_bound(const key_type& __x) 441 { 442 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 443 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 444 return iterator(_Base::lower_bound(__x), this); 445 } 446 447#if __cplusplus > 201103L 448 template<typename _Kt, 449 typename _Req = 450 typename __has_is_transparent<_Compare, _Kt>::type> 451 iterator 452 lower_bound(const _Kt& __x) 453 { 454 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 455 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 456 return { _Base::lower_bound(__x), this }; 457 } 458#endif 459 460 const_iterator 461 lower_bound(const key_type& __x) const 462 { 463 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 464 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 465 return const_iterator(_Base::lower_bound(__x), this); 466 } 467 468#if __cplusplus > 201103L 469 template<typename _Kt, 470 typename _Req = 471 typename __has_is_transparent<_Compare, _Kt>::type> 472 const_iterator 473 lower_bound(const _Kt& __x) const 474 { 475 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 476 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 477 return { _Base::lower_bound(__x), this }; 478 } 479#endif 480 481 iterator 482 upper_bound(const key_type& __x) 483 { 484 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 485 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 486 return iterator(_Base::upper_bound(__x), this); 487 } 488 489#if __cplusplus > 201103L 490 template<typename _Kt, 491 typename _Req = 492 typename __has_is_transparent<_Compare, _Kt>::type> 493 iterator 494 upper_bound(const _Kt& __x) 495 { 496 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 497 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 498 return { _Base::upper_bound(__x), this }; 499 } 500#endif 501 502 const_iterator 503 upper_bound(const key_type& __x) const 504 { 505 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 506 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 507 return const_iterator(_Base::upper_bound(__x), this); 508 } 509 510#if __cplusplus > 201103L 511 template<typename _Kt, 512 typename _Req = 513 typename __has_is_transparent<_Compare, _Kt>::type> 514 const_iterator 515 upper_bound(const _Kt& __x) const 516 { 517 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 518 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 519 return { _Base::upper_bound(__x), this }; 520 } 521#endif 522 523 std::pair<iterator,iterator> 524 equal_range(const key_type& __x) 525 { 526 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 527 std::pair<_Base_iterator, _Base_iterator> __base_ret 528 = _Base::equal_range(__x); 529 return std::make_pair(iterator(__base_ret.first, this), 530 iterator(__base_ret.second, this)); 531 } 532 533#if __cplusplus > 201103L 534 template<typename _Kt, 535 typename _Req = 536 typename __has_is_transparent<_Compare, _Kt>::type> 537 std::pair<iterator, iterator> 538 equal_range(const _Kt& __x) 539 { 540 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 541 auto __res = _Base::equal_range(__x); 542 return { { __res.first, this }, { __res.second, this } }; 543 } 544#endif 545 546 std::pair<const_iterator,const_iterator> 547 equal_range(const key_type& __x) const 548 { 549 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 550 std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret 551 = _Base::equal_range(__x); 552 return std::make_pair(const_iterator(__base_ret.first, this), 553 const_iterator(__base_ret.second, this)); 554 } 555 556#if __cplusplus > 201103L 557 template<typename _Kt, 558 typename _Req = 559 typename __has_is_transparent<_Compare, _Kt>::type> 560 std::pair<const_iterator, const_iterator> 561 equal_range(const _Kt& __x) const 562 { 563 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 564 auto __res = _Base::equal_range(__x); 565 return { { __res.first, this }, { __res.second, this } }; 566 } 567#endif 568 569 _Base& 570 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 571 572 const _Base& 573 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 574 575 private: 576 /** If hint is used we consider that the map and unordered_map 577 * operations have equivalent insertion cost so we do not update metrics 578 * about it. 579 * Note that to find out if hint has been used is libstdc++ 580 * implementation dependent. 581 */ 582 bool 583 _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res) 584 { 585 return (__hint == __res 586 || (__hint == _M_base().end() && ++__res == _M_base().end()) 587 || (__hint != _M_base().end() && (++__hint == __res 588 || ++__res == --__hint))); 589 } 590 591 template<typename _K1, typename _T1, typename _C1, typename _A1> 592 friend bool 593 operator==(const multimap<_K1, _T1, _C1, _A1>&, 594 const multimap<_K1, _T1, _C1, _A1>&); 595 596 template<typename _K1, typename _T1, typename _C1, typename _A1> 597 friend bool 598 operator<(const multimap<_K1, _T1, _C1, _A1>&, 599 const multimap<_K1, _T1, _C1, _A1>&); 600 }; 601 602 template<typename _Key, typename _Tp, 603 typename _Compare, typename _Allocator> 604 inline bool 605 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 606 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 607 { 608 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 609 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 610 return __lhs._M_base() == __rhs._M_base(); 611 } 612 613 template<typename _Key, typename _Tp, 614 typename _Compare, typename _Allocator> 615 inline bool 616 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 617 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 618 { 619 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 620 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 621 return __lhs._M_base() < __rhs._M_base(); 622 } 623 624 template<typename _Key, typename _Tp, 625 typename _Compare, typename _Allocator> 626 inline bool 627 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 628 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 629 { return !(__lhs == __rhs); } 630 631 template<typename _Key, typename _Tp, 632 typename _Compare, typename _Allocator> 633 inline bool 634 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 635 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 636 { return !(__rhs < __lhs); } 637 638 template<typename _Key, typename _Tp, 639 typename _Compare, typename _Allocator> 640 inline bool 641 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 642 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 643 { return !(__lhs < __rhs); } 644 645 template<typename _Key, typename _Tp, 646 typename _Compare, typename _Allocator> 647 inline bool 648 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 649 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 650 { return __rhs < __lhs; } 651 652 template<typename _Key, typename _Tp, 653 typename _Compare, typename _Allocator> 654 inline void 655 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 656 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 657 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) 658 { __lhs.swap(__rhs); } 659 660} // namespace __profile 661} // namespace std 662 663#endif 664