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 
58 namespace 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
Generated by doxygen 1.9.1