[PATCH] libstdc++: Add P1206R7 from_range members to unordered sets [PR111055]
Jonathan Wakely
jwakely@redhat.com
Tue Mar 18 13:29:46 GMT 2025
On 17/03/25 17:21 +0100, Tomasz Kamiński wrote:
>This is another piece of P1206R7, adding new members to std::unordered_set
>and std::unordered_multiset.
>
> PR libstdc++/111055
>
>libstdc++-v3/ChangeLog:
Oh actually I didn't review this change log part properly ...
> * include/bits/hashtable.h (_M_rehash_insert)
> (_M_insert_range_multi): Extracted rehashing for range insertion
> to separate function.
> * include/bits/unordered_set.h: (unordered_(multi)?set::insert_range)
The GNU changelog style says to not use patterns like
unordered_(multi)?set because it won't work if people are searching
the change logs for "unordered_set".
You could use:
* include/bits/unordered_set.h (unordered_set): Define
from_range constructors and insert_range member.
* (unordered_multiset) Likewise.
> (unordered_(multi)?set(from_range_t, _Rg&&, size_type,
> const hasher&, const key_equal&, const allocator_type&))
> (unordered_(multi)?set(from_range_t, _Rg&&, size_type,
> const hasher&, const allocator_type&))
> (unordered_(multi)?set(from_range_t, _Rg&&, size_type,
> const allocator_type&)): Define
> * testsuite/23_containers/unordered_multiset/cons/from_range.cc: New test.
Please put in a line break before "New test" here, and the
next three lines.
> * testsuite/23_containers/unordered_multiset/modifiers/insert_range.cc: New test.
> * testsuite/23_containers/unordered_set/cons/from_range.cc: New test.
> * testsuite/23_containers/unordered_set/modifiers/insert_range.cc: New test.
>---
> Tested on x86_64-linux (all-test) and unordered_(multi)_set without PCH.
> OK for trunk?
>
> libstdc++-v3/include/bits/hashtable.h | 43 ++--
> libstdc++-v3/include/bits/unordered_set.h | 199 +++++++++++++++++
> .../unordered_multiset/cons/from_range.cc | 201 ++++++++++++++++++
> .../modifiers/insert_range.cc | 62 ++++++
> .../unordered_set/cons/from_range.cc | 201 ++++++++++++++++++
> .../unordered_set/modifiers/insert_range.cc | 65 ++++++
> 6 files changed, 755 insertions(+), 16 deletions(-)
> create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/from_range.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/insert_range.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/cons/from_range.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert_range.cc
>
>diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
>index 246e62afc6a..20f9bd98d5b 100644
>--- a/libstdc++-v3/include/bits/hashtable.h
>+++ b/libstdc++-v3/include/bits/hashtable.h
>@@ -798,6 +798,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> _M_equal_range_tr(const _Kt& __k) const;
> #endif // __glibcxx_generic_unordered_lookup
>
>+ void _M_rehash_insert(size_type __n);
>+
> private:
> // Bucket index computation helpers.
> size_type
>@@ -2388,6 +2390,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return __pos;
> }
>
>+ template<typename _Key, typename _Value, typename _Alloc,
>+ typename _ExtractKey, typename _Equal,
>+ typename _Hash, typename _RangeHash, typename _Unused,
>+ typename _RehashPolicy, typename _Traits>
>+ void
>+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
>+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
>+ _M_rehash_insert(size_type __n)
>+ {
>+ using __pair_type = std::pair<bool, std::size_t>;
>+ if (__n == 0)
>+ return;
>+
>+ __rehash_guard_t __rehash_guard(_M_rehash_policy);
>+ __pair_type __do_rehash
>+ = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, __n);
>+
>+ if (__do_rehash.first)
>+ _M_rehash(__do_rehash.second, false_type{});
>+
>+ __rehash_guard._M_guarded_obj = nullptr;
>+ }
>+
>+
> template<typename _Key, typename _Value, typename _Alloc,
> typename _ExtractKey, typename _Equal,
> typename _Hash, typename _RangeHash, typename _Unused,
>@@ -2398,22 +2424,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
> _M_insert_range_multi(_InputIterator __first, _InputIterator __last)
> {
>- using __pair_type = std::pair<bool, std::size_t>;
>-
>- size_type __n_elt = __detail::__distance_fw(__first, __last);
>- if (__n_elt == 0)
>- return;
>-
>- __rehash_guard_t __rehash_guard(_M_rehash_policy);
>- __pair_type __do_rehash
>- = _M_rehash_policy._M_need_rehash(_M_bucket_count,
>- _M_element_count,
>- __n_elt);
>-
>- if (__do_rehash.first)
>- _M_rehash(__do_rehash.second, false_type{});
>-
>- __rehash_guard._M_guarded_obj = nullptr;
>+ _M_rehash_insert(__detail::__distance_fw(__first, __last));
> for (; __first != __last; ++__first)
> _M_emplace_multi(cend(), *__first);
> }
>diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
>index fc9d584c036..361ead0068c 100644
>--- a/libstdc++-v3/include/bits/unordered_set.h
>+++ b/libstdc++-v3/include/bits/unordered_set.h
>@@ -34,6 +34,9 @@
> #include <bits/allocator.h>
> #include <bits/functional_hash.h> // hash
> #include <bits/stl_function.h> // equal_to
>+#if __glibcxx_ranges_to_container // C++ >= 23
>+# include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
>+#endif
>
> namespace std _GLIBCXX_VISIBILITY(default)
> {
>@@ -268,6 +271,43 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> : unordered_set(__l, __n, __hf, key_equal(), __a)
> { }
>
>+#if __glibcxx_ranges_to_container // C++ >= 23
>+ /**
>+ * @brief Builds an %unordered_set from an initializer_list.
>+ * @since C++23
>+ * @param __rg An input range of elements that can be converted to
>+ * the list's value type.
>+ * @param __l An initializer_list.
>+ * @param __n Minimal initial number of buckets.
>+ * @param __hf A hash functor.
>+ * @param __eql A key equality functor.
>+ * @param __a An allocator object.
>+ *
>+ * Create an %unordered_set consisting of copies of the elements in the
>+ * list. This is linear in N (where N is @a std::ranges::size(__rg)).
>+ */
>+ template<__detail::__container_compatible_range<_Value> _Rg>
>+ unordered_set(from_range_t, _Rg&& __rg,
>+ size_type __n = 0,
>+ const hasher& __hf = hasher(),
>+ const key_equal& __eql = key_equal(),
>+ const allocator_type& __a = allocator_type())
>+ : _M_h(__n, __hf, __eql, __a)
>+ { insert_range(std::forward<_Rg>(__rg)); }
>+
>+ template<__detail::__container_compatible_range<_Value> _Rg>
>+ unordered_set(from_range_t, _Rg&& __rg, size_type __n,
>+ const allocator_type& __a)
>+ : _M_h(__n, hasher(), key_equal(), __a)
>+ { insert_range(std::forward<_Rg>(__rg)); }
>+
>+ template<__detail::__container_compatible_range<_Value> _Rg>
>+ unordered_set(from_range_t, _Rg&& __rg, size_type __n,
>+ const hasher& __hf, const allocator_type& __a)
>+ : _M_h(__n, __hf, key_equal(), __a)
>+ { insert_range(std::forward<_Rg>(__rg)); }
>+#endif
>+
> /// Copy assignment operator.
> unordered_set&
> operator=(const unordered_set&) = default;
>@@ -487,6 +527,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> insert(initializer_list<value_type> __l)
> { _M_h.insert(__l); }
>
>+#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<_Value> _Rg>
>+ void
>+ insert_range(_Rg&& __rg)
>+ {
>+ auto __first = ranges::begin(__rg);
>+ const auto __last = ranges::end(__rg);
>+ for (; __first != __last; ++__first)
>+ _M_h.emplace(*__first);
>+ }
>+#endif
>+
> #ifdef __glibcxx_node_extract // >= C++17 && HOSTED
> /// Extract a node.
> node_type
>@@ -942,6 +1000,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> unordered_set<int>::size_type, _Allocator)
> -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
>
>+
> template<typename _Tp, typename _Hash, typename _Allocator,
> typename = _RequireNotAllocatorOrIntegral<_Hash>,
> typename = _RequireAllocator<_Allocator>>
>@@ -949,6 +1008,42 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> unordered_set<int>::size_type, _Hash, _Allocator)
> -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
>
>+
>+#if __glibcxx_ranges_to_container // C++ >= 23
>+ template<ranges::input_range _Rg,
>+ __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
>+ __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
>+ __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
>+ unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type = {},
>+ _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
>+ -> unordered_set<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
>+
>+ template<ranges::input_range _Rg,
>+ __allocator_like _Allocator>
>+ unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
>+ _Allocator)
>+ -> unordered_set<ranges::range_value_t<_Rg>,
>+ hash<ranges::range_value_t<_Rg>>,
>+ equal_to<ranges::range_value_t<_Rg>>,
>+ _Allocator>;
>+
>+ template<ranges::input_range _Rg,
>+ __allocator_like _Allocator>
>+ unordered_set(from_range_t, _Rg&&, _Allocator)
>+ -> unordered_set<ranges::range_value_t<_Rg>,
>+ hash<ranges::range_value_t<_Rg>>,
>+ equal_to<ranges::range_value_t<_Rg>>,
>+ _Allocator>;
>+
>+ template<ranges::input_range _Rg,
>+ __not_allocator_like _Hash,
>+ __allocator_like _Allocator>
>+ unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
>+ _Hash, _Allocator)
>+ -> unordered_set<ranges::range_value_t<_Rg>, _Hash,
>+ equal_to<ranges::range_value_t<_Rg>>,
>+ _Allocator>;
>+#endif
> #endif
>
> /**
>@@ -1150,6 +1245,44 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> : unordered_multiset(__l, __n, __hf, key_equal(), __a)
> { }
>
>+#if __glibcxx_ranges_to_container // C++ >= 23
>+ /**
>+ * @brief Builds an %unordered_multiset from an initializer_list.
>+ * @since C++23
>+ * @param __rg An input range of elements that can be converted to
>+ * the list's value type.
>+ * @param __l An initializer_list.
>+ * @param __n Minimal initial number of buckets.
>+ * @param __hf A hash functor.
>+ * @param __eql A key equality functor.
>+ * @param __a An allocator object.
>+ *
>+ * Create an %unordered_multiset consisting of copies of the elements in the
>+ * list. This is linear in N (where N is @a std::ranges::size(__rg)).
>+ */
>+ template<__detail::__container_compatible_range<_Value> _Rg>
>+ unordered_multiset(from_range_t, _Rg&& __rg,
>+ size_type __n = 0,
>+ const hasher& __hf = hasher(),
>+ const key_equal& __eql = key_equal(),
>+ const allocator_type& __a = allocator_type())
>+ : _M_h(__n, __hf, __eql, __a)
>+ { insert_range(std::forward<_Rg>(__rg)); }
>+
>+ template<__detail::__container_compatible_range<_Value> _Rg>
>+ unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
>+ const allocator_type& __a)
>+ : _M_h(__n, hasher(), key_equal(), __a)
>+ { insert_range(std::forward<_Rg>(__rg)); }
>+
>+ template<__detail::__container_compatible_range<_Value> _Rg>
>+ unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
>+ const hasher& __hf, const allocator_type& __a)
>+ : _M_h(__n, __hf, key_equal(), __a)
>+ { insert_range(std::forward<_Rg>(__rg)); }
>+#endif
>+
>+
> /**
> * @brief %Unordered_multiset list assignment operator.
> * @param __l An initializer_list.
>@@ -1339,6 +1472,33 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> insert(initializer_list<value_type> __l)
> { _M_h.insert(__l); }
>
>+#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<_Value> _Rg>
>+ void
>+ insert_range(_Rg&& __rg)
>+ {
>+ auto __first = ranges::begin(__rg);
>+ const auto __last = ranges::end(__rg);
>+ if (__first == __last)
>+ return;
>+
>+ if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
>+ _M_h._M_rehash_insert(ranges::distance(__rg));
>+ else
>+ _M_h._M_rehash_insert(1);
>+
>+ for (; __first != __last; ++__first)
>+ _M_h.emplace(*__first);
>+ }
>+#endif
>+
>+
> #ifdef __glibcxx_node_extract // >= C++17 && HOSTED
> /// Extract a node.
> node_type
>@@ -1807,6 +1967,45 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> unordered_multiset<int>::size_type, _Hash, _Allocator)
> -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
>
>+#if __glibcxx_ranges_to_container // C++ >= 23
>+ template<ranges::input_range _Rg,
>+ __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
>+ __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
>+ __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
>+ unordered_multiset(from_range_t, _Rg&&,
>+ unordered_multiset<int>::size_type = {},
>+ _Hash = _Hash(), _Pred = _Pred(),
>+ _Allocator = _Allocator())
>+ -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
>+
>+ template<ranges::input_range _Rg,
>+ __allocator_like _Allocator>
>+ unordered_multiset(from_range_t, _Rg&&, _Allocator)
>+ -> unordered_multiset<ranges::range_value_t<_Rg>,
>+ hash<ranges::range_value_t<_Rg>>,
>+ equal_to<ranges::range_value_t<_Rg>>,
>+ _Allocator>;
>+
>+ template<ranges::input_range _Rg,
>+ __allocator_like _Allocator>
>+ unordered_multiset(from_range_t, _Rg&&, unordered_multiset<int>::size_type,
>+ _Allocator)
>+ -> unordered_multiset<ranges::range_value_t<_Rg>,
>+ hash<ranges::range_value_t<_Rg>>,
>+ equal_to<ranges::range_value_t<_Rg>>,
>+ _Allocator>;
>+
>+ template<ranges::input_range _Rg,
>+ __not_allocator_like _Hash,
>+ __allocator_like _Allocator>
>+ unordered_multiset(from_range_t, _Rg&&,
>+ unordered_multiset<int>::size_type,
>+ _Hash, _Allocator)
>+ -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash,
>+ equal_to<ranges::range_value_t<_Rg>>,
>+ _Allocator>;
>+#endif
>+
> #endif
>
> template<class _Value, class _Hash, class _Pred, class _Alloc>
>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/from_range.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/from_range.cc
>new file mode 100644
>index 00000000000..5e9460a44fa
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/from_range.cc
>@@ -0,0 +1,201 @@
>+// { dg-do run { target c++23 } }
>+
>+#include <algorithm>
>+#include <unordered_set>
>+#include <span>
>+#include <testsuite_allocator.h>
>+#include <testsuite_hooks.h>
>+#include <testsuite_iterators.h>
>+
>+struct StateHash {
>+ int state = 17;
>+
>+ template<typename T>
>+ size_t operator()(T const& t) const {
>+ return std::hash<T>()(t) + 43;
>+ }
>+};
>+
>+struct StateEq {
>+ 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::unordered_multiset s(std::from_range, r);
>+ static_assert(std::is_same_v<decltype(s), std::unordered_multiset<long>>);
>+
>+ std::unordered_multiset s2(std::from_range, r, 0);
>+ static_assert(std::is_same_v<decltype(s2), std::unordered_multiset<long>>);
>+
>+ StateHash hf;
>+ std::unordered_multiset s3(std::from_range, r, 0, hf);
>+ static_assert(std::is_same_v<
>+ decltype(s3),
>+ std::unordered_multiset<long, StateHash>>);
>+
>+ StateEq eq;
>+ std::unordered_multiset s4(std::from_range, r, 0, hf, eq);
>+ static_assert(std::is_same_v<
>+ decltype(s4),
>+ std::unordered_multiset<long, StateHash, StateEq>>);
>+
>+ using Alloc = __gnu_test::SimpleAllocator<long>;
>+ Alloc alloc;
>+ // LWG2713: there is no matching constructor
>+ // std::unordered_multiset s5(std::from_range, r, alloc);
>+ // static_assert(std::is_same_v<
>+ // decltype(s5),
>+ // std::unordered_multiset<long, std::hash<long>, std::equal_to<long>, Alloc>>);
>+
>+ std::unordered_multiset s6(std::from_range, r, 0, alloc);
>+ static_assert(std::is_same_v<
>+ decltype(s6),
>+ std::unordered_multiset<long, std::hash<long>, std::equal_to<long>, Alloc>>);
>+
>+ std::unordered_multiset s7(std::from_range, r, 0, hf, alloc);
>+ static_assert(std::is_same_v<
>+ decltype(s7),
>+ std::unordered_multiset<long, StateHash, std::equal_to<long>, Alloc>>);
>+
>+ std::unordered_multiset s8(std::from_range, r, 0, hf, eq, alloc);
>+ static_assert(std::is_same_v<
>+ decltype(s8),
>+ std::unordered_multiset<long, StateHash, StateEq, Alloc>>);
>+}
>+
>+template<typename T, typename U>
>+constexpr bool is_equal(std::hash<T>, std::hash<U>)
>+{ return true; }
>+
>+template<typename T, typename U>
>+constexpr bool is_equal(std::equal_to<T>, std::equal_to<U>)
>+{ return true; }
>+
>+constexpr bool is_equal(StateHash lhs, StateHash rhs)
>+{ return lhs.state = rhs.state; }
>+
>+
>+constexpr bool is_equal(StateEq lhs, StateEq rhs)
>+{ return lhs.state = rhs.state; }
>+
>+template<typename Range, typename Alloc, typename Hash, typename Equal>
>+constexpr void
>+do_test(Alloc alloc, Hash hf, Equal eqf)
>+{
>+ // The unordered_multiset'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::unordered_multiset<V, Hash, Equal, Alloc> const& l,
>+ std::span<T> r) {
>+ if (l.size() != r.size())
>+ return false;
>+
>+ return std::ranges::is_permutation(l, r, eqf);
>+ };
>+
>+ std::unordered_multiset<V, Hash, Equal, Alloc>
>+ s0(std::from_range, Range(a, a+0));
>+ VERIFY( s0.empty() );
>+ VERIFY( is_equal(s0.hash_function(), Hash()) );
>+ VERIFY( is_equal(s0.key_eq(), Equal()) );
>+ VERIFY( s0.get_allocator() == Alloc() );
>+
>+ std::unordered_multiset<V, Hash, Equal, Alloc>
>+ s4(std::from_range, Range(a, a+4), 2);
>+ VERIFY( eq(s4, {a, 4}) );
>+ VERIFY( s4.bucket_count() >= 2 );
>+ VERIFY( is_equal(s4.hash_function(), Hash()) );
>+ VERIFY( is_equal(s4.key_eq(), Equal()) );
>+ VERIFY( s4.get_allocator() == Alloc() );
>+
>+ std::unordered_multiset<V, Hash, Equal, Alloc>
>+ s7(std::from_range, Range(a, a+7), 3, hf);
>+ VERIFY( eq(s7, {a, 7}) );
>+ VERIFY( s7.bucket_count() >= 3 );
>+ VERIFY( is_equal(s7.hash_function(), hf) );
>+ VERIFY( is_equal(s7.key_eq(), Equal()) );
>+ VERIFY( s7.get_allocator() == Alloc() );
>+
>+ std::unordered_multiset<V, Hash, Equal, Alloc>
>+ s9(std::from_range, Range(a, a+9), 5, hf, eqf);
>+ VERIFY( eq(s9, {a, 9}) );
>+ VERIFY( s9.bucket_count() >= 5 );
>+ VERIFY( s9.get_allocator() == Alloc() );
>+ VERIFY( is_equal(s9.hash_function(), hf) );
>+ VERIFY( is_equal(s9.key_eq(), eqf) );
>+
>+ // LWG2713: there is no matching constructor
>+ // std::unordered_multiset<V, Hash, Equal, Alloc>
>+ // sa(std::from_range, Range(a, a+14), 1, alloc);
>+ // VERIFY( eq(sa1, {a, 14}) );
>+ // VERIFY( is_equal(sa1.hash_function(), Hash()) );
>+ // VERIFY( is_equal(sa1.key_eq(), Equal()) );
>+ // VERIFY( sa1.get_allocator() == alloc );
>+
>+ std::unordered_multiset<V, Hash, Equal, Alloc>
>+ sa2(std::from_range, Range(a, a+14), 2, alloc);
>+ VERIFY( eq(sa2, {a, 14}) );
>+ VERIFY( sa2.bucket_count() >= 2 );
>+ VERIFY( is_equal(sa2.hash_function(), Hash()) );
>+ VERIFY( is_equal(sa2.key_eq(), Equal()) );
>+ VERIFY( sa2.get_allocator() == alloc );
>+
>+ std::unordered_multiset<V, Hash, Equal, Alloc>
>+ sa3(std::from_range, Range(a, a+14), 3, hf, alloc);
>+ VERIFY( eq(sa3, {a, 14}) );
>+ VERIFY( sa3.bucket_count() >= 3 );
>+ VERIFY( is_equal(sa3.hash_function(), hf) );
>+ VERIFY( is_equal(sa3.key_eq(), Equal()) );
>+ VERIFY( sa3.get_allocator() == alloc );
>+
>+ std::unordered_multiset<V, Hash, Equal, Alloc>
>+ sa4(std::from_range, Range(a, a+14), 5, hf, eqf, alloc);
>+ VERIFY( eq(sa4, {a, 14}) );
>+ VERIFY( sa4.bucket_count() >= 5 );
>+ VERIFY( is_equal(sa4.hash_function(), hf) );
>+ VERIFY( is_equal(sa4.key_eq(), eqf) );
>+ VERIFY( sa4.get_allocator() == alloc );
>+}
>+
>+template<typename Range>
>+void
>+do_test_ahe()
>+{
>+ do_test<Range>(std::allocator<int>(),
>+ std::hash<int>(), std::equal_to<int>());
>+ do_test<Range>(std::allocator<int>(),
>+ StateHash{27}, StateEq{17});
>+ do_test<Range>(__gnu_test::uneq_allocator<int>(42),
>+ std::hash<int>(), std::equal_to<int>());
>+ do_test<Range>(__gnu_test::uneq_allocator<int>(42),
>+ StateHash{27}, StateEq{17});
>+}
>+
>+bool
>+test_ranges()
>+{
>+ using namespace __gnu_test;
>+
>+ do_test_ahe<test_forward_range<int>>();
>+ do_test_ahe<test_range_nocopy<int, input_iterator_wrapper_nocopy>>();
>+ do_test_ahe<test_forward_range<short>>();
>+
>+ return true;
>+}
>+
>+int main()
>+{
>+ test_ranges();
>+}
>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/insert_range.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/insert_range.cc
>new file mode 100644
>index 00000000000..efb66bd5772
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/insert_range.cc
>@@ -0,0 +1,62 @@
>+// { dg-do run { target c++23 } }
>+
>+#include <algorithm>
>+#include <unordered_set>
>+#include <span>
>+#include <testsuite_allocator.h>
>+#include <testsuite_hooks.h>
>+#include <testsuite_iterators.h>
>+
>+template<typename Range, typename V>
>+constexpr void
>+do_test()
>+{
>+ // 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::unordered_multiset<V> const& l,
>+ std::span<T> r) {
>+ if (l.size() != r.size())
>+ return false;
>+
>+ return std::ranges::is_permutation(l, r);
>+ };
>+
>+ std::unordered_multiset<V> 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_v()
>+{
>+ do_test<Range, int>();
>+}
>+
>+bool
>+test_ranges()
>+{
>+ using namespace __gnu_test;
>+
>+ do_test_v<test_forward_range<int>>();
>+ do_test_v<test_range_nocopy<int, input_iterator_wrapper_nocopy>>();
>+ do_test_v<test_forward_range<short>>();
>+
>+ return true;
>+}
>+
>+int main()
>+{
>+ test_ranges();
>+}
>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/from_range.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/from_range.cc
>new file mode 100644
>index 00000000000..3fe06a1d740
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/from_range.cc
>@@ -0,0 +1,201 @@
>+// { dg-do run { target c++23 } }
>+
>+#include <algorithm>
>+#include <unordered_set>
>+#include <span>
>+#include <testsuite_allocator.h>
>+#include <testsuite_hooks.h>
>+#include <testsuite_iterators.h>
>+
>+struct StateHash {
>+ int state = 17;
>+
>+ template<typename T>
>+ size_t operator()(T const& t) const {
>+ return std::hash<T>()(t) + 43;
>+ }
>+};
>+
>+struct StateEq {
>+ 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::unordered_set s(std::from_range, r);
>+ static_assert(std::is_same_v<decltype(s), std::unordered_set<long>>);
>+
>+ std::unordered_set s2(std::from_range, r, 0);
>+ static_assert(std::is_same_v<decltype(s2), std::unordered_set<long>>);
>+
>+ StateHash hf;
>+ std::unordered_set s3(std::from_range, r, 0, hf);
>+ static_assert(std::is_same_v<
>+ decltype(s3),
>+ std::unordered_set<long, StateHash>>);
>+
>+ StateEq eq;
>+ std::unordered_set s4(std::from_range, r, 0, hf, eq);
>+ static_assert(std::is_same_v<
>+ decltype(s4),
>+ std::unordered_set<long, StateHash, StateEq>>);
>+
>+ using Alloc = __gnu_test::SimpleAllocator<long>;
>+ Alloc alloc;
>+ // LWG2713: there is no matching constructor
>+ // std::unordered_set s5(std::from_range, r, alloc);
>+ // static_assert(std::is_same_v<
>+ // decltype(s5),
>+ // std::unordered_set<long, std::hash<long>, std::equal_to<long>, Alloc>>);
>+
>+ std::unordered_set s6(std::from_range, r, 0, alloc);
>+ static_assert(std::is_same_v<
>+ decltype(s6),
>+ std::unordered_set<long, std::hash<long>, std::equal_to<long>, Alloc>>);
>+
>+ std::unordered_set s7(std::from_range, r, 0, hf, alloc);
>+ static_assert(std::is_same_v<
>+ decltype(s7),
>+ std::unordered_set<long, StateHash, std::equal_to<long>, Alloc>>);
>+
>+ std::unordered_set s8(std::from_range, r, 0, hf, eq, alloc);
>+ static_assert(std::is_same_v<
>+ decltype(s8),
>+ std::unordered_set<long, StateHash, StateEq, Alloc>>);
>+}
>+
>+template<typename T, typename U>
>+constexpr bool is_equal(std::hash<T>, std::hash<U>)
>+{ return true; }
>+
>+template<typename T, typename U>
>+constexpr bool is_equal(std::equal_to<T>, std::equal_to<U>)
>+{ return true; }
>+
>+constexpr bool is_equal(StateHash lhs, StateHash rhs)
>+{ return lhs.state = rhs.state; }
>+
>+
>+constexpr bool is_equal(StateEq lhs, StateEq rhs)
>+{ return lhs.state = rhs.state; }
>+
>+template<typename Range, typename Alloc, typename Hash, typename Equal>
>+constexpr void
>+do_test(Alloc alloc, Hash hf, Equal eqf)
>+{
>+ // The unordered_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::unordered_set<V, Hash, Equal, Alloc> const& l,
>+ std::span<T> r) {
>+ if (l.size() != r.size())
>+ return false;
>+
>+ return std::ranges::is_permutation(l, r, eqf);
>+ };
>+
>+ std::unordered_set<V, Hash, Equal, Alloc>
>+ s0(std::from_range, Range(a, a+0));
>+ VERIFY( s0.empty() );
>+ VERIFY( is_equal(s0.hash_function(), Hash()) );
>+ VERIFY( is_equal(s0.key_eq(), Equal()) );
>+ VERIFY( s0.get_allocator() == Alloc() );
>+
>+ std::unordered_set<V, Hash, Equal, Alloc>
>+ s4(std::from_range, Range(a, a+4), 2);
>+ VERIFY( eq(s4, {a, 4}) );
>+ VERIFY( s4.bucket_count() >= 2 );
>+ VERIFY( is_equal(s4.hash_function(), Hash()) );
>+ VERIFY( is_equal(s4.key_eq(), Equal()) );
>+ VERIFY( s4.get_allocator() == Alloc() );
>+
>+ std::unordered_set<V, Hash, Equal, Alloc>
>+ s7(std::from_range, Range(a, a+7), 3, hf);
>+ VERIFY( eq(s7, {a, 7}) );
>+ VERIFY( s7.bucket_count() >= 3 );
>+ VERIFY( is_equal(s7.hash_function(), hf) );
>+ VERIFY( is_equal(s7.key_eq(), Equal()) );
>+ VERIFY( s7.get_allocator() == Alloc() );
>+
>+ std::unordered_set<V, Hash, Equal, Alloc>
>+ s9(std::from_range, Range(a, a+9), 5, hf, eqf);
>+ VERIFY( eq(s9, {a, 9}) );
>+ VERIFY( s9.bucket_count() >= 5 );
>+ VERIFY( s9.get_allocator() == Alloc() );
>+ VERIFY( is_equal(s9.hash_function(), hf) );
>+ VERIFY( is_equal(s9.key_eq(), eqf) );
>+
>+ // LWG2713: there is no matching constructor
>+ // std::unordered_set<V, Hash, Equal, Alloc>
>+ // sa(std::from_range, Range(a, a+14), 1, alloc);
>+ // VERIFY( eq(sa1, {a, 9}) );
>+ // VERIFY( is_equal(sa1.hash_function(), Hash()) );
>+ // VERIFY( is_equal(sa1.key_eq(), Equal()) );
>+ // VERIFY( sa1.get_allocator() == alloc );
>+
>+ std::unordered_set<V, Hash, Equal, Alloc>
>+ sa2(std::from_range, Range(a, a+14), 2, alloc);
>+ VERIFY( eq(sa2, {a, 9}) );
>+ VERIFY( sa2.bucket_count() >= 2 );
>+ VERIFY( is_equal(sa2.hash_function(), Hash()) );
>+ VERIFY( is_equal(sa2.key_eq(), Equal()) );
>+ VERIFY( sa2.get_allocator() == alloc );
>+
>+ std::unordered_set<V, Hash, Equal, Alloc>
>+ sa3(std::from_range, Range(a, a+14), 3, hf, alloc);
>+ VERIFY( eq(sa3, {a, 9}) );
>+ VERIFY( sa3.bucket_count() >= 3 );
>+ VERIFY( is_equal(sa3.hash_function(), hf) );
>+ VERIFY( is_equal(sa3.key_eq(), Equal()) );
>+ VERIFY( sa3.get_allocator() == alloc );
>+
>+ std::unordered_set<V, Hash, Equal, Alloc>
>+ sa4(std::from_range, Range(a, a+14), 5, hf, eqf, alloc);
>+ VERIFY( eq(sa4, {a, 9}) );
>+ VERIFY( sa4.bucket_count() >= 5 );
>+ VERIFY( is_equal(sa4.hash_function(), hf) );
>+ VERIFY( is_equal(sa4.key_eq(), eqf) );
>+ VERIFY( sa4.get_allocator() == alloc );
>+}
>+
>+template<typename Range>
>+void
>+do_test_ahe()
>+{
>+ do_test<Range>(std::allocator<int>(),
>+ std::hash<int>(), std::equal_to<int>());
>+ do_test<Range>(std::allocator<int>(),
>+ StateHash{27}, StateEq{17});
>+ do_test<Range>(__gnu_test::uneq_allocator<int>(42),
>+ std::hash<int>(), std::equal_to<int>());
>+ do_test<Range>(__gnu_test::uneq_allocator<int>(42),
>+ StateHash{27}, StateEq{17});
>+}
>+
>+bool
>+test_ranges()
>+{
>+ using namespace __gnu_test;
>+
>+ do_test_ahe<test_forward_range<int>>();
>+ do_test_ahe<test_range_nocopy<int, input_iterator_wrapper_nocopy>>();
>+ do_test_ahe<test_forward_range<short>>();
>+
>+ return true;
>+}
>+
>+int main()
>+{
>+ test_ranges();
>+}
>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert_range.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert_range.cc
>new file mode 100644
>index 00000000000..9c74ac5f9b4
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert_range.cc
>@@ -0,0 +1,65 @@
>+// { dg-do run { target c++23 } }
>+
>+#include <algorithm>
>+#include <unordered_set>
>+#include <span>
>+#include <testsuite_allocator.h>
>+#include <testsuite_hooks.h>
>+#include <testsuite_iterators.h>
>+
>+template<typename Range, typename V>
>+constexpr void
>+do_test()
>+{
>+ // 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::unordered_set<V> const& l,
>+ std::span<T> r) {
>+ if (l.size() != r.size())
>+ return false;
>+
>+ return std::ranges::is_permutation(l, r);
>+ };
>+
>+ std::unordered_set<V> 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+14));
>+ VERIFY( eq(s, {a, 9}) );
>+}
>+
>+template<typename Range>
>+void
>+do_test_v()
>+{
>+ do_test<Range, int>();
>+}
>+
>+bool
>+test_ranges()
>+{
>+ using namespace __gnu_test;
>+
>+ do_test_v<test_forward_range<int>>();
>+ do_test_v<test_range_nocopy<int, input_iterator_wrapper_nocopy>>();
>+ do_test_v<test_forward_range<short>>();
>+
>+ return true;
>+}
>+
>+int main()
>+{
>+ test_ranges();
>+}
>--
>2.48.1
>
>
More information about the Libstdc++
mailing list