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