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