On Fri, 31 Jan 2025 at 18:29, Patrick Palka <ppa...@redhat.com> wrote:
>
> This fixes flat_map/multimap::insert_range by simply generalizing the
> ::insert implementation to handle heterogenous iterator/sentinel pair.
> I'm not sure we can do better than this, e.g. we can't implement it
> in terms of the adapted containers' insert_range because that'd require
> two passes over the range.
>
> For flat_set/multiset, we can implement insert_range directly in terms
> of the adapted container's insert_range. A fallback implementation
> is also provided if insert_range isn't available, as is the case for
> std::deque currently.
Looks good. OK for trunk, thanks.
>
> PR libstdc++/118156
>
> libstdc++-v3/ChangeLog:
>
> * include/std/flat_map (_Flat_map_impl::_M_insert): Generalized
> version of insert taking heterogenous iterator/sentinel pair.
> (_Flat_map_impl::insert): Dispatch to _M_insert.
> (_Flat_map_impl::insert_range): Likewise.
> (flat_map): Export _Flat_map_impl::insert_range.
> (flat_multimap): Likewise.
> * include/std/flat_set (_Flat_set_impl::insert_range):
> Reimplement directly, not in terms of insert.
> (flat_set): Export _Flat_set_impl::insert_range.
> (flat_multiset): Likewise.
> * testsuite/23_containers/flat_map/1.cc (test06): New test.
> * testsuite/23_containers/flat_multimap/1.cc (test06): New test.
> * testsuite/23_containers/flat_multiset/1.cc (test06): New test.
> * testsuite/23_containers/flat_set/1.cc (test06): New test.
> ---
> libstdc++-v3/include/std/flat_map | 17 +++++++++----
> libstdc++-v3/include/std/flat_set | 25 ++++++++++++++++---
> .../testsuite/23_containers/flat_map/1.cc | 17 +++++++++++++
> .../23_containers/flat_multimap/1.cc | 16 ++++++++++++
> .../23_containers/flat_multiset/1.cc | 16 ++++++++++++
> .../testsuite/23_containers/flat_set/1.cc | 16 ++++++++++++
> 6 files changed, 99 insertions(+), 8 deletions(-)
>
> diff --git a/libstdc++-v3/include/std/flat_map
> b/libstdc++-v3/include/std/flat_map
> index 1ecc2e7f6e7..405caa8a81b 100644
> --- a/libstdc++-v3/include/std/flat_map
> +++ b/libstdc++-v3/include/std/flat_map
> @@ -538,9 +538,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> insert(const_iterator __position, _Arg&& __x)
> { return emplace_hint(__position, std::forward<_Arg>(__x)); }
>
> - template<__has_input_iter_cat _InputIterator>
> + private:
> + template<typename _Iter, typename _Sent>
> void
> - insert(_InputIterator __first, _InputIterator __last)
> + _M_insert(_Iter __first, _Sent __last)
> {
> // FIXME: This implementation fails its complexity requirements.
> // We can't idiomatically implement an efficient version (as in the
> @@ -574,6 +575,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> #endif
> }
>
> + public:
> + template<__has_input_iter_cat _InputIterator>
> + void
> + insert(_InputIterator __first, _InputIterator __last)
> + { _M_insert(std::move(__first), std::move(__last)); }
> +
> template<__has_input_iter_cat _InputIterator>
> void
> insert(__sorted_t, _InputIterator __first, _InputIterator __last)
> @@ -585,7 +592,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> template<__detail::__container_compatible_range<value_type> _Rg>
> void
> insert_range(_Rg&& __rg)
> - { insert(ranges::begin(__rg), ranges::end(__rg)); }
> + { _M_insert(ranges::begin(__rg), ranges::end(__rg)); }
>
> void
> insert(initializer_list<value_type> __il)
> @@ -1181,7 +1188,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> using _Impl::emplace;
> using _Impl::emplace_hint;
> using _Impl::insert;
> - // using _Impl::insert_range;
> + using _Impl::insert_range;
> using _Impl::extract;
> using _Impl::replace;
> using _Impl::erase;
> @@ -1460,7 +1467,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> using _Impl::emplace;
> using _Impl::emplace_hint;
> using _Impl::insert;
> - // using _Impl::insert_range;
> + using _Impl::insert_range;
> using _Impl::extract;
> using _Impl::replace;
> using _Impl::erase;
> diff --git a/libstdc++-v3/include/std/flat_set
> b/libstdc++-v3/include/std/flat_set
> index 3e1347a6a0a..c7b48e5d2a7 100644
> --- a/libstdc++-v3/include/std/flat_set
> +++ b/libstdc++-v3/include/std/flat_set
> @@ -475,7 +475,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> template<__detail::__container_compatible_range<value_type> _Rg>
> void
> insert_range(_Rg&& __rg)
> - { insert(ranges::begin(__rg), ranges::end(__rg)); }
> + {
> + auto __guard = _M_make_clear_guard();
> + typename container_type::iterator __it;
> + if constexpr (requires { _M_cont.insert_range(_M_cont.end(), __rg);
> })
> + __it = _M_cont.insert_range(_M_cont.end(), __rg);
> + else
> + {
> + size_type __n = size();
> + auto __first = ranges::begin(__rg);
> + auto __last = ranges::end(__rg);
> + for (; __first != __last; ++__first)
> + _M_cont.emplace_back(*__first);
> + __it = _M_cont.begin() + __n;
> + }
> + std::sort(__it, _M_cont.end(), _M_comp);
> + std::inplace_merge(_M_cont.begin(), __it, _M_cont.end(), _M_comp);
> + if constexpr (!_Multi)
> + _M_unique();
> + __guard._M_disable();
> + }
>
> void
> insert(initializer_list<value_type> __il)
> @@ -808,7 +827,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> using _Impl::emplace;
> using _Impl::emplace_hint;
> using _Impl::insert;
> - // using _Impl::insert_range;
> + using _Impl::insert_range;
> using _Impl::extract;
> using _Impl::replace;
> using _Impl::erase;
> @@ -947,7 +966,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> using _Impl::emplace;
> using _Impl::emplace_hint;
> using _Impl::insert;
> - // using _Impl::insert_range;
> + using _Impl::insert_range;
> using _Impl::extract;
> using _Impl::replace;
> using _Impl::erase;
> diff --git a/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
> b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
> index 111cafaa6ba..00254dc2ee6 100644
> --- a/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
> +++ b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
> @@ -164,6 +164,22 @@ test05()
> VERIFY( std::ranges::equal(m | std::views::values, (int[]){-1, -2, -3, -4,
> -5}) );
> }
>
> +void
> +test06()
> +{
> + // PR libstdc++/118156 - flat_foo::insert_range cannot handle non-common
> ranges
> + std::flat_map<int, int> m;
> + auto r = std::views::zip(std::views::iota(1), std::views::iota(2)) |
> std::views::take(5);
> + static_assert(!std::ranges::common_range<decltype(r)>);
> + m.insert_range(r);
> + VERIFY( std::ranges::equal(m | std::views::keys, (int[]){1, 2, 3, 4, 5}) );
> + VERIFY( std::ranges::equal(m | std::views::values, (int[]){2, 3, 4, 5, 6})
> );
> + m.clear();
> + m.insert_range(r | std::views::reverse);
> + VERIFY( std::ranges::equal(m | std::views::keys, (int[]){1, 2, 3, 4, 5}) );
> + VERIFY( std::ranges::equal(m | std::views::values, (int[]){2, 3, 4, 5, 6})
> );
> +}
> +
> int
> main()
> {
> @@ -175,4 +191,5 @@ main()
> test03();
> test04();
> test05();
> + test06();
> }
> diff --git a/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc
> b/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc
> index 08f4bbc38fd..38650a81bcf 100644
> --- a/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc
> +++ b/libstdc++-v3/testsuite/23_containers/flat_multimap/1.cc
> @@ -138,6 +138,21 @@ test05()
> VERIFY( std::ranges::equal(m | std::views::keys, (int[]){1, 2, 3, 3, 4,
> 5}) );
> VERIFY( std::ranges::equal(m | std::views::values, (int[]){-1, -2, -3, 3,
> -4, -5}) );
> }
> +void
> +test06()
> +{
> + // PR libstdc++/118156 - flat_foo::insert_range cannot handle non-common
> ranges
> + std::flat_multimap<int, int> m;
> + auto r = std::views::zip(std::views::iota(1), std::views::iota(2)) |
> std::views::take(5);
> + static_assert(!std::ranges::common_range<decltype(r)>);
> + m.insert_range(r);
> + VERIFY( std::ranges::equal(m | std::views::keys, (int[]){1, 2, 3, 4, 5}) );
> + VERIFY( std::ranges::equal(m | std::views::values, (int[]){2, 3, 4, 5, 6})
> );
> + m.clear();
> + m.insert_range(r | std::views::reverse);
> + VERIFY( std::ranges::equal(m | std::views::keys, (int[]){1, 2, 3, 4, 5}) );
> + VERIFY( std::ranges::equal(m | std::views::values, (int[]){2, 3, 4, 5, 6})
> );
> +}
>
> int
> main()
> @@ -150,4 +165,5 @@ main()
> test03();
> test04();
> test05();
> + test06();
> }
> diff --git a/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> index 82958f7939b..910f5dca5be 100644
> --- a/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> +++ b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> @@ -2,6 +2,7 @@
>
> #include <flat_set>
> #include <deque>
> +#include <ranges>
> #include <vector>
> #include <testsuite_allocator.h>
> #include <testsuite_hooks.h>
> @@ -128,6 +129,20 @@ test05()
> VERIFY( std::ranges::equal(m, (int[]){1, 2, 3, 3, 4, 5}) );
> }
>
> +void
> +test06()
> +{
> + // PR libstdc++/118156 - flat_foo::insert_range cannot handle non-common
> ranges
> + std::flat_multiset<int> s;
> + auto r = std::views::iota(1) | std::views::take(5);
> + static_assert(!std::ranges::common_range<decltype(r)>);
> + s.insert_range(r);
> + VERIFY( std::ranges::equal(s, (int[]){1, 2, 3, 4, 5}) );
> + s.clear();
> + s.insert_range(r | std::views::reverse);
> + VERIFY( std::ranges::equal(s, (int[]){1, 2, 3, 4, 5}) );
> +}
> +
> int
> main()
> {
> @@ -137,4 +152,5 @@ main()
> test03();
> test04();
> test05();
> + test06();
> }
> diff --git a/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> index 325b1263aa3..f0eaac936bf 100644
> --- a/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> +++ b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> @@ -7,6 +7,7 @@
> #endif
>
> #include <deque>
> +#include <ranges>
> #include <vector>
> #include <testsuite_allocator.h>
> #include <testsuite_hooks.h>
> @@ -143,6 +144,20 @@ test05()
> VERIFY( std::ranges::equal(m, (int[]){1, 2, 3, 4, 5}) );
> }
>
> +void
> +test06()
> +{
> + // PR libstdc++/118156 - flat_foo::insert_range cannot handle non-common
> ranges
> + std::flat_set<int> s;
> + auto r = std::views::iota(1) | std::views::take(5);
> + static_assert(!std::ranges::common_range<decltype(r)>);
> + s.insert_range(r);
> + VERIFY( std::ranges::equal(s, (int[]){1, 2, 3, 4, 5}) );
> + s.clear();
> + s.insert_range(r | std::views::reverse);
> + VERIFY( std::ranges::equal(s, (int[]){1, 2, 3, 4, 5}) );
> +}
> +
> int
> main()
> {
> @@ -152,4 +167,5 @@ main()
> test03();
> test04();
> test05();
> + test06();
> }
> --
> 2.48.1.157.g3b0d05c4a7
>
