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 using __ref = iter_reference_t<_Iter>;
639 for (; __first != __last; ++__first)
640 if constexpr (__pair_like<__ref>)
641 {
642 __ref __value = *__first;
643 _M_cont.keys.emplace_back(std::get<0>(std::forward<__ref>(__value)));
644 _M_cont.values.emplace_back(std::get<1>(std::forward<__ref>(__value)));
645 }
646 else
647 {
648 value_type __value = *__first;
649 _M_cont.keys.emplace_back(std::move(__value.first));
650 _M_cont.values.emplace_back(std::move(__value.second));
651 }
652 auto __zv = views::zip(_M_cont.keys, _M_cont.values);
653 if (__is_sorted)
654 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__zv.begin() + __n, __zv.end(),
655 value_comp()));
656 else
657 ranges::sort(__zv.begin() + __n, __zv.end(), value_comp());
658 ranges::inplace_merge(__zv.begin(), __zv.begin() + __n, __zv.end(),
659 value_comp());
660 if constexpr (!_Multi)
661 _M_unique();
662 __guard._M_disable();
663 }
664
665 public:
666 template<__has_input_iter_cat _InputIterator>
667 _GLIBCXX26_CONSTEXPR
668 void
669 insert(_InputIterator __first, _InputIterator __last)
670 { _M_insert(std::move(__first), std::move(__last)); }
671
672 template<__has_input_iter_cat _InputIterator>
673 _GLIBCXX26_CONSTEXPR
674 void
675 insert(__sorted_t, _InputIterator __first, _InputIterator __last)
676 { _M_insert(std::move(__first), std::move(__last), true); }
677
678 template<__detail::__container_compatible_range<value_type> _Rg>
679 _GLIBCXX26_CONSTEXPR
680 void
681 insert_range(_Rg&& __rg)
682 { _M_insert(ranges::begin(__rg), ranges::end(__rg)); }
683
684 template<__detail::__container_compatible_range<value_type> _Rg>
685 _GLIBCXX26_CONSTEXPR
686 void
687 insert_range(__sorted_t, _Rg&& __rg)
688 { _M_insert(ranges::begin(__rg), ranges::end(__rg), true); }
689
690 _GLIBCXX26_CONSTEXPR
691 void
692 insert(initializer_list<value_type> __il)
693 { insert(__il.begin(), __il.end()); }
694
695 _GLIBCXX26_CONSTEXPR
696 void
697 insert(__sorted_t __s, initializer_list<value_type> __il)
698 { insert(__s, __il.begin(), __il.end()); }
699
700 _GLIBCXX26_CONSTEXPR
701 containers
702 extract() &&
703 {
704 auto __guard = _M_make_clear_guard();
705 return {std::move(_M_cont.keys), std::move(_M_cont.values)};
706 }
707
708 _GLIBCXX26_CONSTEXPR
709 void
710 replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont)
711 {
712 __glibcxx_assert(__key_cont.size() == __mapped_cont.size());
713 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__key_cont, _M_comp));
714 auto __guard = _M_make_clear_guard();
715 _M_cont.keys = std::move(__key_cont);
716 _M_cont.values = std::move(__mapped_cont);
717 __guard._M_disable();
718 }
719
720 // try_emplace and insert_or_assign defined directly in class flat_map only.
721
722 _GLIBCXX26_CONSTEXPR
723 iterator
724 erase(iterator __position)
725 { return erase(static_cast<const_iterator>(__position)); }
726
727 _GLIBCXX26_CONSTEXPR
728 iterator
729 erase(const_iterator __position)
730 {
731 auto __guard = _M_make_clear_guard();
732 auto __idx = __position._M_index;
733 auto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __idx);
734 _M_cont.values.erase(_M_cont.values.begin() + __idx);
735 __guard._M_disable();
736 return iterator{this, __it};
737 }
738
739 _GLIBCXX26_CONSTEXPR
740 size_type
741 erase(const key_type& __x)
742 { return erase<const key_type&>(__x); }
743
744 template<typename _Key2>
745 requires same_as<remove_cvref_t<_Key2>, _Key>
746 || (__transparent_comparator<_Compare>
747 && !is_convertible_v<_Key2, iterator>
748 && !is_convertible_v<_Key2, const_iterator>)
749 _GLIBCXX26_CONSTEXPR
750 size_type
751 erase(_Key2&& __x)
752 {
753 auto [__first, __last] = equal_range(std::forward<_Key2>(__x));
754 auto __n = __last - __first;
755 erase(__first, __last);
756 return __n;
757 }
758
759 _GLIBCXX26_CONSTEXPR
760 iterator
761 erase(const_iterator __first, const_iterator __last)
762 {
763 auto __guard = _M_make_clear_guard();
764 auto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __first._M_index,
765 _M_cont.keys.begin() + __last._M_index);
766 _M_cont.values.erase(_M_cont.values.begin() + __first._M_index,
767 _M_cont.values.begin() + __last._M_index);
768 __guard._M_disable();
769 return iterator{this, __it};
770 }
771
772 _GLIBCXX26_CONSTEXPR
773 void
774 swap(_Derived& __y)
775 noexcept(is_nothrow_swappable_v<key_container_type>
776 && is_nothrow_swappable_v<mapped_container_type>
777 && is_nothrow_swappable_v<key_compare>)
778 {
779 auto __guard = _M_make_clear_guard();
780 auto __guard_y = _ClearGuard{__y._M_cont};
781 ranges::swap(_M_cont.keys, __y._M_cont.keys);
782 ranges::swap(_M_cont.values, __y._M_cont.values);
783 ranges::swap(_M_comp, __y._M_comp);
784 __guard._M_disable();
785 __guard_y._M_disable();
786 }
787
788 _GLIBCXX26_CONSTEXPR
789 void
790 clear() noexcept
791 {
792 _M_cont.keys.clear();
793 _M_cont.values.clear();
794 }
795
796 // observers
797 [[nodiscard]]
798 _GLIBCXX26_CONSTEXPR
799 key_compare
800 key_comp() const
801 { return _M_comp; }
802
803 [[nodiscard]]
804 _GLIBCXX26_CONSTEXPR
805 value_compare
806 value_comp() const
807 { return value_compare(_M_comp); }
808
809 [[nodiscard]]
810 _GLIBCXX26_CONSTEXPR
811 const key_container_type&
812 keys() const noexcept
813 { return _M_cont.keys; }
814
815 [[nodiscard]]
816 _GLIBCXX26_CONSTEXPR
817 const mapped_container_type&
818 values() const noexcept
819 { return _M_cont.values; }
820
821 // map operations
822 [[nodiscard]]
823 _GLIBCXX26_CONSTEXPR
824 iterator
825 find(const key_type& __x)
826 { return find<key_type>(__x); }
827
828 [[nodiscard]]
829 _GLIBCXX26_CONSTEXPR
830 const_iterator
831 find(const key_type& __x) const
832 { return find<key_type>(__x); }
833
834 template<typename _Key2>
835 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
836 [[nodiscard]]
837 _GLIBCXX26_CONSTEXPR
838 iterator
839 find(const _Key2& __x)
840 {
841 auto __it = lower_bound(__x);
842 if (__it != end() && !_M_comp(__x, __it->first))
843 return __it;
844 else
845 return end();
846 }
847
848 template<typename _Key2>
849 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
850 [[nodiscard]]
851 _GLIBCXX26_CONSTEXPR
852 const_iterator
853 find(const _Key2& __x) const
854 {
855 auto __it = lower_bound(__x);
856 if (__it != cend() && !_M_comp(__x, __it->first))
857 return __it;
858 else
859 return cend();
860 }
861
862 [[nodiscard]]
863 _GLIBCXX26_CONSTEXPR
864 size_type
865 count(const key_type& __x) const
866 { return count<key_type>(__x); }
867
868 template<typename _Key2>
869 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
870 [[nodiscard]]
871 _GLIBCXX26_CONSTEXPR
872 size_type
873 count(const _Key2& __x) const
874 {
875 if constexpr (!_Multi)
876 return contains<_Key2>(__x);
877 else
878 {
879 auto [__first, __last] = equal_range(__x);
880 return __last - __first;
881 }
882 }
883
884 [[nodiscard]]
885 _GLIBCXX26_CONSTEXPR
886 bool
887 contains(const key_type& __x) const
888 { return contains<key_type>(__x); }
889
890 template<typename _Key2>
891 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
892 [[nodiscard]]
893 _GLIBCXX26_CONSTEXPR
894 bool
895 contains(const _Key2& __x) const
896 { return find(__x) != cend(); }
897
898 [[nodiscard]]
899 _GLIBCXX26_CONSTEXPR
900 iterator
901 lower_bound(const key_type& __x)
902 { return lower_bound<key_type>(__x); }
903
904 [[nodiscard]]
905 _GLIBCXX26_CONSTEXPR
906 const_iterator
907 lower_bound(const key_type& __x) const
908 { return lower_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 lower_bound(const _Key2& __x)
916 {
917 auto __it = std::lower_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 lower_bound(const _Key2& __x) const
928 {
929 auto __it = std::lower_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 iterator
937 upper_bound(const key_type& __x)
938 { return upper_bound<key_type>(__x); }
939
940 [[nodiscard]]
941 _GLIBCXX26_CONSTEXPR
942 const_iterator
943 upper_bound(const key_type& __x) const
944 { return upper_bound<key_type>(__x); }
945
946 template<typename _Key2>
947 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
948 [[nodiscard]]
949 _GLIBCXX26_CONSTEXPR
950 iterator
951 upper_bound(const _Key2& __x)
952 {
953 auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
954 __x, _M_comp);
955 return {this, __it};
956 }
957
958 template<typename _Key2>
959 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
960 [[nodiscard]]
961 _GLIBCXX26_CONSTEXPR
962 const_iterator
963 upper_bound(const _Key2& __x) const
964 {
965 auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
966 __x, _M_comp);
967 return {this, __it};
968 }
969
970 [[nodiscard]]
971 _GLIBCXX26_CONSTEXPR
972 pair<iterator, iterator>
973 equal_range(const key_type& __x)
974 { return equal_range<key_type>(__x); }
975
976 [[nodiscard]]
977 _GLIBCXX26_CONSTEXPR
978 pair<const_iterator, const_iterator>
979 equal_range(const key_type& __x) const
980 { return equal_range<key_type>(__x); }
981
982 template<typename _Key2>
983 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
984 [[nodiscard]]
985 _GLIBCXX26_CONSTEXPR
986 pair<iterator, iterator>
987 equal_range(const _Key2& __x)
988 {
989 auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),
990 _M_cont.keys.end(),
991 __x, _M_comp);
992 return {{this, __first}, {this, __last}};
993 }
994
995 template<typename _Key2>
996 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
997 [[nodiscard]]
998 _GLIBCXX26_CONSTEXPR
999 pair<const_iterator, const_iterator>
1000 equal_range(const _Key2& __x) const
1001 {
1002 auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),
1003 _M_cont.keys.end(),
1004 __x, _M_comp);
1005 return {{this, __first}, {this, __last}};
1006 }
1007
1008 [[nodiscard]]
1009 friend _GLIBCXX26_CONSTEXPR bool
1010 operator==(const _Derived& __x, const _Derived& __y)
1011 {
1012 return __x._M_cont.keys == __y._M_cont.keys
1013 && __x._M_cont.values == __y._M_cont.values;
1014 }
1015
1016 template<typename _Up = value_type>
1017 [[nodiscard]]
1018 friend _GLIBCXX26_CONSTEXPR __detail::__synth3way_t<_Up>
1019 operator<=>(const _Derived& __x, const _Derived& __y)
1020 {
1021 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
1022 __y.begin(), __y.end(),
1023 __detail::__synth3way);
1024 }
1025
1026 friend _GLIBCXX26_CONSTEXPR void
1027 swap(_Derived& __x, _Derived& __y) noexcept(noexcept(__x.swap(__y)))
1028 { return __x.swap(__y); }
1029
1030 template<typename _Predicate>
1031 _GLIBCXX26_CONSTEXPR
1032 size_type
1033 _M_erase_if(_Predicate __pred)
1034 {
1035 auto __guard = _M_make_clear_guard();
1036 auto __zv = views::zip(_M_cont.keys, _M_cont.values);
1037 auto __sr = ranges::remove_if(__zv, __pred,
1038 [](const auto& __e) {
1039 return const_reference(__e);
1040 });
1041 auto __erased = __sr.size();
1042 erase(end() - __erased, end());
1043 __guard._M_disable();
1044 return __erased;
1045 }
1046
1047 private:
1048 containers _M_cont;
1049 [[no_unique_address]] _Compare _M_comp;
1050
1051 _GLIBCXX26_CONSTEXPR
1052 void
1053 _M_sort_uniq()
1054 {
1055 auto __zv = views::zip(_M_cont.keys, _M_cont.values);
1056 ranges::sort(__zv, value_comp());
1057 if constexpr (!_Multi)
1058 _M_unique();
1059 }
1060
1061 _GLIBCXX26_CONSTEXPR
1062 void
1063 _M_unique() requires (!_Multi)
1064 {
1065 struct __key_equiv
1066 {
1067 _GLIBCXX26_CONSTEXPR
1068 __key_equiv(key_compare __c) : _M_comp(__c) { }
1069
1070 _GLIBCXX26_CONSTEXPR
1071 bool
1072 operator()(const_reference __x, const_reference __y) const
1073 { return !_M_comp(__x.first, __y.first) && !_M_comp(__y.first, __x.first); }
1074
1075 [[no_unique_address]] key_compare _M_comp;
1076 };
1077
1078 auto __zv = views::zip(_M_cont.keys, _M_cont.values);
1079 auto __it = ranges::unique(__zv, __key_equiv(_M_comp)).begin();
1080 auto __n = __it - __zv.begin();
1081 _M_cont.keys.erase(_M_cont.keys.begin() + __n, _M_cont.keys.end());
1082 _M_cont.values.erase(_M_cont.values.begin() + __n, _M_cont.values.end());
1083 }
1084 };
1085
1086 template<typename _Key, typename _Tp, typename _Compare,
1087 typename _KeyContainer, typename _MappedContainer, bool _Multi>
1088 template<bool _Const>
1089 class _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, _Multi>::_Iterator
1090 {
1091 using __size_type = typename _Flat_map_impl::size_type;
1092
1093 public:
1094 using iterator_category = input_iterator_tag;
1095 using iterator_concept = random_access_iterator_tag;
1096 using value_type = pair<key_type, mapped_type>;
1097 using reference = pair<const key_type&,
1098 ranges::__maybe_const_t<_Const, mapped_type>&>;
1099 using difference_type = ptrdiff_t;
1100
1101 _GLIBCXX26_CONSTEXPR
1102 _Iterator() = default;
1103
1104 _GLIBCXX26_CONSTEXPR
1105 _Iterator(_Iterator<!_Const> __it) requires _Const
1106 : _M_cont(__it._M_cont), _M_index(__it._M_index)
1107 { }
1108
1109 _GLIBCXX26_CONSTEXPR
1110 reference
1111 operator*() const noexcept
1112 {
1113 __glibcxx_assert(_M_index < _M_cont->keys.size());
1114 return {_M_cont->keys[_M_index], _M_cont->values[_M_index]};
1115 }
1116
1117 struct pointer
1118 {
1119 reference __p;
1120
1121 _GLIBCXX26_CONSTEXPR
1122 const reference*
1123 operator->() const noexcept
1124 { return std::__addressof(__p); }
1125 };
1126
1127 _GLIBCXX26_CONSTEXPR
1128 pointer
1129 operator->() const
1130 { return pointer{operator*()}; }
1131
1132 _GLIBCXX26_CONSTEXPR
1133 reference
1134 operator[](difference_type __n) const noexcept
1135 { return *(*this + __n); }
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--() noexcept
1148 {
1149 --_M_index;
1150 return *this;
1151 }
1152
1153 _GLIBCXX26_CONSTEXPR
1154 _Iterator
1155 operator++(int) noexcept
1156 {
1157 auto __tmp = *this;
1158 ++*this;
1159 return __tmp;
1160 }
1161
1162 _GLIBCXX26_CONSTEXPR
1163 _Iterator
1164 operator--(int) noexcept
1165 {
1166 auto __tmp = *this;
1167 --*this;
1168 return __tmp;
1169 }
1170
1171 _GLIBCXX26_CONSTEXPR
1172 _Iterator&
1173 operator+=(difference_type __n) noexcept
1174 {
1175 _M_index += __n;
1176 return *this;
1177 }
1178
1179 _GLIBCXX26_CONSTEXPR
1180 _Iterator&
1181 operator-=(difference_type __n) noexcept
1182 {
1183 _M_index -= __n;
1184 return *this;
1185 }
1186
1187 private:
1188 friend _Flat_map_impl;
1189 friend _Iterator<!_Const>;
1190
1191 _GLIBCXX26_CONSTEXPR
1192 _Iterator(_Flat_map_impl* __fm, typename key_container_type::const_iterator __it)
1193 requires (!_Const)
1194 : _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin())
1195 { }
1196
1197 _GLIBCXX26_CONSTEXPR
1198 _Iterator(const _Flat_map_impl* __fm, typename key_container_type::const_iterator __it)
1199 requires _Const
1200 : _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin())
1201 { }
1202
1203 friend _GLIBCXX26_CONSTEXPR _Iterator
1204 operator+(_Iterator __it, difference_type __n) noexcept
1205 {
1206 __it += __n;
1207 return __it;
1208 }
1209
1210 friend _GLIBCXX26_CONSTEXPR _Iterator
1211 operator+(difference_type __n, _Iterator __it) noexcept
1212 {
1213 __it += __n;
1214 return __it;
1215 }
1216
1217 friend _GLIBCXX26_CONSTEXPR _Iterator
1218 operator-(_Iterator __it, difference_type __n) noexcept
1219 {
1220 __it -= __n;
1221 return __it;
1222 }
1223
1224 friend _GLIBCXX26_CONSTEXPR difference_type
1225 operator-(const _Iterator& __x, const _Iterator& __y) noexcept
1226 {
1227 __glibcxx_assert(__x._M_cont == __y._M_cont);
1228 return __x._M_index - __y._M_index;
1229 }
1230
1231 friend _GLIBCXX26_CONSTEXPR bool
1232 operator==(const _Iterator& __x, const _Iterator& __y) noexcept
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 friend _GLIBCXX26_CONSTEXPR strong_ordering
1240 operator<=>(const _Iterator& __x, const _Iterator& __y)
1241 {
1242 __glibcxx_assert(__x._M_cont == __y._M_cont);
1243 __glibcxx_assert((__x._M_index == size_t(-1)) == (__y._M_index == size_t(-1)));
1244 return __x._M_index <=> __y._M_index;
1245 }
1246
1247 ranges::__maybe_const_t<_Const, containers>* _M_cont = nullptr;
1248 __size_type _M_index = -1;
1249 };
1250
1251 /* Class template flat_map - container adaptor
1252 *
1253 * @ingroup
1254 */
1255 template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
1256 typename _KeyContainer = vector<_Key>,
1257 typename _MappedContainer = vector<_Tp>>
1258 class flat_map
1259 : private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>
1260 {
1261 using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>;
1262 friend _Impl;
1263
1264 public:
1265 // types
1266 using typename _Impl::key_type;
1267 using typename _Impl::mapped_type;
1268 using typename _Impl::value_type;
1269 using typename _Impl::key_compare;
1270 using typename _Impl::reference;
1271 using typename _Impl::const_reference;
1272 using typename _Impl::size_type;
1273 using typename _Impl::difference_type;
1274 using typename _Impl::iterator;
1275 using typename _Impl::const_iterator;
1276 using typename _Impl::reverse_iterator;
1277 using typename _Impl::const_reverse_iterator;
1278 using typename _Impl::key_container_type;
1279 using typename _Impl::mapped_container_type;
1280 using typename _Impl::value_compare;
1281 using typename _Impl::containers;
1282
1283 // constructors
1284 using _Impl::_Impl;
1285
1286 // operator=(initializer_list<value_type>)
1287 // Although this also brings in the base move/copy assignment operators,
1288 // they will be hidden by our synthesized ones.
1289 using _Impl::operator=;
1290
1291 // iterators
1292 using _Impl::begin;
1293 using _Impl::end;
1294 using _Impl::rbegin;
1295 using _Impl::rend;
1296
1297 using _Impl::cbegin;
1298 using _Impl::cend;
1299 using _Impl::crbegin;
1300 using _Impl::crend;
1301
1302 // capacity
1303 using _Impl::empty;
1304 using _Impl::size;
1305 using _Impl::max_size;
1306
1307 // element access
1308 _GLIBCXX26_CONSTEXPR
1309 mapped_type&
1310 operator[](const key_type& __x)
1311 { return try_emplace(__x).first->second; }
1312
1313 _GLIBCXX26_CONSTEXPR
1314 mapped_type&
1315 operator[](key_type&& __x)
1316 { return try_emplace(std::move(__x)).first->second; }
1317
1318 template<typename _Key2>
1319 requires __transparent_comparator<_Compare>
1320 _GLIBCXX26_CONSTEXPR
1321 mapped_type&
1322 operator[](_Key2&& __x)
1323 { return try_emplace(std::forward<_Key2>(__x)).first->second; }
1324
1325 _GLIBCXX26_CONSTEXPR
1326 mapped_type&
1327 at(const key_type& __x)
1328 { return at<key_type>(__x); }
1329
1330 _GLIBCXX26_CONSTEXPR
1331 const mapped_type&
1332 at(const key_type& __x) const
1333 { return at<key_type>(__x); }
1334
1335 template<typename _Key2>
1336 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
1337 _GLIBCXX26_CONSTEXPR
1338 mapped_type&
1339 at(const _Key2& __x)
1340 {
1341 auto __it = this->find(__x);
1342 if (__it == this->end())
1343 __throw_out_of_range("flat_map::at");
1344 return __it->second;
1345 }
1346
1347 template<typename _Key2>
1348 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
1349 _GLIBCXX26_CONSTEXPR
1350 const mapped_type&
1351 at(const _Key2& __x) const
1352 {
1353 auto __it = this->find(__x);
1354 if (__it == this->end())
1355 __throw_out_of_range("flat_map::at");
1356 return __it->second;
1357 }
1358
1359 // modifiers
1360 using _Impl::emplace;
1361 using _Impl::emplace_hint;
1362 using _Impl::insert;
1363 using _Impl::insert_range;
1364 using _Impl::extract;
1365 using _Impl::replace;
1366 using _Impl::erase;
1367 using _Impl::swap;
1368 using _Impl::clear;
1369
1370 template<typename... _Args>
1371 requires is_constructible_v<mapped_type, _Args...>
1372 _GLIBCXX26_CONSTEXPR
1373 pair<iterator, bool>
1374 try_emplace(const key_type& __k, _Args&&... __args)
1375 { return _Impl::_M_try_emplace(nullopt, __k, std::forward<_Args>(__args)...); }
1376
1377 template<typename... _Args>
1378 requires is_constructible_v<mapped_type, _Args...>
1379 _GLIBCXX26_CONSTEXPR
1380 pair<iterator, bool>
1381 try_emplace(key_type&& __k, _Args&&... __args)
1382 {
1383 return _Impl::_M_try_emplace(nullopt, std::move(__k),
1384 std::forward<_Args>(__args)...);
1385 }
1386
1387 template<typename _Key2, typename... _Args>
1388 requires __transparent_comparator<_Compare>
1389 && is_constructible_v<key_type, _Key2>
1390 && is_constructible_v<mapped_type, _Args...>
1391 && (!is_convertible_v<_Key2&&, const_iterator>)
1392 && (!is_convertible_v<_Key2&&, iterator>)
1393 _GLIBCXX26_CONSTEXPR
1394 pair<iterator, bool>
1395 try_emplace(_Key2&& __k, _Args&&... __args)
1396 {
1397 return _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k),
1398 std::forward<_Args>(__args)...);
1399 }
1400
1401 template<typename... _Args>
1402 requires is_constructible_v<mapped_type, _Args...>
1403 _GLIBCXX26_CONSTEXPR
1404 iterator
1405 try_emplace(const_iterator __hint, const key_type& __k, _Args&&... __args)
1406 { return _Impl::_M_try_emplace(__hint, __k, std::forward<_Args>(__args)...).first; }
1407
1408 template<typename... _Args>
1409 requires is_constructible_v<mapped_type, _Args...>
1410 _GLIBCXX26_CONSTEXPR
1411 iterator
1412 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
1413 {
1414 return _Impl::_M_try_emplace(__hint, std::move(__k),
1415 std::forward<_Args>(__args)...).first;
1416 }
1417
1418 template<typename _Key2, typename... _Args>
1419 requires __transparent_comparator<_Compare>
1420 && is_constructible_v<key_type, _Key2>
1421 && is_constructible_v<mapped_type, _Args...>
1422 _GLIBCXX26_CONSTEXPR
1423 iterator
1424 try_emplace(const_iterator __hint, _Key2&& __k, _Args&&... __args)
1425 {
1426 return _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k),
1427 std::forward<_Args>(__args)...).first;
1428 }
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(const key_type& __k, _Mapped&& __obj)
1436 { return insert_or_assign<const key_type&, _Mapped>(__k, std::forward<_Mapped>(__obj)); }
1437
1438 template<typename _Mapped>
1439 requires is_assignable_v<mapped_type&, _Mapped>
1440 && is_constructible_v<mapped_type, _Mapped>
1441 _GLIBCXX26_CONSTEXPR
1442 pair<iterator, bool>
1443 insert_or_assign(key_type&& __k, _Mapped&& __obj)
1444 {
1445 return insert_or_assign<key_type, _Mapped>(std::move(__k),
1446 std::forward<_Mapped>(__obj));
1447 }
1448
1449 template<typename _Key2, typename _Mapped>
1450 requires (same_as<remove_cvref_t<_Key2>, _Key> || __transparent_comparator<_Compare>)
1451 && is_constructible_v<key_type, _Key2>
1452 && is_assignable_v<mapped_type&, _Mapped>
1453 && is_constructible_v<mapped_type, _Mapped>
1454 _GLIBCXX26_CONSTEXPR
1455 pair<iterator, bool>
1456 insert_or_assign(_Key2&& __k, _Mapped&& __obj)
1457 {
1458 auto __r = _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k),
1459 std::forward<_Mapped>(__obj));
1460 if (!__r.second)
1461 __r.first->second = std::forward<_Mapped>(__obj);
1462 return __r;
1463 }
1464
1465 template<typename _Mapped>
1466 requires is_assignable_v<mapped_type&, _Mapped>
1467 && is_constructible_v<mapped_type, _Mapped>
1468 _GLIBCXX26_CONSTEXPR
1469 iterator
1470 insert_or_assign(const_iterator __hint, const key_type& __k, _Mapped&& __obj)
1471 {
1472 return insert_or_assign<const key_type&, _Mapped>(__hint, __k,
1473 std::forward<_Mapped>(__obj));
1474 }
1475
1476 template<typename _Mapped>
1477 requires is_assignable_v<mapped_type&, _Mapped>
1478 && is_constructible_v<mapped_type, _Mapped>
1479 _GLIBCXX26_CONSTEXPR
1480 iterator
1481 insert_or_assign(const_iterator __hint, key_type&& __k, _Mapped&& __obj)
1482 {
1483 return insert_or_assign<key_type, _Mapped>(__hint, std::move(__k),
1484 std::forward<_Mapped>(__obj));
1485 }
1486
1487 template<typename _Key2, typename _Mapped>
1488 requires (same_as<remove_cvref_t<_Key2>, _Key> || __transparent_comparator<_Compare>)
1489 && is_constructible_v<key_type, _Key2>
1490 && is_assignable_v<mapped_type&, _Mapped>
1491 && is_constructible_v<mapped_type, _Mapped>
1492 _GLIBCXX26_CONSTEXPR
1493 iterator
1494 insert_or_assign(const_iterator __hint, _Key2&& __k, _Mapped&& __obj)
1495 {
1496 auto __r = _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k),
1497 std::forward<_Mapped>(__obj));
1498 if (!__r.second)
1499 __r.first->second = std::forward<_Mapped>(__obj);
1500 return __r.first;
1501 }
1502
1503 // observers
1504 using _Impl::key_comp;
1505 using _Impl::value_comp;
1506 using _Impl::keys;
1507 using _Impl::values;
1508
1509 // map operations
1510 using _Impl::find;
1511 using _Impl::count;
1512 using _Impl::contains;
1513 using _Impl::lower_bound;
1514 using _Impl::upper_bound;
1515 using _Impl::equal_range;
1516
1517 using _Impl::_M_erase_if;
1518 };
1519
1520 template<typename _KeyContainer, typename _MappedContainer,
1521 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1522 flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())
1523 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1524 _Compare, _KeyContainer, _MappedContainer>;
1525
1526 template<typename _KeyContainer, typename _MappedContainer,
1527 __allocator_for<_KeyContainer, _MappedContainer> _Alloc>
1528 flat_map(_KeyContainer, _MappedContainer, _Alloc)
1529 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1530 less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;
1531
1532 template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,
1533 __allocator_for<_KeyContainer, _MappedContainer> _Alloc>
1534 flat_map(_KeyContainer, _MappedContainer, _Compare, _Alloc)
1535 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1536 _Compare, _KeyContainer, _MappedContainer>;
1537
1538 template<typename _KeyContainer, typename _MappedContainer,
1539 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1540 flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
1541 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1542 _Compare, _KeyContainer, _MappedContainer>;
1543
1544 template<typename _KeyContainer, typename _MappedContainer,
1545 __allocator_for<_KeyContainer, _MappedContainer> _Alloc>
1546 flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Alloc)
1547 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1548 less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;
1549
1550 template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,
1551 __allocator_for<_KeyContainer, _MappedContainer> _Alloc>
1552 flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Alloc)
1553 -> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1554 _Compare, _KeyContainer, _MappedContainer>;
1555
1556 template<__has_input_iter_cat _InputIterator,
1557 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1558 flat_map(_InputIterator, _InputIterator, _Compare = _Compare())
1559 -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1560
1561 template<__has_input_iter_cat _InputIterator,
1562 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1563 flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
1564 -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1565
1566 template<ranges::input_range _Rg,
1567 __not_allocator_like _Compare = less<__detail::__range_key_type<_Rg>>,
1568 __allocator_like _Alloc = allocator<byte>>
1569 flat_map(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
1570 -> flat_map<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
1571 _Compare,
1572 vector<__detail::__range_key_type<_Rg>,
1573 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
1574 vector<__detail::__range_mapped_type<_Rg>,
1575 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
1576
1577 template<ranges::input_range _Rg, __allocator_like _Alloc>
1578 flat_map(from_range_t, _Rg&&, _Alloc)
1579 -> flat_map<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
1580 less<__detail::__range_key_type<_Rg>>,
1581 vector<__detail::__range_key_type<_Rg>,
1582 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
1583 vector<__detail::__range_mapped_type<_Rg>,
1584 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
1585
1586 template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>
1587 flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
1588 -> flat_map<_Key, _Tp, _Compare>;
1589
1590 template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>
1591 flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
1592 -> flat_map<_Key, _Tp, _Compare>;
1593
1594 template<typename _Key, typename _Tp, typename _Compare,
1595 typename _KeyContainer, typename _MappedContainer, typename _Alloc>
1596 struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Alloc>
1597 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>
1598 && uses_allocator_v<_MappedContainer, _Alloc>>
1599 { };
1600
1601 template<typename _Key, typename _Tp, typename _Compare,
1602 typename _KeyContainer, typename _MappedContainer, typename _Predicate>
1603 _GLIBCXX26_CONSTEXPR
1604 typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
1605 erase_if(flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __c,
1606 _Predicate __pred)
1607 { return __c._M_erase_if(std::move(__pred)); }
1608
1609 /* Class template flat_multimap - container adaptor
1610 *
1611 * @ingroup
1612 */
1613 template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
1614 typename _KeyContainer = vector<_Key>,
1615 typename _MappedContainer = vector<_Tp>>
1616 class flat_multimap
1617 : private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>
1618 {
1619 using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>;
1620 friend _Impl;
1621
1622 public:
1623 // types
1624 using typename _Impl::key_type;
1625 using typename _Impl::mapped_type;
1626 using typename _Impl::value_type;
1627 using typename _Impl::key_compare;
1628 using typename _Impl::reference;
1629 using typename _Impl::const_reference;
1630 using typename _Impl::size_type;
1631 using typename _Impl::difference_type;
1632 using typename _Impl::iterator;
1633 using typename _Impl::const_iterator;
1634 using typename _Impl::reverse_iterator;
1635 using typename _Impl::const_reverse_iterator;
1636 using typename _Impl::key_container_type;
1637 using typename _Impl::mapped_container_type;
1638 using typename _Impl::value_compare;
1639 using typename _Impl::containers;
1640
1641 // constructors
1642 using _Impl::_Impl;
1643
1644 // operator=(initializer_list<value_type>)
1645 // Although this also brings in the base move/copy assignment operators,
1646 // they will be hidden by our synthesized ones.
1647 using _Impl::operator=;
1648
1649 // iterators
1650 using _Impl::begin;
1651 using _Impl::end;
1652 using _Impl::rbegin;
1653 using _Impl::rend;
1654
1655 using _Impl::cbegin;
1656 using _Impl::cend;
1657 using _Impl::crbegin;
1658 using _Impl::crend;
1659
1660 // capacity
1661 using _Impl::empty;
1662 using _Impl::size;
1663 using _Impl::max_size;
1664
1665 // modifiers
1666 using _Impl::emplace;
1667 using _Impl::emplace_hint;
1668 using _Impl::insert;
1669 using _Impl::insert_range;
1670 using _Impl::extract;
1671 using _Impl::replace;
1672 using _Impl::erase;
1673 using _Impl::swap;
1674 using _Impl::clear;
1675
1676 // observers
1677 using _Impl::key_comp;
1678 using _Impl::value_comp;
1679 using _Impl::keys;
1680 using _Impl::values;
1681
1682 // map operations
1683 using _Impl::find;
1684 using _Impl::count;
1685 using _Impl::contains;
1686 using _Impl::lower_bound;
1687 using _Impl::upper_bound;
1688 using _Impl::equal_range;
1689
1690 using _Impl::_M_erase_if;
1691 };
1692
1693 template<typename _KeyContainer, typename _MappedContainer,
1694 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1695 flat_multimap(_KeyContainer, _MappedContainer, _Compare = _Compare())
1696 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1697 _Compare, _KeyContainer, _MappedContainer>;
1698
1699 template<typename _KeyContainer, typename _MappedContainer,
1700 __allocator_for<_KeyContainer, _MappedContainer> _Alloc>
1701 flat_multimap(_KeyContainer, _MappedContainer, _Alloc)
1702 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1703 less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;
1704
1705 template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,
1706 __allocator_for<_KeyContainer, _MappedContainer> _Alloc>
1707 flat_multimap(_KeyContainer, _MappedContainer, _Compare, _Alloc)
1708 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1709 _Compare, _KeyContainer, _MappedContainer>;
1710
1711 template<typename _KeyContainer, typename _MappedContainer,
1712 __not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
1713 flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
1714 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1715 _Compare, _KeyContainer, _MappedContainer>;
1716
1717 template<typename _KeyContainer, typename _MappedContainer,
1718 __allocator_for<_KeyContainer, _MappedContainer> _Alloc>
1719 flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Alloc)
1720 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1721 less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;
1722
1723 template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,
1724 __allocator_for<_KeyContainer, _MappedContainer> _Alloc>
1725 flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare, _Alloc)
1726 -> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
1727 _Compare, _KeyContainer, _MappedContainer>;
1728
1729 template<__has_input_iter_cat _InputIterator,
1730 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1731 flat_multimap(_InputIterator, _InputIterator, _Compare = _Compare())
1732 -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1733
1734 template<__has_input_iter_cat _InputIterator,
1735 __not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
1736 flat_multimap(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())
1737 -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1738
1739 template<ranges::input_range _Rg,
1740 __not_allocator_like _Compare = less<__detail::__range_key_type<_Rg>>,
1741 __allocator_like _Alloc = allocator<byte>>
1742 flat_multimap(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
1743 -> flat_multimap<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
1744 _Compare,
1745 vector<__detail::__range_key_type<_Rg>,
1746 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
1747 vector<__detail::__range_mapped_type<_Rg>,
1748 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
1749
1750 template<ranges::input_range _Rg, __allocator_like _Alloc>
1751 flat_multimap(from_range_t, _Rg&&, _Alloc)
1752 -> flat_multimap<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
1753 less<__detail::__range_key_type<_Rg>>,
1754 vector<__detail::__range_key_type<_Rg>,
1755 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
1756 vector<__detail::__range_mapped_type<_Rg>,
1757 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
1758
1759 template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>
1760 flat_multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
1761 -> flat_multimap<_Key, _Tp, _Compare>;
1762
1763 template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>
1764 flat_multimap(sorted_equivalent_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
1765 -> flat_multimap<_Key, _Tp, _Compare>;
1766
1767 template<typename _Key, typename _Tp, typename _Compare,
1768 typename _KeyContainer, typename _MappedContainer, typename _Alloc>
1769 struct uses_allocator<flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>,
1770 _Alloc>
1771 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>
1772 && uses_allocator_v<_MappedContainer, _Alloc>>
1773 { };
1774
1775 template<typename _Key, typename _Tp, typename _Compare,
1776 typename _KeyContainer, typename _MappedContainer, typename _Predicate>
1777 _GLIBCXX26_CONSTEXPR
1778 typename flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
1779 erase_if(flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __c,
1780 _Predicate __pred)
1781 { return __c._M_erase_if(std::move(__pred)); }
1782
1783_GLIBCXX_END_NAMESPACE_VERSION
1784} // namespace std
1785#endif // __cpp_lib_flat_map
1786#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:53
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