breeze/gcc
1
0
Fork 0
mirror of https://github.com/gcc-mirror/gcc.git synced 2026-01-12 00:05:41 +08:00
Code Issues Packages Projects Releases Wiki Activity
Files
master
gcc/libstdc++-v3/include/std/flat_map
Yuao Ma 2226b67bbe libstdc++: constexpr flat_map and flat_multimap 
This patch makes flat_map and flat_multimap constexpr as part of P3372R3.

libstdc++-v3/ChangeLog:

	* include/bits/version.def: Add FTM.
	* include/bits/version.h: Regenerate.
	* include/std/flat_map: Add constexpr.
	* testsuite/23_containers/flat_map/1.cc: Add constexpr test.
	* testsuite/23_containers/flat_multimap/1.cc: Add constexpr test.
2026-01-10 15:08:53 +08:00

1741 lines
55 KiB
C++
Raw Permalink Blame History

// <flat_map> -*- C++ -*-
// Copyright The GNU Toolchain Authors.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/** @file include/flat_map
* This is a Standard C++ Library header.
*/
#ifndef _GLIBCXX_FLAT_MAP
#define _GLIBCXX_FLAT_MAP 1
#ifdef _GLIBCXX_SYSHDR
#pragma GCC system_header
#endif
#define __glibcxx_want_constexpr_flat_map
#define __glibcxx_want_flat_map
#include <bits/version.h>
#ifdef __cpp_lib_flat_map // >= C++23
#include <compare>
#include <initializer_list>
#include <exception>
#include <functional> // not_fn
#include <optional>
#include <ranges> // views::zip
#include <type_traits>
#include <vector>
#include <bits/stdexcept_throw.h>
#include <bits/stl_algo.h>
#include <bits/stl_function.h> // less
#include <bits/stl_pair.h>
#include <bits/uses_allocator_args.h> // make_obj_using_allocator
#include <bits/ranges_algo.h>
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Key, typename _Tp, typename _Compare,
typename _KeyContainer, typename _MappedContainer>
class flat_map;
template<typename _Key, typename _Tp, typename _Compare,
typename _KeyContainer, typename _MappedContainer>
class flat_multimap;
template<typename _Key, typename _Tp, typename _Compare,
typename _KeyContainer, typename _MappedContainer, bool _Multi>
class _Flat_map_impl
{
static_assert(is_same_v<_Key, typename _KeyContainer::value_type>);
static_assert(is_same_v<_Tp, typename _MappedContainer::value_type>);
static_assert(is_nothrow_swappable_v<_KeyContainer>);
static_assert(is_nothrow_swappable_v<_MappedContainer>);
using _Derived = __conditional_t<_Multi,
flat_multimap<_Key, _Tp, _Compare,
_KeyContainer, _MappedContainer>,
flat_map<_Key, _Tp, _Compare,
_KeyContainer, _MappedContainer>>;
using __sorted_t = __conditional_t<_Multi, sorted_equivalent_t, sorted_unique_t>;
public:
template<bool _Const> struct _Iterator;
using key_type = _Key;
using mapped_type = _Tp;
using value_type = pair<key_type, mapped_type>;
using key_compare = _Compare;
using reference = pair<const key_type&, mapped_type&>;
using const_reference = pair<const key_type&, const mapped_type&>;
using size_type = size_t;
using difference_type = ptrdiff_t;
using iterator = _Iterator<false>;
using const_iterator = _Iterator<true>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
using key_container_type = _KeyContainer;
using mapped_container_type = _MappedContainer;
private:
using __emplace_result_t = __conditional_t<_Multi, iterator, pair<iterator, bool>>;
public:
class value_compare
{
[[no_unique_address]] key_compare _M_comp;
_GLIBCXX26_CONSTEXPR
value_compare(key_compare __c) : _M_comp(__c) { }
public:
_GLIBCXX26_CONSTEXPR
bool
operator()(const_reference __x, const_reference __y) const
{ return _M_comp(__x.first, __y.first); }
friend _Flat_map_impl;
};
struct containers
{
key_container_type keys;
mapped_container_type values;
};
private:
struct _ClearGuard
{
containers* _M_cont;
_GLIBCXX26_CONSTEXPR
_ClearGuard(containers& __cont)
: _M_cont(std::__addressof(__cont))
{ }
_GLIBCXX26_CONSTEXPR
~_ClearGuard()
{
if (_M_cont)
{
_M_cont->keys.clear();
_M_cont->values.clear();
}
}
_GLIBCXX26_CONSTEXPR
void
_M_disable()
{ _M_cont = nullptr; }
};
_GLIBCXX26_CONSTEXPR
_ClearGuard
_M_make_clear_guard()
{ return _ClearGuard{this->_M_cont}; }
public:
// constructors
_GLIBCXX26_CONSTEXPR
_Flat_map_impl() : _Flat_map_impl(key_compare()) { }
_GLIBCXX26_CONSTEXPR
explicit
_Flat_map_impl(const key_compare& __comp)
: _M_cont(), _M_comp(__comp)
{ }
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(key_container_type __key_cont,
mapped_container_type __mapped_cont,
const key_compare& __comp = key_compare())
: _M_cont(std::move(__key_cont), std::move(__mapped_cont)), _M_comp(__comp)
{
__glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());
_M_sort_uniq();
}
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(__sorted_t,
key_container_type __key_cont,
mapped_container_type __mapped_cont,
const key_compare& __comp = key_compare())
: _M_cont(std::move(__key_cont), std::move(__mapped_cont)), _M_comp(__comp)
{
__glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());
_GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont.keys, _M_comp));
}
template<__has_input_iter_cat _InputIterator>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(_InputIterator __first, _InputIterator __last,
const key_compare& __comp = key_compare())
: _M_cont(), _M_comp(__comp)
{ insert(__first, __last); }
template<__has_input_iter_cat _InputIterator>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(__sorted_t __s,
_InputIterator __first, _InputIterator __last,
const key_compare& __comp = key_compare())
: _M_cont(), _M_comp(__comp)
{ insert(__s, __first, __last); }
template<__detail::__container_compatible_range<value_type> _Rg>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(from_range_t, _Rg&& __rg)
: _Flat_map_impl(from_range, std::forward<_Rg>(__rg), key_compare())
{ }
template<__detail::__container_compatible_range<value_type> _Rg>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(from_range_t, _Rg&& __rg, const key_compare& __comp)
: _Flat_map_impl(__comp)
{ insert_range(std::forward<_Rg>(__rg)); }
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(initializer_list<value_type> __il,
const key_compare& __comp = key_compare())
: _Flat_map_impl(__il.begin(), __il.end(), __comp)
{ }
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(__sorted_t __s,
initializer_list<value_type> __il,
const key_compare& __comp = key_compare())
: _Flat_map_impl(__s, __il.begin(), __il.end(), __comp)
{ }
// constructors with allocators
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
explicit
_Flat_map_impl(const _Alloc& __a)
: _Flat_map_impl(key_compare(), __a)
{ }
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(const key_compare& __comp, const _Alloc& __a)
: _M_cont(std::make_obj_using_allocator<key_container_type>(__a),
std::make_obj_using_allocator<mapped_container_type>(__a)),
_M_comp(__comp)
{ }
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(const key_container_type& __key_cont,
const mapped_container_type& __mapped_cont,
const _Alloc& __a)
: _Flat_map_impl(__key_cont, __mapped_cont, key_compare(), __a)
{ }
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(const key_container_type& __key_cont,
const mapped_container_type& __mapped_cont,
const key_compare& __comp,
const _Alloc& __a)
: _M_cont(std::make_obj_using_allocator<key_container_type>(__a, __key_cont),
std::make_obj_using_allocator<mapped_container_type>(__a, __mapped_cont)),
_M_comp(__comp)
{
__glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());
_M_sort_uniq();
}
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(__sorted_t __s,
const key_container_type& __key_cont,
const mapped_container_type& __mapped_cont,
const _Alloc& __a)
: _Flat_map_impl(__s, __key_cont, __mapped_cont, key_compare(), __a)
{ }
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(__sorted_t,
const key_container_type& __key_cont,
const mapped_container_type& __mapped_cont,
const key_compare& __comp,
const _Alloc& __a)
: _M_cont(std::make_obj_using_allocator<key_container_type>(__a, __key_cont),
std::make_obj_using_allocator<mapped_container_type>(__a, __mapped_cont)),
_M_comp(__comp)
{
__glibcxx_assert(_M_cont.keys.size() == _M_cont.values.size());
_GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(_M_cont.keys, _M_comp));
}
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(const _Derived& __x, const _Alloc& __a)
: _M_cont(std::make_obj_using_allocator<key_container_type>(__a, __x._M_cont.keys),
std::make_obj_using_allocator<mapped_container_type>(__a, __x._M_cont.values)),
_M_comp(__x._M_comp)
{ }
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(_Derived&& __x, const _Alloc& __a)
: _M_cont(std::make_obj_using_allocator<key_container_type>
(__a, std::move(__x._M_cont.keys)),
std::make_obj_using_allocator<mapped_container_type>
(__a, std::move(__x._M_cont.values))),
_M_comp(__x._M_comp)
{ }
template<__has_input_iter_cat _InputIterator,
__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(_InputIterator __first, _InputIterator __last,
const _Alloc& __a)
: _Flat_map_impl(std::move(__first), std::move(__last), key_compare(), __a)
{ }
template<__has_input_iter_cat _InputIterator,
__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(_InputIterator __first, _InputIterator __last,
const key_compare& __comp,
const _Alloc& __a)
: _Flat_map_impl(__comp, __a)
{ insert(__first, __last); }
template<__has_input_iter_cat _InputIterator,
__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(__sorted_t __s,
_InputIterator __first, _InputIterator __last,
const _Alloc& __a)
: _Flat_map_impl(__s, std::move(__first), std::move(__last), key_compare(), __a)
{ }
template<__has_input_iter_cat _InputIterator,
__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(__sorted_t __s,
_InputIterator __first, _InputIterator __last,
const key_compare& __comp,
const _Alloc& __a)
: _Flat_map_impl(__comp, __a)
{ insert(__s, __first, __last); }
template<__detail::__container_compatible_range<value_type> _Rg,
__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(from_range_t, _Rg&& __rg,
const _Alloc& __a)
: _Flat_map_impl(from_range, std::forward<_Rg>(__rg), key_compare(), __a)
{ }
template<__detail::__container_compatible_range<value_type> _Rg,
__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(from_range_t, _Rg&& __rg, const key_compare& __comp,
const _Alloc& __a)
: _Flat_map_impl(__comp, __a)
{ insert_range(std::forward<_Rg>(__rg)); }
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(initializer_list<value_type> __il,
const _Alloc& __a)
: _Flat_map_impl(__il, key_compare(), __a)
{ }
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(initializer_list<value_type> __il,
const key_compare& __comp,
const _Alloc& __a)
: _Flat_map_impl(__il.begin(), __il.end(), __comp, __a)
{ }
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(__sorted_t __s,
initializer_list<value_type> __il,
const _Alloc& __a)
: _Flat_map_impl(__s, __il.begin(), __il.end(), key_compare(), __a)
{ }
template<__allocator_for<key_container_type, mapped_container_type> _Alloc>
_GLIBCXX26_CONSTEXPR
_Flat_map_impl(__sorted_t __s,
initializer_list<value_type> __il,
const key_compare& __comp,
const _Alloc& __a)
: _Flat_map_impl(__s, __il.begin(), __il.end(), __comp, __a)
{ }
_GLIBCXX26_CONSTEXPR
_Derived&
operator=(initializer_list<value_type> __il)
{
clear();
insert(__il);
return static_cast<_Derived&>(*this);
}
// iterators
_GLIBCXX26_CONSTEXPR
iterator
begin() noexcept
{ return {this, _M_cont.keys.cbegin()}; }
_GLIBCXX26_CONSTEXPR
const_iterator
begin() const noexcept
{ return {this, _M_cont.keys.cbegin()}; }
_GLIBCXX26_CONSTEXPR
iterator
end() noexcept
{ return {this, _M_cont.keys.cend()}; }
_GLIBCXX26_CONSTEXPR
const_iterator
end() const noexcept
{ return {this, _M_cont.keys.cend()}; }
_GLIBCXX26_CONSTEXPR
reverse_iterator
rbegin() noexcept
{ return reverse_iterator(end()); }
_GLIBCXX26_CONSTEXPR
const_reverse_iterator
rbegin() const noexcept
{ return const_reverse_iterator(end()); }
_GLIBCXX26_CONSTEXPR
reverse_iterator
rend() noexcept
{ return reverse_iterator(begin()); }
_GLIBCXX26_CONSTEXPR
const_reverse_iterator
rend() const noexcept
{ return const_reverse_iterator(begin()); }
_GLIBCXX26_CONSTEXPR
const_iterator
cbegin() const noexcept
{ return {this, _M_cont.keys.cbegin()}; }
_GLIBCXX26_CONSTEXPR
const_iterator
cend() const noexcept
{ return {this, _M_cont.keys.cend()}; }
_GLIBCXX26_CONSTEXPR
const_reverse_iterator
crbegin() const noexcept
{ return const_reverse_iterator(cend()); }
_GLIBCXX26_CONSTEXPR
const_reverse_iterator
crend() const noexcept
{ return const_reverse_iterator(cbegin()); }
// capacity
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
bool
empty() const noexcept
{ return _M_cont.keys.empty(); }
_GLIBCXX26_CONSTEXPR
size_type
size() const noexcept
{ return _M_cont.keys.size(); }
_GLIBCXX26_CONSTEXPR
size_type
max_size() const noexcept
{ return std::min<size_type>(keys().max_size(), values().max_size()); }
// element access
// operator[] and at defined directly in class flat_map only.
// modifiers
template<typename _Key2, typename... _Args>
_GLIBCXX26_CONSTEXPR
pair<iterator, bool>
_M_try_emplace(optional<const_iterator> __hint, _Key2&& __k, _Args&&... __args)
{
// TODO: Simplify and audit the hint handling.
typename key_container_type::iterator __key_it;
typename mapped_container_type::iterator __value_it;
int __r = -1, __s = -1;
if (__hint.has_value()
&& (__hint == cbegin()
|| (__r = !_M_comp(__k, (*__hint)[-1].first))) // k >= hint[-1]
&& (__hint == cend()
|| (__s = !_M_comp((*__hint)[0].first, __k)))) // k <= hint[0]
{
__key_it = _M_cont.keys.begin() + __hint->_M_index;
if constexpr (!_Multi)
if (__r == 1 && !_M_comp(__key_it[-1], __k)) // k == hint[-1]
return {iterator{this, __key_it - 1}, false};
}
else
{
auto __first = _M_cont.keys.begin();
auto __last = _M_cont.keys.end();
if (__r == 1) // k >= hint[-1]
__first += __hint->_M_index;
else if (__r == 0) // k < __hint[-1]
__last = __first + __hint->_M_index;
if constexpr (_Multi)
{
if (__s == 0) // hint[0] < k
// Insert before the leftmost equivalent key.
__key_it = std::lower_bound(__first, __last, __k, _M_comp);
else
// Insert after the rightmost equivalent key.
__key_it = std::upper_bound(std::make_reverse_iterator(__last),
std::make_reverse_iterator(__first),
__k, std::not_fn(_M_comp)).base();
}
else
__key_it = std::lower_bound(__first, __last, __k, _M_comp);
}
if constexpr (!_Multi)
if (__key_it != _M_cont.keys.end() && !_M_comp(__k, __key_it[0]))
return {iterator{this, __key_it}, false};
auto __guard = _M_make_clear_guard();
__key_it = _M_cont.keys.insert(__key_it, std::move(__k));
__value_it = _M_cont.values.begin() + (__key_it - _M_cont.keys.begin());
_M_cont.values.emplace(__value_it, std::forward<_Args>(__args)...);
__guard._M_disable();
return {iterator{this, __key_it}, true};
}
template<typename... _Args>
requires is_constructible_v<value_type, _Args...>
_GLIBCXX26_CONSTEXPR
__emplace_result_t
emplace(_Args&&... __args)
{
value_type __p(std::forward<_Args>(__args)...);
auto __r = _M_try_emplace(nullopt, std::move(__p.first), std::move(__p.second));
if constexpr (_Multi)
return __r.first;
else
return __r;
}
template<typename... _Args>
_GLIBCXX26_CONSTEXPR
iterator
emplace_hint(const_iterator __position, _Args&&... __args)
{
value_type __p(std::forward<_Args>(__args)...);
return _M_try_emplace(__position, std::move(__p.first), std::move(__p.second)).first;
}
_GLIBCXX26_CONSTEXPR
__emplace_result_t
insert(const value_type& __x)
{ return emplace(__x); }
_GLIBCXX26_CONSTEXPR
__emplace_result_t
insert(value_type&& __x)
{ return emplace(std::move(__x)); }
_GLIBCXX26_CONSTEXPR
iterator
insert(const_iterator __position, const value_type& __x)
{ return emplace_hint(__position, __x); }
_GLIBCXX26_CONSTEXPR
iterator
insert(const_iterator __position, value_type&& __x)
{ return emplace_hint(__position, std::move(__x)); }
template<typename _Arg>
requires is_constructible_v<value_type, _Arg>
_GLIBCXX26_CONSTEXPR
__emplace_result_t
insert(_Arg&& __x)
{ return emplace(std::forward<_Arg>(__x)); }
template<typename _Arg>
requires is_constructible_v<value_type, _Arg>
_GLIBCXX26_CONSTEXPR
iterator
insert(const_iterator __position, _Arg&& __x)
{ return emplace_hint(__position, std::forward<_Arg>(__x)); }
private:
template<typename _Iter, typename _Sent>
_GLIBCXX26_CONSTEXPR
void
_M_insert(_Iter __first, _Sent __last)
{
// FIXME: This implementation fails its complexity requirements.
// We can't idiomatically implement an efficient version (as in the
// disabled code) until ranges::inplace_merge is fixed to dispatch
// on iterator concept instead of iterator category.
#if 0
auto __guard = _M_make_clear_guard();
auto __n = size();
for (; __first != __last; ++__first)
{
value_type __value = *__first;
_M_cont.keys.emplace_back(std::move(__value.first));
_M_cont.values.emplace_back(std::move(__value.second));
}
auto __zv = views::zip(_M_cont.keys, _M_cont.values);
ranges::sort(__zv.begin() + __n, __zv.end(), value_comp());
ranges::inplace_merge(__zv.begin(), __zv.begin() + __n, __zv.end(), value_comp());
if constexpr (!_Multi)
_M_unique();
__guard._M_cont = nullptr;
#else
auto __guard = _M_make_clear_guard();
for (; __first != __last; ++__first)
{
value_type __value = *__first;
_M_cont.keys.emplace_back(std::move(__value.first));
_M_cont.values.emplace_back(std::move(__value.second));
}
_M_sort_uniq();
__guard._M_disable();
#endif
}
public:
template<__has_input_iter_cat _InputIterator>
_GLIBCXX26_CONSTEXPR
void
insert(_InputIterator __first, _InputIterator __last)
{ _M_insert(std::move(__first), std::move(__last)); }
template<__has_input_iter_cat _InputIterator>
_GLIBCXX26_CONSTEXPR
void
insert(__sorted_t, _InputIterator __first, _InputIterator __last)
{
// FIXME: This implementation fails its complexity requirements; see above.
insert(std::move(__first), std::move(__last));
}
template<__detail::__container_compatible_range<value_type> _Rg>
_GLIBCXX26_CONSTEXPR
void
insert_range(_Rg&& __rg)
{ _M_insert(ranges::begin(__rg), ranges::end(__rg)); }
_GLIBCXX26_CONSTEXPR
void
insert(initializer_list<value_type> __il)
{ insert(__il.begin(), __il.end()); }
_GLIBCXX26_CONSTEXPR
void
insert(__sorted_t __s, initializer_list<value_type> __il)
{ insert(__s, __il.begin(), __il.end()); }
_GLIBCXX26_CONSTEXPR
containers
extract() &&
{
auto __guard = _M_make_clear_guard();
return {std::move(_M_cont.keys), std::move(_M_cont.values)};
}
_GLIBCXX26_CONSTEXPR
void
replace(key_container_type&& __key_cont, mapped_container_type&& __mapped_cont)
{
__glibcxx_assert(__key_cont.size() == __mapped_cont.size());
_GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__key_cont, _M_comp));
auto __guard = _M_make_clear_guard();
_M_cont.keys = std::move(__key_cont);
_M_cont.values = std::move(__mapped_cont);
__guard._M_disable();
}
// try_emplace and insert_or_assign defined directly in class flat_map only.
_GLIBCXX26_CONSTEXPR
iterator
erase(iterator __position)
{ return erase(static_cast<const_iterator>(__position)); }
_GLIBCXX26_CONSTEXPR
iterator
erase(const_iterator __position)
{
auto __guard = _M_make_clear_guard();
auto __idx = __position._M_index;
auto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __idx);
_M_cont.values.erase(_M_cont.values.begin() + __idx);
__guard._M_disable();
return iterator{this, __it};
}
_GLIBCXX26_CONSTEXPR
size_type
erase(const key_type& __x)
{ return erase<const key_type&>(__x); }
template<typename _Key2>
requires same_as<remove_cvref_t<_Key2>, _Key>
|| (__transparent_comparator<_Compare>
&& !is_convertible_v<_Key2, iterator>
&& !is_convertible_v<_Key2, const_iterator>)
_GLIBCXX26_CONSTEXPR
size_type
erase(_Key2&& __x)
{
auto [__first, __last] = equal_range(std::forward<_Key2>(__x));
auto __n = __last - __first;
erase(__first, __last);
return __n;
}
_GLIBCXX26_CONSTEXPR
iterator
erase(const_iterator __first, const_iterator __last)
{
auto __guard = _M_make_clear_guard();
auto __it = _M_cont.keys.erase(_M_cont.keys.begin() + __first._M_index,
_M_cont.keys.begin() + __last._M_index);
_M_cont.values.erase(_M_cont.values.begin() + __first._M_index,
_M_cont.values.begin() + __last._M_index);
__guard._M_disable();
return iterator{this, __it};
}
_GLIBCXX26_CONSTEXPR
void
swap(_Derived& __y) noexcept
{
ranges::swap(_M_comp, __y._M_comp);
ranges::swap(_M_cont.keys, __y._M_cont.keys);
ranges::swap(_M_cont.values, __y._M_cont.values);
}
_GLIBCXX26_CONSTEXPR
void
clear() noexcept
{
_M_cont.keys.clear();
_M_cont.values.clear();
}
// observers
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
key_compare
key_comp() const
{ return _M_comp; }
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
value_compare
value_comp() const
{ return value_compare(_M_comp); }
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
const key_container_type&
keys() const noexcept
{ return _M_cont.keys; }
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
const mapped_container_type&
values() const noexcept
{ return _M_cont.values; }
// map operations
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
iterator
find(const key_type& __x)
{ return find<key_type>(__x); }
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
const_iterator
find(const key_type& __x) const
{ return find<key_type>(__x); }
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
iterator
find(const _Key2& __x)
{
auto __it = lower_bound(__x);
if (__it != end() && !_M_comp(__x, __it->first))
return __it;
else
return end();
}
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
const_iterator
find(const _Key2& __x) const
{
auto __it = lower_bound(__x);
if (__it != cend() && !_M_comp(__x, __it->first))
return __it;
else
return cend();
}
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
size_type
count(const key_type& __x) const
{ return count<key_type>(__x); }
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
size_type
count(const _Key2& __x) const
{
if constexpr (!_Multi)
return contains<_Key2>(__x);
else
{
auto [__first, __last] = equal_range(__x);
return __last - __first;
}
}
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
bool
contains(const key_type& __x) const
{ return contains<key_type>(__x); }
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
bool
contains(const _Key2& __x) const
{ return find(__x) != cend(); }
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
iterator
lower_bound(const key_type& __x)
{ return lower_bound<key_type>(__x); }
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
const_iterator
lower_bound(const key_type& __x) const
{ return lower_bound<key_type>(__x); }
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
iterator
lower_bound(const _Key2& __x)
{
auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
__x, _M_comp);
return {this, __it};
}
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
const_iterator
lower_bound(const _Key2& __x) const
{
auto __it = std::lower_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
__x, _M_comp);
return {this, __it};
}
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
iterator
upper_bound(const key_type& __x)
{ return upper_bound<key_type>(__x); }
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
const_iterator
upper_bound(const key_type& __x) const
{ return upper_bound<key_type>(__x); }
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
iterator
upper_bound(const _Key2& __x)
{
auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
__x, _M_comp);
return {this, __it};
}
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
const_iterator
upper_bound(const _Key2& __x) const
{
auto __it = std::upper_bound(_M_cont.keys.begin(), _M_cont.keys.end(),
__x, _M_comp);
return {this, __it};
}
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
pair<iterator, iterator>
equal_range(const key_type& __x)
{ return equal_range<key_type>(__x); }
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
pair<const_iterator, const_iterator>
equal_range(const key_type& __x) const
{ return equal_range<key_type>(__x); }
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
pair<iterator, iterator>
equal_range(const _Key2& __x)
{
auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),
_M_cont.keys.end(),
__x, _M_comp);
return {{this, __first}, {this, __last}};
}
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
[[nodiscard]]
_GLIBCXX26_CONSTEXPR
pair<const_iterator, const_iterator>
equal_range(const _Key2& __x) const
{
auto [__first, __last] = std::equal_range(_M_cont.keys.begin(),
_M_cont.keys.end(),
__x, _M_comp);
return {{this, __first}, {this, __last}};
}
[[nodiscard]]
friend _GLIBCXX26_CONSTEXPR bool
operator==(const _Derived& __x, const _Derived& __y)
{
return __x._M_cont.keys == __y._M_cont.keys
&& __x._M_cont.values == __y._M_cont.values;
}
template<typename _Up = value_type>
[[nodiscard]]
friend _GLIBCXX26_CONSTEXPR __detail::__synth3way_t<_Up>
operator<=>(const _Derived& __x, const _Derived& __y)
{
return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
__y.begin(), __y.end(),
__detail::__synth3way);
}
friend _GLIBCXX26_CONSTEXPR void
swap(_Derived& __x, _Derived& __y) noexcept
{ return __x.swap(__y); }
template<typename _Predicate>
_GLIBCXX26_CONSTEXPR
size_type
_M_erase_if(_Predicate __pred)
{
auto __guard = _M_make_clear_guard();
auto __zv = views::zip(_M_cont.keys, _M_cont.values);
auto __sr = ranges::remove_if(__zv, __pred,
[](const auto& __e) {
return const_reference(__e);
});
auto __erased = __sr.size();
erase(end() - __erased, end());
__guard._M_disable();
return __erased;
}
private:
containers _M_cont;
[[no_unique_address]] _Compare _M_comp;
_GLIBCXX26_CONSTEXPR
void
_M_sort_uniq()
{
auto __zv = views::zip(_M_cont.keys, _M_cont.values);
ranges::sort(__zv, value_comp());
if constexpr (!_Multi)
_M_unique();
}
_GLIBCXX26_CONSTEXPR
void
_M_unique() requires (!_Multi)
{
struct __key_equiv
{
_GLIBCXX26_CONSTEXPR
__key_equiv(key_compare __c) : _M_comp(__c) { }
_GLIBCXX26_CONSTEXPR
bool
operator()(const_reference __x, const_reference __y) const
{ return !_M_comp(__x.first, __y.first) && !_M_comp(__y.first, __x.first); }
[[no_unique_address]] key_compare _M_comp;
};
auto __zv = views::zip(_M_cont.keys, _M_cont.values);
auto __it = ranges::unique(__zv, __key_equiv(_M_comp)).begin();
auto __n = __it - __zv.begin();
_M_cont.keys.erase(_M_cont.keys.begin() + __n, _M_cont.keys.end());
_M_cont.values.erase(_M_cont.values.begin() + __n, _M_cont.values.end());
}
};
template<typename _Key, typename _Tp, typename _Compare,
typename _KeyContainer, typename _MappedContainer, bool _Multi>
template<bool _Const>
class _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, _Multi>::_Iterator
{
using __size_type = typename _Flat_map_impl::size_type;
public:
using iterator_category = input_iterator_tag;
using iterator_concept = random_access_iterator_tag;
using value_type = pair<key_type, mapped_type>;
using reference = pair<const key_type&,
ranges::__maybe_const_t<_Const, mapped_type>&>;
using difference_type = ptrdiff_t;
_GLIBCXX26_CONSTEXPR
_Iterator() = default;
_GLIBCXX26_CONSTEXPR
_Iterator(_Iterator<!_Const> __it) requires _Const
: _M_cont(__it._M_cont), _M_index(__it._M_index)
{ }
_GLIBCXX26_CONSTEXPR
reference
operator*() const noexcept
{
__glibcxx_assert(_M_index < _M_cont->keys.size());
return {_M_cont->keys[_M_index], _M_cont->values[_M_index]};
}
struct pointer
{
reference __p;
_GLIBCXX26_CONSTEXPR
const reference*
operator->() const noexcept
{ return std::__addressof(__p); }
};
_GLIBCXX26_CONSTEXPR
pointer
operator->() const
{ return pointer{operator*()}; }
_GLIBCXX26_CONSTEXPR
reference
operator[](difference_type __n) const noexcept
{ return *(*this + __n); }
_GLIBCXX26_CONSTEXPR
_Iterator&
operator++() noexcept
{
++_M_index;
return *this;
}
_GLIBCXX26_CONSTEXPR
_Iterator&
operator--() noexcept
{
--_M_index;
return *this;
}
_GLIBCXX26_CONSTEXPR
_Iterator
operator++(int) noexcept
{
auto __tmp = *this;
++*this;
return __tmp;
}
_GLIBCXX26_CONSTEXPR
_Iterator
operator--(int) noexcept
{
auto __tmp = *this;
--*this;
return __tmp;
}
_GLIBCXX26_CONSTEXPR
_Iterator&
operator+=(difference_type __n) noexcept
{
_M_index += __n;
return *this;
}
_GLIBCXX26_CONSTEXPR
_Iterator&
operator-=(difference_type __n) noexcept
{
_M_index -= __n;
return *this;
}
private:
friend _Flat_map_impl;
friend _Iterator<!_Const>;
_GLIBCXX26_CONSTEXPR
_Iterator(_Flat_map_impl* __fm, typename key_container_type::const_iterator __it)
requires (!_Const)
: _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin())
{ }
_GLIBCXX26_CONSTEXPR
_Iterator(const _Flat_map_impl* __fm, typename key_container_type::const_iterator __it)
requires _Const
: _M_cont(std::__addressof(__fm->_M_cont)), _M_index(__it - __fm->keys().cbegin())
{ }
friend _GLIBCXX26_CONSTEXPR _Iterator
operator+(_Iterator __it, difference_type __n) noexcept
{
__it += __n;
return __it;
}
friend _GLIBCXX26_CONSTEXPR _Iterator
operator+(difference_type __n, _Iterator __it) noexcept
{
__it += __n;
return __it;
}
friend _GLIBCXX26_CONSTEXPR _Iterator
operator-(_Iterator __it, difference_type __n) noexcept
{
__it -= __n;
return __it;
}
friend _GLIBCXX26_CONSTEXPR difference_type
operator-(const _Iterator& __x, const _Iterator& __y) noexcept
{
__glibcxx_assert(__x._M_cont == __y._M_cont);
return __x._M_index - __y._M_index;
}
friend _GLIBCXX26_CONSTEXPR bool
operator==(const _Iterator& __x, const _Iterator& __y) noexcept
{
__glibcxx_assert(__x._M_cont == __y._M_cont);
__glibcxx_assert((__x._M_index == size_t(-1)) == (__y._M_index == size_t(-1)));
return __x._M_index == __y._M_index;
}
friend _GLIBCXX26_CONSTEXPR strong_ordering
operator<=>(const _Iterator& __x, const _Iterator& __y)
{
__glibcxx_assert(__x._M_cont == __y._M_cont);
__glibcxx_assert((__x._M_index == size_t(-1)) == (__y._M_index == size_t(-1)));
return __x._M_index <=> __y._M_index;
}
ranges::__maybe_const_t<_Const, containers>* _M_cont = nullptr;
__size_type _M_index = -1;
};
/* Class template flat_map - container adaptor
*
* @ingroup
*/
template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
typename _KeyContainer = vector<_Key>,
typename _MappedContainer = vector<_Tp>>
class flat_map
: private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>
{
using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, false>;
friend _Impl;
public:
// types
using typename _Impl::key_type;
using typename _Impl::mapped_type;
using typename _Impl::value_type;
using typename _Impl::key_compare;
using typename _Impl::reference;
using typename _Impl::const_reference;
using typename _Impl::size_type;
using typename _Impl::difference_type;
using typename _Impl::iterator;
using typename _Impl::const_iterator;
using typename _Impl::reverse_iterator;
using typename _Impl::const_reverse_iterator;
using typename _Impl::key_container_type;
using typename _Impl::mapped_container_type;
using typename _Impl::value_compare;
using typename _Impl::containers;
// constructors
using _Impl::_Impl;
// iterators
using _Impl::begin;
using _Impl::end;
using _Impl::rbegin;
using _Impl::rend;
using _Impl::cbegin;
using _Impl::cend;
using _Impl::crbegin;
using _Impl::crend;
// capacity
using _Impl::empty;
using _Impl::size;
using _Impl::max_size;
// element access
_GLIBCXX26_CONSTEXPR
mapped_type&
operator[](const key_type& __x)
{ return try_emplace(__x).first->second; }
_GLIBCXX26_CONSTEXPR
mapped_type&
operator[](key_type&& __x)
{ return try_emplace(std::move(__x)).first->second; }
template<typename _Key2>
requires __transparent_comparator<_Compare>
_GLIBCXX26_CONSTEXPR
mapped_type&
operator[](_Key2&& __x)
{ return try_emplace(std::forward<_Key2>(__x)).first->second; }
_GLIBCXX26_CONSTEXPR
mapped_type&
at(const key_type& __x)
{ return at<key_type>(__x); }
_GLIBCXX26_CONSTEXPR
const mapped_type&
at(const key_type& __x) const
{ return at<key_type>(__x); }
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
_GLIBCXX26_CONSTEXPR
mapped_type&
at(const _Key2& __x)
{
auto __it = this->find(__x);
if (__it == this->end())
__throw_out_of_range("flat_map::at");
return __it->second;
}
template<typename _Key2>
requires same_as<_Key2, _Key> || __transparent_comparator<_Compare>
_GLIBCXX26_CONSTEXPR
const mapped_type&
at(const _Key2& __x) const
{
auto __it = this->find(__x);
if (__it == this->end())
__throw_out_of_range("flat_map::at");
return __it->second;
}
// modifiers
using _Impl::emplace;
using _Impl::emplace_hint;
using _Impl::insert;
using _Impl::insert_range;
using _Impl::extract;
using _Impl::replace;
using _Impl::erase;
using _Impl::swap;
using _Impl::clear;
template<typename... _Args>
requires is_constructible_v<mapped_type, _Args...>
_GLIBCXX26_CONSTEXPR
pair<iterator, bool>
try_emplace(const key_type& __k, _Args&&... __args)
{ return _Impl::_M_try_emplace(nullopt, __k, std::forward<_Args>(__args)...); }
template<typename... _Args>
requires is_constructible_v<mapped_type, _Args...>
_GLIBCXX26_CONSTEXPR
pair<iterator, bool>
try_emplace(key_type&& __k, _Args&&... __args)
{
return _Impl::_M_try_emplace(nullopt, std::move(__k),
std::forward<_Args>(__args)...);
}
template<typename _Key2, typename... _Args>
requires __transparent_comparator<_Compare>
&& is_constructible_v<key_type, _Key2>
&& is_constructible_v<mapped_type, _Args...>
&& (!is_convertible_v<_Key2&&, const_iterator>)
&& (!is_convertible_v<_Key2&&, iterator>)
_GLIBCXX26_CONSTEXPR
pair<iterator, bool>
try_emplace(_Key2&& __k, _Args&&... __args)
{
return _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k),
std::forward<_Args>(__args)...);
}
template<typename... _Args>
requires is_constructible_v<mapped_type, _Args...>
_GLIBCXX26_CONSTEXPR
iterator
try_emplace(const_iterator __hint, const key_type& __k, _Args&&... __args)
{ return _Impl::_M_try_emplace(__hint, __k, std::forward<_Args>(__args)...).first; }
template<typename... _Args>
requires is_constructible_v<mapped_type, _Args...>
_GLIBCXX26_CONSTEXPR
iterator
try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
{
return _Impl::_M_try_emplace(__hint, std::move(__k),
std::forward<_Args>(__args)...).first;
}
template<typename _Key2, typename... _Args>
requires __transparent_comparator<_Compare>
&& is_constructible_v<key_type, _Key2>
&& is_constructible_v<mapped_type, _Args...>
_GLIBCXX26_CONSTEXPR
iterator
try_emplace(const_iterator __hint, _Key2&& __k, _Args&&... __args)
{
return _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k),
std::forward<_Args>(__args)...).first;
}
template<typename _Mapped>
requires is_assignable_v<mapped_type&, _Mapped>
&& is_constructible_v<mapped_type, _Mapped>
_GLIBCXX26_CONSTEXPR
pair<iterator, bool>
insert_or_assign(const key_type& __k, _Mapped&& __obj)
{ return insert_or_assign<const key_type&, _Mapped>(__k, std::forward<_Mapped>(__obj)); }
template<typename _Mapped>
requires is_assignable_v<mapped_type&, _Mapped>
&& is_constructible_v<mapped_type, _Mapped>
_GLIBCXX26_CONSTEXPR
pair<iterator, bool>
insert_or_assign(key_type&& __k, _Mapped&& __obj)
{
return insert_or_assign<key_type, _Mapped>(std::move(__k),
std::forward<_Mapped>(__obj));
}
template<typename _Key2, typename _Mapped>
requires (same_as<remove_cvref_t<_Key2>, _Key> || __transparent_comparator<_Compare>)
&& is_constructible_v<key_type, _Key2>
&& is_assignable_v<mapped_type&, _Mapped>
&& is_constructible_v<mapped_type, _Mapped>
_GLIBCXX26_CONSTEXPR
pair<iterator, bool>
insert_or_assign(_Key2&& __k, _Mapped&& __obj)
{
auto __r = _Impl::_M_try_emplace(nullopt, std::forward<_Key2>(__k),
std::forward<_Mapped>(__obj));
if (!__r.second)
__r.first->second = std::forward<_Mapped>(__obj);
return __r;
}
template<typename _Mapped>
requires is_assignable_v<mapped_type&, _Mapped>
&& is_constructible_v<mapped_type, _Mapped>
_GLIBCXX26_CONSTEXPR
iterator
insert_or_assign(const_iterator __hint, const key_type& __k, _Mapped&& __obj)
{
return insert_or_assign<const key_type&, _Mapped>(__hint, __k,
std::forward<_Mapped>(__obj));
}
template<typename _Mapped>
requires is_assignable_v<mapped_type&, _Mapped>
&& is_constructible_v<mapped_type, _Mapped>
_GLIBCXX26_CONSTEXPR
iterator
insert_or_assign(const_iterator __hint, key_type&& __k, _Mapped&& __obj)
{
return insert_or_assign<key_type, _Mapped>(__hint, std::move(__k),
std::forward<_Mapped>(__obj));
}
template<typename _Key2, typename _Mapped>
requires (same_as<remove_cvref_t<_Key2>, _Key> || __transparent_comparator<_Compare>)
&& is_constructible_v<key_type, _Key2>
&& is_assignable_v<mapped_type&, _Mapped>
&& is_constructible_v<mapped_type, _Mapped>
_GLIBCXX26_CONSTEXPR
iterator
insert_or_assign(const_iterator __hint, _Key2&& __k, _Mapped&& __obj)
{
auto __r = _Impl::_M_try_emplace(__hint, std::forward<_Key2>(__k),
std::forward<_Mapped>(__obj));
if (!__r.second)
__r.first->second = std::forward<_Mapped>(__obj);
return __r.first;
}
// observers
using _Impl::key_comp;
using _Impl::value_comp;
using _Impl::keys;
using _Impl::values;
// map operations
using _Impl::find;
using _Impl::count;
using _Impl::contains;
using _Impl::lower_bound;
using _Impl::upper_bound;
using _Impl::equal_range;
using _Impl::_M_erase_if;
};
template<typename _KeyContainer, typename _MappedContainer,
__not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
flat_map(_KeyContainer, _MappedContainer, _Compare = _Compare())
-> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
_Compare, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer,
__allocator_for<_KeyContainer, _MappedContainer> _Alloc>
flat_map(_KeyContainer, _MappedContainer, _Alloc)
-> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,
__allocator_for<_KeyContainer, _MappedContainer> _Alloc>
flat_map(_KeyContainer, _MappedContainer, _Compare, _Alloc)
-> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
_Compare, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer,
__not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
-> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
_Compare, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer,
__allocator_for<_KeyContainer, _MappedContainer> _Alloc>
flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Alloc)
-> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,
__allocator_for<_KeyContainer, _MappedContainer> _Alloc>
flat_map(sorted_unique_t, _KeyContainer, _MappedContainer, _Compare, _Alloc)
-> flat_map<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
_Compare, _KeyContainer, _MappedContainer>;
template<__has_input_iter_cat _InputIterator,
__not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
flat_map(_InputIterator, _InputIterator, _Compare = _Compare())
-> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
template<__has_input_iter_cat _InputIterator,
__not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
flat_map(sorted_unique_t, _InputIterator, _InputIterator, _Compare = _Compare())
-> flat_map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
template<ranges::input_range _Rg,
__not_allocator_like _Compare = less<__detail::__range_key_type<_Rg>>,
__allocator_like _Alloc = allocator<byte>>
flat_map(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
-> flat_map<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
_Compare,
vector<__detail::__range_key_type<_Rg>,
__alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
vector<__detail::__range_mapped_type<_Rg>,
__alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
template<ranges::input_range _Rg, __allocator_like _Alloc>
flat_map(from_range_t, _Rg&&, _Alloc)
-> flat_map<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
less<__detail::__range_key_type<_Rg>>,
vector<__detail::__range_key_type<_Rg>,
__alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
vector<__detail::__range_mapped_type<_Rg>,
__alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>
flat_map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
-> flat_map<_Key, _Tp, _Compare>;
template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>
flat_map(sorted_unique_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
-> flat_map<_Key, _Tp, _Compare>;
template<typename _Key, typename _Tp, typename _Compare,
typename _KeyContainer, typename _MappedContainer, typename _Alloc>
struct uses_allocator<flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>, _Alloc>
: bool_constant<uses_allocator_v<_KeyContainer, _Alloc>
&& uses_allocator_v<_MappedContainer, _Alloc>>
{ };
template<typename _Key, typename _Tp, typename _Compare,
typename _KeyContainer, typename _MappedContainer, typename _Predicate>
_GLIBCXX26_CONSTEXPR
typename flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
erase_if(flat_map<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __c,
_Predicate __pred)
{ return __c._M_erase_if(std::move(__pred)); }
/* Class template flat_multimap - container adaptor
*
* @ingroup
*/
template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
typename _KeyContainer = vector<_Key>,
typename _MappedContainer = vector<_Tp>>
class flat_multimap
: private _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>
{
using _Impl = _Flat_map_impl<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer, true>;
friend _Impl;
public:
// types
using typename _Impl::key_type;
using typename _Impl::mapped_type;
using typename _Impl::value_type;
using typename _Impl::key_compare;
using typename _Impl::reference;
using typename _Impl::const_reference;
using typename _Impl::size_type;
using typename _Impl::difference_type;
using typename _Impl::iterator;
using typename _Impl::const_iterator;
using typename _Impl::reverse_iterator;
using typename _Impl::const_reverse_iterator;
using typename _Impl::key_container_type;
using typename _Impl::mapped_container_type;
using typename _Impl::value_compare;
using typename _Impl::containers;
// constructors
using _Impl::_Impl;
// iterators
using _Impl::begin;
using _Impl::end;
using _Impl::rbegin;
using _Impl::rend;
using _Impl::cbegin;
using _Impl::cend;
using _Impl::crbegin;
using _Impl::crend;
// capacity
using _Impl::empty;
using _Impl::size;
using _Impl::max_size;
// modifiers
using _Impl::emplace;
using _Impl::emplace_hint;
using _Impl::insert;
using _Impl::insert_range;
using _Impl::extract;
using _Impl::replace;
using _Impl::erase;
using _Impl::swap;
using _Impl::clear;
// observers
using _Impl::key_comp;
using _Impl::value_comp;
using _Impl::keys;
using _Impl::values;
// map operations
using _Impl::find;
using _Impl::count;
using _Impl::contains;
using _Impl::lower_bound;
using _Impl::upper_bound;
using _Impl::equal_range;
using _Impl::_M_erase_if;
};
template<typename _KeyContainer, typename _MappedContainer,
__not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
flat_multimap(_KeyContainer, _MappedContainer, _Compare = _Compare())
-> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
_Compare, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer,
__allocator_for<_KeyContainer, _MappedContainer> _Alloc>
flat_multimap(_KeyContainer, _MappedContainer, _Alloc)
-> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,
__allocator_for<_KeyContainer, _MappedContainer> _Alloc>
flat_multimap(_KeyContainer, _MappedContainer, _Compare, _Alloc)
-> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
_Compare, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer,
__not_allocator_like _Compare = less<typename _KeyContainer::value_type>>
flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare = _Compare())
-> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
_Compare, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer,
__allocator_for<_KeyContainer, _MappedContainer> _Alloc>
flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Alloc)
-> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
less<typename _KeyContainer::value_type>, _KeyContainer, _MappedContainer>;
template<typename _KeyContainer, typename _MappedContainer, __not_allocator_like _Compare,
__allocator_for<_KeyContainer, _MappedContainer> _Alloc>
flat_multimap(sorted_equivalent_t, _KeyContainer, _MappedContainer, _Compare, _Alloc)
-> flat_multimap<typename _KeyContainer::value_type, typename _MappedContainer::value_type,
_Compare, _KeyContainer, _MappedContainer>;
template<__has_input_iter_cat _InputIterator,
__not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
flat_multimap(_InputIterator, _InputIterator, _Compare = _Compare())
-> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
template<__has_input_iter_cat _InputIterator,
__not_allocator_like _Compare = less<__iter_key_t<_InputIterator>>>
flat_multimap(sorted_equivalent_t, _InputIterator, _InputIterator, _Compare = _Compare())
-> flat_multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, _Compare>;
template<ranges::input_range _Rg,
__not_allocator_like _Compare = less<__detail::__range_key_type<_Rg>>,
__allocator_like _Alloc = allocator<byte>>
flat_multimap(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
-> flat_multimap<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
_Compare,
vector<__detail::__range_key_type<_Rg>,
__alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
vector<__detail::__range_mapped_type<_Rg>,
__alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
template<ranges::input_range _Rg, __allocator_like _Alloc>
flat_multimap(from_range_t, _Rg&&, _Alloc)
-> flat_multimap<__detail::__range_key_type<_Rg>, __detail::__range_mapped_type<_Rg>,
less<__detail::__range_key_type<_Rg>>,
vector<__detail::__range_key_type<_Rg>,
__alloc_rebind<_Alloc, __detail::__range_key_type<_Rg>>>,
vector<__detail::__range_mapped_type<_Rg>,
__alloc_rebind<_Alloc, __detail::__range_mapped_type<_Rg>>>>;
template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>
flat_multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
-> flat_multimap<_Key, _Tp, _Compare>;
template<typename _Key, typename _Tp, __not_allocator_like _Compare = less<_Key>>
flat_multimap(sorted_equivalent_t, initializer_list<pair<_Key, _Tp>>, _Compare = _Compare())
-> flat_multimap<_Key, _Tp, _Compare>;
template<typename _Key, typename _Tp, typename _Compare,
typename _KeyContainer, typename _MappedContainer, typename _Alloc>
struct uses_allocator<flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>,
_Alloc>
: bool_constant<uses_allocator_v<_KeyContainer, _Alloc>
&& uses_allocator_v<_MappedContainer, _Alloc>>
{ };
template<typename _Key, typename _Tp, typename _Compare,
typename _KeyContainer, typename _MappedContainer, typename _Predicate>
_GLIBCXX26_CONSTEXPR
typename flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>::size_type
erase_if(flat_multimap<_Key, _Tp, _Compare, _KeyContainer, _MappedContainer>& __c,
_Predicate __pred)
{ return __c._M_erase_if(std::move(__pred)); }
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#endif // __cpp_lib_flat_map
#endif // _GLIBCXX_FLAT_MAP
Reference in New Issue View Git Blame Copy Permalink