Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/flat_map
1 // <flat_map> -*- C++ -*- 2 3 // Copyright The GNU Toolchain Authors. 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 include/flat_map 26 * This is a Standard C++ Library header. 27 */ 28 29 #ifndef _GLIBCXX_FLAT_MAP 30 #define _GLIBCXX_FLAT_MAP 1 31 32 #ifdef _GLIBCXX_SYSHDR 33 #pragma GCC system_header 34 #endif 35 36 #define __glibcxx_want_flat_map 37 #include <bits/version.h> 38 39 #ifdef __cpp_lib_flat_map // >= C++23 40 41 #include <compare> 42 #include <initializer_list> 43 44 #include <exception> 45 #include <functional> // not_fn 46 #include <optional> 47 #include <ranges> // views::zip 48 #include <type_traits> 49 #include <vector> 50 #include <bits/functexcept.h> 51 #include <bits/stl_algo.h> 52 #include <bits/stl_function.h> // less 53 #include <bits/stl_pair.h> 54 #include <bits/uses_allocator_args.h> // make_obj_using_allocator 55 #include <bits/ranges_algo.h> 56 57 namespace std _GLIBCXX_VISIBILITY(default) 58 { 59 _GLIBCXX_BEGIN_NAMESPACE_VERSION 60 61 template<typename _Key, typename _Tp, typename _Compare, 62 typename _KeyContainer, typename _MappedContainer> 63 class flat_map; 64 65 template<typename _Key, typename _Tp, typename _Compare, 66 typename _KeyContainer, typename _MappedContainer> 67 class flat_multimap; 68 69 template<typename _Key, typename _Tp, typename _Compare, 70 typename _KeyContainer, typename _MappedContainer, bool _Multi> 71 class _Flat_map_impl 72 { 73 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>); 74 static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>); 75 76 static_assert(is_nothrow_swappable_v<_KeyContainer>); 77 static_assert(is_nothrow_swappable_v<_MappedContainer>); 78 79 using _Derived = __conditional_t<_Multi, 80 flat_multimap<_Key, _Tp, _Compare, 81 _KeyContainer, _MappedContainer>, 82 flat_map<_Key, _Tp, _Compare, 83 _KeyContainer, _MappedContainer>>; 84 using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>; 85 86 public: 87 template<bool _Const> struct _Iterator; 88 89 using key_type = _Key; 90 using mapped_type = _Tp; 91 using value_type = pair<key_type, mapped_type>; 92 using key_compare = _Compare; 93 using reference = pair<const key_type&, mapped_type&>; 94 using const_reference = pair<const key_type&, const mapped_type&>; 95 using size_type = size_t; 96 using difference_type = ptrdiff_t; 97 using iterator = _Iterator<false>; 98 using const_iterator = _Iterator<true>; 99 using reverse_iterator = std::reverse_iterator<iterator>; 100 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 101 using key_container_type = _KeyContainer; 102 using mapped_container_type = _MappedContainer; 103 104 private: 105 using __emplace_result_t = __conditional_t<_Multi, iterator, pair<iterator, bool>>; 106 107 public: 108 class value_compare 109 { 110 [[no_unique_address]] key_compare _M_comp; 111 value_compare(key_compare __c) : _M_comp(__c) { } 112 113 public: 114 bool 115 operator()(const_reference __x, const_reference __y) const 116 { return _M_comp(__x.first, __y.first); } 117 118 friend _Flat_map_impl; 119 }; 120 121 struct containers 122 { 123 key_container_type keys; 124 mapped_container_type values; 125 }; 126 127 private: 128 struct _ClearGuard 129 { 130 containers* _M_cont; 131 132 _ClearGuard(containers& __cont) 133 : _M_cont(std::__addressof(__cont)) 134 { } 135 136 ~_ClearGuard() 137 { 138 if (_M_cont) 139 { 140 _M_cont->keys.clear(); 141 _M_cont->values.clear(); 142 } 143 } 144 145 void 146 _M_disable() 147 { _M_cont = nullptr; } 148 }; 149 150 _ClearGuard 151 _M_make_clear_guard() 152 { return _ClearGuard{this->_M_cont}; } 153 154 public: 155 // constructors 156 _Flat_map_impl() : _Flat_map_impl(key_compare()) { } 157 158 explicit 159 _Flat_map_impl(const key_compare& __comp) 160 : _M_cont(), _M_comp(__comp) 161 { } 162 163 _Flat_map_impl(key_container_type __key_cont, 164 mapped_container_type __mapped_cont, 165 const key_compare& __comp = key_compare()) 166 : _M_cont(std::move(__key_cont), std::move(__mapped_cont)), _M_comp(__comp) 167 { 168 __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size()); 169 _M_sort_uniq(); 170 } 171 172 _Flat_map_impl(__sorted_t, 173 key_container_type __key_cont, 174 mapped_container_type __mapped_cont, 175 const key_compare& __comp = key_compare()) 176 : _M_cont(std::move(__key_cont), std::move(__mapped_cont)), _M_comp(__comp) 177 { 178 __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size()); 179 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont.keys, _M_comp)); 180 } 181 182 template<__has_input_iter_cat _InputIterator> 183 _Flat_map_impl(_InputIterator __first, _InputIterator __last, 184 const key_compare& __comp = key_compare()) 185 : _M_cont(), _M_comp(__comp) 186 { insert(__first, __last); } 187 188 template<__has_input_iter_cat _InputIterator> 189 _Flat_map_impl(__sorted_t __s, 190 _InputIterator __first, _InputIterator __last, 191 const key_compare& __comp = key_compare()) 192 : _M_cont(), _M_comp(__comp) 193 { insert(__s, __first, __last); } 194 195 template<__detail::__container_compatible_range<value_type> _Rg> 196 _Flat_map_impl(from_range_t, _Rg&& __rg) 197 : _Flat_map_impl(from_range, std::forward<_Rg>(__rg), key_compare()) 198 { } 199 200 template<__detail::__container_compatible_range<value_type> _Rg> 201 _Flat_map_impl(from_range_t, _Rg&& __rg, const key_compare& __comp) 202 : _Flat_map_impl(__comp) 203 { insert_range(std::forward<_Rg>(__rg)); } 204 205 _Flat_map_impl(initializer_list<value_type> __il, 206 const key_compare& __comp = key_compare()) 207 : _Flat_map_impl(__il.begin(), __il.end(), __comp) 208 { } 209 210 _Flat_map_impl(__sorted_t __s, 211 initializer_list<value_type> __il, 212 const key_compare& __comp = key_compare()) 213 : _Flat_map_impl(__s, __il.begin(), __il.end(), __comp) 214 { } 215 216 // constructors with allocators 217 218 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 219 explicit 220 _Flat_map_impl(const _Alloc& __a) 221 : _Flat_map_impl(key_compare(), __a) 222 { } 223 224 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 225 _Flat_map_impl(const key_compare& __comp, const _Alloc& __a) 226 : _M_cont(std::make_obj_using_allocator<key_container_type>(__a), 227 std::make_obj_using_allocator<mapped_container_type>(__a)), 228 _M_comp(__comp) 229 { } 230 231 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 232 _Flat_map_impl(const key_container_type& __key_cont, 233 const mapped_container_type& __mapped_cont, 234 const _Alloc& __a) 235 : _Flat_map_impl(__key_cont, __mapped_cont, key_compare(), __a) 236 { } 237 238 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 239 _Flat_map_impl(const key_container_type& __key_cont, 240 const mapped_container_type& __mapped_cont, 241 const key_compare& __comp, 242 const _Alloc& __a) 243 : _M_cont(std::make_obj_using_allocator<key_container_type>(__a, __key_cont), 244 std::make_obj_using_allocator<mapped_container_type>(__a, __mapped_cont)), 245 _M_comp(__comp) 246 { 247 __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size()); 248 _M_sort_uniq(); 249 } 250 251 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 252 _Flat_map_impl(__sorted_t __s, 253 const key_container_type& __key_cont, 254 const mapped_container_type& __mapped_cont, 255 const _Alloc& __a) 256 : _Flat_map_impl(__s, __key_cont, __mapped_cont, key_compare(), __a) 257 { } 258 259 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 260 _Flat_map_impl(__sorted_t, 261 const key_container_type& __key_cont, 262 const mapped_container_type& __mapped_cont, 263 const key_compare& __comp, 264 const _Alloc& __a) 265 : _M_cont(std::make_obj_using_allocator<key_container_type>(__a, __key_cont), 266 std::make_obj_using_allocator<mapped_container_type>(__a, __mapped_cont)), 267 _M_comp(__comp) 268 { 269 __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size()); 270 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont.keys, _M_comp)); 271 } 272 273 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 274 _Flat_map_impl(const _Derived& __x, const _Alloc& __a) 275 : _M_cont(std::make_obj_using_allocator<key_container_type>(__a, __x._M_cont.keys), 276 std::make_obj_using_allocator<mapped_container_type>(__a, __x._M_cont.values)), 277 _M_comp(__x._M_comp) 278 { } 279 280 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 281 _Flat_map_impl(_Derived&& __x, const _Alloc& __a) 282 : _M_cont(std::make_obj_using_allocator<key_container_type> 283 (__a, std::move(__x._M_cont.keys)), 284 std::make_obj_using_allocator<mapped_container_type> 285 (__a, std::move(__x._M_cont.values))), 286 _M_comp(__x._M_comp) 287 { } 288 289 template<__has_input_iter_cat _InputIterator, 290 __allocator_for<key_container_type, mapped_container_type> _Alloc> 291 _Flat_map_impl(_InputIterator __first, _InputIterator __last, 292 const _Alloc& __a) 293 : _Flat_map_impl(std::move(__first), std::move(__last), key_compare(), __a) 294 { } 295 296 template<__has_input_iter_cat _InputIterator, 297 __allocator_for<key_container_type, mapped_container_type> _Alloc> 298 _Flat_map_impl(_InputIterator __first, _InputIterator __last, 299 const key_compare& __comp, 300 const _Alloc& __a) 301 : _Flat_map_impl(__comp, __a) 302 { insert(__first, __last); } 303 304 template<__has_input_iter_cat _InputIterator, 305 __allocator_for<key_container_type, mapped_container_type> _Alloc> 306 _Flat_map_impl(__sorted_t __s, 307 _InputIterator __first, _InputIterator __last, 308 const _Alloc& __a) 309 : _Flat_map_impl(__s, std::move(__first), std::move(__last), key_compare(), __a) 310 { } 311 312 template<__has_input_iter_cat _InputIterator, 313 __allocator_for<key_container_type, mapped_container_type> _Alloc> 314 _Flat_map_impl(__sorted_t __s, 315 _InputIterator __first, _InputIterator __last, 316 const key_compare& __comp, 317 const _Alloc& __a) 318 : _Flat_map_impl(__comp, __a) 319 { insert(__s, __first, __last); } 320 321 template<__detail::__container_compatible_range<value_type> _Rg, 322 __allocator_for<key_container_type, mapped_container_type> _Alloc> 323 _Flat_map_impl(from_range_t, _Rg&& __rg, 324 const _Alloc& __a) 325 : _Flat_map_impl(from_range, std::forward<_Rg>(__rg), key_compare(), __a) 326 { } 327 328 template<__detail::__container_compatible_range<value_type> _Rg, 329 __allocator_for<key_container_type, mapped_container_type> _Alloc> 330 _Flat_map_impl(from_range_t, _Rg&& __rg, const key_compare& __comp, 331 const _Alloc& __a) 332 : _Flat_map_impl(__comp, __a) 333 { insert_range(std::forward<_Rg>(__rg)); } 334 335 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 336 _Flat_map_impl(initializer_list<value_type> __il, 337 const _Alloc& __a) 338 : _Flat_map_impl(__il, key_compare(), __a) 339 { } 340 341 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 342 _Flat_map_impl(initializer_list<value_type> __il, 343 const key_compare& __comp, 344 const _Alloc& __a) 345 : _Flat_map_impl(__il.begin(), __il.end(), __comp, __a) 346 { } 347 348 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 349 _Flat_map_impl(__sorted_t __s, 350 initializer_list<value_type> __il, 351 const _Alloc& __a) 352 : _Flat_map_impl(__s, __il.begin(), __il.end(), key_compare(), __a) 353 { } 354 355 template<__allocator_for<key_container_type, mapped_container_type> _Alloc> 356 _Flat_map_impl(__sorted_t __s, 357 initializer_list<value_type> __il, 358 const key_compare& __comp, 359 const _Alloc& __a) 360 : _Flat_map_impl(__s, __il.begin(), __il.end(), __comp, __a) 361 { } 362 363 _Derived& 364 operator=(initializer_list<value_type> __il) 365 { 366 clear(); 367 insert(__il); 368 return static_cast<_Derived&>(*this); 369 } 370 371 // iterators 372 iterator 373 begin() noexcept 374 { return {this, _M_cont.keys.cbegin()}; } 375 376 const_iterator 377 begin() const noexcept 378 { return {this, _M_cont.keys.cbegin()}; } 379 380 iterator 381 end() noexcept 382 { return {this, _M_cont.keys.cend()}; } 383 384 const_iterator 385 end() const noexcept 386 { return {this, _M_cont.keys.cend()}; } 387 388 reverse_iterator 389 rbegin() noexcept 390 { return reverse_iterator(end()); } 391 392 const_reverse_iterator 393 rbegin() const noexcept 394 { return const_reverse_iterator(end()); } 395 396 reverse_iterator 397 rend() noexcept 398 { return reverse_iterator(begin()); } 399 400 const_reverse_iterator 401 rend() const noexcept 402 { return const_reverse_iterator(begin()); } 403 404 const_iterator 405 cbegin() const noexcept 406 { return {this, _M_cont.keys.cbegin()}; } 407 408 const_iterator 409 cend() const noexcept 410 { return {this, _M_cont.keys.cend()}; } 411 412 const_reverse_iterator 413 crbegin() const noexcept 414 { return const_reverse_iterator(cend()); } 415 416 const_reverse_iterator 417 crend() const noexcept 418 { return const_reverse_iterator(cbegin()); } 419 420 // capacity 421 [[nodiscard]] 422 bool 423 empty() const noexcept 424 { return _M_cont.keys.empty(); } 425 426 size_type 427 size() const noexcept 428 { return _M_cont.keys.size(); } 429 430 size_type 431 max_size() const noexcept 432 { return std::min<size_type>(keys().max_size(), values().max_size()); } 433 434 // element access 435 // operator[] and at defined directly in class flat_map only. 436 437 // modifiers 438 template<typename _Key2, typename... _Args> 439 pair<iterator, bool> 440 _M_try_emplace(optional<const_iterator> __hint, _Key2&& __k, _Args&&... __args) 441 { 442 // TODO: Simplify and audit the hint handling. 443 typename key_container_type::iterator __key_it; 444 typename mapped_container_type::iterator __value_it; 445 int __r = -1, __s = -1; 446 if (__hint.has_value() 447 && (__hint == cbegin() 448 || (__r = !_M_comp(__k, (*__hint)[-1].first))) // k >= hint[-1] 449 && (__hint == cend() 450 || (__s = !_M_comp((*__hint)[0].first, __k)))) // k <= hint[0] 451 { 452 __key_it = _M_cont.keys.begin() + __hint->_M_index; 453 if constexpr (!_Multi) 454 if (__r == 1 && !_M_comp(__key_it[-1], __k)) // k == hint[-1] 455 return {iterator{this, __key_it - 1}, false}; 456 } 457 else 458 { 459 auto __first = _M_cont.keys.begin(); 460 auto __last = _M_cont.keys.end(); 461 if (__r == 1) // k >= hint[-1] 462 __first += __hint->_M_index; 463 else if (__r == 0) // k < __hint[-1] 464 __last = __first + __hint->_M_index; 465 if constexpr (_Multi) 466 { 467 if (__s == 0) // hint[0] < k 468 // Insert before the leftmost equivalent key. 469 __key_it = std::lower_bound(__first, __last, __k, _M_comp); 470 else 471 // Insert after the rightmost equivalent key. 472 __key_it = std::upper_bound(std::make_reverse_iterator(__last), 473 std::make_reverse_iterator(__first), 474 __k, std::not_fn(_M_comp)).base(); 475 } 476 else 477 __key_it = std::lower_bound(__first, __last, __k, _M_comp); 478 } 479 480 if constexpr (!_Multi) 481 if (__key_it != _M_cont.keys.end() && !_M_comp(__k, __key_it[0])) 482 return {iterator{this, __key_it}, false}; 483 484 auto __guard = _M_make_clear_guard(); 485 __key_it = _M_cont.keys.insert(__key_it, std::move(__k)); 486 __value_it = _M_cont.values.begin() + (__key_it - _M_cont.keys.begin()); 487 _M_cont.values.emplace(__value_it, std::forward<_Args>(__args)...); 488 __guard._M_disable(); 489 return {iterator{this, __key_it}, true}; 490 } 491 492 template<typename... _Args> 493 requires is_constructible_v<value_type, _Args...> 494 __emplace_result_t 495 emplace(_Args&&... __args) 496 { 497 value_type __p(std::forward<_Args>(__args)...); 498 auto __r = _M_try_emplace(nullopt, std::move(__p.first), std::move(__p.second)); 499 if constexpr (_Multi) 500 return __r.first; 501 else 502 return __r; 503 } 504 505 template<typename... _Args> 506 iterator 507 emplace_hint(const_iterator __position, _Args&&... __args) 508 { 509 value_type __p(std::forward<_Args>(__args)...); 510 return _M_try_emplace(__position, std::move(__p.first), std::move(__p.second)).first; 511 } 512 513 __emplace_result_t 514 insert(const value_type& __x) 515 { return emplace(__x); } 516 517 __emplace_result_t 518 insert(value_type&& __x) 519 { return emplace(std::move(__x)); } 520 521 iterator 522 insert(const_iterator __position, const value_type& __x) 523 { return emplace_hint(__position, __x); } 524 525 iterator 526 insert(const_iterator __position, value_type&& __x) 527 { return emplace_hint(__position, std::move(__x)); } 528 529 template<typename _Arg> 530 requires is_constructible_v<value_type, _Arg> 531 __emplace_result_t 532 insert(_Arg&& __x) 533 { return emplace(std::forward<_Arg>(__x)); } 534 535 template<typename _Arg> 536 requires is_constructible_v<value_type, _Arg> 537 iterator 538 insert(const_iterator __position, _Arg&& __x) 539 { return emplace_hint(__position, std::forward<_Arg>(__x)); } 540 541 private: 542 template<typename _Iter, typename _Sent> 543 void 544 _M_insert(_Iter __first, _Sent __last) 545 { 546 // FIXME: This implementation fails its complexity requirements. 547 // We can't idiomatically implement an efficient version (as in the 548 // disabled code) until ranges::inplace_merge is fixed to dispatch 549 // on iterator concept instead of iterator category. 550 #if 0 551 auto __guard = _M_make_clear_guard(); 552 auto __n = size(); 553 for (; __first != __last; ++__first) 554 { 555 value_type __value = *__first; 556 _M_cont.keys.emplace_back(std::move(__value.first)); 557 _M_cont.values.emplace_back(std::move(__value.second)); 558 } 559 auto __zv = views::zip(_M_cont.keys, _M_cont.values); 560 ranges::sort(__zv.begin() + __n, __zv.end(), value_comp()); 561 ranges::inplace_merge(__zv.begin(), __zv.begin() + __n, __zv.end(), value_comp()); 562 if constexpr (!_Multi) 563 _M_unique(); 564 __guard._M_cont = nullptr; 565 #else 566 auto __guard = _M_make_clear_guard(); 567 for (; __first != __last; ++__first) 568 { 569 value_type __value = *__first; 570 _M_cont.keys.emplace_back(std::move(__value.first)); 571 _M_cont.values.emplace_back(std::move(__value.second)); 572 } 573 _M_sort_uniq(); 574 __guard._M_disable(); 575 #endif 576 } 577 578 public: 579 template<__has_input_iter_cat _InputIterator> 580 void 581 insert(_InputIterator __first, _InputIterator __last) 582 { _M_insert(std::move(__first), std::move(__last)); } 583 584 template<__has_input_iter_cat _InputIterator> 585 void 586 insert(__sorted_t, _InputIterator __first, _InputIterator __last) 587 { 588 // FIXME: This implementation fails its complexity requirements; see above. 589 insert(std::move(__first), std::move(__last)); 590 } 591 592 template<__detail::__container_compatible_range<value_type> _Rg> 593 void 594 insert_range(_Rg&& __rg) 595 { _M_insert(ranges::begin(__rg), ranges::end(__rg)); } 596 597 void 598 insert(initializer_list<value_type> __il) 599 { insert(__il.begin(), __il.end()); } 600 601 void 602 insert(__sorted_t __s, initializer_list<value_type> __il) 603 { insert(__s, __il.begin(), __il.end()); } 604 605 containers 606 extract() && 607 { 608 auto __guard = _M_make_clear_guard(); 609 return {std::move(_M_cont.keys), std::move(_M_cont.values)}; 610 } 611 612 void 613 replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont) 614 { 615 __glibcxx_assert(__key_cont.size() == __mapped_cont.size()); 616 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__key_cont, _M_comp)); 617 auto __guard = _M_make_clear_guard(); 618 _M_cont.keys = std::move(__key_cont); 619 _M_cont.values = std::move(__mapped_cont); 620 __guard._M_disable(); 621 } 622 623 // try_emplace and insert_or_assign defined directly in class flat_map only. 624 625 iterator 626 erase(iterator __position) 627 { return erase(static_cast<const_iterator>(__position)); } 628 629 iterator 630 erase(const_iterator __position) 631 { 632 auto __guard = _M_make_clear_guard(); 633 auto __idx = __position._M_index; 634 auto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __idx); 635 _M_cont.values.erase(_M_cont.values.begin() + __idx); 636 __guard._M_disable(); 637 return iterator{this, __it}; 638 } 639 640 size_type 641 erase(const key_type& __x) 642 { return erase<const key_type&>(__x); } 643 644 template<typename _Key2> 645 requires same_as<remove_cvref_t<_Key2>, _Key> 646 || (__transparent_comparator<_Compare> 647 && !is_convertible_v<_Key2, iterator> 648 && !is_convertible_v<_Key2, const_iterator>) 649 size_type 650 erase(_Key2&& __x) 651 { 652 auto [__first, __last] = equal_range(std::forward<_Key2>(__x)); 653 auto __n = __last - __first; 654 erase(__first, __last); 655 return __n; 656 } 657 658 iterator 659 erase(const_iterator __first, const_iterator __last) 660 { 661 auto __guard = _M_make_clear_guard(); 662 auto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __first._M_index, 663 _M_cont.keys.begin() + __last._M_index); 664 _M_cont.values.erase(_M_cont.values.begin() + __first._M_index, 665 _M_cont.values.begin() + __last._M_index); 666 __guard._M_disable(); 667 return iterator{this, __it}; 668 } 669 670 void 671 swap(_Derived& __y) noexcept 672 { 673 ranges::swap(_M_comp, __y._M_comp); 674 ranges::swap(_M_cont.keys, __y._M_cont.keys); 675 ranges::swap(_M_cont.values, __y._M_cont.values); 676 } 677 678 void 679 clear() noexcept 680 { 681 _M_cont.keys.clear(); 682 _M_cont.values.clear(); 683 } 684 685 // observers 686 [[nodiscard]] 687 key_compare 688 key_comp() const 689 { return _M_comp; } 690 691 [[nodiscard]] 692 value_compare 693 value_comp() const 694 { return value_compare(_M_comp); } 695 696 [[nodiscard]] 697 const key_container_type& 698 keys() const noexcept 699 { return _M_cont.keys; } 700 701 [[nodiscard]] 702 const mapped_container_type& 703 values() const noexcept 704 { return _M_cont.values; } 705 706 // map operations 707 [[nodiscard]] 708 iterator 709 find(const key_type& __x) 710 { return find<key_type>(__x); } 711 712 [[nodiscard]] 713 const_iterator 714 find(const key_type& __x) const 715 { return find<key_type>(__x); } 716 717 template<typename _Key2> 718 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 719 [[nodiscard]] 720 iterator 721 find(const _Key2& __x) 722 { 723 auto __it = lower_bound(__x); 724 if (__it != end() && !_M_comp(__x, __it->first)) 725 return __it; 726 else 727 return end(); 728 } 729 730 template<typename _Key2> 731 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 732 [[nodiscard]] 733 const_iterator 734 find(const _Key2& __x) const 735 { 736 auto __it = lower_bound(__x); 737 if (__it != cend() && !_M_comp(__x, __it->first)) 738 return __it; 739 else 740 return cend(); 741 } 742 743 [[nodiscard]] 744 size_type 745 count(const key_type& __x) const 746 { return count<key_type>(__x); } 747 748 template<typename _Key2> 749 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 750 [[nodiscard]] 751 size_type 752 count(const _Key2& __x) const 753 { 754 if constexpr (!_Multi) 755 return contains<_Key2>(__x); 756 else 757 { 758 auto [__first, __last] = equal_range(__x); 759 return __last - __first; 760 } 761 } 762 763 [[nodiscard]] 764 bool 765 contains(const key_type& __x) const 766 { return contains<key_type>(__x); } 767 768 template<typename _Key2> 769 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 770 [[nodiscard]] 771 bool 772 contains(const _Key2& __x) const 773 { return find(__x) != cend(); } 774 775 [[nodiscard]] 776 iterator 777 lower_bound(const key_type& __x) 778 { return lower_bound<key_type>(__x); } 779 780 [[nodiscard]] 781 const_iterator 782 lower_bound(const key_type& __x) const 783 { return lower_bound<key_type>(__x); } 784 785 template<typename _Key2> 786 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 787 [[nodiscard]] 788 iterator 789 lower_bound(const _Key2& __x) 790 { 791 auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(), 792 __x, _M_comp); 793 return {this, __it}; 794 } 795 796 template<typename _Key2> 797 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 798 [[nodiscard]] 799 const_iterator 800 lower_bound(const _Key2& __x) const 801 { 802 auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(), 803 __x, _M_comp); 804 return {this, __it}; 805 } 806 807 [[nodiscard]] 808 iterator 809 upper_bound(const key_type& __x) 810 { return upper_bound<key_type>(__x); } 811 812 [[nodiscard]] 813 const_iterator 814 upper_bound(const key_type& __x) const 815 { return upper_bound<key_type>(__x); } 816 817 template<typename _Key2> 818 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 819 [[nodiscard]] 820 iterator 821 upper_bound(const _Key2& __x) 822 { 823 auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(), 824 __x, _M_comp); 825 return {this, __it}; 826 } 827 828 template<typename _Key2> 829 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 830 [[nodiscard]] 831 const_iterator 832 upper_bound(const _Key2& __x) const 833 { 834 auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(), 835 __x, _M_comp); 836 return {this, __it}; 837 } 838 839 [[nodiscard]] 840 pair<iterator, iterator> 841 equal_range(const key_type& __x) 842 { return equal_range<key_type>(__x); } 843 844 [[nodiscard]] 845 pair<const_iterator, const_iterator> 846 equal_range(const key_type& __x) const 847 { return equal_range<key_type>(__x); } 848 849 template<typename _Key2> 850 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 851 [[nodiscard]] 852 pair<iterator, iterator> 853 equal_range(const _Key2& __x) 854 { 855 auto [__first, __last] = std::equal_range(_M_cont.keys.begin(), 856 _M_cont.keys.end(), 857 __x, _M_comp); 858 return {{this, __first}, {this, __last}}; 859 } 860 861 template<typename _Key2> 862 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 863 [[nodiscard]] 864 pair<const_iterator, const_iterator> 865 equal_range(const _Key2& __x) const 866 { 867 auto [__first, __last] = std::equal_range(_M_cont.keys.begin(), 868 _M_cont.keys.end(), 869 __x, _M_comp); 870 return {{this, __first}, {this, __last}}; 871 } 872 873 [[nodiscard]] 874 friend bool 875 operator==(const _Derived& __x, const _Derived& __y) 876 { 877 return __x._M_cont.keys == __y._M_cont.keys 878 && __x._M_cont.values == __y._M_cont.values; 879 } 880 881 template<typename _Up = value_type> 882 [[nodiscard]] 883 friend __detail::__synth3way_t<_Up> 884 operator<=>(const _Derived& __x, const _Derived& __y) 885 { 886 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), 887 __y.begin(), __y.end(), 888 __detail::__synth3way); 889 } 890 891 friend void 892 swap(_Derived& __x, _Derived& __y) noexcept 893 { return __x.swap(__y); } 894 895 template<typename _Predicate> 896 size_type 897 _M_erase_if(_Predicate __pred) 898 { 899 auto __guard = _M_make_clear_guard(); 900 auto __zv = views::zip(_M_cont.keys, _M_cont.values); 901 auto __sr = ranges::remove_if(__zv, __pred, 902 [](const auto& __e) { 903 return const_reference(__e); 904 }); 905 auto __erased = __sr.size(); 906 erase(end() - __erased, end()); 907 __guard._M_disable(); 908 return __erased; 909 } 910 911 private: 912 containers _M_cont; 913 [[no_unique_address]] _Compare _M_comp; 914 915 void 916 _M_sort_uniq() 917 { 918 auto __zv = views::zip(_M_cont.keys, _M_cont.values); 919 ranges::sort(__zv, value_comp()); 920 if constexpr (!_Multi) 921 _M_unique(); 922 } 923 924 void 925 _M_unique() requires (!_Multi) 926 { 927 struct __key_equiv 928 { 929 __key_equiv(key_compare __c) : _M_comp(__c) { } 930 931 bool 932 operator()(const_reference __x, const_reference __y) const 933 { return !_M_comp(__x.first, __y.first) && !_M_comp(__y.first, __x.first); } 934 935 [[no_unique_address]] key_compare _M_comp; 936 }; 937 938 auto __zv = views::zip(_M_cont.keys, _M_cont.values); 939 auto __it = ranges::unique(__zv, __key_equiv(_M_comp)).begin(); 940 auto __n = __it - __zv.begin(); 941 _M_cont.keys.erase(_M_cont.keys.begin() + __n, _M_cont.keys.end()); 942 _M_cont.values.erase(_M_cont.values.begin() + __n, _M_cont.values.end()); 943 } 944 }; 945 946 template<typename _Key, typename _Tp, typename _Compare, 947 typename _KeyContainer, typename _MappedContainer, bool _Multi> 948 template<bool _Const> 949 class _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, _Multi>::_Iterator 950 { 951 using __size_type = typename _Flat_map_impl::size_type; 952 953 public: 954 using iterator_category = input_iterator_tag; 955 using iterator_concept = random_access_iterator_tag; 956 using value_type = pair<key_type, mapped_type>; 957 using reference = pair<const key_type&, 958 ranges::__maybe_const_t<_Const, mapped_type>&>; 959 using difference_type = ptrdiff_t; 960 961 _Iterator() = default; 962 963 _Iterator(_Iterator<!_Const> __it) requires _Const 964 : _M_cont(__it._M_cont), _M_index(__it._M_index) 965 { } 966 967 reference 968 operator*() const noexcept 969 { 970 __glibcxx_assert(_M_index < _M_cont->keys.size()); 971 return {_M_cont->keys[_M_index], _M_cont->values[_M_index]}; 972 } 973 974 struct pointer 975 { 976 reference __p; 977 978 const reference* 979 operator->() const noexcept 980 { return std::__addressof(__p); } 981 }; 982 983 pointer 984 operator->() const 985 { return pointer{operator*()}; } 986 987 reference 988 operator[](difference_type __n) const noexcept 989 { return *(*this + __n); } 990 991 _Iterator& 992 operator++() noexcept 993 { 994 ++_M_index; 995 return *this; 996 } 997 998 _Iterator& 999 operator--() noexcept 1000 { 1001 --_M_index; 1002 return *this; 1003 } 1004 1005 _Iterator 1006 operator++(int) noexcept 1007 { 1008 auto __tmp = *this; 1009 ++*this; 1010 return __tmp; 1011 } 1012 1013 _Iterator 1014 operator--(int) noexcept 1015 { 1016 auto __tmp = *this; 1017 --*this; 1018 return __tmp; 1019 } 1020 1021 _Iterator& 1022 operator+=(difference_type __n) noexcept 1023 { 1024 _M_index += __n; 1025 return *this; 1026 } 1027 1028 _Iterator& 1029 operator-=(difference_type __n) noexcept 1030 { 1031 _M_index -= __n; 1032 return *this; 1033 } 1034 1035 private: 1036 friend _Flat_map_impl; 1037 friend _Iterator<!_Const>; 1038 1039 _Iterator(_Flat_map_impl* __fm, typename key_container_type::const_iterator __it) 1040 requires (!_Const) 1041 : _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin()) 1042 { } 1043 1044 _Iterator(const _Flat_map_impl* __fm, typename key_container_type::const_iterator __it) 1045 requires _Const 1046 : _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin()) 1047 { } 1048 1049 friend _Iterator 1050 operator+(_Iterator __it, difference_type __n) noexcept 1051 { 1052 __it += __n; 1053 return __it; 1054 } 1055 1056 friend _Iterator 1057 operator+(difference_type __n, _Iterator __it) noexcept 1058 { 1059 __it += __n; 1060 return __it; 1061 } 1062 1063 friend _Iterator 1064 operator-(_Iterator __it, difference_type __n) noexcept 1065 { 1066 __it -= __n; 1067 return __it; 1068 } 1069 1070 friend difference_type 1071 operator-(const _Iterator& __x, const _Iterator& __y) noexcept 1072 { 1073 __glibcxx_assert(__x._M_cont == __y._M_cont); 1074 return __x._M_index - __y._M_index; 1075 } 1076 1077 friend bool 1078 operator==(const _Iterator& __x, const _Iterator& __y) noexcept 1079 { 1080 __glibcxx_assert(__x._M_cont == __y._M_cont); 1081 __glibcxx_assert((__x._M_index == size_t(-1)) == (__y._M_index == size_t(-1))); 1082 return __x._M_index == __y._M_index; 1083 } 1084 1085 friend strong_ordering 1086 operator<=>(const _Iterator& __x, const _Iterator& __y) 1087 { 1088 __glibcxx_assert(__x._M_cont == __y._M_cont); 1089 __glibcxx_assert((__x._M_index == size_t(-1)) == (__y._M_index == size_t(-1))); 1090 return __x._M_index <=> __y._M_index; 1091 } 1092 1093 ranges::__maybe_const_t<_Const, containers>* _M_cont = nullptr; 1094 __size_type _M_index = -1; 1095 }; 1096 1097 /* Class template flat_map - container adaptor 1098 * 1099 * @ingroup 1100 */ 1101 template<typename _Key, typename _Tp, typename _Compare = less<_Key>, 1102 typename _KeyContainer = vector<_Key>, 1103 typename _MappedContainer = vector<_Tp>> 1104 class flat_map 1105 : private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false> 1106 { 1107 using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>; 1108 friend _Impl; 1109 1110 public: 1111 // types 1112 using typename _Impl::key_type; 1113 using typename _Impl::mapped_type; 1114 using typename _Impl::value_type; 1115 using typename _Impl::key_compare; 1116 using typename _Impl::reference; 1117 using typename _Impl::const_reference; 1118 using typename _Impl::size_type; 1119 using typename _Impl::difference_type; 1120 using typename _Impl::iterator; 1121 using typename _Impl::const_iterator; 1122 using typename _Impl::reverse_iterator; 1123 using typename _Impl::const_reverse_iterator; 1124 using typename _Impl::key_container_type; 1125 using typename _Impl::mapped_container_type; 1126 using typename _Impl::value_compare; 1127 using typename _Impl::containers; 1128 1129 // constructors 1130 using _Impl::_Impl; 1131 1132 // iterators 1133 using _Impl::begin; 1134 using _Impl::end; 1135 using _Impl::rbegin; 1136 using _Impl::rend; 1137 1138 using _Impl::cbegin; 1139 using _Impl::cend; 1140 using _Impl::crbegin; 1141 using _Impl::crend; 1142 1143 // capacity 1144 using _Impl::empty; 1145 using _Impl::size; 1146 using _Impl::max_size; 1147 1148 // element access 1149 mapped_type& 1150 operator[](const key_type& __x) 1151 { return try_emplace(__x).first->second; } 1152 1153 mapped_type& 1154 operator[](key_type&& __x) 1155 { return try_emplace(std::move(__x)).first->second; } 1156 1157 template<typename _Key2> 1158 requires __transparent_comparator<_Compare> 1159 mapped_type& 1160 operator[](_Key2&& __x) 1161 { return try_emplace(std::forward<_Key2>(__x)).first->second; } 1162 1163 mapped_type& 1164 at(const key_type& __x) 1165 { return at<key_type>(__x); } 1166 1167 const mapped_type& 1168 at(const key_type& __x) const 1169 { return at<key_type>(__x); } 1170 1171 template<typename _Key2> 1172 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 1173 mapped_type& 1174 at(const _Key2& __x) 1175 { 1176 auto __it = this->find(__x); 1177 if (__it == this->end()) 1178 __throw_out_of_range("flat_map::at"); 1179 return __it->second; 1180 } 1181 1182 template<typename _Key2> 1183 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare> 1184 const mapped_type& 1185 at(const _Key2& __x) const 1186 { 1187 auto __it = this->find(__x); 1188 if (__it == this->end()) 1189 __throw_out_of_range("flat_map::at"); 1190 return __it->second; 1191 } 1192 1193 // modifiers 1194 using _Impl::emplace; 1195 using _Impl::emplace_hint; 1196 using _Impl::insert; 1197 using _Impl::insert_range; 1198 using _Impl::extract; 1199 using _Impl::replace; 1200 using _Impl::erase; 1201 using _Impl::swap; 1202 using _Impl::clear; 1203 1204 template<typename... _Args> 1205 requires is_constructible_v<mapped_type, _Args...> 1206 pair<iterator, bool> 1207 try_emplace(const key_type& __k, _Args&&... __args) 1208 { return _Impl::_M_try_emplace(nullopt, __k, std::forward<_Args>(__args)...); } 1209 1210 template<typename... _Args> 1211 requires is_constructible_v<mapped_type, _Args...> 1212 pair<iterator, bool> 1213 try_emplace(key_type&& __k, _Args&&... __args) 1214 { 1215 return _Impl::_M_try_emplace(nullopt, std::move(__k), 1216 std::forward<_Args>(__args)...); 1217 } 1218 1219 template<typename _Key2, typename... _Args> 1220 requires __transparent_comparator<_Compare> 1221 && is_constructible_v<key_type, _Key2> 1222 && is_constructible_v<mapped_type, _Args...> 1223 && (!is_convertible_v<_Key2&&, const_iterator>) 1224 && (!is_convertible_v<_Key2&&, iterator>) 1225 pair<iterator, bool> 1226 try_emplace(_Key2&& __k, _Args&&... __args) 1227 { 1228 return _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k), 1229 std::forward<_Args>(__args)...); 1230 } 1231 1232 template<typename... _Args> 1233 requires is_constructible_v<mapped_type, _Args...> 1234 iterator 1235 try_emplace(const_iterator __hint, const key_type& __k, _Args&&... __args) 1236 { return _Impl::_M_try_emplace(__hint, __k, std::forward<_Args>(__args)...).first; } 1237 1238 template<typename... _Args> 1239 requires is_constructible_v<mapped_type, _Args...> 1240 iterator 1241 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) 1242 { 1243 return _Impl::_M_try_emplace(__hint, std::move(__k), 1244 std::forward<_Args>(__args)...).first; 1245 } 1246 1247 template<typename _Key2, typename... _Args> 1248 requires __transparent_comparator<_Compare> 1249 && is_constructible_v<key_type, _Key2> 1250 && is_constructible_v<mapped_type, _Args...> 1251 iterator 1252 try_emplace(const_iterator __hint, _Key2&& __k, _Args&&... __args) 1253 { 1254 return _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k), 1255 std::forward<_Args>(__args)...).first; 1256 } 1257 1258 template<typename _Mapped> 1259 requires is_assignable_v<mapped_type&, _Mapped> 1260 && is_constructible_v<mapped_type, _Mapped> 1261 pair<iterator, bool> 1262 insert_or_assign(const key_type& __k, _Mapped&& __obj) 1263 { return insert_or_assign<const key_type&, _Mapped>(__k, std::forward<_Mapped>(__obj)); } 1264 1265 template<typename _Mapped> 1266 requires is_assignable_v<mapped_type&, _Mapped> 1267 && is_constructible_v<mapped_type, _Mapped> 1268 pair<iterator, bool> 1269 insert_or_assign(key_type&& __k, _Mapped&& __obj) 1270 { 1271 return insert_or_assign<key_type, _Mapped>(std::move(__k), 1272 std::forward<_Mapped>(__obj)); 1273 } 1274 1275 template<typename _Key2, typename _Mapped> 1276 requires (same_as<remove_cvref_t<_Key2>, _Key> || __transparent_comparator<_Compare>) 1277 && is_constructible_v<key_type, _Key2> 1278 && is_assignable_v<mapped_type&, _Mapped> 1279 && is_constructible_v<mapped_type, _Mapped> 1280 pair<iterator, bool> 1281 insert_or_assign(_Key2&& __k, _Mapped&& __obj) 1282 { 1283 auto __r = _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k), 1284 std::forward<_Mapped>(__obj)); 1285 if (!__r.second) 1286 __r.first->second = std::forward<_Mapped>(__obj); 1287 return __r; 1288 } 1289 1290 template<typename _Mapped> 1291 requires is_assignable_v<mapped_type&, _Mapped> 1292 && is_constructible_v<mapped_type, _Mapped> 1293 iterator 1294 insert_or_assign(const_iterator __hint, const key_type& __k, _Mapped&& __obj) 1295 { 1296 return insert_or_assign<const key_type&, _Mapped>(__hint, __k, 1297 std::forward<_Mapped>(__obj)); 1298 } 1299 1300 template<typename _Mapped> 1301 requires is_assignable_v<mapped_type&, _Mapped> 1302 && is_constructible_v<mapped_type, _Mapped> 1303 iterator 1304 insert_or_assign(const_iterator __hint, key_type&& __k, _Mapped&& __obj) 1305 { 1306 return insert_or_assign<key_type, _Mapped>(__hint, std::move(__k), 1307 std::forward<_Mapped>(__obj)); 1308 } 1309 1310 template<typename _Key2, typename _Mapped> 1311 requires (same_as<remove_cvref_t<_Key2>, _Key> || __transparent_comparator<_Compare>) 1312 && is_constructible_v<key_type, _Key2> 1313 && is_assignable_v<mapped_type&, _Mapped> 1314 && is_constructible_v<mapped_type, _Mapped> 1315 iterator 1316 insert_or_assign(const_iterator __hint, _Key2&& __k, _Mapped&& __obj) 1317 { 1318 auto __r = _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k), 1319 std::forward<_Mapped>(__obj)); 1320 if (!__r.second) 1321 __r.first->second = std::forward<_Mapped>(__obj); 1322 return __r.first; 1323 } 1324 1325 // observers 1326 using _Impl::key_comp; 1327 using _Impl::value_comp; 1328 using _Impl::keys; 1329 using _Impl::values; 1330 1331 // map operations 1332 using _Impl::find; 1333 using _Impl::count; 1334 using _Impl::contains; 1335 using _Impl::lower_bound; 1336 using _Impl::upper_bound; 1337 using _Impl::equal_range; 1338 1339 using _Impl::_M_erase_if; 1340 }; 1341 1342 template<typename _KeyContainer, typename _MappedContainer, 1343 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>> 1344 flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare()) 1345 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1346 _Compare, _KeyContainer, _MappedContainer>; 1347 1348 template<typename _KeyContainer, typename _MappedContainer, 1349 __allocator_for<_KeyContainer, _MappedContainer> _Alloc> 1350 flat_map(_KeyContainer, _MappedContainer, _Alloc) 1351 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1352 less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>; 1353 1354 template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare, 1355 __allocator_for<_KeyContainer, _MappedContainer> _Alloc> 1356 flat_map(_KeyContainer, _MappedContainer, _Compare, _Alloc) 1357 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1358 _Compare, _KeyContainer, _MappedContainer>; 1359 1360 template<typename _KeyContainer, typename _MappedContainer, 1361 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>> 1362 flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare()) 1363 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1364 _Compare, _KeyContainer, _MappedContainer>; 1365 1366 template<typename _KeyContainer, typename _MappedContainer, 1367 __allocator_for<_KeyContainer, _MappedContainer> _Alloc> 1368 flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Alloc) 1369 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1370 less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>; 1371 1372 template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare, 1373 __allocator_for<_KeyContainer, _MappedContainer> _Alloc> 1374 flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Alloc) 1375 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1376 _Compare, _KeyContainer, _MappedContainer>; 1377 1378 template<__has_input_iter_cat _InputIterator, 1379 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>> 1380 flat_map(_InputIterator, _InputIterator, _Compare = _Compare()) 1381 -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; 1382 1383 template<__has_input_iter_cat _InputIterator, 1384 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>> 1385 flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare()) 1386 -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; 1387 1388 template<ranges::input_range _Rg, 1389 __not_allocator_like _Compare = less<__detail::__range_key_type<_Rg>>, 1390 __allocator_like _Alloc = allocator<byte>> 1391 flat_map(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc()) 1392 -> flat_map<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>, 1393 _Compare, 1394 vector<__detail::__range_key_type<_Rg>, 1395 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>, 1396 vector<__detail::__range_mapped_type<_Rg>, 1397 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>; 1398 1399 template<ranges::input_range _Rg, __allocator_like _Alloc> 1400 flat_map(from_range_t, _Rg&&, _Alloc) 1401 -> flat_map<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>, 1402 less<__detail::__range_key_type<_Rg>>, 1403 vector<__detail::__range_key_type<_Rg>, 1404 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>, 1405 vector<__detail::__range_mapped_type<_Rg>, 1406 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>; 1407 1408 template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>> 1409 flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) 1410 -> flat_map<_Key, _Tp, _Compare>; 1411 1412 template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>> 1413 flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) 1414 -> flat_map<_Key, _Tp, _Compare>; 1415 1416 template<typename _Key, typename _Tp, typename _Compare, 1417 typename _KeyContainer, typename _MappedContainer, typename _Alloc> 1418 struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Alloc> 1419 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc> 1420 && uses_allocator_v<_MappedContainer, _Alloc>> 1421 { }; 1422 1423 template<typename _Key, typename _Tp, typename _Compare, 1424 typename _KeyContainer, typename _MappedContainer, typename _Predicate> 1425 typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type 1426 erase_if(flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __c, 1427 _Predicate __pred) 1428 { return __c._M_erase_if(std::move(__pred)); } 1429 1430 /* Class template flat_multimap - container adaptor 1431 * 1432 * @ingroup 1433 */ 1434 template<typename _Key, typename _Tp, typename _Compare = less<_Key>, 1435 typename _KeyContainer = vector<_Key>, 1436 typename _MappedContainer = vector<_Tp>> 1437 class flat_multimap 1438 : private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true> 1439 { 1440 using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>; 1441 friend _Impl; 1442 1443 public: 1444 // types 1445 using typename _Impl::key_type; 1446 using typename _Impl::mapped_type; 1447 using typename _Impl::value_type; 1448 using typename _Impl::key_compare; 1449 using typename _Impl::reference; 1450 using typename _Impl::const_reference; 1451 using typename _Impl::size_type; 1452 using typename _Impl::difference_type; 1453 using typename _Impl::iterator; 1454 using typename _Impl::const_iterator; 1455 using typename _Impl::reverse_iterator; 1456 using typename _Impl::const_reverse_iterator; 1457 using typename _Impl::key_container_type; 1458 using typename _Impl::mapped_container_type; 1459 using typename _Impl::value_compare; 1460 using typename _Impl::containers; 1461 1462 // constructors 1463 using _Impl::_Impl; 1464 1465 // iterators 1466 using _Impl::begin; 1467 using _Impl::end; 1468 using _Impl::rbegin; 1469 using _Impl::rend; 1470 1471 using _Impl::cbegin; 1472 using _Impl::cend; 1473 using _Impl::crbegin; 1474 using _Impl::crend; 1475 1476 // capacity 1477 using _Impl::empty; 1478 using _Impl::size; 1479 using _Impl::max_size; 1480 1481 // modifiers 1482 using _Impl::emplace; 1483 using _Impl::emplace_hint; 1484 using _Impl::insert; 1485 using _Impl::insert_range; 1486 using _Impl::extract; 1487 using _Impl::replace; 1488 using _Impl::erase; 1489 using _Impl::swap; 1490 using _Impl::clear; 1491 1492 // observers 1493 using _Impl::key_comp; 1494 using _Impl::value_comp; 1495 using _Impl::keys; 1496 using _Impl::values; 1497 1498 // map operations 1499 using _Impl::find; 1500 using _Impl::count; 1501 using _Impl::contains; 1502 using _Impl::lower_bound; 1503 using _Impl::upper_bound; 1504 using _Impl::equal_range; 1505 1506 using _Impl::_M_erase_if; 1507 }; 1508 1509 template<typename _KeyContainer, typename _MappedContainer, 1510 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>> 1511 flat_multimap(_KeyContainer, _MappedContainer, _Compare = _Compare()) 1512 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1513 _Compare, _KeyContainer, _MappedContainer>; 1514 1515 template<typename _KeyContainer, typename _MappedContainer, 1516 __allocator_for<_KeyContainer, _MappedContainer> _Alloc> 1517 flat_multimap(_KeyContainer, _MappedContainer, _Alloc) 1518 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1519 less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>; 1520 1521 template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare, 1522 __allocator_for<_KeyContainer, _MappedContainer> _Alloc> 1523 flat_multimap(_KeyContainer, _MappedContainer, _Compare, _Alloc) 1524 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1525 _Compare, _KeyContainer, _MappedContainer>; 1526 1527 template<typename _KeyContainer, typename _MappedContainer, 1528 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>> 1529 flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare = _Compare()) 1530 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1531 _Compare, _KeyContainer, _MappedContainer>; 1532 1533 template<typename _KeyContainer, typename _MappedContainer, 1534 __allocator_for<_KeyContainer, _MappedContainer> _Alloc> 1535 flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Alloc) 1536 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1537 less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>; 1538 1539 template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare, 1540 __allocator_for<_KeyContainer, _MappedContainer> _Alloc> 1541 flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare, _Alloc) 1542 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type, 1543 _Compare, _KeyContainer, _MappedContainer>; 1544 1545 template<__has_input_iter_cat _InputIterator, 1546 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>> 1547 flat_multimap(_InputIterator, _InputIterator, _Compare = _Compare()) 1548 -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; 1549 1550 template<__has_input_iter_cat _InputIterator, 1551 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>> 1552 flat_multimap(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare()) 1553 -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>; 1554 1555 template<ranges::input_range _Rg, 1556 __not_allocator_like _Compare = less<__detail::__range_key_type<_Rg>>, 1557 __allocator_like _Alloc = allocator<byte>> 1558 flat_multimap(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc()) 1559 -> flat_multimap<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>, 1560 _Compare, 1561 vector<__detail::__range_key_type<_Rg>, 1562 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>, 1563 vector<__detail::__range_mapped_type<_Rg>, 1564 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>; 1565 1566 template<ranges::input_range _Rg, __allocator_like _Alloc> 1567 flat_multimap(from_range_t, _Rg&&, _Alloc) 1568 -> flat_multimap<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>, 1569 less<__detail::__range_key_type<_Rg>>, 1570 vector<__detail::__range_key_type<_Rg>, 1571 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>, 1572 vector<__detail::__range_mapped_type<_Rg>, 1573 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>; 1574 1575 template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>> 1576 flat_multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) 1577 -> flat_multimap<_Key, _Tp, _Compare>; 1578 1579 template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>> 1580 flat_multimap(sorted_equivalent_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare()) 1581 -> flat_multimap<_Key, _Tp, _Compare>; 1582 1583 template<typename _Key, typename _Tp, typename _Compare, 1584 typename _KeyContainer, typename _MappedContainer, typename _Alloc> 1585 struct uses_allocator<flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, 1586 _Alloc> 1587 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc> 1588 && uses_allocator_v<_MappedContainer, _Alloc>> 1589 { }; 1590 1591 template<typename _Key, typename _Tp, typename _Compare, 1592 typename _KeyContainer, typename _MappedContainer, typename _Predicate> 1593 typename flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type 1594 erase_if(flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __c, 1595 _Predicate __pred) 1596 { return __c._M_erase_if(std::move(__pred)); } 1597 1598 _GLIBCXX_END_NAMESPACE_VERSION 1599 } // namespace std 1600 #endif // __cpp_lib_flat_map 1601 #endif // _GLIBCXX_FLAT_MAP
