libstdc++
flat_map
Go to the documentation of this file.
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
57namespace 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<const 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