29#ifndef _GLIBCXX_FLAT_MAP
30#define _GLIBCXX_FLAT_MAP 1
33#pragma GCC system_header
36#define __glibcxx_want_flat_map
39#ifdef __cpp_lib_flat_map
57namespace std _GLIBCXX_VISIBILITY(default)
59_GLIBCXX_BEGIN_NAMESPACE_VERSION
61 template<
typename _Key,
typename _Tp,
typename _Compare,
62 typename _KeyContainer,
typename _MappedContainer>
65 template<
typename _Key,
typename _Tp,
typename _Compare,
66 typename _KeyContainer,
typename _MappedContainer>
69 template<
typename _Key,
typename _Tp,
typename _Compare,
70 typename _KeyContainer,
typename _MappedContainer,
bool _Multi>
73 static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
74 static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>);
76 static_assert(is_nothrow_swappable_v<_KeyContainer>);
77 static_assert(is_nothrow_swappable_v<_MappedContainer>);
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>;
87 template<
bool _Const>
struct _Iterator;
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;
105 using __emplace_result_t = __conditional_t<_Multi, iterator, pair<iterator, bool>>;
110 [[no_unique_address]] key_compare _M_comp;
111 value_compare(key_compare __c) : _M_comp(__c) { }
115 operator()(const_reference __x, const_reference __y)
const
116 {
return _M_comp(__x.first, __y.first); }
118 friend _Flat_map_impl;
123 key_container_type keys;
124 mapped_container_type values;
132 _ClearGuard(containers& __cont)
140 _M_cont->keys.clear();
141 _M_cont->values.clear();
147 { _M_cont =
nullptr; }
151 _M_make_clear_guard()
152 {
return _ClearGuard{this->_M_cont}; }
156 _Flat_map_impl() : _Flat_map_impl(key_compare()) { }
159 _Flat_map_impl(
const key_compare& __comp)
160 : _M_cont(), _M_comp(__comp)
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)
168 __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());
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)
178 __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());
179 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont.keys, _M_comp));
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); }
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); }
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())
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)
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)
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)
218 template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
220 _Flat_map_impl(
const _Alloc& __a)
221 : _Flat_map_impl(key_compare(), __a)
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)),
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,
235 : _Flat_map_impl(__key_cont, __mapped_cont, key_compare(), __a)
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,
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)),
247 __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());
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,
256 : _Flat_map_impl(__s, __key_cont, __mapped_cont, key_compare(), __a)
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,
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)),
269 __glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());
270 _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont.keys, _M_comp));
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)),
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))),
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,
293 : _Flat_map_impl(std::
move(__first), std::
move(__last), key_compare(), __a)
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,
301 : _Flat_map_impl(__comp, __a)
302 { insert(__first, __last); }
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,
309 : _Flat_map_impl(__s, std::
move(__first), std::
move(__last), key_compare(), __a)
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,
318 : _Flat_map_impl(__comp, __a)
319 { insert(__s, __first, __last); }
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,
325 : _Flat_map_impl(from_range, std::
forward<_Rg>(__rg), key_compare(), __a)
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,
332 : _Flat_map_impl(__comp, __a)
335 template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
336 _Flat_map_impl(initializer_list<value_type> __il,
338 : _Flat_map_impl(__il, key_compare(), __a)
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,
345 : _Flat_map_impl(__il.
begin(), __il.
end(), __comp, __a)
348 template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
349 _Flat_map_impl(__sorted_t __s,
350 initializer_list<value_type> __il,
352 : _Flat_map_impl(__s, __il.
begin(), __il.
end(), key_compare(), __a)
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,
360 : _Flat_map_impl(__s, __il.
begin(), __il.
end(), __comp, __a)
364 operator=(initializer_list<value_type> __il)
368 return static_cast<_Derived&
>(*this);
374 {
return {
this, _M_cont.keys.cbegin()}; }
377 begin() const noexcept
378 {
return {
this, _M_cont.keys.cbegin()}; }
382 {
return {
this, _M_cont.keys.cend()}; }
386 {
return {
this, _M_cont.keys.cend()}; }
390 {
return reverse_iterator(
end()); }
392 const_reverse_iterator
394 {
return const_reverse_iterator(
end()); }
398 {
return reverse_iterator(
begin()); }
400 const_reverse_iterator
401 rend() const noexcept
402 {
return const_reverse_iterator(
begin()); }
406 {
return {
this, _M_cont.keys.cbegin()}; }
409 cend() const noexcept
410 {
return {
this, _M_cont.keys.cend()}; }
412 const_reverse_iterator
414 {
return const_reverse_iterator(
cend()); }
416 const_reverse_iterator
417 crend() const noexcept
418 {
return const_reverse_iterator(
cbegin()); }
423 empty() const noexcept
424 {
return _M_cont.keys.empty(); }
427 size() const noexcept
428 {
return _M_cont.keys.size(); }
431 max_size() const noexcept
438 template<
typename _Key2,
typename... _Args>
440 _M_try_emplace(optional<const_iterator> __hint, _Key2&& __k, _Args&&... __args)
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()
448 || (__r = !_M_comp(__k, (*__hint)[-1].first)))
450 || (__s = !_M_comp((*__hint)[0].first, __k))))
452 __key_it = _M_cont.keys.begin() + __hint->_M_index;
453 if constexpr (!_Multi)
454 if (__r == 1 && !_M_comp(__key_it[-1], __k))
455 return {iterator{
this, __key_it - 1},
false};
459 auto __first = _M_cont.keys.begin();
460 auto __last = _M_cont.keys.end();
462 __first += __hint->_M_index;
464 __last = __first + __hint->_M_index;
465 if constexpr (_Multi)
469 __key_it = std::lower_bound(__first, __last, __k, _M_comp);
474 __k, std::not_fn(_M_comp)).base();
477 __key_it = std::lower_bound(__first, __last, __k, _M_comp);
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};
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());
488 __guard._M_disable();
489 return {iterator{
this, __key_it},
true};
492 template<
typename... _Args>
493 requires is_constructible_v<value_type, _Args...>
495 emplace(_Args&&... __args)
499 if constexpr (_Multi)
505 template<
typename... _Args>
507 emplace_hint(const_iterator __position, _Args&&... __args)
514 insert(
const value_type& __x)
515 {
return emplace(__x); }
518 insert(value_type&& __x)
522 insert(const_iterator __position,
const value_type& __x)
523 {
return emplace_hint(__position, __x); }
526 insert(const_iterator __position, value_type&& __x)
527 {
return emplace_hint(__position,
std::move(__x)); }
529 template<
typename _Arg>
530 requires is_constructible_v<value_type, _Arg>
535 template<
typename _Arg>
536 requires is_constructible_v<value_type, _Arg>
538 insert(const_iterator __position, _Arg&& __x)
542 template<
typename _Iter,
typename _Sent>
544 _M_insert(_Iter __first, _Sent __last)
551 auto __guard = _M_make_clear_guard();
553 for (; __first != __last; ++__first)
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));
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)
564 __guard._M_cont =
nullptr;
566 auto __guard = _M_make_clear_guard();
567 for (; __first != __last; ++__first)
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));
574 __guard._M_disable();
579 template<__has_input_iter_cat _InputIterator>
581 insert(_InputIterator __first, _InputIterator __last)
584 template<__has_input_iter_cat _InputIterator>
586 insert(__sorted_t, _InputIterator __first, _InputIterator __last)
592 template<__detail::__container_compatible_range<value_type> _Rg>
594 insert_range(_Rg&& __rg)
595 { _M_insert(ranges::begin(__rg), ranges::end(__rg)); }
598 insert(initializer_list<value_type> __il)
599 { insert(__il.begin(), __il.end()); }
602 insert(__sorted_t __s, initializer_list<value_type> __il)
603 { insert(__s, __il.begin(), __il.end()); }
608 auto __guard = _M_make_clear_guard();
613 replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont)
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();
619 _M_cont.values =
std::move(__mapped_cont);
620 __guard._M_disable();
626 erase(iterator __position)
627 {
return erase(
static_cast<const_iterator
>(__position)); }
630 erase(const_iterator __position)
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};
641 erase(
const key_type& __x)
642 {
return erase<const key_type&>(__x); }
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>)
653 auto __n = __last - __first;
654 erase(__first, __last);
659 erase(const_iterator __first, const_iterator __last)
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};
671 swap(_Derived& __y)
noexcept
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);
681 _M_cont.keys.clear();
682 _M_cont.values.clear();
694 {
return value_compare(_M_comp); }
697 const key_container_type&
698 keys() const noexcept
699 {
return _M_cont.keys; }
702 const mapped_container_type&
703 values() const noexcept
704 {
return _M_cont.values; }
709 find(
const key_type& __x)
710 {
return find<key_type>(__x); }
714 find(
const key_type& __x)
const
715 {
return find<key_type>(__x); }
717 template<
typename _Key2>
718 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
721 find(
const _Key2& __x)
723 auto __it = lower_bound(__x);
724 if (__it !=
end() && !_M_comp(__x, __it->first))
730 template<
typename _Key2>
731 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
734 find(
const _Key2& __x)
const
736 auto __it = lower_bound(__x);
737 if (__it !=
cend() && !_M_comp(__x, __it->first))
745 count(
const key_type& __x)
const
746 {
return count<key_type>(__x); }
748 template<
typename _Key2>
749 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
752 count(
const _Key2& __x)
const
754 if constexpr (!_Multi)
755 return contains<_Key2>(__x);
758 auto [__first, __last] = equal_range(__x);
759 return __last - __first;
765 contains(
const key_type& __x)
const
766 {
return contains<key_type>(__x); }
768 template<
typename _Key2>
769 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
772 contains(
const _Key2& __x)
const
773 {
return find(__x) !=
cend(); }
777 lower_bound(
const key_type& __x)
778 {
return lower_bound<key_type>(__x); }
782 lower_bound(
const key_type& __x)
const
783 {
return lower_bound<key_type>(__x); }
785 template<
typename _Key2>
786 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
789 lower_bound(
const _Key2& __x)
791 auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
796 template<
typename _Key2>
797 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
800 lower_bound(
const _Key2& __x)
const
802 auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
809 upper_bound(
const key_type& __x)
810 {
return upper_bound<key_type>(__x); }
814 upper_bound(
const key_type& __x)
const
815 {
return upper_bound<key_type>(__x); }
817 template<
typename _Key2>
818 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
821 upper_bound(
const _Key2& __x)
823 auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
828 template<
typename _Key2>
829 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
832 upper_bound(
const _Key2& __x)
const
834 auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
840 pair<iterator, iterator>
841 equal_range(
const key_type& __x)
842 {
return equal_range<key_type>(__x); }
845 pair<const_iterator, const_iterator>
846 equal_range(
const key_type& __x)
const
847 {
return equal_range<key_type>(__x); }
849 template<
typename _Key2>
850 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
852 pair<iterator, iterator>
853 equal_range(
const _Key2& __x)
855 auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),
858 return {{
this, __first}, {
this, __last}};
861 template<
typename _Key2>
862 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
864 pair<const_iterator, const_iterator>
865 equal_range(
const _Key2& __x)
const
867 auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),
870 return {{
this, __first}, {
this, __last}};
875 operator==(
const _Derived& __x,
const _Derived& __y)
877 return __x._M_cont.keys == __y._M_cont.keys
878 && __x._M_cont.values == __y._M_cont.values;
881 template<
typename _Up = value_type>
883 friend __detail::__synth3way_t<_Up>
884 operator<=>(
const _Derived& __x,
const _Derived& __y)
887 __y.begin(), __y.end(),
888 __detail::__synth3way);
892 swap(_Derived& __x, _Derived& __y)
noexcept
893 {
return __x.swap(__y); }
895 template<
typename _Predicate>
897 _M_erase_if(_Predicate __pred)
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);
905 auto __erased = __sr.size();
906 erase(
end() - __erased,
end());
907 __guard._M_disable();
913 [[no_unique_address]] _Compare _M_comp;
918 auto __zv = views::zip(_M_cont.keys, _M_cont.values);
919 ranges::sort(__zv, value_comp());
920 if constexpr (!_Multi)
925 _M_unique()
requires (!_Multi)
929 __key_equiv(key_compare __c) : _M_comp(__c) { }
932 operator()(const_reference __x, const_reference __y)
const
933 {
return !_M_comp(__x.first, __y.first) && !_M_comp(__y.first, __x.first); }
935 [[no_unique_address]] key_compare _M_comp;
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());
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
951 using __size_type =
typename _Flat_map_impl::size_type;
954 using iterator_category = input_iterator_tag;
955 using iterator_concept = random_access_iterator_tag;
956 using value_type = pair<const 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;
961 _Iterator() =
default;
963 _Iterator(_Iterator<!_Const> __it)
requires _Const
964 : _M_cont(__it._M_cont), _M_index(__it._M_index)
970 __glibcxx_assert(_M_index < _M_cont->keys.size());
971 return {_M_cont->keys[_M_index], _M_cont->values[_M_index]};
979 operator->() const noexcept
988 operator[](difference_type __n)
const noexcept
989 {
return *(*
this + __n); }
992 operator++() noexcept
999 operator--() noexcept
1006 operator++(
int)
noexcept
1014 operator--(
int)
noexcept
1022 operator+=(difference_type __n)
noexcept
1029 operator-=(difference_type __n)
noexcept
1036 friend _Flat_map_impl;
1037 friend _Iterator<!_Const>;
1039 _Iterator(_Flat_map_impl* __fm,
typename key_container_type::const_iterator __it)
1041 : _M_cont(std::
__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().
cbegin())
1044 _Iterator(
const _Flat_map_impl* __fm,
typename key_container_type::const_iterator __it)
1046 : _M_cont(
std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin())
1050 operator+(_Iterator __it, difference_type __n)
noexcept
1057 operator+(difference_type __n, _Iterator __it)
noexcept
1064 operator-(_Iterator __it, difference_type __n)
noexcept
1070 friend difference_type
1071 operator-(
const _Iterator& __x,
const _Iterator& __y)
noexcept
1073 __glibcxx_assert(__x._M_cont == __y._M_cont);
1074 return __x._M_index - __y._M_index;
1078 operator==(
const _Iterator& __x,
const _Iterator& __y)
noexcept
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;
1085 friend strong_ordering
1086 operator<=>(
const _Iterator& __x,
const _Iterator& __y)
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;
1093 ranges::__maybe_const_t<_Const, containers>* _M_cont =
nullptr;
1094 __size_type _M_index = -1;
1101 template<
typename _Key,
typename _Tp,
typename _Compare = less<_Key>,
1102 typename _KeyContainer = vector<_Key>,
1103 typename _MappedContainer = vector<_Tp>>
1105 :
private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>
1107 using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>;
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;
1135 using _Impl::rbegin;
1138 using _Impl::cbegin;
1140 using _Impl::crbegin;
1146 using _Impl::max_size;
1150 operator[](
const key_type& __x)
1151 {
return try_emplace(__x).first->second; }
1154 operator[](key_type&& __x)
1155 {
return try_emplace(
std::move(__x)).first->second; }
1157 template<
typename _Key2>
1158 requires __transparent_comparator<_Compare>
1160 operator[](_Key2&& __x)
1164 at(
const key_type& __x)
1165 {
return at<key_type>(__x); }
1168 at(
const key_type& __x)
const
1169 {
return at<key_type>(__x); }
1171 template<
typename _Key2>
1172 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
1174 at(
const _Key2& __x)
1176 auto __it = this->find(__x);
1177 if (__it == this->
end())
1178 __throw_out_of_range(
"flat_map::at");
1179 return __it->second;
1182 template<
typename _Key2>
1183 requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
1185 at(
const _Key2& __x)
const
1187 auto __it = this->find(__x);
1188 if (__it == this->
end())
1189 __throw_out_of_range(
"flat_map::at");
1190 return __it->second;
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;
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)
1210 template<
typename... _Args>
1211 requires is_constructible_v<mapped_type, _Args...>
1212 pair<iterator, bool>
1213 try_emplace(key_type&& __k, _Args&&... __args)
1215 return _Impl::_M_try_emplace(nullopt,
std::move(__k),
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)
1232 template<
typename... _Args>
1233 requires is_constructible_v<mapped_type, _Args...>
1235 try_emplace(const_iterator __hint,
const key_type& __k, _Args&&... __args)
1238 template<
typename... _Args>
1239 requires is_constructible_v<mapped_type, _Args...>
1241 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
1243 return _Impl::_M_try_emplace(__hint,
std::move(__k),
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...>
1252 try_emplace(const_iterator __hint, _Key2&& __k, _Args&&... __args)
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)
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)
1271 return insert_or_assign<key_type, _Mapped>(
std::move(__k),
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)
1290 template<
typename _Mapped>
1291 requires is_assignable_v<mapped_type&, _Mapped>
1292 && is_constructible_v<mapped_type, _Mapped>
1294 insert_or_assign(const_iterator __hint,
const key_type& __k, _Mapped&& __obj)
1296 return insert_or_assign<const key_type&, _Mapped>(__hint, __k,
1300 template<
typename _Mapped>
1301 requires is_assignable_v<mapped_type&, _Mapped>
1302 && is_constructible_v<mapped_type, _Mapped>
1304 insert_or_assign(const_iterator __hint, key_type&& __k, _Mapped&& __obj)
1306 return insert_or_assign<key_type, _Mapped>(__hint,
std::move(__k),
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>
1316 insert_or_assign(const_iterator __hint, _Key2&& __k, _Mapped&& __obj)
1326 using _Impl::key_comp;
1327 using _Impl::value_comp;
1329 using _Impl::values;
1334 using _Impl::contains;
1335 using _Impl::lower_bound;
1336 using _Impl::upper_bound;
1337 using _Impl::equal_range;
1339 using _Impl::_M_erase_if;
1342 template<
typename _KeyContainer,
typename _MappedContainer,
1344 flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())
1345 -> flat_map<
typename _KeyContainer::value_type,
typename _MappedContainer::value_type,
1346 _Compare, _KeyContainer, _MappedContainer>;
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,
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>;
1360 template<
typename _KeyContainer,
typename _MappedContainer,
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>;
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,
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>;
1378 template<__has_input_iter_cat _InputIterator,
1380 flat_map(_InputIterator, _InputIterator, _Compare = _Compare())
1381 -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1383 template<__has_input_iter_cat _InputIterator,
1385 flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
1386 -> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1388 template<ranges::input_range _Rg,
1391 flat_map(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
1392 -> flat_map<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
1395 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
1397 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
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>,
1404 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
1406 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
1408 template<
typename _Key,
typename _Tp, __not_allocator_like _Compare = less<_Key>>
1410 -> flat_map<_Key, _Tp, _Compare>;
1412 template<
typename _Key,
typename _Tp, __not_allocator_like _Compare = less<_Key>>
1414 -> flat_map<_Key, _Tp, _Compare>;
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>>
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,
1428 {
return __c._M_erase_if(
std::move(__pred)); }
1434 template<
typename _Key,
typename _Tp,
typename _Compare = less<_Key>,
1435 typename _KeyContainer = vector<_Key>,
1436 typename _MappedContainer = vector<_Tp>>
1438 :
private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>
1440 using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>;
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;
1468 using _Impl::rbegin;
1471 using _Impl::cbegin;
1473 using _Impl::crbegin;
1479 using _Impl::max_size;
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;
1493 using _Impl::key_comp;
1494 using _Impl::value_comp;
1496 using _Impl::values;
1501 using _Impl::contains;
1502 using _Impl::lower_bound;
1503 using _Impl::upper_bound;
1504 using _Impl::equal_range;
1506 using _Impl::_M_erase_if;
1509 template<
typename _KeyContainer,
typename _MappedContainer,
1511 flat_multimap(_KeyContainer, _MappedContainer, _Compare = _Compare())
1512 -> flat_multimap<
typename _KeyContainer::value_type,
typename _MappedContainer::value_type,
1513 _Compare, _KeyContainer, _MappedContainer>;
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,
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>;
1527 template<
typename _KeyContainer,
typename _MappedContainer,
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>;
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,
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>;
1545 template<__has_input_iter_cat _InputIterator,
1547 flat_multimap(_InputIterator, _InputIterator, _Compare = _Compare())
1548 -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1550 template<__has_input_iter_cat _InputIterator,
1552 flat_multimap(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())
1553 -> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
1555 template<ranges::input_range _Rg,
1558 flat_multimap(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
1559 -> flat_multimap<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
1562 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
1564 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
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>,
1571 __alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
1573 __alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
1575 template<
typename _Key,
typename _Tp, __not_allocator_like _Compare = less<_Key>>
1577 -> flat_multimap<_Key, _Tp, _Compare>;
1579 template<
typename _Key,
typename _Tp, __not_allocator_like _Compare = less<_Key>>
1581 -> flat_multimap<_Key, _Tp, _Compare>;
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>,
1587 : bool_constant<uses_allocator_v<_KeyContainer, _Alloc>
1588 && uses_allocator_v<_MappedContainer, _Alloc>>
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,
1596 {
return __c._M_erase_if(
std::move(__pred)); }
1598_GLIBCXX_END_NAMESPACE_VERSION
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
constexpr complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs are equal iff their members are equal.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
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.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
ISO C++ entities toplevel namespace is std.
constexpr auto rbegin(_Container &__cont) noexcept(noexcept(__cont.rbegin())) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
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.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
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.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
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.
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.
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.
The standard allocator, as per C++03 [20.4.1].
Declare uses_allocator so it can be specialized in <queue> etc.
One of the comparison functors.
Struct holding two objects of arbitrary type.
A standard container which offers fixed time access to individual elements in any order.