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