1 // Profiling multiset implementation -*- C++ -*- 2 3 // Copyright (C) 2009-2018 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/multiset.h 26 * This file is a GNU profile extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_PROFILE_MULTISET_H 30 #define _GLIBCXX_PROFILE_MULTISET_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::multiset wrapper with performance instrumentation. 40 template<typename _Key, typename _Compare = std::less<_Key>, 41 typename _Allocator = std::allocator<_Key> > 42 class multiset 43 : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>, 44 public _Ordered_profile<multiset<_Key, _Compare, _Allocator> > 45 { 46 typedef _GLIBCXX_STD_C::multiset<_Key, _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 _Key value_type; 55 typedef _Compare key_compare; 56 typedef _Compare value_compare; 57 typedef _Allocator allocator_type; 58 typedef typename _Base::reference reference; 59 typedef typename _Base::const_reference const_reference; 60 61 typedef __iterator_tracker<_Base_iterator, 62 multiset> iterator; 63 typedef __iterator_tracker<_Base_const_iterator, 64 multiset> const_iterator; 65 typedef std::reverse_iterator<iterator> reverse_iterator; 66 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 67 68 typedef typename _Base::size_type size_type; 69 typedef typename _Base::difference_type difference_type; 70 71 // 23.3.3.1 construct/copy/destroy: 72 73 #if __cplusplus < 201103L 74 multiset() 75 : _Base() { } 76 multiset(const multiset& __x) 77 : _Base(__x) { } 78 ~multiset() { } 79 #else 80 multiset() = default; 81 multiset(const multiset&) = default; 82 multiset(multiset&&) = default; 83 ~multiset() = default; 84 #endif 85 86 explicit multiset(const _Compare& __comp, 87 const _Allocator& __a = _Allocator()) 88 : _Base(__comp, __a) { } 89 90 #if __cplusplus >= 201103L 91 template<typename _InputIterator, 92 typename = std::_RequireInputIter<_InputIterator>> 93 #else 94 template<typename _InputIterator> 95 #endif 96 multiset(_InputIterator __first, _InputIterator __last, 97 const _Compare& __comp = _Compare(), 98 const _Allocator& __a = _Allocator()) 99 : _Base(__first, __last, __comp, __a) { } 100 101 #if __cplusplus >= 201103L 102 multiset(initializer_list<value_type> __l, 103 const _Compare& __comp = _Compare(), 104 const allocator_type& __a = allocator_type()) 105 : _Base(__l, __comp, __a) { } 106 107 explicit 108 multiset(const allocator_type& __a) 109 : _Base(__a) { } 110 111 multiset(const multiset& __x, const allocator_type& __a) 112 : _Base(__x, __a) { } 113 114 multiset(multiset&& __x, const allocator_type& __a) 115 noexcept( noexcept(_Base(std::move(__x), __a)) ) 116 : _Base(std::move(__x), __a) { } 117 118 multiset(initializer_list<value_type> __l, const allocator_type& __a) 119 : _Base(__l, __a) { } 120 121 template<typename _InputIterator> 122 multiset(_InputIterator __first, _InputIterator __last, 123 const allocator_type& __a) 124 : _Base(__first, __last, __a) { } 125 #endif 126 127 multiset(const _Base& __x) 128 : _Base(__x) { } 129 130 #if __cplusplus < 201103L 131 multiset& 132 operator=(const multiset& __x) 133 { 134 this->_M_profile_destruct(); 135 _M_base() = __x; 136 this->_M_profile_construct(); 137 return *this; 138 } 139 #else 140 multiset& 141 operator=(const multiset&) = default; 142 143 multiset& 144 operator=(multiset&&) = default; 145 146 multiset& 147 operator=(initializer_list<value_type> __l) 148 { 149 this->_M_profile_destruct(); 150 _M_base() = __l; 151 this->_M_profile_construct(); 152 return *this; 153 } 154 #endif 155 156 // iterators 157 iterator 158 begin() _GLIBCXX_NOEXCEPT 159 { return iterator(_Base::begin(), this); } 160 161 const_iterator 162 begin() const _GLIBCXX_NOEXCEPT 163 { return const_iterator(_Base::begin(), this); } 164 165 iterator 166 end() _GLIBCXX_NOEXCEPT 167 { return iterator(_Base::end(), this); } 168 169 const_iterator 170 end() const _GLIBCXX_NOEXCEPT 171 { return const_iterator(_Base::end(), this); } 172 173 #if __cplusplus >= 201103L 174 const_iterator 175 cbegin() const noexcept 176 { return const_iterator(_Base::cbegin(), this); } 177 178 const_iterator 179 cend() const noexcept 180 { return const_iterator(_Base::cend(), this); } 181 #endif 182 183 reverse_iterator 184 rbegin() _GLIBCXX_NOEXCEPT 185 { 186 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 187 return reverse_iterator(end()); 188 } 189 190 const_reverse_iterator 191 rbegin() const _GLIBCXX_NOEXCEPT 192 { 193 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 194 return const_reverse_iterator(end()); 195 } 196 197 reverse_iterator 198 rend() _GLIBCXX_NOEXCEPT 199 { 200 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 201 return reverse_iterator(begin()); 202 } 203 204 const_reverse_iterator 205 rend() const _GLIBCXX_NOEXCEPT 206 { 207 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 208 return const_reverse_iterator(begin()); 209 } 210 211 #if __cplusplus >= 201103L 212 const_reverse_iterator 213 crbegin() const noexcept 214 { 215 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 216 return const_reverse_iterator(cend()); 217 } 218 219 const_reverse_iterator 220 crend() const noexcept 221 { 222 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 223 return const_reverse_iterator(cbegin()); 224 } 225 #endif 226 227 void 228 swap(multiset& __x) 229 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 230 { 231 _Base::swap(__x); 232 this->_M_swap(__x); 233 } 234 235 // modifiers: 236 #if __cplusplus >= 201103L 237 template<typename... _Args> 238 iterator 239 emplace(_Args&&... __args) 240 { 241 // The cost is the same whether or not the element is inserted so we 242 // always report insertion of 1 element. 243 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 244 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); 245 } 246 247 template<typename... _Args> 248 iterator 249 emplace_hint(const_iterator __pos, _Args&&... __args) 250 { 251 auto size_before = this->size(); 252 auto __res 253 = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...); 254 __profcxx_map2umap_insert(this->_M_map2umap_info, 255 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 256 return iterator(__res, this); 257 } 258 #endif 259 260 iterator 261 insert(const value_type& __x) 262 { 263 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 264 return iterator(_Base::insert(__x), this); 265 } 266 267 #if __cplusplus >= 201103L 268 iterator 269 insert(value_type&& __x) 270 { 271 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 272 return iterator(_Base::insert(std::move(__x)), this); 273 } 274 #endif 275 276 iterator 277 insert(const_iterator __pos, const value_type& __x) 278 { 279 size_type size_before = this->size(); 280 _Base_iterator __res = _Base::insert(__pos.base(), __x); 281 282 __profcxx_map2umap_insert(this->_M_map2umap_info, 283 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 284 return iterator(__res, this); 285 } 286 287 #if __cplusplus >= 201103L 288 iterator 289 insert(const_iterator __pos, value_type&& __x) 290 { 291 auto size_before = this->size(); 292 auto __res = _Base::insert(__pos.base(), std::move(__x)); 293 __profcxx_map2umap_insert(this->_M_map2umap_info, 294 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 295 return iterator(__res, this); 296 } 297 #endif 298 299 #if __cplusplus >= 201103L 300 template<typename _InputIterator, 301 typename = std::_RequireInputIter<_InputIterator>> 302 #else 303 template<typename _InputIterator> 304 #endif 305 void 306 insert(_InputIterator __first, _InputIterator __last) 307 { 308 for (; __first != __last; ++__first) 309 insert(*__first); 310 } 311 312 #if __cplusplus >= 201103L 313 void 314 insert(initializer_list<value_type> __l) 315 { insert(__l.begin(), __l.end()); } 316 #endif 317 318 #if __cplusplus >= 201103L 319 iterator 320 erase(const_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 clear() _GLIBCXX_NOEXCEPT 367 { 368 this->_M_profile_destruct(); 369 _Base::clear(); 370 this->_M_profile_construct(); 371 } 372 373 size_type 374 count(const key_type& __x) const 375 { 376 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 377 return _Base::count(__x); 378 } 379 380 #if __cplusplus > 201103L 381 template<typename _Kt, 382 typename _Req = 383 typename __has_is_transparent<_Compare, _Kt>::type> 384 size_type 385 count(const _Kt& __x) const 386 { 387 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 388 return _Base::count(__x); 389 } 390 #endif 391 392 // multiset operations: 393 iterator 394 find(const key_type& __x) 395 { 396 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 397 return iterator(_Base::find(__x), this); 398 } 399 400 // _GLIBCXX_RESOLVE_LIB_DEFECTS 401 // 214. set::find() missing const overload 402 const_iterator 403 find(const key_type& __x) const 404 { 405 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 406 return const_iterator(_Base::find(__x), this); 407 } 408 409 #if __cplusplus > 201103L 410 template<typename _Kt, 411 typename _Req = 412 typename __has_is_transparent<_Compare, _Kt>::type> 413 iterator 414 find(const _Kt& __x) 415 { 416 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 417 return { _Base::find(__x), this }; 418 } 419 420 template<typename _Kt, 421 typename _Req = 422 typename __has_is_transparent<_Compare, _Kt>::type> 423 const_iterator 424 find(const _Kt& __x) const 425 { 426 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 427 return { _Base::find(__x), this }; 428 } 429 #endif 430 431 iterator 432 lower_bound(const key_type& __x) 433 { 434 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 435 return iterator(_Base::lower_bound(__x), this); 436 } 437 438 // _GLIBCXX_RESOLVE_LIB_DEFECTS 439 // 214. set::find() missing const overload 440 const_iterator 441 lower_bound(const key_type& __x) const 442 { 443 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 444 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 445 return const_iterator(_Base::lower_bound(__x), this); 446 } 447 448 #if __cplusplus > 201103L 449 template<typename _Kt, 450 typename _Req = 451 typename __has_is_transparent<_Compare, _Kt>::type> 452 iterator 453 lower_bound(const _Kt& __x) 454 { 455 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 456 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 457 return { _Base::lower_bound(__x), this }; 458 } 459 460 template<typename _Kt, 461 typename _Req = 462 typename __has_is_transparent<_Compare, _Kt>::type> 463 const_iterator 464 lower_bound(const _Kt& __x) const 465 { 466 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 467 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 468 return { _Base::lower_bound(__x), this }; 469 } 470 #endif 471 472 iterator 473 upper_bound(const key_type& __x) 474 { 475 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 476 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 477 return iterator(_Base::upper_bound(__x), this); 478 } 479 480 // _GLIBCXX_RESOLVE_LIB_DEFECTS 481 // 214. set::find() missing const overload 482 const_iterator 483 upper_bound(const key_type& __x) const 484 { 485 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 486 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 487 return const_iterator(_Base::upper_bound(__x), this); 488 } 489 490 #if __cplusplus > 201103L 491 template<typename _Kt, 492 typename _Req = 493 typename __has_is_transparent<_Compare, _Kt>::type> 494 iterator 495 upper_bound(const _Kt& __x) 496 { 497 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 498 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 499 return { _Base::upper_bound(__x), this }; 500 } 501 502 template<typename _Kt, 503 typename _Req = 504 typename __has_is_transparent<_Compare, _Kt>::type> 505 const_iterator 506 upper_bound(const _Kt& __x) const 507 { 508 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 509 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 510 return { _Base::upper_bound(__x), this }; 511 } 512 #endif 513 514 std::pair<iterator,iterator> 515 equal_range(const key_type& __x) 516 { 517 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 518 std::pair<_Base_iterator, _Base_iterator> __base_ret 519 = _Base::equal_range(__x); 520 return std::make_pair(iterator(__base_ret.first, this), 521 iterator(__base_ret.second, this)); 522 } 523 524 // _GLIBCXX_RESOLVE_LIB_DEFECTS 525 // 214. set::find() missing const overload 526 std::pair<const_iterator,const_iterator> 527 equal_range(const key_type& __x) const 528 { 529 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 530 std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret 531 = _Base::equal_range(__x); 532 return std::make_pair(const_iterator(__base_ret.first, this), 533 const_iterator(__base_ret.second, this)); 534 } 535 536 #if __cplusplus > 201103L 537 template<typename _Kt, 538 typename _Req = 539 typename __has_is_transparent<_Compare, _Kt>::type> 540 std::pair<iterator, iterator> 541 equal_range(const _Kt& __x) 542 { 543 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 544 auto __res = _Base::equal_range(__x); 545 return { { __res.first, this }, { __res.second, this } }; 546 } 547 548 template<typename _Kt, 549 typename _Req = 550 typename __has_is_transparent<_Compare, _Kt>::type> 551 std::pair<const_iterator, const_iterator> 552 equal_range(const _Kt& __x) const 553 { 554 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 555 auto __res = _Base::equal_range(__x); 556 return { { __res.first, this }, { __res.second, this } }; 557 } 558 #endif 559 560 _Base& 561 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 562 563 const _Base& 564 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 565 566 private: 567 /** If hint is used we consider that the map and unordered_map 568 * operations have equivalent insertion cost so we do not update metrics 569 * about it. 570 * Note that to find out if hint has been used is libstdc++ 571 * implementation dependent. 572 */ 573 bool 574 _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res) 575 { 576 return (__hint == __res 577 || (__hint == _M_base().end() && ++__res == _M_base().end()) 578 || (__hint != _M_base().end() && (++__hint == __res 579 || ++__res == --__hint))); 580 } 581 582 template<typename _K1, typename _C1, typename _A1> 583 friend bool 584 operator==(const multiset<_K1, _C1, _A1>&, 585 const multiset<_K1, _C1, _A1>&); 586 587 template<typename _K1, typename _C1, typename _A1> 588 friend bool 589 operator< (const multiset<_K1, _C1, _A1>&, 590 const multiset<_K1, _C1, _A1>&); 591 }; 592 593 template<typename _Key, typename _Compare, typename _Allocator> 594 inline bool 595 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs, 596 const multiset<_Key, _Compare, _Allocator>& __rhs) 597 { 598 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 599 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 600 return __lhs._M_base() == __rhs._M_base(); 601 } 602 603 template<typename _Key, typename _Compare, typename _Allocator> 604 inline bool 605 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs, 606 const multiset<_Key, _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 _Compare, typename _Allocator> 614 inline bool 615 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs, 616 const multiset<_Key, _Compare, _Allocator>& __rhs) 617 { return !(__lhs == __rhs); } 618 619 template<typename _Key, typename _Compare, typename _Allocator> 620 inline bool 621 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs, 622 const multiset<_Key, _Compare, _Allocator>& __rhs) 623 { return !(__rhs < __lhs); } 624 625 template<typename _Key, typename _Compare, typename _Allocator> 626 inline bool 627 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs, 628 const multiset<_Key, _Compare, _Allocator>& __rhs) 629 { return !(__lhs < __rhs); } 630 631 template<typename _Key, typename _Compare, typename _Allocator> 632 inline bool 633 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs, 634 const multiset<_Key, _Compare, _Allocator>& __rhs) 635 { return __rhs < __lhs; } 636 637 template<typename _Key, typename _Compare, typename _Allocator> 638 void 639 swap(multiset<_Key, _Compare, _Allocator>& __x, 640 multiset<_Key, _Compare, _Allocator>& __y) 641 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 642 { return __x.swap(__y); } 643 644 } // namespace __profile 645 } // namespace std 646 647 #endif 648