I have fixed missing <algorithm> headers locally.
And also added include <bits/ranges_base.h> to multiset.
On Fri, Mar 14, 2025 at 8:54 AM Tomasz Kamiński <tkami...@redhat.com> wrote:
> This is another piece of P1206R7, adding new members to std::set
> and std::multiset.
>
> PR libstdc++/111055
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/stl_multiset.h: (inser_range)
> (multiset(from_range_t, _Rg&&, const _Compare&, const _Alloc&))
> (multiset(from_range_t, _Rg&&, const _Alloc&)): Define.
> * include/bits/stl_set.h: (set(from_range_t, _Rg&&, const _Alloc&))
> (set(from_range_t, _Rg&&, const _Compare&, const _Alloc&),
> insert_range):
> Define.
> * testsuite/23_containers/multiset/cons/from_range.cc: New test.
> *
> testsuite/23_containers/multiset/modifiers/insert/insert_range.cc: New test.
> * testsuite/23_containers/set/cons/from_range.cc: New test.
> * testsuite/23_containers/set/modifiers/insert/insert_range.cc:
> New test.
> ---
> Test on x86_64-linux. OK for trunk?
>
> In my impl the (multi)?set(from_range, r) will call
> (from_range_t, _Rg&& __rg, const _Alloc& __a) constructor,
> instead of _Compare, as specified in standard.
> This avoids making copy of _Comparator and is technically observable,
> but I do not think anybody will complain about it.
>
> libstdc++-v3/include/bits/stl_multiset.h | 49 ++++++++
> libstdc++-v3/include/bits/stl_set.h | 55 +++++++++
> .../23_containers/multiset/cons/from_range.cc | 115 ++++++++++++++++++
> .../multiset/modifiers/insert/insert_range.cc | 73 +++++++++++
> .../23_containers/set/cons/from_range.cc | 115 ++++++++++++++++++
> .../set/modifiers/insert/insert_range.cc | 76 ++++++++++++
> 6 files changed, 483 insertions(+)
> create mode 100644
> libstdc++-v3/testsuite/23_containers/multiset/cons/from_range.cc
> create mode 100644
> libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/insert_range.cc
> create mode 100644
> libstdc++-v3/testsuite/23_containers/set/cons/from_range.cc
> create mode 100644
> libstdc++-v3/testsuite/23_containers/set/modifiers/insert/insert_range.cc
>
> diff --git a/libstdc++-v3/include/bits/stl_multiset.h
> b/libstdc++-v3/include/bits/stl_multiset.h
> index 57caf6e8cc4..d5c2c07c955 100644
> --- a/libstdc++-v3/include/bits/stl_multiset.h
> +++ b/libstdc++-v3/include/bits/stl_multiset.h
> @@ -271,6 +271,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> : _M_t(_Key_alloc_type(__a))
> { _M_t._M_insert_range_equal(__first, __last); }
>
> +#if __glibcxx_ranges_to_container // C++ >= 23
> + /**
> + * @brief Builds a %set from a range.
> + * @since C++23
> + */
> + template<__detail::__container_compatible_range<_Key> _Rg>
> + multiset(from_range_t, _Rg&& __rg,
> + const _Compare& __comp,
> + const _Alloc& __a = _Alloc())
> + : _M_t(__comp, _Key_alloc_type(__a))
> + { insert_range(std::forward<_Rg>(__rg)); }
> +
> + /// Allocator-extended range constructor.
> + template<__detail::__container_compatible_range<_Key> _Rg>
> + multiset(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
> + : _M_t(_Key_alloc_type(__a))
> + { insert_range(std::forward<_Rg>(__rg)); }
> +#endif
> +
> /**
> * The dtor only erases the elements, and note that if the elements
> * themselves are pointers, the pointed-to memory is not touched
> in any
> @@ -566,6 +585,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { this->insert(__l.begin(), __l.end()); }
> #endif
>
> +#if __glibcxx_ranges_to_container // C++ >= 23
> + /**
> + * @brief Inserts a range of elements.
> + * @since C++23
> + * @param __rg An input range of elements that can be converted to
> + * the list's value type.
> + */
> + template<__detail::__container_compatible_range<_Key> _Rg>
> + void
> + insert_range(_Rg&& __rg)
> + {
> + auto __first = ranges::begin(__rg);
> + const auto __last = ranges::end(__rg);
> + for (; __first != __last; ++__first)
> + _M_t._M_emplace_equal(*__first);
> + }
> +#endif
> +
> +
> #ifdef __glibcxx_node_extract // >= C++17
> /// Extract a node.
> node_type
> @@ -955,6 +993,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> multiset(initializer_list<_Key>, _Allocator)
> -> multiset<_Key, less<_Key>, _Allocator>;
>
> +#if __glibcxx_ranges_to_container // C++ >= 23
> + template<ranges::input_range _Rg,
> + __not_allocator_like _Compare =
> less<ranges::range_value_t<_Rg>>,
> + __allocator_like _Alloc =
> std::allocator<ranges::range_value_t<_Rg>>>
> + multiset(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc =
> _Alloc())
> + -> multiset<ranges::range_value_t<_Rg>, _Compare, _Alloc>;
> +
> + template<ranges::input_range _Rg, __allocator_like _Alloc>
> + multiset(from_range_t, _Rg&&, _Alloc)
> + -> multiset<ranges::range_value_t<_Rg>,
> less<ranges::range_value_t<_Rg>>, _Alloc>;
> +#endif
> #endif // deduction guides
>
> /**
> diff --git a/libstdc++-v3/include/bits/stl_set.h
> b/libstdc++-v3/include/bits/stl_set.h
> index f32323db368..697df22c03b 100644
> --- a/libstdc++-v3/include/bits/stl_set.h
> +++ b/libstdc++-v3/include/bits/stl_set.h
> @@ -60,6 +60,9 @@
> #if __cplusplus >= 201103L
> #include <initializer_list>
> #endif
> +#if __glibcxx_ranges_to_container // C++ >= 23
> +# include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
> +#endif
>
> namespace std _GLIBCXX_VISIBILITY(default)
> {
> @@ -275,6 +278,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> : _M_t(_Key_alloc_type(__a))
> { _M_t._M_insert_range_unique(__first, __last); }
>
> +#if __glibcxx_ranges_to_container // C++ >= 23
> + /**
> + * @brief Builds a %set from a range.
> + * @since C++23
> + */
> + template<__detail::__container_compatible_range<_Key> _Rg>
> + set(from_range_t, _Rg&& __rg,
> + const _Compare& __comp,
> + const _Alloc& __a = _Alloc())
> + : _M_t(__comp, _Key_alloc_type(__a))
> + { insert_range(std::forward<_Rg>(__rg)); }
> +
> + /// Allocator-extended range constructor.
> + template<__detail::__container_compatible_range<_Key> _Rg>
> + set(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
> + : _M_t(_Key_alloc_type(__a))
> + { insert_range(std::forward<_Rg>(__rg)); }
> +#endif
> +
> /**
> * The dtor only erases the elements, and note that if the elements
> * themselves are pointers, the pointed-to memory is not touched
> in any
> @@ -581,6 +603,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { this->insert(__l.begin(), __l.end()); }
> #endif
>
> +#if __glibcxx_ranges_to_container // C++ >= 23
> + /**
> + * @brief Inserts a range of elements.
> + * @since C++23
> + * @param __rg An input range of elements that can be converted to
> + * the list's value type.
> + */
> + template<__detail::__container_compatible_range<_Key> _Rg>
> + void
> + insert_range(_Rg&& __rg)
> + {
> + auto __first = ranges::begin(__rg);
> + const auto __last = ranges::end(__rg);
> + using _Rv = __remove_cvref_t<ranges::range_value_t<_Rg>>;
> + for (; __first != __last; ++__first)
> + if constexpr (is_same_v<_Rv, _Key>)
> + _M_t._M_insert_unique(*__first);
> + else
> + _M_t._M_emplace_unique(*__first);
> + }
> +#endif
> +
> #ifdef __glibcxx_node_extract // >= C++17
> /// Extract a node.
> node_type
> @@ -970,6 +1014,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> set(initializer_list<_Key>, _Allocator)
> -> set<_Key, less<_Key>, _Allocator>;
>
> +#if __glibcxx_ranges_to_container // C++ >= 23
> + template<ranges::input_range _Rg,
> + __not_allocator_like _Compare =
> less<ranges::range_value_t<_Rg>>,
> + __allocator_like _Alloc =
> std::allocator<ranges::range_value_t<_Rg>>>
> + set(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
> + -> set<ranges::range_value_t<_Rg>, _Compare, _Alloc>;
> +
> + template<ranges::input_range _Rg, __allocator_like _Alloc>
> + set(from_range_t, _Rg&&, _Alloc)
> + -> set<ranges::range_value_t<_Rg>,
> less<ranges::range_value_t<_Rg>>, _Alloc>;
> +#endif
> #endif // deduction guides
>
> /**
> diff --git
> a/libstdc++-v3/testsuite/23_containers/multiset/cons/from_range.cc
> b/libstdc++-v3/testsuite/23_containers/multiset/cons/from_range.cc
> new file mode 100644
> index 00000000000..dfe786d235b
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/from_range.cc
> @@ -0,0 +1,115 @@
> +// { dg-do run { target c++23 } }
> +
> +#include <set>
> +#include <span>
> +#include <testsuite_allocator.h>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +struct StateCmp {
> + int state = 7;
> +
> + template<typename T, typename U>
> + bool operator()(T const& l, U const & r) const {
> + return l > r;
> + }
> +};
> +
> +void
> +test_deduction_guide(long* p)
> +{
> + __gnu_test::test_input_range<long> r(p, p);
> + std::set s(std::from_range, r);
> + static_assert(std::is_same_v<decltype(s), std::set<long>>);
> +
> + StateCmp cmp;
> + std::set s2(std::from_range, r, cmp);
> + static_assert(std::is_same_v<decltype(s2), std::set<long, StateCmp>>);
> +
> + using Alloc = __gnu_test::SimpleAllocator<long>;
> + Alloc alloc;
> + std::set s3(std::from_range, r, alloc);
> + static_assert(std::is_same_v<decltype(s3), std::set<long,
> std::less<long>, Alloc>>);
> +
> + std::set s4(std::from_range, r, cmp, alloc);
> + static_assert(std::is_same_v<decltype(s4), std::set<long, StateCmp,
> Alloc>>);
> +}
> +
> +template<typename T, typename U>
> +constexpr bool is_equal(std::less<T>, std::less<U>)
> +{ return true; }
> +
> +constexpr bool is_equal(StateCmp lhs, StateCmp rhs)
> +{ return lhs.state = rhs.state; }
> +
> +template<typename Range, typename Alloc, typename Cmp>
> +constexpr void
> +do_test(Alloc alloc, Cmp cmp)
> +{
> + // The set's value_typ.
> + using V = typename Alloc::value_type;
> +
> + // The range's value_type.
> + using T = std::ranges::range_value_t<Range>;
> + T a[]{1,2,3,4,5,6,7,8,9,1,2,3,4,5};
> +
> + auto eq = [&](std::set<V, Cmp, Alloc> const& l, std::span<T> r) {
> + if (l.size() != r.size())
> + return false;
> +
> + std::vector<T> s(r.begin(), r.end());
> + std::ranges::sort(s, cmp);
> + for (auto const& [vl, vr] : std::views::zip(l, s)) {
> + if (vl != vr)
> + return false;
> + }
> + return true;
> + };
> +
> + std::set<V, Cmp, Alloc> s0(std::from_range, Range(a, a+0));
> + VERIFY( s0.empty() );
> + VERIFY( s0.get_allocator() == Alloc() );
> + VERIFY( is_equal(s0.key_comp(), Cmp()) );
> +
> + std::set<V, Cmp, Alloc> s4(std::from_range, Range(a, a+4), cmp);
> + VERIFY( eq(s4, {a, 4}) );
> + VERIFY( s4.get_allocator() == Alloc() );
> + VERIFY( is_equal(s4.key_comp(), Cmp()) );
> +
> + std::set<V, Cmp, Alloc> s9(std::from_range, Range(a, a+9), alloc);
> + VERIFY( eq(s9, {a, 9}) );
> + VERIFY( s9.get_allocator() == alloc );
> + VERIFY( is_equal(s9.key_comp(), cmp) );
> +
> + std::set<V, Cmp, Alloc> sr(std::from_range, Range(a, a+14), cmp, alloc);
> + VERIFY( eq(sr, {a, 9}) );
> + VERIFY( sr.get_allocator() == alloc );
> + VERIFY( is_equal(sr.key_comp(), cmp) );
> +}
> +
> +template<typename Range>
> +void
> +do_test_ac()
> +{
> + do_test<Range>(std::allocator<int>(), std::less<int>());
> + do_test<Range>(std::allocator<int>(), StateCmp{17});
> + do_test<Range>(__gnu_test::uneq_allocator<int>(42), std::less<int>());
> + do_test<Range>(__gnu_test::uneq_allocator<int>(42), StateCmp{17});
> +}
> +
> +bool
> +test_ranges()
> +{
> + using namespace __gnu_test;
> +
> + do_test_ac<test_forward_range<int>>();
> + do_test_ac<test_range_nocopy<int, input_iterator_wrapper_nocopy>>();
> + do_test_ac<test_forward_range<short>>();
> +
> + return true;
> +}
> +
> +int main()
> +{
> + test_ranges();
> +}
> diff --git
> a/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/insert_range.cc
> b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/insert_range.cc
> new file mode 100644
> index 00000000000..b5d97d177cc
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/insert/insert_range.cc
> @@ -0,0 +1,73 @@
> +// { dg-do run { target c++23 } }
> +
> +#include <set>
> +#include <span>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +struct Gt {
> + template<typename T, typename U>
> + bool operator()(T const& l, U const & r) const {
> + return l > r;
> + }
> +};
> +
> +template<typename Range, typename V, typename Cmp>
> +constexpr void
> +do_test(Cmp cmp = Cmp())
> +{
> + // The range's value_type.
> + using T = std::ranges::range_value_t<Range>;
> + T a[]{1,2,3,4,5,6,7,8,9,1,2,3,4,5};
> +
> + auto eq = [&](std::multiset<V, Cmp> const& l, std::span<T> r) {
> + if (l.size() != r.size())
> + return false;
> +
> + std::vector<T> s(r.begin(), r.end());
> + std::ranges::sort(s, cmp);
> + for (auto const& [vl, vr] : std::views::zip(l, s)) {
> + if (vl != vr)
> + return false;
> + }
> + return true;
> + };
> +
> + std::multiset<V, Cmp> s;
> + s.insert_range(Range(a, a+0));
> + VERIFY( s.empty() );
> +
> + s.insert_range(Range(a, a+4));
> + VERIFY( eq(s, {a, 4}) );
> +
> + s.insert_range(Range(a+4, a+9));
> + VERIFY( eq(s, {a, 9}) );
> +
> + s.insert_range(Range(a+9, a+14));
> + VERIFY( eq(s, {a, 14}) );
> +}
> +
> +template<typename Range>
> +void
> +do_test_c()
> +{
> + do_test<Range, int, std::less<int>>();
> + do_test<Range, int, Gt>();
> +}
> +
> +bool
> +test_ranges()
> +{
> + using namespace __gnu_test;
> +
> + do_test_c<test_forward_range<int>>();
> + do_test_c<test_range_nocopy<int, input_iterator_wrapper_nocopy>>();
> + do_test_c<test_forward_range<short>>();
> +
> + return true;
> +}
> +
> +int main()
> +{
> + test_ranges();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/from_range.cc
> b/libstdc++-v3/testsuite/23_containers/set/cons/from_range.cc
> new file mode 100644
> index 00000000000..dfe786d235b
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/set/cons/from_range.cc
> @@ -0,0 +1,115 @@
> +// { dg-do run { target c++23 } }
> +
> +#include <set>
> +#include <span>
> +#include <testsuite_allocator.h>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +struct StateCmp {
> + int state = 7;
> +
> + template<typename T, typename U>
> + bool operator()(T const& l, U const & r) const {
> + return l > r;
> + }
> +};
> +
> +void
> +test_deduction_guide(long* p)
> +{
> + __gnu_test::test_input_range<long> r(p, p);
> + std::set s(std::from_range, r);
> + static_assert(std::is_same_v<decltype(s), std::set<long>>);
> +
> + StateCmp cmp;
> + std::set s2(std::from_range, r, cmp);
> + static_assert(std::is_same_v<decltype(s2), std::set<long, StateCmp>>);
> +
> + using Alloc = __gnu_test::SimpleAllocator<long>;
> + Alloc alloc;
> + std::set s3(std::from_range, r, alloc);
> + static_assert(std::is_same_v<decltype(s3), std::set<long,
> std::less<long>, Alloc>>);
> +
> + std::set s4(std::from_range, r, cmp, alloc);
> + static_assert(std::is_same_v<decltype(s4), std::set<long, StateCmp,
> Alloc>>);
> +}
> +
> +template<typename T, typename U>
> +constexpr bool is_equal(std::less<T>, std::less<U>)
> +{ return true; }
> +
> +constexpr bool is_equal(StateCmp lhs, StateCmp rhs)
> +{ return lhs.state = rhs.state; }
> +
> +template<typename Range, typename Alloc, typename Cmp>
> +constexpr void
> +do_test(Alloc alloc, Cmp cmp)
> +{
> + // The set's value_typ.
> + using V = typename Alloc::value_type;
> +
> + // The range's value_type.
> + using T = std::ranges::range_value_t<Range>;
> + T a[]{1,2,3,4,5,6,7,8,9,1,2,3,4,5};
> +
> + auto eq = [&](std::set<V, Cmp, Alloc> const& l, std::span<T> r) {
> + if (l.size() != r.size())
> + return false;
> +
> + std::vector<T> s(r.begin(), r.end());
> + std::ranges::sort(s, cmp);
> + for (auto const& [vl, vr] : std::views::zip(l, s)) {
> + if (vl != vr)
> + return false;
> + }
> + return true;
> + };
> +
> + std::set<V, Cmp, Alloc> s0(std::from_range, Range(a, a+0));
> + VERIFY( s0.empty() );
> + VERIFY( s0.get_allocator() == Alloc() );
> + VERIFY( is_equal(s0.key_comp(), Cmp()) );
> +
> + std::set<V, Cmp, Alloc> s4(std::from_range, Range(a, a+4), cmp);
> + VERIFY( eq(s4, {a, 4}) );
> + VERIFY( s4.get_allocator() == Alloc() );
> + VERIFY( is_equal(s4.key_comp(), Cmp()) );
> +
> + std::set<V, Cmp, Alloc> s9(std::from_range, Range(a, a+9), alloc);
> + VERIFY( eq(s9, {a, 9}) );
> + VERIFY( s9.get_allocator() == alloc );
> + VERIFY( is_equal(s9.key_comp(), cmp) );
> +
> + std::set<V, Cmp, Alloc> sr(std::from_range, Range(a, a+14), cmp, alloc);
> + VERIFY( eq(sr, {a, 9}) );
> + VERIFY( sr.get_allocator() == alloc );
> + VERIFY( is_equal(sr.key_comp(), cmp) );
> +}
> +
> +template<typename Range>
> +void
> +do_test_ac()
> +{
> + do_test<Range>(std::allocator<int>(), std::less<int>());
> + do_test<Range>(std::allocator<int>(), StateCmp{17});
> + do_test<Range>(__gnu_test::uneq_allocator<int>(42), std::less<int>());
> + do_test<Range>(__gnu_test::uneq_allocator<int>(42), StateCmp{17});
> +}
> +
> +bool
> +test_ranges()
> +{
> + using namespace __gnu_test;
> +
> + do_test_ac<test_forward_range<int>>();
> + do_test_ac<test_range_nocopy<int, input_iterator_wrapper_nocopy>>();
> + do_test_ac<test_forward_range<short>>();
> +
> + return true;
> +}
> +
> +int main()
> +{
> + test_ranges();
> +}
> diff --git
> a/libstdc++-v3/testsuite/23_containers/set/modifiers/insert/insert_range.cc
> b/libstdc++-v3/testsuite/23_containers/set/modifiers/insert/insert_range.cc
> new file mode 100644
> index 00000000000..9503e3f75ae
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/set/modifiers/insert/insert_range.cc
> @@ -0,0 +1,76 @@
> +// { dg-do run { target c++23 } }
> +
> +#include <set>
> +#include <span>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +struct Gt {
> + template<typename T, typename U>
> + bool operator()(T const& l, U const & r) const {
> + return l > r;
> + }
> +};
> +
> +template<typename Range, typename V, typename Cmp>
> +constexpr void
> +do_test(Cmp cmp = Cmp())
> +{
> + // The range's value_type.
> + using T = std::ranges::range_value_t<Range>;
> + T a[]{1,2,3,4,5,6,7,8,9};
> +
> + auto eq = [&](std::set<V, Cmp> const& l, std::span<T> r) {
> + if (l.size() != r.size())
> + return false;
> +
> + std::vector<T> s(r.begin(), r.end());
> + std::ranges::sort(s, cmp);
> + for (auto const& [vl, vr] : std::views::zip(l, s)) {
> + if (vl != vr)
> + return false;
> + }
> + return true;
> + };
> +
> + std::set<V, Cmp> s;
> + s.insert_range(Range(a, a+0));
> + VERIFY( s.empty() );
> +
> + s.insert_range(Range(a, a+4));
> + VERIFY( eq(s, {a, 4}) );
> +
> + s.insert_range(Range(a+4, a+7));
> + VERIFY( eq(s, {a, 7}) );
> +
> + s.insert_range(Range(a, a+9));
> + VERIFY( eq(s, {a, 9}) );
> +
> + s.insert_range(Range(a, a+9));
> + VERIFY( eq(s, {a, 9}) );
> +}
> +
> +template<typename Range>
> +void
> +do_test_c()
> +{
> + do_test<Range, int, std::less<int>>();
> + do_test<Range, int, Gt>();
> +}
> +
> +bool
> +test_ranges()
> +{
> + using namespace __gnu_test;
> +
> + do_test_c<test_forward_range<int>>();
> + do_test_c<test_range_nocopy<int, input_iterator_wrapper_nocopy>>();
> + do_test_c<test_forward_range<short>>();
> +
> + return true;
> +}
> +
> +int main()
> +{
> + test_ranges();
> +}
> --
> 2.48.1
>
>
