| | 1 | // Debugging multimap implementation -*- C++ -*- |
| | 2 | |
| | 3 | // Copyright (C) 2003-2025 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 debug/multimap.h |
| | 26 | * This file is a GNU debug extension to the Standard C++ Library. |
| | 27 | */ |
| | 28 | |
| | 29 | #ifndef _GLIBCXX_DEBUG_MULTIMAP_H |
| | 30 | #define _GLIBCXX_DEBUG_MULTIMAP_H 1 |
| | 31 | |
| | 32 | #include <debug/safe_sequence.h> |
| | 33 | #include <debug/safe_container.h> |
| | 34 | #include <debug/safe_iterator.h> |
| | 35 | #include <bits/stl_pair.h> |
| | 36 | |
| | 37 | namespace std _GLIBCXX_VISIBILITY(default) |
| | 38 | { |
| | 39 | namespace __debug |
| | 40 | { |
| | 41 | /// Class std::multimap with safety/checking/debug instrumentation. |
| | 42 | template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, |
| | 43 | typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > |
| | 44 | class multimap |
| | 45 | : public __gnu_debug::_Safe_container< |
| | 46 | multimap<_Key, _Tp, _Compare, _Allocator>, _Allocator, |
| | 47 | __gnu_debug::_Safe_node_sequence>, |
| | 48 | public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> |
| | 49 | { |
| | 50 | typedef _GLIBCXX_STD_C::multimap< |
| | 51 | _Key, _Tp, _Compare, _Allocator> _Base; |
| | 52 | typedef __gnu_debug::_Safe_container< |
| | 53 | multimap, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; |
| | 54 | |
| | 55 | typedef typename _Base::const_iterator _Base_const_iterator; |
| | 56 | typedef typename _Base::iterator _Base_iterator; |
| | 57 | typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; |
| | 58 | |
| | 59 | template<typename _ItT, typename _SeqT, typename _CatT> |
| | 60 | friend class ::__gnu_debug::_Safe_iterator; |
| | 61 | |
| | 62 | // Reference wrapper for base class. Disambiguates multimap(const _Base&) |
| | 63 | // from copy constructor by requiring a user-defined conversion. |
| | 64 | // See PR libstdc++/90102. |
| | 65 | struct _Base_ref |
| | 66 | { |
| | 67 | _Base_ref(const _Base& __r) : _M_ref(__r) { } |
| | 68 | |
| | 69 | const _Base& _M_ref; |
| | 70 | }; |
| | 71 | |
| | 72 | public: |
| | 73 | // types: |
| | 74 | typedef _Key key_type; |
| | 75 | typedef _Tp mapped_type; |
| | 76 | typedef std::pair<const _Key, _Tp> value_type; |
| | 77 | typedef _Compare key_compare; |
| | 78 | typedef _Allocator allocator_type; |
| | 79 | typedef typename _Base::reference reference; |
| | 80 | typedef typename _Base::const_reference const_reference; |
| | 81 | |
| | 82 | typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap> |
| | 83 | iterator; |
| | 84 | typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, |
| | 85 | multimap> const_iterator; |
| | 86 | |
| | 87 | typedef typename _Base::size_type size_type; |
| | 88 | typedef typename _Base::difference_type difference_type; |
| | 89 | typedef typename _Base::pointer pointer; |
| | 90 | typedef typename _Base::const_pointer const_pointer; |
| | 91 | typedef std::reverse_iterator<iterator> reverse_iterator; |
| | 92 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
| | 93 | |
| | 94 | // 23.3.1.1 construct/copy/destroy: |
| | 95 | |
| | 96 | #if __cplusplus < 201103L |
| | 97 | multimap() : _Base() { } |
| | 98 | |
| | 99 | multimap(const multimap& __x) |
| | 100 | : _Base(__x) { } |
| | 101 | |
| | 102 | ~multimap() { } |
| | 103 | #else |
| | 104 | multimap() = default; |
| | 105 | multimap(const multimap&) = default; |
| | 106 | multimap(multimap&&) = default; |
| | 107 | |
| | 108 | multimap(initializer_list<value_type> __l, |
| | 109 | const _Compare& __c = _Compare(), |
| | 110 | const allocator_type& __a = allocator_type()) |
| | 111 | : _Base(__l, __c, __a) { } |
| | 112 | |
| | 113 | explicit |
| | 114 | multimap(const allocator_type& __a) |
| | 115 | : _Base(__a) { } |
| | 116 | |
| | 117 | multimap(const multimap& __m, |
| | 118 | const __type_identity_t<allocator_type>& __a) |
| | 119 | : _Base(__m, __a) { } |
| | 120 | |
| | 121 | multimap(multimap&& __m, const __type_identity_t<allocator_type>& __a) |
| | 122 | noexcept( noexcept(_Base(std::move(__m), __a)) ) |
| | 123 | : _Safe(std::move(__m), __a), |
| | 124 | _Base(std::move(__m), __a) { } |
| | 125 | |
| | 126 | multimap(initializer_list<value_type> __l, const allocator_type& __a) |
| | 127 | : _Base(__l, __a) { } |
| | 128 | |
| | 129 | template<typename _InputIterator> |
| | 130 | multimap(_InputIterator __first, _InputIterator __last, |
| | 131 | const allocator_type& __a) |
| | 132 | : _Base(__gnu_debug::__base( |
| | 133 | __glibcxx_check_valid_constructor_range(__first, __last)), |
| | 134 | __gnu_debug::__base(__last), __a) { } |
| | 135 | |
| | 136 | #if __glibcxx_containers_ranges // C++ >= 23 |
| | 137 | /** |
| | 138 | * @brief Construct a multimap from a range. |
| | 139 | * @since C++23 |
| | 140 | */ |
| | 141 | template<std::__detail::__container_compatible_range<value_type> _Rg> |
| | 142 | multimap(std::from_range_t __t, _Rg&& __rg, |
| | 143 | const _Compare& __c, |
| | 144 | const allocator_type& __a = allocator_type()) |
| | 145 | : _Base(__t, std::forward<_Rg>(__rg), __c, __a) |
| | 146 | { } |
| | 147 | |
| | 148 | template<std::__detail::__container_compatible_range<value_type> _Rg> |
| | 149 | multimap(std::from_range_t __t, _Rg&& __rg, |
| | 150 | const allocator_type& __a = allocator_type()) |
| | 151 | : _Base(__t, std::forward<_Rg>(__rg), __a) |
| | 152 | { } |
| | 153 | #endif |
| | 154 | |
| | 155 | ~multimap() = default; |
| | 156 | #endif |
| | 157 | |
| | 158 | explicit multimap(const _Compare& __comp, |
| | 159 | const _Allocator& __a = _Allocator()) |
| | 160 | : _Base(__comp, __a) { } |
| | 161 | |
| | 162 | template<typename _InputIterator> |
| | 163 | multimap(_InputIterator __first, _InputIterator __last, |
| | 164 | const _Compare& __comp = _Compare(), |
| | 165 | const _Allocator& __a = _Allocator()) |
| | 166 | : _Base(__gnu_debug::__base( |
| | 167 | __glibcxx_check_valid_constructor_range(__first, __last)), |
| | 168 | __gnu_debug::__base(__last), |
| | 169 | __comp, __a) { } |
| | 170 | |
| | 171 | multimap(_Base_ref __x) |
| | 172 | : _Base(__x._M_ref) { } |
| | 173 | |
| | 174 | #if __cplusplus >= 201103L |
| | 175 | multimap& |
| | 176 | operator=(const multimap&) = default; |
| | 177 | |
| | 178 | multimap& |
| | 179 | operator=(multimap&&) = default; |
| | 180 | |
| | 181 | multimap& |
| | 182 | operator=(initializer_list<value_type> __l) |
| | 183 | { |
| | 184 | _Base::operator=(__l); |
| | 185 | this->_M_invalidate_all(); |
| | 186 | return *this; |
| | 187 | } |
| | 188 | #endif |
| | 189 | |
| | 190 | using _Base::get_allocator; |
| | 191 | |
| | 192 | // iterators: |
| | 193 | iterator |
| | 194 | begin() _GLIBCXX_NOEXCEPT |
| | 195 | { return iterator(_Base::begin(), this); } |
| | 196 | |
| | 197 | const_iterator |
| | 198 | begin() const _GLIBCXX_NOEXCEPT |
| | 199 | { return const_iterator(_Base::begin(), this); } |
| | 200 | |
| | 201 | iterator |
| | 202 | end() _GLIBCXX_NOEXCEPT |
| | 203 | { return iterator(_Base::end(), this); } |
| | 204 | |
| | 205 | const_iterator |
| | 206 | end() const _GLIBCXX_NOEXCEPT |
| | 207 | { return const_iterator(_Base::end(), this); } |
| | 208 | |
| | 209 | reverse_iterator |
| | 210 | rbegin() _GLIBCXX_NOEXCEPT |
| | 211 | { return reverse_iterator(end()); } |
| | 212 | |
| | 213 | const_reverse_iterator |
| | 214 | rbegin() const _GLIBCXX_NOEXCEPT |
| | 215 | { return const_reverse_iterator(end()); } |
| | 216 | |
| | 217 | reverse_iterator |
| | 218 | rend() _GLIBCXX_NOEXCEPT |
| | 219 | { return reverse_iterator(begin()); } |
| | 220 | |
| | 221 | const_reverse_iterator |
| | 222 | rend() const _GLIBCXX_NOEXCEPT |
| | 223 | { return const_reverse_iterator(begin()); } |
| | 224 | |
| | 225 | #if __cplusplus >= 201103L |
| | 226 | const_iterator |
| | 227 | cbegin() const noexcept |
| | 228 | { return const_iterator(_Base::begin(), this); } |
| | 229 | |
| | 230 | const_iterator |
| | 231 | cend() const noexcept |
| | 232 | { return const_iterator(_Base::end(), this); } |
| | 233 | |
| | 234 | const_reverse_iterator |
| | 235 | crbegin() const noexcept |
| | 236 | { return const_reverse_iterator(end()); } |
| | 237 | |
| | 238 | const_reverse_iterator |
| | 239 | crend() const noexcept |
| | 240 | { return const_reverse_iterator(begin()); } |
| | 241 | #endif |
| | 242 | |
| | 243 | // capacity: |
| | 244 | using _Base::empty; |
| | 245 | using _Base::size; |
| | 246 | using _Base::max_size; |
| | 247 | |
| | 248 | // modifiers: |
| | 249 | #if __cplusplus >= 201103L |
| | 250 | template<typename... _Args> |
| | 251 | iterator |
| | 252 | emplace(_Args&&... __args) |
| | 253 | { return { _Base::emplace(std::forward<_Args>(__args)...), this }; } |
| | 254 | |
| | 255 | template<typename... _Args> |
| | 256 | iterator |
| | 257 | emplace_hint(const_iterator __pos, _Args&&... __args) |
| | 258 | { |
| | 259 | __glibcxx_check_insert(__pos); |
| | 260 | return |
| | 261 | { |
| | 262 | _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...), |
| | 263 | this |
| | 264 | }; |
| | 265 | } |
| | 266 | #endif |
| | 267 | |
| | 268 | iterator |
| | 269 | insert(const value_type& __x) |
| | 270 | { return iterator(_Base::insert(__x), this); } |
| | 271 | |
| | 272 | #if __cplusplus >= 201103L |
| | 273 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| | 274 | // 2354. Unnecessary copying when inserting into maps with braced-init |
| | 275 | iterator |
| | 276 | insert(value_type&& __x) |
| | 277 | { return { _Base::insert(std::move(__x)), this }; } |
| | 278 | |
| | 279 | template<typename _Pair, typename = typename |
| | 280 | std::enable_if<std::is_constructible<value_type, |
| | 281 | _Pair&&>::value>::type> |
| | 282 | iterator |
| | 283 | insert(_Pair&& __x) |
| | 284 | { return { _Base::insert(std::forward<_Pair>(__x)), this }; } |
| | 285 | #endif |
| | 286 | |
| | 287 | #if __cplusplus >= 201103L |
| | 288 | void |
| | 289 | insert(std::initializer_list<value_type> __list) |
| | 290 | { _Base::insert(__list); } |
| | 291 | #endif |
| | 292 | |
| | 293 | iterator |
| | 294 | #if __cplusplus >= 201103L |
| | 295 | insert(const_iterator __position, const value_type& __x) |
| | 296 | #else |
| | 297 | insert(iterator __position, const value_type& __x) |
| | 298 | #endif |
| | 299 | { |
| | 300 | __glibcxx_check_insert(__position); |
| | 301 | return iterator(_Base::insert(__position.base(), __x), this); |
| | 302 | } |
| | 303 | |
| | 304 | #if __cplusplus >= 201103L |
| | 305 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| | 306 | // 2354. Unnecessary copying when inserting into maps with braced-init |
| | 307 | iterator |
| | 308 | insert(const_iterator __position, value_type&& __x) |
| | 309 | { |
| | 310 | __glibcxx_check_insert(__position); |
| | 311 | return { _Base::insert(__position.base(), std::move(__x)), this }; |
| | 312 | } |
| | 313 | |
| | 314 | template<typename _Pair, typename = typename |
| | 315 | std::enable_if<std::is_constructible<value_type, |
| | 316 | _Pair&&>::value>::type> |
| | 317 | iterator |
| | 318 | insert(const_iterator __position, _Pair&& __x) |
| | 319 | { |
| | 320 | __glibcxx_check_insert(__position); |
| | 321 | return |
| | 322 | { |
| | 323 | _Base::insert(__position.base(), std::forward<_Pair>(__x)), |
| | 324 | this |
| | 325 | }; |
| | 326 | } |
| | 327 | #endif |
| | 328 | |
| | 329 | template<typename _InputIterator> |
| | 330 | void |
| | 331 | insert(_InputIterator __first, _InputIterator __last) |
| | 332 | { |
| | 333 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
| | 334 | __glibcxx_check_valid_range2(__first, __last, __dist); |
| | 335 | |
| | 336 | if (__dist.second >= __gnu_debug::__dp_sign) |
| | 337 | _Base::insert(__gnu_debug::__unsafe(__first), |
| | 338 | __gnu_debug::__unsafe(__last)); |
| | 339 | else |
| | 340 | _Base::insert(__first, __last); |
| | 341 | } |
| | 342 | |
| | 343 | #if __cplusplus > 201402L |
| | 344 | using node_type = typename _Base::node_type; |
| | 345 | |
| | 346 | node_type |
| | 347 | extract(const_iterator __position) |
| | 348 | { |
| | 349 | __glibcxx_check_erase(__position); |
| | 350 | this->_M_invalidate_if(_Equal(__position.base())); |
| | 351 | return _Base::extract(__position.base()); |
| | 352 | } |
| | 353 | |
| | 354 | node_type |
| | 355 | extract(const key_type& __key) |
| | 356 | { |
| | 357 | const auto __position = find(__key); |
| | 358 | if (__position != end()) |
| | 359 | return extract(__position); |
| | 360 | return {}; |
| | 361 | } |
| | 362 | |
| | 363 | iterator |
| | 364 | insert(node_type&& __nh) |
| | 365 | { return { _Base::insert(std::move(__nh)), this }; } |
| | 366 | |
| | 367 | iterator |
| | 368 | insert(const_iterator __hint, node_type&& __nh) |
| | 369 | { |
| | 370 | __glibcxx_check_insert(__hint); |
| | 371 | return { _Base::insert(__hint.base(), std::move(__nh)), this }; |
| | 372 | } |
| | 373 | |
| | 374 | using _Base::merge; |
| | 375 | #endif // C++17 |
| | 376 | |
| | 377 | #if __cplusplus >= 201103L |
| | 378 | iterator |
| | 379 | erase(const_iterator __position) |
| | 380 | { |
| | 381 | __glibcxx_check_erase(__position); |
| | 382 | return { erase(__position.base()), this }; |
| | 383 | } |
| | 384 | |
| | 385 | _Base_iterator |
| | 386 | erase(_Base_const_iterator __position) |
| | 387 | { |
| | 388 | __glibcxx_check_erase2(__position); |
| | 389 | this->_M_invalidate_if(_Equal(__position)); |
| | 390 | return _Base::erase(__position); |
| | 391 | } |
| | 392 | |
| | 393 | _GLIBCXX_ABI_TAG_CXX11 |
| | 394 | iterator |
| | 395 | erase(iterator __position) |
| | 396 | { return erase(const_iterator(__position)); } |
| | 397 | #else |
| | 398 | void |
| | 399 | erase(iterator __position) |
| | 400 | { |
| | 401 | __glibcxx_check_erase(__position); |
| | 402 | this->_M_invalidate_if(_Equal(__position.base())); |
| | 403 | _Base::erase(__position.base()); |
| | 404 | } |
| | 405 | #endif |
| | 406 | |
| | 407 | size_type |
| | 408 | erase(const key_type& __x) |
| | 409 | { |
| | 410 | std::pair<_Base_iterator, _Base_iterator> __victims = |
| | 411 | _Base::equal_range(__x); |
| | 412 | size_type __count = 0; |
| | 413 | _Base_iterator __victim = __victims.first; |
| | 414 | while (__victim != __victims.second) |
| | 415 | { |
| | 416 | this->_M_invalidate_if(_Equal(__victim)); |
| | 417 | _Base::erase(__victim++); |
| | 418 | ++__count; |
| | 419 | } |
| | 420 | return __count; |
| | 421 | } |
| | 422 | |
| | 423 | #if __cplusplus >= 201103L |
| | 424 | iterator |
| | 425 | erase(const_iterator __first, const_iterator __last) |
| | 426 | { |
| | 427 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| | 428 | // 151. can't currently clear() empty container |
| | 429 | __glibcxx_check_erase_range(__first, __last); |
| | 430 | for (_Base_const_iterator __victim = __first.base(); |
| | 431 | __victim != __last.base(); ++__victim) |
| | 432 | { |
| | 433 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(), |
| | 434 | _M_message(__gnu_debug::__msg_valid_range) |
| | 435 | ._M_iterator(__first, "first") |
| | 436 | ._M_iterator(__last, "last")); |
| | 437 | this->_M_invalidate_if(_Equal(__victim)); |
| | 438 | } |
| | 439 | |
| | 440 | return { _Base::erase(__first.base(), __last.base()), this }; |
| | 441 | } |
| | 442 | #else |
| | 443 | void |
| | 444 | erase(iterator __first, iterator __last) |
| | 445 | { |
| | 446 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| | 447 | // 151. can't currently clear() empty container |
| | 448 | __glibcxx_check_erase_range(__first, __last); |
| | 449 | for (_Base_iterator __victim = __first.base(); |
| | 450 | __victim != __last.base(); ++__victim) |
| | 451 | { |
| | 452 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), |
| | 453 | _M_message(__gnu_debug::__msg_valid_range) |
| | 454 | ._M_iterator(__first, "first") |
| | 455 | ._M_iterator(__last, "last")); |
| | 456 | this->_M_invalidate_if(_Equal(__victim)); |
| | 457 | } |
| | 458 | _Base::erase(__first.base(), __last.base()); |
| | 459 | } |
| | 460 | #endif |
| | 461 | |
| | 462 | void |
| | 463 | swap(multimap& __x) |
| | 464 | _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) |
| | 465 | { |
| | 466 | _Safe::_M_swap(__x); |
| | 467 | _Base::swap(__x); |
| | 468 | } |
| | 469 | |
| | 470 | void |
| | 471 | clear() _GLIBCXX_NOEXCEPT |
| | 472 | { |
| | 473 | this->_M_invalidate_all(); |
| | 474 | _Base::clear(); |
| | 475 | } |
| | 476 | |
| | 477 | // observers: |
| | 478 | using _Base::key_comp; |
| | 479 | using _Base::value_comp; |
| | 480 | |
| | 481 | // 23.3.1.3 multimap operations: |
| | 482 | iterator |
| | 483 | find(const key_type& __x) |
| | 484 | { return iterator(_Base::find(__x), this); } |
| | 485 | |
| | 486 | #if __cplusplus > 201103L |
| | 487 | template<typename _Kt, |
| | 488 | typename _Req = |
| | 489 | typename __has_is_transparent<_Compare, _Kt>::type> |
| | 490 | iterator |
| | 491 | find(const _Kt& __x) |
| | 492 | { return { _Base::find(__x), this }; } |
| | 493 | #endif |
| | 494 | |
| | 495 | const_iterator |
| | 496 | find(const key_type& __x) const |
| | 497 | { return const_iterator(_Base::find(__x), this); } |
| | 498 | |
| | 499 | #if __cplusplus > 201103L |
| | 500 | template<typename _Kt, |
| | 501 | typename _Req = |
| | 502 | typename __has_is_transparent<_Compare, _Kt>::type> |
| | 503 | const_iterator |
| | 504 | find(const _Kt& __x) const |
| | 505 | { return { _Base::find(__x), this }; } |
| | 506 | #endif |
| | 507 | |
| | 508 | using _Base::count; |
| | 509 | |
| | 510 | iterator |
| | 511 | lower_bound(const key_type& __x) |
| | 512 | { return iterator(_Base::lower_bound(__x), this); } |
| | 513 | |
| | 514 | #if __cplusplus > 201103L |
| | 515 | template<typename _Kt, |
| | 516 | typename _Req = |
| | 517 | typename __has_is_transparent<_Compare, _Kt>::type> |
| | 518 | iterator |
| | 519 | lower_bound(const _Kt& __x) |
| | 520 | { return { _Base::lower_bound(__x), this }; } |
| | 521 | #endif |
| | 522 | |
| | 523 | const_iterator |
| | 524 | lower_bound(const key_type& __x) const |
| | 525 | { return const_iterator(_Base::lower_bound(__x), this); } |
| | 526 | |
| | 527 | #if __cplusplus > 201103L |
| | 528 | template<typename _Kt, |
| | 529 | typename _Req = |
| | 530 | typename __has_is_transparent<_Compare, _Kt>::type> |
| | 531 | const_iterator |
| | 532 | lower_bound(const _Kt& __x) const |
| | 533 | { return { _Base::lower_bound(__x), this }; } |
| | 534 | #endif |
| | 535 | |
| | 536 | iterator |
| | 537 | upper_bound(const key_type& __x) |
| | 538 | { return iterator(_Base::upper_bound(__x), this); } |
| | 539 | |
| | 540 | #if __cplusplus > 201103L |
| | 541 | template<typename _Kt, |
| | 542 | typename _Req = |
| | 543 | typename __has_is_transparent<_Compare, _Kt>::type> |
| | 544 | iterator |
| | 545 | upper_bound(const _Kt& __x) |
| | 546 | { return { _Base::upper_bound(__x), this }; } |
| | 547 | #endif |
| | 548 | |
| | 549 | const_iterator |
| | 550 | upper_bound(const key_type& __x) const |
| | 551 | { return const_iterator(_Base::upper_bound(__x), this); } |
| | 552 | |
| | 553 | #if __cplusplus > 201103L |
| | 554 | template<typename _Kt, |
| | 555 | typename _Req = |
| | 556 | typename __has_is_transparent<_Compare, _Kt>::type> |
| | 557 | const_iterator |
| | 558 | upper_bound(const _Kt& __x) const |
| | 559 | { return { _Base::upper_bound(__x), this }; } |
| | 560 | #endif |
| | 561 | |
| | 562 | std::pair<iterator,iterator> |
| | 563 | equal_range(const key_type& __x) |
| | 564 | { |
| | 565 | std::pair<_Base_iterator, _Base_iterator> __res = |
| | 566 | _Base::equal_range(__x); |
| | 567 | return std::make_pair(iterator(__res.first, this), |
| | 568 | iterator(__res.second, this)); |
| | 569 | } |
| | 570 | |
| | 571 | #if __cplusplus > 201103L |
| | 572 | template<typename _Kt, |
| | 573 | typename _Req = |
| | 574 | typename __has_is_transparent<_Compare, _Kt>::type> |
| | 575 | std::pair<iterator, iterator> |
| | 576 | equal_range(const _Kt& __x) |
| | 577 | { |
| | 578 | auto __res = _Base::equal_range(__x); |
| | 579 | return { { __res.first, this }, { __res.second, this } }; |
| | 580 | } |
| | 581 | #endif |
| | 582 | |
| | 583 | std::pair<const_iterator,const_iterator> |
| | 584 | equal_range(const key_type& __x) const |
| | 585 | { |
| | 586 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
| | 587 | _Base::equal_range(__x); |
| | 588 | return std::make_pair(const_iterator(__res.first, this), |
| | 589 | const_iterator(__res.second, this)); |
| | 590 | } |
| | 591 | |
| | 592 | #if __cplusplus > 201103L |
| | 593 | template<typename _Kt, |
| | 594 | typename _Req = |
| | 595 | typename __has_is_transparent<_Compare, _Kt>::type> |
| | 596 | std::pair<const_iterator, const_iterator> |
| | 597 | equal_range(const _Kt& __x) const |
| | 598 | { |
| | 599 | auto __res = _Base::equal_range(__x); |
| | 600 | return { { __res.first, this }, { __res.second, this } }; |
| | 601 | } |
| | 602 | #endif |
| | 603 | |
| | 604 | _Base& |
| | 605 | _M_base() _GLIBCXX_NOEXCEPT { return *this; } |
| | 606 | |
| | 607 | const _Base& |
| | 608 | _M_base() const _GLIBCXX_NOEXCEPT { return *this; } |
| | 609 | }; |
| | 610 | |
| | 611 | #if __cpp_deduction_guides >= 201606 |
| | 612 | |
| | 613 | template<typename _InputIterator, |
| | 614 | typename _Compare = less<__iter_key_t<_InputIterator>>, |
| | 615 | typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, |
| | 616 | typename = _RequireInputIter<_InputIterator>, |
| | 617 | typename = _RequireNotAllocator<_Compare>, |
| | 618 | typename = _RequireAllocator<_Allocator>> |
| | 619 | multimap(_InputIterator, _InputIterator, |
| | 620 | _Compare = _Compare(), _Allocator = _Allocator()) |
| | 621 | -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, |
| | 622 | _Compare, _Allocator>; |
| | 623 | |
| | 624 | template<typename _Key, typename _Tp, typename _Compare = less<_Key>, |
| | 625 | typename _Allocator = allocator<pair<const _Key, _Tp>>, |
| | 626 | typename = _RequireNotAllocator<_Compare>, |
| | 627 | typename = _RequireAllocator<_Allocator>> |
| | 628 | multimap(initializer_list<pair<_Key, _Tp>>, |
| | 629 | _Compare = _Compare(), _Allocator = _Allocator()) |
| | 630 | -> multimap<_Key, _Tp, _Compare, _Allocator>; |
| | 631 | |
| | 632 | template<typename _InputIterator, typename _Allocator, |
| | 633 | typename = _RequireInputIter<_InputIterator>, |
| | 634 | typename = _RequireAllocator<_Allocator>> |
| | 635 | multimap(_InputIterator, _InputIterator, _Allocator) |
| | 636 | -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, |
| | 637 | less<__iter_key_t<_InputIterator>>, _Allocator>; |
| | 638 | |
| | 639 | template<typename _Key, typename _Tp, typename _Allocator, |
| | 640 | typename = _RequireAllocator<_Allocator>> |
| | 641 | multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) |
| | 642 | -> multimap<_Key, _Tp, less<_Key>, _Allocator>; |
| | 643 | |
| | 644 | #if __glibcxx_containers_ranges // C++ >= 23 |
| | 645 | template<ranges::input_range _Rg, |
| | 646 | __not_allocator_like _Compare = less<__detail::__range_key_type<_Rg>>, |
| | 647 | __allocator_like _Alloc = |
| | 648 | std::allocator<__detail::__range_to_alloc_type<_Rg>>> |
| | 649 | multimap(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc()) |
| | 650 | -> multimap<__detail::__range_key_type<_Rg>, |
| | 651 | __detail::__range_mapped_type<_Rg>, |
| | 652 | _Compare, _Alloc>; |
| | 653 | |
| | 654 | template<ranges::input_range _Rg, __allocator_like _Alloc> |
| | 655 | multimap(from_range_t, _Rg&&, _Alloc) |
| | 656 | -> multimap<__detail::__range_key_type<_Rg>, |
| | 657 | __detail::__range_mapped_type<_Rg>, |
| | 658 | less<__detail::__range_key_type<_Rg>>, |
| | 659 | _Alloc>; |
| | 660 | #endif |
| | 661 | #endif |
| | 662 | |
| | 663 | template<typename _Key, typename _Tp, |
| | 664 | typename _Compare, typename _Allocator> |
| | 665 | inline bool |
| | 666 | operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
| | 667 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) |
| | 668 | { return __lhs._M_base() == __rhs._M_base(); } |
| | 669 | |
| | 670 | #if __cpp_lib_three_way_comparison |
| | 671 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> |
| | 672 | inline __detail::__synth3way_t<pair<const _Key, _Tp>> |
| | 673 | operator<=>(const multimap<_Key, _Tp, _Compare, _Alloc>& __lhs, |
| | 674 | const multimap<_Key, _Tp, _Compare, _Alloc>& __rhs) |
| | 675 | { return __lhs._M_base() <=> __rhs._M_base(); } |
| | 676 | #else |
| | 677 | template<typename _Key, typename _Tp, |
| | 678 | typename _Compare, typename _Allocator> |
| | 679 | inline bool |
| | 680 | operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
| | 681 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) |
| | 682 | { return __lhs._M_base() != __rhs._M_base(); } |
| | 683 | |
| | 684 | template<typename _Key, typename _Tp, |
| | 685 | typename _Compare, typename _Allocator> |
| | 686 | inline bool |
| | 687 | operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
| | 688 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) |
| | 689 | { return __lhs._M_base() < __rhs._M_base(); } |
| | 690 | |
| | 691 | template<typename _Key, typename _Tp, |
| | 692 | typename _Compare, typename _Allocator> |
| | 693 | inline bool |
| | 694 | operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
| | 695 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) |
| | 696 | { return __lhs._M_base() <= __rhs._M_base(); } |
| | 697 | |
| | 698 | template<typename _Key, typename _Tp, |
| | 699 | typename _Compare, typename _Allocator> |
| | 700 | inline bool |
| | 701 | operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
| | 702 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) |
| | 703 | { return __lhs._M_base() >= __rhs._M_base(); } |
| | 704 | |
| | 705 | template<typename _Key, typename _Tp, |
| | 706 | typename _Compare, typename _Allocator> |
| | 707 | inline bool |
| | 708 | operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
| | 709 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) |
| | 710 | { return __lhs._M_base() > __rhs._M_base(); } |
| | 711 | #endif // three-way comparison |
| | 712 | |
| | 713 | template<typename _Key, typename _Tp, |
| | 714 | typename _Compare, typename _Allocator> |
| | 715 | inline void |
| | 716 | swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
| | 717 | multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) |
| | 718 | _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) |
| | 719 | { __lhs.swap(__rhs); } |
| | 720 | |
| | 721 | } // namespace __debug |
| | 722 | } // namespace std |
| | 723 | |
| | 724 | #endif |
projects / thirdparty / gcc.git / blame_incremental