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