[PATCH v11] libstdc++: container heterogeneous insertion (P2363) [PR117402]
Jonathan Wakely
jwakely@redhat.com
Tue Mar 3 15:55:57 GMT 2026
On Fri, 27 Feb 2026 at 21:58 -0500, Nathan Myers wrote:
>Changes in v11
> - Delete #include, debug instrumentation that called abort.
> - Delete spurious DR comment text.
> - Delete unused _M_index_to_tr.
> - Un-de-duplicate lower/upper_bound apparatus, pending cleanup
> in gcc-17.
> - Regularize formal argument names (e.g. __pos -> __hint) for
> consistency and to match doxygen annotations.
> - Move ++after, --before iterator operations to separate
> statement for better clarity.
> - Improve tests.
> - Further improve, regularize doxygen annotation text.
> - Adjust Changelog entries to match.
>
>Changes in v10
> - Fix tests that had exercised non-heterogeneous insertion.
> - Test, handle inserting to empty tree.
> - Clean up and modernize doxygen annotations.
>
>Changes in v9:
> - Redo code path for new map<> and set<> insertion hinted
> overloads to correctly choose the place to operate on.
> - Document heterogeneous map operations.
> - Extend new map and set tests to exercise new code paths.
> - De-duplicate some code in bits/stl_tree.h.
>
>Changes in v8:
> - Test approximate key matching in map<>::insert_or_assign.
> - Give test functions meaningful names.
>
>Changes in v7:
> - Regularize comments on new #ifdefs ("C++26, no "P2363").
>
>Changes in v6:
> - More testing for op[] and at(): move-from key argument when
> and only when permitted.
>
> - Test op[] and at more: move-from key argument when and only
> when permitted.
>
>Changes in v5:
> - Fix typos in set/modifiers/hetero/insert.cc.
> - Fix chart in commit message.
>
>Changes in v4:
> - Rebase on committed P2077 erasures.
> - Remove conditional compilation on impl helpers in
> bits/stl_tree.h, hashtable.h, hashtable_policy.h.
> - Regularize ChangeLog format.
> - Test propagation of heterogeneous key's value category
> through to conversion to key_type.
> - Test propagation of variadic-arguments' value categories
> from try_emplace through to underlying constructors.
> - Regularize template argument name s/_Mapped/_Obj/.
>
>Changes in v3:
> - Make tests run, and pass.
> - Note added members in Changelog.
>
>Change in v2: fix remaining regression, SEGV in 92878_92947.cc.
>
>Implements P2353R5 "Extending associative containers with the
>remaining heterogeneous overloads". Adds overloads templated on
>heterogeneous key types for several members of associative
>containers, particularly insertions:
>
> /-- unordered --\
> set map mset mmap set map mset mmap
> @ . . . @ . . . insert
> . @ . . . @ . . op[], at, try_emplace,
> insert_or_assign
> . . . . @ @ @ @ bucket
>
>(Nothing is added to the multiset or multimap tree containers.)
>All the insert*() and try_emplace() members also get a hinted
>overload. The at() members get const and non-const overloads.
>
>The new overloads enforce concept __heterogeneous_tree_key or
>__heterogeneous_hash_key, as in P2077, to enforce that the
>function objects provided meet requirements, and that the key
>supplied is not an iterator or the native key. Insertions
>implicitly construct the required key_type object from the
>argument, by move where permitted.
>
>Doxygen annotations are improved and formal argument names
>made consistent with annotations and other functions.
>
>libstdc++-v3/ChangeLog:
> PR libstdc++/117402
> * include/bits/stl_map.h (operator[], at (2x), try_emplace (2x),
> insert_or_assign (2x)): Add overloads.
> Also, modernize doxygen text, regularize formal argument names.
> * include/bits/unordered_map.h (operator[], at (2x),
> try_emplace (2x), insert_or_assign (2x), bucket (2x)): Add overloads.
> * include/bits/stl_set.h (insert (2x)): Add overloads.
> Also, modernize doxygen text, regularize formal argument names.
> * include/bits/unordered_set.h (insert (2x), bucket (2x)): Add overloads.
> * include/bits/hashtable.h (_M_bucket_tr, _M_insert_tr): Define.
> * include/bits/hashtable_policy.h (_M_at_tr (2x)): Define.
> * include/bits/stl_tree.h (_M_emplace_here, _M_get_insert_unique_pos_tr,
> _M_get_insert_hint_unique_pos_tr): Define new heterogeneous insertion
> code path for set and map.
> * include/bits/version.def (associative_heterogeneous_insertion):
> Define.
> * include/bits/version.h: Regenerate.
> * include/std/map (__glibcxx_want_associative_heterogeneous_insertion):
> Define macro.
> * include/std/set: Same.
> * include/std/unordered_map: Same.
> * include/std/unordered_set: Same.
> * testsuite/23_containers/map/modifiers/hetero/insert.cc: New tests.
> * testsuite/23_containers/set/modifiers/hetero/insert.cc: Same.
> * testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc:
> Same.
> * testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc:
> Same.
> * testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc:
> Same.
> * testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc:
> Same.
>---
> libstdc++-v3/include/bits/hashtable.h | 27 +
> libstdc++-v3/include/bits/hashtable_policy.h | 26 +-
> libstdc++-v3/include/bits/stl_map.h | 695 +++++++------
> libstdc++-v3/include/bits/stl_set.h | 300 +++---
> libstdc++-v3/include/bits/stl_tree.h | 146 ++-
> libstdc++-v3/include/bits/unordered_map.h | 96 ++
> libstdc++-v3/include/bits/unordered_set.h | 32 +
> libstdc++-v3/include/bits/version.def | 8 +
> libstdc++-v3/include/bits/version.h | 10 +
> libstdc++-v3/include/std/map | 1 +
> libstdc++-v3/include/std/set | 1 +
> libstdc++-v3/include/std/unordered_map | 1 +
> libstdc++-v3/include/std/unordered_set | 1 +
> .../map/modifiers/hetero/insert.cc | 932 ++++++++++++++++++
> .../set/modifiers/hetero/insert.cc | 376 +++++++
> .../unordered_map/modifiers/hetero/insert.cc | 353 +++++++
> .../modifiers/hetero/insert.cc | 57 ++
> .../modifiers/hetero/insert.cc | 56 ++
> .../unordered_set/modifiers/hetero/insert.cc | 134 +++
> 19 files changed, 2827 insertions(+), 425 deletions(-)
> create mode 100644 libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc
>
>diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
>index 48695c013f3..f4211eba516 100644
>--- a/libstdc++-v3/include/bits/hashtable.h
>+++ b/libstdc++-v3/include/bits/hashtable.h
>@@ -700,6 +700,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> bucket(const key_type& __k) const
> { return _M_bucket_index(this->_M_hash_code(__k)); }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <typename _Kt>
>+ size_type
>+ _M_bucket_tr(const _Kt& __k) const
>+ { return _M_bucket_index(this->_M_hash_code_tr(__k)); }
>+#endif
>+
> local_iterator
> begin(size_type __bkt)
> {
>@@ -1097,6 +1104,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> std::pair<iterator, bool>
> try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
> {
>+ // Note we ignore the hint argument.
> __hash_code __code;
> size_type __bkt;
> if (auto __loc = _M_locate(__k))
>@@ -1117,6 +1125,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> __node._M_node = nullptr;
> return { __it, true };
> }
>+
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template<typename _Kt>
>+ std::pair<iterator, bool>
>+ _M_insert_tr(_Kt&& __k)
>+ {
>+ auto __loc = _M_locate_tr(__k);
>+ if (__loc)
>+ return { iterator(__loc), false };
>+
>+ _Scoped_node __node(
>+ this->_M_allocate_node(std::forward<_Kt>(__k)), this);
>+ auto __it = _M_insert_unique_node(
>+ __loc._M_bucket_index, __loc._M_hash_code, __node._M_node);
>+ __node._M_node = nullptr;
>+ return { __it, true };
>+ }
>+#endif
> #endif
>
> void
>@@ -2363,6 +2389,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> __node._M_node = nullptr;
> return { __pos, true };
> }
>+
> #pragma GCC diagnostic pop
>
> template<typename _Key, typename _Value, typename _Alloc,
>diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
>index 6d7bde1e785..79c36e4a02b 100644
>--- a/libstdc++-v3/include/bits/hashtable_policy.h
>+++ b/libstdc++-v3/include/bits/hashtable_policy.h
>@@ -872,6 +872,26 @@ namespace __detail
> __throw_out_of_range(__N("unordered_map::at"));
> return __ite->second;
> }
>+
>+ template <typename _Kt>
>+ mapped_type&
>+ _M_at_tr(const _Kt& __k)
>+ {
>+ auto __ite = static_cast<__hashtable*>(this)->_M_find_tr(__k);
>+ if (!__ite._M_cur)
>+ __throw_out_of_range(__N("unordered_map::at"));
>+ return __ite->second;
>+ }
>+
>+ template <typename _Kt>
>+ const mapped_type&
>+ _M_at_tr(const _Kt& __k) const
>+ {
>+ auto __ite = static_cast<const __hashtable*>(this)->_M_find_tr(__k);
>+ if (!__ite._M_cur)
>+ __throw_out_of_range(__N("unordered_map::at"));
>+ return __ite->second;
>+ }
> };
>
> template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
>@@ -1413,8 +1433,7 @@ namespace __detail
> template<typename _Kt>
> bool
> _M_key_equals_tr(const _Kt& __k,
>- const _Hash_node_value<_Value,
>- __hash_cached::value>& __n) const
>+ const _Hash_node_value<_Value, __hash_cached::value>& __n) const
> {
> static_assert(
> __is_invocable<const _Equal&, const _Kt&, const _Key&>{},
>@@ -1439,8 +1458,7 @@ namespace __detail
> template<typename _Kt>
> bool
> _M_equals_tr(const _Kt& __k, __hash_code __c,
>- const _Hash_node_value<_Value,
>- __hash_cached::value>& __n) const
>+ const _Hash_node_value<_Value, __hash_cached::value>& __n) const
> {
> if constexpr (__hash_cached::value)
> if (__c != __n._M_hash_code)
>diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
>index 4cb0c982c3d..a4bba07b52e 100644
>--- a/libstdc++-v3/include/bits/stl_map.h
>+++ b/libstdc++-v3/include/bits/stl_map.h
>@@ -330,11 +330,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>
>
> #if __cplusplus >= 201103L
>- /**
>- * The dtor only erases the elements, and note that if the elements
>- * themselves are pointers, the pointed-to memory is not touched in any
>- * way. Managing the pointer is the user's responsibility.
>- */
> ~map() = default;
> #endif
>
>@@ -383,45 +378,39 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return allocator_type(_M_t.get_allocator()); }
>
> // iterators
>+ ///@{
> /**
>- * Returns a read/write iterator that points to the first pair in the
>- * %map.
>+ * Returns a read/write iterator to the first pair element in the
>+ * %map, or end() if no such element exists.
Why are you doing all these doxygen changes in the same patch as the
heterogeneous insertions?!
The might be fine changes but they don't belong in this patch.
(And have you checked that the grouping with ///@{ actually works as
intended here? It doesn't always!)
> * Iteration is done in ascending order according to the keys.
> */
> iterator
> begin() _GLIBCXX_NOEXCEPT
> { return _M_t.begin(); }
>
>- /**
>- * Returns a read-only (constant) iterator that points to the first pair
>- * in the %map. Iteration is done in ascending order according to the
>- * keys.
>- */
> const_iterator
> begin() const _GLIBCXX_NOEXCEPT
> { return _M_t.begin(); }
>+ ///@}
>
>+ ///@{
> /**
>- * Returns a read/write iterator that points one past the last
>- * pair in the %map. Iteration is done in ascending order
>- * according to the keys.
>+ * Returns a read/write iterator to one past the last pair in the %map.
>+ * Iteration is done in ascending order according to the keys.
> */
> iterator
> end() _GLIBCXX_NOEXCEPT
> { return _M_t.end(); }
>
>- /**
>- * Returns a read-only (constant) iterator that points one past the last
>- * pair in the %map. Iteration is done in ascending order according to
>- * the keys.
>- */
> const_iterator
> end() const _GLIBCXX_NOEXCEPT
> { return _M_t.end(); }
>+ ///@}
>
>+ ///@{
> /**
>- * Returns a read/write reverse iterator that points to the last pair in
>- * the %map. Iteration is done in descending order according to the
>+ * Returns a read/write reverse iterator to the last pair in the %map.
>+ * Iteration is done in descending order according to the
> * keys.
> */
> reverse_iterator
>@@ -429,16 +418,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return _M_t.rbegin(); }
>
> /**
>- * Returns a read-only (constant) reverse iterator that points to the
>- * last pair in the %map. Iteration is done in descending order
>+ * Returns a read-only (constant) reverse iterator to the last pair
>+ * in the %map. Iteration is done in descending order
> * according to the keys.
> */
> const_reverse_iterator
> rbegin() const _GLIBCXX_NOEXCEPT
> { return _M_t.rbegin(); }
>+ ///@}
>
>+ ///@{
> /**
>- * Returns a read/write reverse iterator that points to one before the
>+ * Returns a read/write reverse iterator to one before the
> * first pair in the %map. Iteration is done in descending order
> * according to the keys.
> */
>@@ -446,18 +437,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> rend() _GLIBCXX_NOEXCEPT
> { return _M_t.rend(); }
>
>- /**
>- * Returns a read-only (constant) reverse iterator that points to one
>- * before the first pair in the %map. Iteration is done in descending
>- * order according to the keys.
>- */
> const_reverse_iterator
> rend() const _GLIBCXX_NOEXCEPT
> { return _M_t.rend(); }
>+ ///@}
>
> #if __cplusplus >= 201103L
> /**
>- * Returns a read-only (constant) iterator that points to the first pair
>+ * Returns a read-only (constant) iterator to the first pair
> * in the %map. Iteration is done in ascending order according to the
> * keys.
> */
>@@ -475,7 +462,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return _M_t.end(); }
>
> /**
>- * Returns a read-only (constant) reverse iterator that points to the
>+ * Returns a read-only (constant) reverse iterator to the
> * last pair in the %map. Iteration is done in descending order
> * according to the keys.
> */
>@@ -484,7 +471,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return _M_t.rbegin(); }
>
> /**
>- * Returns a read-only (constant) reverse iterator that points to one
>+ * Returns a read-only (constant) reverse iterator to one
> * before the first pair in the %map. Iteration is done in descending
> * order according to the keys.
> */
>@@ -511,16 +498,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> max_size() const _GLIBCXX_NOEXCEPT
> { return _M_t.max_size(); }
>
>+ ///@{
> // [23.3.1.2] element access
> /**
>- * @brief Subscript ( @c [] ) access to %map data.
>- * @param __k The key for which data should be retrieved.
>- * @return A reference to the data of the (key,data) %pair.
>+ * @brief Subscript ( @c [] ) access to a mapped value.
>+ * @param __k The key whose mapped value should be returned.
>+ * @return A reference to a mapped value whose key matches @a __k.
>+ *
>+ * Allows for easy lookup with the subscript ( @c [] ) operator.
>+ * Returns a reference to a value associated with the key. If no
>+ * matching element is present, an element is inserted that is
>+ * constructed from the key and a defaulted value.
> *
>- * Allows for easy lookup with the subscript ( @c [] )
>- * operator. Returns data associated with the key specified in
>- * subscript. If the key does not exist, a pair with that key
>- * is created using default values, which is then returned.
>+ * If a heterogeneous key matches a range of elements, the first is
>+ * chosen.
> *
> * Lookup requires logarithmic time.
> */
>@@ -560,14 +551,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> }
> #endif
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_tree_key<map> _Kt>
>+ mapped_type&
>+ operator[](_Kt&& __k)
>+ { return try_emplace(std::forward<_Kt>(__k)).first->second; }
>+#endif
>+ ///@}
>+
>+ ///@{
> // _GLIBCXX_RESOLVE_LIB_DEFECTS
> // DR 464. Suggestion for new member functions in standard containers.
> /**
>- * @brief Access to %map data.
>- * @param __k The key for which data should be retrieved.
>- * @return A reference to the data whose key is equivalent to @a __k, if
>- * such a data is present in the %map.
>- * @throw std::out_of_range If no such data is present.
>+ * @brief Access to a mapped value.
>+ * @param __k The key for which the mapped value should be retrieved.
>+ * @return A reference to the mapped value whose key matches @a __k,
>+ * if present.
>+ * @throw std::out_of_range If no matching key is present.
>+ *
>+ * If a heterogeneous key __k matches a range of elements, the
>+ * first is chosen.
> */
> mapped_type&
> at(const key_type& __k)
>@@ -578,6 +581,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> return (*__i).second;
> }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_tree_key<map> _Kt>
>+ mapped_type&
>+ at(const _Kt& __k)
>+ {
>+ iterator __i = lower_bound(__k);
>+ if (__i == end() || key_comp()(__k, (*__i).first))
>+ __throw_out_of_range(__N("map::at"));
>+ return (*__i).second;
>+ }
>+#endif
>+
> const mapped_type&
> at(const key_type& __k) const
> {
>@@ -587,23 +602,34 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> return (*__i).second;
> }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_tree_key<map> _Kt>
>+ const mapped_type&
>+ at(const _Kt& __k) const
>+ {
>+ const_iterator __i = lower_bound(__k);
>+ if (__i == end() || key_comp()(__k, (*__i).first))
>+ __throw_out_of_range(__N("map::at"));
>+ return (*__i).second;
>+ }
>+#endif
>+ ///@}
>+
> // modifiers
> #if __cplusplus >= 201103L
> /**
>- * @brief Attempts to build and insert a std::pair into the %map.
>+ * @brief Attempts to construct and insert a new element into the %map.
>+ * @param __args Arguments used to generate a new element (see
>+ * std::piecewise_contruct for passing arguments to each
>+ * part of the pair constructor).
>+ * @return A pair (iterator, bool) to the inserted or a matching
>+ * element already present, and reporting whether an element
>+ * was inserted.
> *
>- * @param __args Arguments used to generate a new pair instance (see
>- * std::piecewise_contruct for passing arguments to each
>- * part of the pair constructor).
>- *
>- * @return A pair, of which the first element is an iterator that points
>- * to the possibly inserted pair, and the second is a bool that
>- * is true if the pair was actually inserted.
>- *
>- * This function attempts to build and insert a (key, value) %pair into
>- * the %map.
>- * A %map relies on unique keys and thus a %pair is only inserted if its
>- * first element (the key) is not already present in the %map.
>+ * This function attempts to construct and insert a (key, value) %pair
>+ * element into the %map. If the key matches an element already present,
>+ * no element is constructed, and an iterator to the matching element
>+ * is returned instead.
> *
> * Insertion requires logarithmic time.
> */
>@@ -633,46 +659,63 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> }
>
> /**
>- * @brief Attempts to build and insert a std::pair into the %map.
>- *
>- * @param __pos An iterator that serves as a hint as to where the pair
>- * should be inserted.
>- * @param __args Arguments used to generate a new pair instance (see
>- * std::piecewise_contruct for passing arguments to each
>- * part of the pair constructor).
>- * @return An iterator that points to the element with key of the
>- * std::pair built from @a __args (may or may not be that
>- * std::pair).
>- *
>- * This function is not concerned about whether the insertion took place,
>- * and thus does not return a boolean like the single-argument emplace()
>- * does.
>- * Note that the first parameter is only a hint and can potentially
>- * improve the performance of the insertion process. A bad hint would
>- * cause no gains in efficiency.
>+ * @brief Attempts to construct and insert a new element into the %map.
>+ *
>+ * @param __hint An iterator hinting where the new element may be
>+ * inserted.
>+ * @param __args Arguments used to generate a element (see
>+ * std::piecewise_contruct for passing arguments to each part
>+ * of the element constructor).
>+ * @return An iterator to the element inserted, or to a matching element
>+ * already present.
>+ *
>+ * This function attempts to construct and insert a (key, value) %pair
>+ * element into the %map. If the key matches an element already present,
>+ * no element is constructed, and an iterator to the matching element
>+ * is returned instead.
>+ *
>+ * The __hint parameter is a hint that may improve performance if it
>+ * indicates a position adjacent to the final placement of the inserted
>+ * element, or of the matching element.
> *
> * See
> * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
> * for more on @a hinting.
> *
>- * Insertion requires logarithmic time (if the hint is not taken).
>+ * Insertion requires logarithmic time if the hint is not helpful.
> */
> template<typename... _Args>
> iterator
>- emplace_hint(const_iterator __pos, _Args&&... __args)
>+ emplace_hint(const_iterator __hint, _Args&&... __args)
> {
>- return _M_t._M_emplace_hint_unique(__pos,
>+ return _M_t._M_emplace_hint_unique(__hint,
> std::forward<_Args>(__args)...);
> }
> #endif
>
> #ifdef __glibcxx_node_extract // >= C++17
>- /// Extract a node.
>+ ///@{
>+ /**
>+ * @brief Attempts to extract an element from a %map.
>+ * @param __x Key of an element to be extracted.
>+ * @param __position Position of an element to extract.
>+ * @return A %node_type, which may be empty.
>+ *
>+ * This function extracts an element from the %map into a %node_type
>+ * object, which may be reinserted into this or another compatible
>+ * container without allocation. If __x does not match any element,
>+ * an empty node is returned.
>+ *
>+ * If a heterogeneous key __x matches a range of elements, the
>+ * first is extracted.
>+ *
>+ * Extraction by key requires logarithmic time.
>+ */
> node_type
>- extract(const_iterator __pos)
>+ extract(const_iterator __position)
> {
>- __glibcxx_assert(__pos != end());
>- return _M_t.extract(__pos);
>+ __glibcxx_assert(__position != end());
>+ return _M_t.extract(__position);
> }
>
> /// Extract a node.
>@@ -683,16 +726,49 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #ifdef __glibcxx_associative_heterogeneous_erasure // C++23
> template <__heterogeneous_tree_key<map> _Kt>
> node_type
>- extract(_Kt&& __key)
>- { return _M_t._M_extract_tr(__key); }
>+ extract(_Kt&& __x)
>+ { return _M_t._M_extract_tr(__x); }
> #endif
>+ ///@}
>
>- /// Re-insert an extracted node.
>+ /**
>+ * @brief Attempts to re-insert an element extracted from a %map.
>+ * @param __nh The element node to be reinserted
>+ * @return An %insert_return_type reporting whether the element
>+ * was inserted, and where.
>+ *
>+ * This function re-inserts a %node_type object extracted from a
>+ * compatible container into the %map if no element with a matching
>+ * key is already present. If insertion fails, the resulting iterator
>+ * points to the matching element. Inserting an empty %node_type
>+ * has no effect, reports failure, and yields the end() iterator.
>+ *
>+ * Insertion requires logarithmic time.
>+ */
> insert_return_type
> insert(node_type&& __nh)
> { return _M_t._M_reinsert_node_unique(std::move(__nh)); }
>
>- /// Re-insert an extracted node.
>+ /**
>+ * @brief Attempts to re-insert an element extracted from a %map.
>+ * @param __nh The element node to be reinserted
>+ * @param __hint Position expected to be adjacent to the placement
>+ * of the inserted node.
>+ * @return An %iterator reporting where the element was inserted,
>+ * or to the element already present.
>+ *
>+ * This function re-inserts a %node_type object extracted from a
>+ * compatible container into the %map if no element with a matching
>+ * key is already present. If insertion fails, the resulting iterator
>+ * points to the matching element. Inserting an empty %node_type
>+ * has no effect, and yields the end() iterator.
>+ *
>+ * An iterator may be passed as a hint that may improve performance
>+ * if it indicates a position adjacent to the final position of the
>+ * element, or the matching element.
>+ *
>+ * Insertion requires logarithmic time if the hint is not helpful.
>+ */
> iterator
> insert(const_iterator __hint, node_type&& __nh)
> { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
>@@ -700,6 +776,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> template<typename, typename>
> friend struct std::_Rb_tree_merge_helper;
>
>+ ///@{
>+ /**
>+ * @brief Attempts to merge elements from another container
>+ * @param __source The other container
>+ *
>+ * This function extracts all nodes from the argument container
>+ * and inserts those whose keys do not match any existing element,
>+ * discarding the rest. Of elements from a %multimap with matching
>+ * keys, only the first is inserted.
>+ */
> template<typename _Cmp2>
> void
> merge(map<_Key, _Tp, _Cmp2, _Alloc>& __source)
>@@ -725,26 +811,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> void
> merge(multimap<_Key, _Tp, _Cmp2, _Alloc>&& __source)
> { merge(__source); }
>+ ///@}
> #endif // C++17
>
> #ifdef __glibcxx_map_try_emplace // C++ >= 17 && HOSTED
>+ ///@{
> /**
>- * @brief Attempts to build and insert a std::pair into the %map.
>+ * @brief Attempts to build and insert a new element into the %map.
> *
>- * @param __k Key to use for finding a possibly existing pair in
>- * the map.
>- * @param __args Arguments used to generate the .second for a new pair
>- * instance.
>+ * @param __k A key used to check for an existing element in the map
>+ * and to construct the new element.
>+ * @param __args Arguments used to generate the mapped value for a new
>+ * element.
>+ * @return A pair (iterator, bool) to the inserted or a matching
>+ * element, and reporting whether insertion succeeded.
> *
>- * @return A pair, of which the first element is an iterator that points
>- * to the possibly inserted pair, and the second is a bool that
>- * is true if the pair was actually inserted.
>+ * This function attempts to build and insert a (key, value) element
>+ * into the %map. If the key matches an element already present in the
>+ * %map, failure is reported, no such element is constructed, and the
>+ * iterator returned indicates the existing element.
> *
>- * This function attempts to build and insert a (key, value) %pair into
>- * the %map.
>- * A %map relies on unique keys and thus a %pair is only inserted if its
>- * first element (the key) is not already present in the %map.
>- * If a %pair is not inserted, this function has no effect.
>+ * If a heterogeneous key __k matches a range of elements, an iterator
>+ * to the first is returned.
> *
> * Insertion requires logarithmic time.
> */
>@@ -781,32 +869,54 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> return {__i, false};
> }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_tree_key<map> _Kt, typename ..._Args>
>+ pair<iterator, bool>
>+ try_emplace(_Kt&& __k, _Args&&... __args)
>+ {
>+ iterator __i;
>+ auto [__left, __node] = _M_t._M_get_insert_unique_pos_tr(__k);
>+ if (__node)
>+ {
>+ __i = _M_t._M_emplace_here(__left == __node, __node,
>+ std::piecewise_construct,
>+ std::forward_as_tuple(std::forward<_Kt>(__k)),
>+ std::forward_as_tuple(std::forward<_Args>(__args)...));
>+ return { __i, true };
>+ }
>+ __i = iterator(__left);
>+ return { __i, false };
>+ }
>+#endif
>+ ///@}
>+
>+ ///@{
> /**
>- * @brief Attempts to build and insert a std::pair into the %map.
>- *
>- * @param __hint An iterator that serves as a hint as to where the
>- * pair should be inserted.
>- * @param __k Key to use for finding a possibly existing pair in
>- * the map.
>- * @param __args Arguments used to generate the .second for a new pair
>- * instance.
>- * @return An iterator that points to the element with key of the
>- * std::pair built from @a __args (may or may not be that
>- * std::pair).
>- *
>- * This function is not concerned about whether the insertion took place,
>- * and thus does not return a boolean like the single-argument
>- * try_emplace() does. However, if insertion did not take place,
>- * this function has no effect.
>- * Note that the first parameter is only a hint and can potentially
>- * improve the performance of the insertion process. A bad hint would
>- * cause no gains in efficiency.
>+ * @brief Attempts to build and insert a new element into the %map.
>+ *
>+ * @param __hint An iterator hinting where the new element may be
>+ * inserted.
>+ * @param __k A key used to check for an existing element in the map,
>+ * and as part of the new element.
>+ * @param __args Arguments used to construct the mapped value in a new
>+ * element.
>+ * @return An iterator to the inserted or a matching element.
>+ *
>+ * If no element with a matching key is present, constructs and inserts
>+ * an element; otherwise, this function has no effect.
>+ *
>+ * An iterator may be passed as a hint that may improve performance
>+ * if it indicates a position adjacent to the final position of the
>+ * element, or to the matching element.
> *
> * See
> * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
> * for more on @a hinting.
> *
>- * Insertion requires logarithmic time (if the hint is not taken).
>+ * If a heterogeneous key __k matches a range of elements, an iterator
>+ * to the first is returned.
>+ *
>+ * Insertion requires logarithmic time if the hint is not helpful.
> */
> template <typename... _Args>
> iterator
>@@ -845,18 +955,39 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> }
> #endif
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_tree_key<map> _Kt, typename ..._Args>
>+ iterator
>+ try_emplace(const_iterator __hint, _Kt&& __k, _Args&&... __args)
>+ {
>+ iterator __i;
>+ auto [__left, __node] =
>+ _M_t._M_get_insert_hint_unique_pos_tr(__hint, __k);
>+ if (__node)
>+ {
>+ __i = _M_t._M_emplace_here(__left == __node, __node,
>+ std::piecewise_construct,
>+ std::forward_as_tuple(std::forward<_Kt>(__k)),
>+ std::forward_as_tuple(std::forward<_Args>(__args)...));
>+ }
>+ else __i = iterator(__left);
>+ return __i;
>+ }
>+#endif
>+ ///@}
>+
>+ ///@{
> /**
>- * @brief Attempts to insert a std::pair into the %map.
>- * @param __x Pair to be inserted (see std::make_pair for easy
>- * creation of pairs).
>- *
>- * @return A pair, of which the first element is an iterator that
>- * points to the possibly inserted pair, and the second is
>- * a bool that is true if the pair was actually inserted.
>+ * @brief Attempts to insert a std::pair element into the %map.
>+ * @param __x The pair to be inserted.
>+ * @return A pair (iterator, bool) to the inserted element or a
>+ * matching element, and reporting whether the pair was
>+ * inserted.
> *
> * This function attempts to insert a (key, value) %pair into the %map.
>- * A %map relies on unique keys and thus a %pair is only inserted if its
>- * first element (the key) is not already present in the %map.
>+ * If an element matching the key part is already present, the function
>+ * has no effect, an iterator to the matching element is returned, and
>+ * failure is reported.
> *
> * Insertion requires logarithmic time.
> * @{
>@@ -896,7 +1027,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> return _M_t._M_emplace_unique(std::forward<_Pair>(__x));
> }
> #endif
>- /// @}
>+ ///@}
>
> #if __cplusplus >= 201103L
> /**
>@@ -929,50 +1060,46 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> }
> #endif
>
>+ ///@{
> /**
>- * @brief Attempts to insert a std::pair into the %map.
>- * @param __position An iterator that serves as a hint as to where the
>- * pair should be inserted.
>- * @param __x Pair to be inserted (see std::make_pair for easy creation
>- * of pairs).
>- * @return An iterator that points to the element with key of
>- * @a __x (may or may not be the %pair passed in).
>- *
>-
>- * This function is not concerned about whether the insertion
>- * took place, and thus does not return a boolean like the
>- * single-argument insert() does. Note that the first
>- * parameter is only a hint and can potentially improve the
>- * performance of the insertion process. A bad hint would
>- * cause no gains in efficiency.
>+ * @brief Attempts to insert a std::pair element into the %map.
>+ * @param __hint An iterator hinting where the new element may be
>+ * inserted.
>+ * @param __x Pair to be inserted.
>+ * @return An iterator to the element inserted, or to a matching
>+ * element already present.
>+ *
>+ * An iterator may be passed as a hint that may improve performance
>+ * if it indicates a position adjacent to the final position of the
>+ * element, or to the matching element.
> *
> * See
> * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
> * for more on @a hinting.
> *
>- * Insertion requires logarithmic time (if the hint is not taken).
>+ * Insertion requires logarithmic time if the hint is not helpful.
> * @{
> */
> iterator
> #if __cplusplus >= 201103L
>- insert(const_iterator __position, const value_type& __x)
>+ insert(const_iterator __hint, const value_type& __x)
> #else
>- insert(iterator __position, const value_type& __x)
>+ insert(iterator __hint, const value_type& __x)
> #endif
>- { return _M_t._M_insert_unique_(__position, __x); }
>+ { return _M_t._M_insert_unique_(__hint, __x); }
>
> #if __cplusplus >= 201103L
> // _GLIBCXX_RESOLVE_LIB_DEFECTS
> // 2354. Unnecessary copying when inserting into maps with braced-init
> iterator
>- insert(const_iterator __position, value_type&& __x)
>- { return _M_t._M_insert_unique_(__position, std::move(__x)); }
>+ insert(const_iterator __hint, value_type&& __x)
>+ { return _M_t._M_insert_unique_(__hint, std::move(__x)); }
>
> template<typename _Pair>
> __enable_if_t<is_constructible<value_type, _Pair>::value, iterator>
>- insert(const_iterator __position, _Pair&& __x)
>+ insert(const_iterator __hint, _Pair&& __x)
> {
>- return _M_t._M_emplace_hint_unique(__position,
>+ return _M_t._M_emplace_hint_unique(__hint,
> std::forward<_Pair>(__x));
> }
> #endif
>@@ -980,9 +1107,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>
> /**
> * @brief Template function that attempts to insert a range of elements.
>- * @param __first Iterator pointing to the start of the range to be
>- * inserted.
>- * @param __last Iterator pointing to the end of the range.
>+ * @param __first Iterator to the start of the range to be inserted.
>+ * @param __last Iterator to the end of the range.
> *
> * Complexity similar to that of the range constructor.
> */
>@@ -992,22 +1118,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { _M_t._M_insert_range_unique(__first, __last); }
>
> #if __cplusplus > 201402L
>+ ///@{
> /**
>- * @brief Attempts to insert or assign a std::pair into the %map.
>- * @param __k Key to use for finding a possibly existing pair in
>- * the map.
>- * @param __obj Argument used to generate the .second for a pair
>- * instance.
>- *
>- * @return A pair, of which the first element is an iterator that
>- * points to the possibly inserted pair, and the second is
>- * a bool that is true if the pair was actually inserted.
>+ * @brief Attempts to insert a new, or re-assign an existing, element.
>+ * @param __k Key to locate existing element in the %map, or to
>+ * construct a new element if none is found.
>+ * @param __obj Argument used to generate a mapped value.
>+ * @return A pair (iterator, bool) to the new element inserted or
>+ * existing element re-assigned, and reports whether a new
>+ * element was inserted.
> *
> * This function attempts to insert a (key, value) %pair into the %map.
>- * A %map relies on unique keys and thus a %pair is only inserted if its
>- * first element (the key) is not already present in the %map.
>- * If the %pair was already in the %map, the .second of the %pair
>- * is assigned from __obj.
>+ * If the key matches an existing element, that element's mapped value
>+ * is re-assigned from __obj instead, an iterator to it is returned,
>+ * and failure is reported.
>+ *
>+ * If a heterogeneous key __k matches a range of elements, an iterator
>+ * to the first is returned.
> *
> * Insertion requires logarithmic time.
> */
>@@ -1046,25 +1173,53 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> return {__i, false};
> }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_tree_key<map> _Kt, typename _Obj>
>+ pair<iterator, bool>
>+ insert_or_assign(_Kt&& __k, _Obj&& __obj)
>+ {
>+ iterator __i;
>+ auto [__left, __node] =_M_t._M_get_insert_unique_pos_tr(__k);
>+ if (__node)
>+ {
>+ __i = _M_t._M_emplace_here(__left == __node, __node,
>+ std::piecewise_construct,
>+ std::forward_as_tuple(std::forward<_Kt>(__k)),
>+ std::forward_as_tuple(std::forward<_Obj>(__obj)));
>+ return { __i, true };
>+ }
>+ __i = iterator(__left);
>+ (*__i).second = std::forward<_Obj>(__obj);
>+ return { __i, false };
>+ }
>+#endif
>+ ///@}
>+#endif
>+
>+#if __cplusplus > 201402L
>+ ///@{
> /**
>- * @brief Attempts to insert or assign a std::pair into the %map.
>- * @param __hint An iterator that serves as a hint as to where the
>- * pair should be inserted.
>- * @param __k Key to use for finding a possibly existing pair in
>- * the map.
>- * @param __obj Argument used to generate the .second for a pair
>- * instance.
>- *
>- * @return An iterator that points to the element with key of
>- * @a __x (may or may not be the %pair passed in).
>+ * @brief Attempts to insert a new, or re-assign an existing, element.
>+ * @param __hint An iterator hinting where the new element may be
>+ * inserted.
>+ * @param __k A key used to check for an existing element in the map
>+ * and to construct the new element.
>+ * @param __obj Argument used to generate the mapped value.
>+ * @return An iterator to the new element inserted or the matching
>+ * element re-assigned.
> *
> * This function attempts to insert a (key, value) %pair into the %map.
>- * A %map relies on unique keys and thus a %pair is only inserted if its
>- * first element (the key) is not already present in the %map.
>- * If the %pair was already in the %map, the .second of the %pair
>- * is assigned from __obj.
>+ * If the key matches an existing element, that element's mapped value
>+ * is re-assigned from __obj instead, and an iterator to it is returned.
> *
>- * Insertion requires logarithmic time.
>+ * An iterator may be passed as a hint that may improve performance
>+ * if it indicates a position adjacent to the final position of the
>+ * element, or to the matching element.
>+ *
>+ * If a heterogeneous key __k matches a range of elements, the first
>+ * is chosen.
>+ *
>+ * Insertion requires logarithmic time if the hint is not helpful.
> */
> template <typename _Obj>
> iterator
>@@ -1105,23 +1260,42 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> (*__i).second = std::forward<_Obj>(__obj);
> return __i;
> }
>+
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_tree_key<map> _Kt, typename _Obj>
>+ iterator
>+ insert_or_assign(const_iterator __hint, _Kt&& __k, _Obj&& __obj)
>+ {
>+ iterator __i;
>+ auto [__left, __node] =
>+ _M_t._M_get_insert_hint_unique_pos_tr(__hint, __k);
>+ if (__node)
>+ {
>+ return _M_t._M_emplace_here(__left == __node, __node,
>+ std::piecewise_construct,
>+ std::forward_as_tuple(std::forward<_Kt>(__k)),
>+ std::forward_as_tuple(std::forward<_Obj>(__obj)));
>+ }
>+ __i = iterator(__left);
>+ (*__i).second = std::forward<_Obj>(__obj);
>+ return __i;
>+ }
>+#endif
>+ ///@}
> #endif
>
> #if __cplusplus >= 201103L
>+ ///@{
> // _GLIBCXX_RESOLVE_LIB_DEFECTS
> // DR 130. Associative erase should return an iterator.
> /**
> * @brief Erases an element from a %map.
>- * @param __position An iterator pointing to the element to be erased.
>- * @return An iterator pointing to the element immediately following
>- * @a position prior to the element being erased. If no such
>- * element exists, end() is returned.
>+ * @param __position An iterator to the element to be erased.
>+ * @return An iterator to the element immediately following the
>+ * element erased, or end().
> *
> * This function erases an element, pointed to by the given
>- * iterator, from a %map. Note that this function only erases
>- * the element, and that if the element is itself a pointer,
>- * the pointed-to memory is not touched in any way. Managing
>- * the pointer is the user's responsibility.
>+ * iterator, from a %map.
> *
> * @{
> */
>@@ -1134,17 +1308,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> iterator
> erase(iterator __position)
> { return _M_t.erase(__position); }
>- /// @}
> #else
> /**
> * @brief Erases an element from a %map.
>- * @param __position An iterator pointing to the element to be erased.
>+ * @param __position An iterator to the element to be erased.
> *
> * This function erases an element, pointed to by the given
>- * iterator, from a %map. Note that this function only erases
>- * the element, and that if the element is itself a pointer,
>- * the pointed-to memory is not touched in any way. Managing
>- * the pointer is the user's responsibility.
>+ * iterator, from a %map.
> */
> void
> erase(iterator __position)
>@@ -1153,24 +1323,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>
> ///@{
> /**
>- * @brief Erases elements according to the provided key.
>+ * @brief Erases elements that match a key.
> * @param __x Key of element to be erased.
>- * @return The number of elements erased.
>+ * @return The number of elements matched and erased.
> *
>- * This function erases all the elements located by the given key from
>+ * This function erases elements matching the given key from
> * a %map.
>- * Note that this function only erases the element, and that if
>- * the element is itself a pointer, the pointed-to memory is not touched
>- * in any way. Managing the pointer is the user's responsibility.
>+ *
>+ * If __x is a heterogeneous key, more than one element may
>+ * be erased.
> */
> size_type
> erase(const key_type& __x)
> { return _M_t._M_erase_unique(__x); }
>
> #ifdef __glibcxx_associative_heterogeneous_erasure // C++23
>- // Note that for some types _Kt this may erase more than
>- // one element, such as if _Kt::operator< checks only part
>- // of the key.
> template <__heterogeneous_tree_key<map> _Kt>
> size_type
> erase(_Kt&& __x)
>@@ -1183,16 +1350,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> // DR 130. Associative erase should return an iterator.
> /**
> * @brief Erases a [first,last) range of elements from a %map.
>- * @param __first Iterator pointing to the start of the range to be
>- * erased.
>- * @param __last Iterator pointing to the end of the range to
>- * be erased.
>+ * @param __first Iterator to the start of the range to be erased.
>+ * @param __last Iterator to the end of the range to be erased.
> * @return The iterator @a __last.
> *
> * This function erases a sequence of elements from a %map.
>- * Note that this function only erases the element, and that if
>- * the element is itself a pointer, the pointed-to memory is not touched
>- * in any way. Managing the pointer is the user's responsibility.
> */
> iterator
> erase(const_iterator __first, const_iterator __last)
>@@ -1200,15 +1362,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #else
> /**
> * @brief Erases a [__first,__last) range of elements from a %map.
>- * @param __first Iterator pointing to the start of the range to be
>- * erased.
>- * @param __last Iterator pointing to the end of the range to
>- * be erased.
>+ * @param __first Iterator to the start of the range to be erased.
>+ * @param __last Iterator to the end of the range to be erased.
> *
> * This function erases a sequence of elements from a %map.
>- * Note that this function only erases the element, and that if
>- * the element is itself a pointer, the pointed-to memory is not touched
>- * in any way. Managing the pointer is the user's responsibility.
> */
> void
> erase(iterator __first, iterator __last)
>@@ -1234,10 +1391,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { _M_t.swap(__x._M_t); }
>
> /**
>- * Erases all elements in a %map. Note that this function only
>- * erases the elements, and that if the elements themselves are
>- * pointers, the pointed-to memory is not touched in any way.
>- * Managing the pointer is the user's responsibility.
>+ * Erases all elements in a %map.
> */
> void
> clear() _GLIBCXX_NOEXCEPT
>@@ -1266,13 +1420,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> /**
> * @brief Tries to locate an element in a %map.
> * @param __x Key of (key, value) %pair to be located.
>- * @return Iterator pointing to sought-after element, or end() if not
>- * found.
>+ * @return Iterator to a matching element, or end().
> *
>- * This function takes a key and tries to locate the element with which
>- * the key matches. If successful the function returns an iterator
>- * pointing to the sought after %pair. If unsuccessful it returns the
>- * past-the-end ( @c end() ) iterator.
>+ * This function locates the element that matches the key, returning
>+ * an iterator to the matching element. If unsuccessful, it returns
>+ * the past-the-end ( @c end() ) iterator.
> */
>
> iterator
>@@ -1285,20 +1437,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
> { return _M_t._M_find_tr(__x); }
> #endif
>- ///@}
>-
>- ///@{
>- /**
>- * @brief Tries to locate an element in a %map.
>- * @param __x Key of (key, value) %pair to be located.
>- * @return Read-only (constant) iterator pointing to sought-after
>- * element, or end() if not found.
>- *
>- * This function takes a key and tries to locate the element with which
>- * the key matches. If successful the function returns a constant
>- * iterator pointing to the sought after %pair. If unsuccessful it
>- * returns the past-the-end ( @c end() ) iterator.
>- */
>
> const_iterator
> find(const key_type& __x) const
>@@ -1318,8 +1456,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> * @param __x Key of (key, value) pairs to be located.
> * @return Number of elements with specified key.
> *
>- * This function only makes sense for multimaps; for map the result will
>- * either be 0 (not present) or 1 (present).
>+ * With a regular key this function returns only 0 or 1, but
>+ * a heterogeneous key may match more than one element.
> */
> size_type
> count(const key_type& __x) const
>@@ -1356,13 +1494,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> /**
> * @brief Finds the beginning of a subsequence matching given key.
> * @param __x Key of (key, value) pair to be located.
>- * @return Iterator pointing to first element equal to or greater
>- * than key, or end().
>+ * @return Iterator to first element equal to or greater than key,
>+ * or end().
> *
>- * This function returns the first element of a subsequence of elements
>- * that matches the given key. If unsuccessful it returns an iterator
>- * pointing to the first element that has a greater value than given key
>- * or end() if no such element exists.
>+ * This function locates the least element that matches the given key,
>+ * or if none then the first element of greater value, or end() if
>+ * no such element exists.
> */
> iterator
> lower_bound(const key_type& __x)
>@@ -1375,20 +1512,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
> { return iterator(_M_t._M_lower_bound_tr(__x)); }
> #endif
>- ///@}
>-
>- ///@{
>- /**
>- * @brief Finds the beginning of a subsequence matching given key.
>- * @param __x Key of (key, value) pair to be located.
>- * @return Read-only (constant) iterator pointing to first element
>- * equal to or greater than key, or end().
>- *
>- * This function returns the first element of a subsequence of elements
>- * that matches the given key. If unsuccessful it returns an iterator
>- * pointing to the first element that has a greater value than given key
>- * or end() if no such element exists.
>- */
> const_iterator
> lower_bound(const key_type& __x) const
> { return _M_t.lower_bound(__x); }
>@@ -1406,8 +1529,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> /**
> * @brief Finds the end of a subsequence matching given key.
> * @param __x Key of (key, value) pair to be located.
>- * @return Iterator pointing to the first element
>- * greater than key, or end().
>+ * @return Iterator to the first element greater than key, or end().
>+ *
>+ * This function locates the least element with a key greater than
>+ * the argument key. It yields end() if no such element exists.
> */
> iterator
> upper_bound(const key_type& __x)
>@@ -1420,15 +1545,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
> { return iterator(_M_t._M_upper_bound_tr(__x)); }
> #endif
>- ///@}
>
>- ///@{
>- /**
>- * @brief Finds the end of a subsequence matching given key.
>- * @param __x Key of (key, value) pair to be located.
>- * @return Read-only (constant) iterator pointing to first iterator
>- * greater than key, or end().
>- */
> const_iterator
> upper_bound(const key_type& __x) const
> { return _M_t.upper_bound(__x); }
>@@ -1444,10 +1561,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>
> ///@{
> /**
>- * @brief Finds a subsequence matching given key.
>+ * @brief Finds a subsequence matching a key.
> * @param __x Key of (key, value) pairs to be located.
>- * @return Pair of iterators that possibly points to the subsequence
>- * matching given key.
>+ * @return Pair of iterators spanning the subsequence matching
>+ * given key.
> *
> * This function is equivalent to
> * @code
>@@ -1456,7 +1573,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> * @endcode
> * (but is faster than making the calls separately).
> *
>- * This function probably only makes sense for multimaps.
>+ * Normally the range will span at most one element. For a
>+ * heterogeneous key, the matched range may be longer.
> */
> std::pair<iterator, iterator>
> equal_range(const key_type& __x)
>@@ -1469,24 +1587,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
> { return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
> #endif
>- ///@}
>
>- ///@{
>- /**
>- * @brief Finds a subsequence matching given key.
>- * @param __x Key of (key, value) pairs to be located.
>- * @return Pair of read-only (constant) iterators that possibly points
>- * to the subsequence matching given key.
>- *
>- * This function is equivalent to
>- * @code
>- * std::make_pair(c.lower_bound(val),
>- * c.upper_bound(val))
>- * @endcode
>- * (but is faster than making the calls separately).
>- *
>- * This function probably only makes sense for multimaps.
>- */
> std::pair<const_iterator, const_iterator>
> equal_range(const key_type& __x) const
> { return _M_t.equal_range(__x); }
>diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
>index d3a4c089110..13afb8936f8 100644
>--- a/libstdc++-v3/include/bits/stl_set.h
>+++ b/libstdc++-v3/include/bits/stl_set.h
>@@ -298,11 +298,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { 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
>- * way. Managing the pointer is the user's responsibility.
>- */
> ~set() = default;
> #endif
>
>@@ -361,7 +356,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return allocator_type(_M_t.get_allocator()); }
>
> /**
>- * Returns a read-only (constant) iterator that points to the first
>+ * Returns a read-only (constant) iterator to the first
> * element in the %set. Iteration is done in ascending order according
> * to the keys.
> */
>@@ -370,7 +365,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return _M_t.begin(); }
>
> /**
>- * Returns a read-only (constant) iterator that points one past the last
>+ * Returns a read-only (constant) iterator to one past the last
> * element in the %set. Iteration is done in ascending order according
> * to the keys.
> */
>@@ -379,7 +374,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return _M_t.end(); }
>
> /**
>- * Returns a read-only (constant) iterator that points to the last
>+ * Returns a read-only (constant) iterator to the last
> * element in the %set. Iteration is done in descending order according
> * to the keys.
> */
>@@ -388,7 +383,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return _M_t.rbegin(); }
>
> /**
>- * Returns a read-only (constant) reverse iterator that points to the
>+ * Returns a read-only (constant) reverse iterator to the
> * last pair in the %set. Iteration is done in descending order
> * according to the keys.
> */
>@@ -398,7 +393,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>
> #if __cplusplus >= 201103L
> /**
>- * Returns a read-only (constant) iterator that points to the first
>+ * Returns a read-only (constant) iterator to the first
> * element in the %set. Iteration is done in ascending order according
> * to the keys.
> */
>@@ -407,7 +402,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return _M_t.begin(); }
>
> /**
>- * Returns a read-only (constant) iterator that points one past the last
>+ * Returns a read-only (constant) iterator to one past the last
> * element in the %set. Iteration is done in ascending order according
> * to the keys.
> */
>@@ -416,7 +411,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return _M_t.end(); }
>
> /**
>- * Returns a read-only (constant) iterator that points to the last
>+ * Returns a read-only (constant) iterator to the last
> * element in the %set. Iteration is done in descending order according
> * to the keys.
> */
>@@ -425,7 +420,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> { return _M_t.rbegin(); }
>
> /**
>- * Returns a read-only (constant) reverse iterator that points to the
>+ * Returns a read-only (constant) reverse iterator to the
> * last pair in the %set. Iteration is done in descending order
> * according to the keys.
> */
>@@ -472,13 +467,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> /**
> * @brief Attempts to build and insert an element into the %set.
> * @param __args Arguments used to generate an element.
>- * @return A pair, of which the first element is an iterator that points
>- * to the possibly inserted element, and the second is a bool
>- * that is true if the element was actually inserted.
>+ * @return A pair (iterator, bool) to the inserted or matched element,
>+ * and reporting whether an element was inserted.
> *
>- * This function attempts to build and insert an element into the %set.
>- * A %set relies on unique keys and thus an element is only inserted if
>- * it is not already present in the %set.
>+ * This function attempts to construct and insert an element into the
>+ * %set. If the a matching element is already present, the function
>+ * has no effect.
> *
> * Insertion requires logarithmic time.
> */
>@@ -489,44 +483,45 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>
> /**
> * @brief Attempts to insert an element into the %set.
>- * @param __pos An iterator that serves as a hint as to where the
>- * element should be inserted.
>+ * @param __hint An iterator hinting where the element may be inserted.
> * @param __args Arguments used to generate the element to be
> * inserted.
>- * @return An iterator that points to the element with key equivalent to
>- * the one generated from @a __args (may or may not be the
>- * element itself).
>+ * @return An iterator to the inserted or matching element.
>+ *
>+ * This function attempts to construct and insert an element into the
>+ * %set. If a matching element is already present, the function
>+ * has no effect.
> *
>- * This function is not concerned about whether the insertion took place,
>- * and thus does not return a boolean like the single-argument emplace()
>- * does. Note that the first parameter is only a hint and can
>- * potentially improve the performance of the insertion process. A bad
>- * hint would cause no gains in efficiency.
>+ * An iterator may be passed as a hint that may improve performance
>+ * if it indicates a position adjacent to the final position of the
>+ * element, or the matching element.
> *
> * For more on @a hinting, see:
> * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
> *
>- * Insertion requires logarithmic time (if the hint is not taken).
>+ * Insertion requires logarithmic time if the hint is not helpful.
> */
> template<typename... _Args>
> iterator
>- emplace_hint(const_iterator __pos, _Args&&... __args)
>+ emplace_hint(const_iterator __hint, _Args&&... __args)
> {
>- return _M_t._M_emplace_hint_unique(__pos,
>+ return _M_t._M_emplace_hint_unique(__hint,
> std::forward<_Args>(__args)...);
> }
> #endif
>
>+ ///@{
> /**
> * @brief Attempts to insert an element into the %set.
> * @param __x Element to be inserted.
>- * @return A pair, of which the first element is an iterator that points
>- * to the possibly inserted element, and the second is a bool
>- * that is true if the element was actually inserted.
>+ * @return A pair (iterator, bool) to the inserted or matched element,
>+ * and reporting if an element was actually inserted.
>+ *
>+ * This function attempts to insert an element into the %set.
>+ * If a matching element is already present, there is no effect.
> *
>- * This function attempts to insert an element into the %set. A %set
>- * relies on unique keys and thus an element is only inserted if it is
>- * not already present in the %set.
>+ * If a heterogeneous key __x matches a range of elements, an iterator
>+ * to the first is returned.
> *
> * Insertion requires logarithmic time.
> */
>@@ -548,43 +543,78 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> }
> #endif
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_tree_key<set> _Kt>
>+ pair<iterator, bool>
>+ insert(_Kt&& __k)
>+ {
>+ auto [__left, __node] =_M_t._M_get_insert_unique_pos_tr(__k);
>+ if (__node)
>+ {
>+ iterator __i = _M_t._M_emplace_here(
>+ (__left == __node), __node, std::forward<_Kt>(__k));
>+ return { __i, true };
>+ }
>+ return { iterator(__left), false };
>+ }
>+#endif
>+ ///@}
>+
>+ ///@{
> /**
> * @brief Attempts to insert an element into the %set.
>- * @param __position An iterator that serves as a hint as to where the
>- * element should be inserted.
>+ * @param __hint An iterator hinting where the element may be inserted.
> * @param __x Element to be inserted.
>- * @return An iterator that points to the element with key of
>- * @a __x (may or may not be the element passed in).
>+ * @return An iterator to the inserted or matching element.
>+ *
>+ * This function attempts to insert an element into the %set.
>+ * If a matching element is already present, there is no effect.
> *
>- * This function is not concerned about whether the insertion took place,
>- * and thus does not return a boolean like the single-argument insert()
>- * does. Note that the first parameter is only a hint and can
>- * potentially improve the performance of the insertion process. A bad
>- * hint would cause no gains in efficiency.
>+ * An iterator may be passed as a hint that may improve performance
>+ * if it indicates a position adjacent to the final position of the
>+ * element, or the matching element.
> *
> * For more on @a hinting, see:
> * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
> *
>- * Insertion requires logarithmic time (if the hint is not taken).
>+ * If a heterogeneous key __k matches a range of elements, an iterator
>+ * to the first is returned.
>+ *
>+ * Insertion requires logarithmic time if the hint or is not helpful.
> */
> iterator
>- insert(const_iterator __position, const value_type& __x)
>- { return _M_t._M_insert_unique_(__position, __x); }
>+ insert(const_iterator __hint, const value_type& __x)
>+ { return _M_t._M_insert_unique_(__hint, __x); }
>
> #if __cplusplus >= 201103L
> iterator
>- insert(const_iterator __position, value_type&& __x)
>- { return _M_t._M_insert_unique_(__position, std::move(__x)); }
>+ insert(const_iterator __hint, value_type&& __x)
>+ { return _M_t._M_insert_unique_(__hint, std::move(__x)); }
>+#endif
>+
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_tree_key<set> _Kt>
>+ iterator
>+ insert(const_iterator __hint, _Kt&& __k)
>+ {
>+ auto [__left, __node] =
>+ _M_t._M_get_insert_hint_unique_pos_tr(__hint, __k);
>+ if (__node)
>+ return _M_t._M_emplace_here(
>+ (__left == __node), __node, std::forward<_Kt>(__k));
>+ else
>+ return iterator(__left);
>+ }
> #endif
>+ ///@}
>
> /**
> * @brief A template function that attempts to insert a range
> * of elements.
>- * @param __first Iterator pointing to the start of the range to be
>- * inserted.
>- * @param __last Iterator pointing to the end of the range.
>+ * @param __first Iterator to the start of the range to be inserted.
>+ * @param __last Iterator to the end of the range.
> *
>- * Complexity similar to that of the range constructor.
>+ * Complexity is similar to that of the range constructor.
> */
> template<typename _InputIterator>
> void
>@@ -597,7 +627,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> * @param __l A std::initializer_list<value_type> of elements
> * to be inserted.
> *
>- * Complexity similar to that of the range constructor.
>+ * Complexity is similar to that of the range constructor.
> */
> void
> insert(initializer_list<value_type> __l)
>@@ -627,12 +657,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #endif
>
> #ifdef __glibcxx_node_extract // >= C++17
>+ ///@{
>+ /**
>+ * @brief Attempts to extract an element from a %set.
>+ * @param __x Key of an element to be extracted.
>+ * @param __position Position of an element to extract.
>+ * @return A %node_type, which may be empty.
>+ *
>+ * This function extracts an element from the %set into a %node_type
>+ * object, which may be reinserted into a compatible container without
>+ * allocation. If no element matches __x, an empty node is returned.
>+ *
>+ * If a heterogeneous key __x matches a range of elements, the
>+ * first is extracted.
>+ *
>+ * Extraction by key requires logarithmic time.
>+ */
>+
> /// Extract a node.
> node_type
>- extract(const_iterator __pos)
>+ extract(const_iterator __position)
> {
>- __glibcxx_assert(__pos != end());
>- return _M_t.extract(__pos);
>+ __glibcxx_assert(__position != end());
>+ return _M_t.extract(__position);
> }
>
> /// Extract a node.
>@@ -643,10 +690,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #ifdef __glibcxx_associative_heterogeneous_erasure // C++23
> template <__heterogeneous_tree_key<set> _Kt>
> node_type
>- extract(_Kt&& __key)
>- { return _M_t._M_extract_tr(__key); }
>+ extract(_Kt&& __x)
>+ { return _M_t._M_extract_tr(__x); }
> #endif
>+ ///@}
>
>+ ///@{
>+ /**
>+ * @brief Attempts to re-insert an element extracted from a %set.
>+ * @param __nh The element node to be reinserted
>+ * @param __hint An iterator hinting where the element may be inserted.
>+ * @return An %insert_return_type reporting whether the element
>+ * was inserted, and where.
>+ *
>+ * This function re-inserts a %node_type object extracted from a
>+ * compatible container into the %set. An iterator pointing adjacent
>+ * to the final position of the element may be passed as a hint to
>+ * improve performance. If insertion fails, the resulting iterator
>+ * indicates the matching element. Inserting an empty %node_type
>+ * has no effect.
>+ *
>+ * Insertion requires logarithmic time if the hint is not provided
>+ * or is not helpful.
>+ */
> /// Re-insert an extracted node.
> insert_return_type
> insert(node_type&& __nh)
>@@ -656,6 +722,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> iterator
> insert(const_iterator __hint, node_type&& __nh)
> { return _M_t._M_reinsert_node_hint_unique(__hint, std::move(__nh)); }
>+ ///@}
>
> template<typename, typename>
> friend struct std::_Rb_tree_merge_helper;
>@@ -692,16 +759,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> // DR 130. Associative erase should return an iterator.
> /**
> * @brief Erases an element from a %set.
>- * @param __position An iterator pointing to the element to be erased.
>- * @return An iterator pointing to the element immediately following
>+ * @param __position An iterator to the element to be erased.
>+ * @return An iterator to the element immediately following
> * @a __position prior to the element being erased. If no such
> * element exists, end() is returned.
> *
>- * This function erases an element, pointed to by the given iterator,
>- * from a %set. Note that this function only erases the element, and
>- * that if the element is itself a pointer, the pointed-to memory is not
>- * touched in any way. Managing the pointer is the user's
>- * responsibility.
>+ * This function erases the element pointed to by the given iterator
>+ * from a %set. Erasing end() has undefined behavior.
> */
> _GLIBCXX_ABI_TAG_CXX11
> iterator
>@@ -710,60 +774,53 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #else
> /**
> * @brief Erases an element from a %set.
>- * @param position An iterator pointing to the element to be erased.
>+ * @param position An iterator the element to be erased.
> *
>- * This function erases an element, pointed to by the given iterator,
>- * from a %set. Note that this function only erases the element, and
>- * that if the element is itself a pointer, the pointed-to memory is not
>- * touched in any way. Managing the pointer is the user's
>- * responsibility.
>+ * This function erases an element pointed to by the given iterator
>+ * from a %set. Erasing end() has undefined behavior.
> */
> void
> erase(iterator __position)
> { _M_t.erase(__position); }
> #endif
>
>+ //@{
> /**
> * @brief Erases elements according to the provided key.
> * @param __x Key of element to be erased.
> * @return The number of elements erased.
> *
>- * This function erases all the elements located by the given key from
>- * a %set.
>- * Note that this function only erases the element, and that if
>- * the element is itself a pointer, the pointed-to memory is not touched
>- * in any way. Managing the pointer is the user's responsibility.
>+ * This function erases elements located by the given key from a %set.
>+ * Erasing with a key that does not match an element has no effect.
>+ * If a heterogeneous key matches a range of elements, all are
>+ * erased.
>+ *
>+ * Erasing by key requires logarithmic time.
> */
> size_type
> erase(const key_type& __x)
> { return _M_t._M_erase_unique(__x); }
>
> #ifdef __glibcxx_associative_heterogeneous_erasure // C++23
>- // Note that for some types _Kt this may erase more than
>- // one element, such as if _Kt::operator< checks only part
>- // of the key.
> template <__heterogeneous_tree_key<set> _Kt>
> size_type
> erase(_Kt&& __key)
> { return _M_t._M_erase_tr(__key); }
> #endif
>+ ///@}
>
> #if __cplusplus >= 201103L
> // _GLIBCXX_RESOLVE_LIB_DEFECTS
> // DR 130. Associative erase should return an iterator.
>+ ///@{
> /**
> * @brief Erases a [__first,__last) range of elements from a %set.
>- * @param __first Iterator pointing to the start of the range to be
>- * erased.
>+ * @param __first Iterator to the start of the range to be erased.
>
>- * @param __last Iterator pointing to the end of the range to
>- * be erased.
>+ * @param __last Iterator to the end of the range to be erased.
> * @return The iterator @a __last.
> *
> * This function erases a sequence of elements from a %set.
>- * Note that this function only erases the element, and that if
>- * the element is itself a pointer, the pointed-to memory is not touched
>- * in any way. Managing the pointer is the user's responsibility.
> */
> _GLIBCXX_ABI_TAG_CXX11
> iterator
>@@ -772,26 +829,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #else
> /**
> * @brief Erases a [first,last) range of elements from a %set.
>- * @param __first Iterator pointing to the start of the range to be
>- * erased.
>- * @param __last Iterator pointing to the end of the range to
>- * be erased.
>+ * @param __first Iterator to the start of the range to be erased.
>+ * @param __last Iterator to the end of the range to be erased.
> *
> * This function erases a sequence of elements from a %set.
>- * Note that this function only erases the element, and that if
>- * the element is itself a pointer, the pointed-to memory is not touched
>- * in any way. Managing the pointer is the user's responsibility.
> */
> void
> erase(iterator __first, iterator __last)
> { _M_t.erase(__first, __last); }
> #endif
>+ ///@}
>
> /**
>- * Erases all elements in a %set. Note that this function only erases
>- * the elements, and that if the elements themselves are pointers, the
>- * pointed-to memory is not touched in any way. Managing the pointer is
>- * the user's responsibility.
>+ * Erases all elements in a %set.
> */
> void
> clear() _GLIBCXX_NOEXCEPT
>@@ -805,8 +855,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> * @param __x Element to located.
> * @return Number of elements with specified key.
> *
>- * This function only makes sense for multisets; for set the result will
>- * either be 0 (not present) or 1 (present).
>+ * With a regular key this function returns only 0 (not present)
>+ * or 1 (present), but a heterogeneous key may match more than
>+ * one element.
> */
> size_type
> count(const key_type& __x) const
>@@ -826,7 +877,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> /**
> * @brief Finds whether an element with the given key exists.
> * @param __x Key of elements to be located.
>- * @return True if there is an element with the specified key.
>+ * @return True if there is an element that matches the key.
>+ *
>+ * Requires logarithmic time.
> */
> bool
> contains(const key_type& __x) const
>@@ -846,13 +899,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> /**
> * @brief Tries to locate an element in a %set.
> * @param __x Element to be located.
>- * @return Iterator pointing to sought-after element, or end() if not
>- * found.
>+ * @return Iterator to the matched element, or end().
>+ *
>+ * This function tries to locate an element which the argument
>+ * key __x matches. On success the function returns an iterator
>+ * to that element; otherwise, it returns the past-the-end
>+ * ( @c end() ) iterator.
>+ *
>+ * If a heterogeneous key __x matches a range of elements, the
>+ * first is chosen.
> *
>- * This function takes a key and tries to locate the element with which
>- * the key matches. If successful the function returns an iterator
>- * pointing to the sought after element. If unsuccessful it returns the
>- * past-the-end ( @c end() ) iterator.
>+ * Requires logarithmic time.
> */
> iterator
> find(const key_type& __x)
>@@ -879,15 +936,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>
> ///@{
> /**
>- * @brief Finds the beginning of a subsequence matching given key.
>+ * @brief Finds the first element that matches or exceeds the given key.
> * @param __x Key to be located.
>- * @return Iterator pointing to first element equal to or greater
>+ * @return Iterator to the first element equal to or greater
> * than key, or end().
> *
>- * This function returns the first element of a subsequence of elements
>- * that matches the given key. If unsuccessful it returns an iterator
>- * pointing to the first element that has a greater value than given key
>- * or end() if no such element exists.
>+ * This function returns the first element that matches, or if none,
>+ * that that exceeds the given key, or end() if no such element exists.
>+ * The result used as a hint may improve performance when inserting
>+ * the key.
> */
> iterator
> lower_bound(const key_type& __x)
>@@ -914,10 +971,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>
> ///@{
> /**
>- * @brief Finds the end of a subsequence matching given key.
>+ * @brief Finds the first element that exceeds the given key.
> * @param __x Key to be located.
>- * @return Iterator pointing to the first element
>- * greater than key, or end().
>+ * @return Iterator to the first element greater than key, or end().
> */
> iterator
> upper_bound(const key_type& __x)
>@@ -946,8 +1002,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> /**
> * @brief Finds a subsequence matching given key.
> * @param __x Key to be located.
>- * @return Pair of iterators that possibly points to the subsequence
>- * matching given key.
>+ * @return Pair of iterators that spans the elements matching the key.
> *
> * This function is equivalent to
> * @code
>@@ -956,7 +1011,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> * @endcode
> * (but is faster than making the calls separately).
> *
>- * This function probably only makes sense for multisets.
>+ * If a heterogeneous key __k matches a range of elements, that
>+ * range is reported.
> */
> std::pair<iterator, iterator>
> equal_range(const key_type& __x)
>diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
>index 5d361b55028..632df6d4bfc 100644
>--- a/libstdc++-v3/include/bits/stl_tree.h
>+++ b/libstdc++-v3/include/bits/stl_tree.h
>@@ -1470,6 +1470,20 @@ namespace __rb_tree
> _M_get_insert_hint_equal_pos(const_iterator __pos,
> const key_type& __k);
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <typename... _Args>
>+ iterator
>+ _M_emplace_here(bool __place_left, _Base_ptr __node, _Args&&... __args);
>+
>+ template <typename _Kt>
>+ pair<_Base_ptr, _Base_ptr>
>+ _M_get_insert_unique_pos_tr(const _Kt& __k);
>+
>+ template <typename _Kt>
>+ pair<_Base_ptr, _Base_ptr>
>+ _M_get_insert_hint_unique_pos_tr(const_iterator, const _Kt& __k);
>+#endif
>+
> private:
> #if __cplusplus >= 201103L
> template<typename _Arg, typename _NodeGen>
>@@ -2060,7 +2074,7 @@ namespace __rb_tree
> _M_move_assign(_Rb_tree&, false_type);
> #endif
>
>-#if __glibcxx_node_extract // >= C++17
>+#ifdef __glibcxx_node_extract // >= C++17
> static _Node_ptr
> _S_adapt(typename _Node_alloc_traits::pointer __ptr)
> {
>@@ -2446,7 +2460,7 @@ namespace __rb_tree
> for (; __first != __last; ++__first)
> _M_insert_equal_(end(), *__first, __roan);
> }
>-#endif
>+#endif // C++11
>
> template<typename _Key, typename _Val, typename _KeyOfValue,
> typename _Compare, typename _Alloc>
>@@ -2830,6 +2844,56 @@ namespace __rb_tree
> return _Res(__x, __y);
> }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+
>+ // Multiple elements may compare equal to __k. Identify the first
>+ // of any such elements, or insert normally.
>+
>+ template <typename _Key, typename _Val, typename _KeyOfValue,
>+ typename _Compare, typename _Alloc>
>+ template <typename _Kt>
>+ auto
>+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
>+ _M_get_insert_unique_pos_tr(const _Kt& __k)
>+ -> pair<_Base_ptr, _Base_ptr>
>+ {
>+ if (size() == 0)
>+ return { _M_end(), _M_end() }; // Insert as root.
>+
>+ _Base_ptr __x = _M_begin(), __y = __x;
>+ bool __k_le_y = false;
>+ do
>+ {
>+ __y = __x;
>+ __k_le_y = ! _M_key_compare(_S_key(__x), __k);
>+ __x = __k_le_y ? _S_left(__x) : _S_right(__x);
>+ }
>+ while (__x);
>+ // If !__k_le_y, __k > *__y;
>+ // If __y is rightmost, put at _M_right under *__y.
>+ // else if __k < *(__y+1), put at _M_right under *__y.
>+ // else __k == *(__y+1), do not insert, report (__y+1).
>+ // else, __k_le_y, __k <= *__y;
>+ // If __k < *__Y, put at _M_left under *__y.
>+ // else __k == *__y, do not insert, report __y.
>+ auto __j = iterator(__y);
>+ if (! __k_le_y) // k > *__y
>+ {
>+ if (__y == _M_rightmost())
>+ return { {}, __y }; // Place to right under __y.
>+ ++__j;
>+ }
>+ if (_M_key_compare(__k, _S_key(__j._M_node)))
>+ {
>+ if (__k_le_y)
>+ return { __y, __y }; // Place to left under __y.
>+ else
>+ return { {}, __y }; // Place to right under __y.
>+ }
>+ return { __j._M_node, {} }; // No insert.
>+ }
>+#endif
>+
> template<typename _Key, typename _Val, typename _KeyOfValue,
> typename _Compare, typename _Alloc>
> #if __cplusplus >= 201103L
>@@ -2936,6 +3000,59 @@ namespace __rb_tree
> return _Res(__position._M_node, _Base_ptr());
> }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <typename _Key, typename _Val, typename _KeyOfValue,
>+ typename _Compare, typename _Alloc>
>+ template <typename _Kt>
>+ auto
>+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
>+ _M_get_insert_hint_unique_pos_tr(const_iterator __hint, const _Kt& __k)
>+ -> pair<_Base_ptr, _Base_ptr>
>+ {
>+ auto __node =__hint._M_node;
>+ if (__node == _M_end())
>+ {
>+ if (size() > 0 && _M_key_compare(_S_key(_M_rightmost()), __k))
>+ return { {}, _M_rightmost() };
>+ return _M_get_insert_unique_pos_tr(__k);
>+ }
>+ if (_M_key_compare(__k, _S_key(__node)))
>+ { // First, try before...
>+ if (__node == _M_leftmost()) // begin()
>+ return { _M_leftmost(), _M_leftmost() };
>+ iterator __before(__node);
>+ --__before;
>+ if (_M_key_compare(_S_key(__before._M_node), __k))
>+ {
>+ if (!_S_right(__before._M_node))
>+ return { {}, __before._M_node }; // put right
>+ return { __node, __node }; // put left;
>+ }
>+ return _M_get_insert_unique_pos_tr(__k);
>+ }
>+ if (_M_key_compare(_S_key(__node), __k))
>+ { // ... then try after.
>+ if (__node == _M_rightmost())
>+ return { {}, _M_rightmost() };
>+ iterator __after(__node);
>+ ++__after;
>+ if (_M_key_compare(__k, _S_key(__after._M_node)))
>+ {
>+ if (!_S_right(__node))
>+ return { {}, __node };
>+ return { __after._M_node, __after._M_node };
>+ }
>+ return _M_get_insert_unique_pos_tr(__k);
>+ }
>+ // Equal to __k; check if any more to the left.
>+ iterator __before(__node);
>+ if (__node == _M_leftmost() ||
>+ _M_key_compare(_S_key((--__before)._M_node), __k))
>+ { return { __node, {} }; }
>+ return _M_get_insert_unique_pos_tr(__k);
>+ }
>+#endif
>+
> template<typename _Key, typename _Val, typename _KeyOfValue,
> typename _Compare, typename _Alloc>
> #if __cplusplus >= 201103L
>@@ -3155,8 +3272,33 @@ namespace __rb_tree
> return __z._M_insert(__res);
> return __z._M_insert_equal_lower();
> }
>+
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+
>+ // If __pos.second == &_M_impl._M_header, insert at root;
>+ // else if __pos.first == __pos.second, insert at __pos.second._M_left;
>+ // else insert at __pos.second._M_right, and rebalance.
>+
>+ template <typename _Key, typename _Val, typename _KeyOfValue,
>+ typename _Compare, typename _Alloc>
>+ template <typename... _Args>
>+ auto
>+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
>+ _M_emplace_here(bool __place_left, _Base_ptr __node, _Args&&... __args)
>+ -> iterator
>+ {
>+ _Auto_node __z(*this, std::forward<_Args>(__args)...);
>+ _Base_ptr __base_z = __z._M_node->_M_base_ptr();
>+ _Node_traits::_S_insert_and_rebalance(
>+ __place_left, __base_z, __node, _M_impl._M_header);
>+ __z._M_node = nullptr;
>+ ++_M_impl._M_node_count;
>+ return iterator(__base_z);
>+ }
> #endif
>
>+#endif // >= C++11
>+
>
> template<typename _Key, typename _Val, typename _KeyOfValue,
> typename _Compare, typename _Alloc>
>diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
>index 9b74cba8675..1bd2906ace4 100644
>--- a/libstdc++-v3/include/bits/unordered_map.h
>+++ b/libstdc++-v3/include/bits/unordered_map.h
>@@ -456,6 +456,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> emplace(_Args&&... __args)
> { return _M_h.emplace(std::forward<_Args>(__args)...); }
>
>+ ///@{
> /**
> * @brief Attempts to build and insert a std::pair into the
> * %unordered_map.
>@@ -520,6 +521,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #endif // node_extract
>
> #ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
>+ ///@{
> /**
> * @brief Attempts to build and insert a std::pair into the
> * %unordered_map.
>@@ -558,6 +560,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> std::forward<_Args>(__args)...);
> }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename ..._Args>
>+ pair<iterator, bool>
>+ try_emplace(_Kt&& __k, _Args&&... __args)
>+ {
>+ return _M_h.try_emplace(cend(),
>+ std::forward<_Kt>(__k), std::forward<_Args>(__args)...);
>+ }
>+#endif
>+ ///@}
>+
>+ ///@{
> /**
> * @brief Attempts to build and insert a std::pair into the
> * %unordered_map.
>@@ -605,6 +619,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> }
> #endif // __glibcxx_unordered_map_try_emplace
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename ..._Args>
>+ iterator
>+ try_emplace(const_iterator __hint, _Kt&& __k, _Args&&... __args)
>+ {
>+ return _M_h.try_emplace(__hint,
>+ std::forward<_Kt>(__k), std::forward<_Args>(__args)...).first;
>+ }
>+#endif
>+ ///@}
>+
> ///@{
> /**
> * @brief Attempts to insert a std::pair into the %unordered_map.
>@@ -722,6 +747,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #endif
>
> #ifdef __glibcxx_unordered_map_try_emplace // >= C++17 && HOSTED
>+ ///@{
> /**
> * @brief Attempts to insert a std::pair into the %unordered_map.
> * @param __k Key to use for finding a possibly existing pair in
>@@ -765,6 +791,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> return __ret;
> }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename _Obj>
>+ pair<iterator, bool>
>+ insert_or_assign(_Kt&& __k, _Obj&& __obj)
>+ {
>+ auto __ret = _M_h.try_emplace(
>+ cend(), std::forward<_Kt>(__k), std::forward<_Obj>(__obj));
>+ if (!__ret.second)
>+ __ret.first->second = std::forward<_Obj>(__obj);
>+ return __ret;
>+ }
>+#endif
>+ ///@}
>+
>+ ///@{
> /**
> * @brief Attempts to insert a std::pair into the %unordered_map.
> * @param __hint An iterator that serves as a hint as to where the
>@@ -813,6 +854,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> __ret.first->second = std::forward<_Obj>(__obj);
> return __ret.first;
> }
>+
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename _Obj>
>+ iterator
>+ insert_or_assign(const_iterator __hint, _Kt&& __k, _Obj&& __obj)
>+ {
>+ auto __ret = _M_h.try_emplace(__hint,
>+ std::forward<_Kt>(__k), std::forward<_Obj>(__obj));
>+ if (!__ret.second)
>+ __ret.first->second = std::forward<_Obj>(__obj);
>+ return __ret.first;
>+ }
>+#endif
>+ ///@}
> #endif // unordered_map_try_emplace
>
> ///@{
>@@ -1089,6 +1144,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> mapped_type&
> operator[](key_type&& __k)
> { return _M_h[std::move(__k)]; }
>+
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_map> _Kt>
>+ mapped_type&
>+ operator[](_Kt&& __k)
>+ {
>+ return try_emplace(std::forward<_Kt>(__k)).first->second;
>+ }
>+#endif
> ///@}
>
> ///@{
>@@ -1103,9 +1167,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> at(const key_type& __k)
> { return _M_h.at(__k); }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_map> _Kt>
>+ mapped_type&
>+ at(const _Kt& __k)
>+ { return _M_h._M_at_tr(__k); }
>+#endif
>+
> const mapped_type&
> at(const key_type& __k) const
> { return _M_h.at(__k); }
>+
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_map> _Kt>
>+ const mapped_type&
>+ at(const _Kt& __k) const
>+ { return _M_h._M_at_tr(__k); }
>+#endif
> ///@}
>
> // bucket interface.
>@@ -1129,6 +1207,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> bucket_size(size_type __n) const
> { return _M_h.bucket_size(__n); }
>
>+ ///@{
> /*
> * @brief Returns the bucket index of a given element.
> * @param __key A key instance.
>@@ -1138,6 +1217,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> bucket(const key_type& __key) const
> { return _M_h.bucket(__key); }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_map> _Kt>
>+ size_type
>+ bucket(const _Kt& __key) const
>+ { return _M_h._M_bucket_tr(__key); }
>+#endif
>+ ///@}
>+
> /**
> * @brief Returns a read/write iterator pointing to the first bucket
> * element.
>@@ -2176,6 +2263,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> bucket_size(size_type __n) const
> { return _M_h.bucket_size(__n); }
>
>+ ///@{
> /*
> * @brief Returns the bucket index of a given element.
> * @param __key A key instance.
>@@ -2185,6 +2273,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> bucket(const key_type& __key) const
> { return _M_h.bucket(__key); }
>
>+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_multimap> _Kt>
>+ size_type
>+ bucket(const _Kt& __key) const
>+ { return _M_h._M_bucket_tr(__key); }
>+#endif
>+ ///@}
>+
> /**
> * @brief Returns a read/write iterator pointing to the first bucket
> * element.
>diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
>index 22b2ad9caf4..c64fe01c447 100644
>--- a/libstdc++-v3/include/bits/unordered_set.h
>+++ b/libstdc++-v3/include/bits/unordered_set.h
>@@ -493,6 +493,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> std::pair<iterator, bool>
> insert(value_type&& __x)
> { return _M_h.insert(std::move(__x)); }
>+
>+#if __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_set> _Kt>
>+ std::pair<iterator, bool>
>+ insert(_Kt&& __x)
>+ { return _M_h._M_insert_tr(std::forward<_Kt>(__x)); }
>+#endif
> ///@}
>
> ///@{
>@@ -522,6 +529,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> iterator
> insert(const_iterator __hint, value_type&& __x)
> { return _M_h.insert(__hint, std::move(__x)); }
>+
>+#if __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_set> _Kt>
>+ iterator
>+ insert(const_iterator, _Kt&& __x)
>+ { return _M_h._M_insert_tr(std::forward<_Kt>(__x)).first; }
>+#endif
> ///@}
>
> /**
>@@ -876,6 +890,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> bucket_size(size_type __n) const
> { return _M_h.bucket_size(__n); }
>
>+ ///@{
> /*
> * @brief Returns the bucket index of a given element.
> * @param __key A key instance.
>@@ -885,6 +900,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> bucket(const key_type& __key) const
> { return _M_h.bucket(__key); }
>
>+#if __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_set> _Kt>
>+ size_type
>+ bucket(const _Kt& __key) const
>+ { return _M_h._M_bucket_tr(__key); }
>+#endif
>+ ///@}
>+
> ///@{
> /**
> * @brief Returns a read-only (constant) iterator pointing to the first
>@@ -1884,6 +1907,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> bucket_size(size_type __n) const
> { return _M_h.bucket_size(__n); }
>
>+ ///@{
> /*
> * @brief Returns the bucket index of a given element.
> * @param __key A key instance.
>@@ -1893,6 +1917,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> bucket(const key_type& __key) const
> { return _M_h.bucket(__key); }
>
>+#if __glibcxx_associative_heterogeneous_insertion // C++26
>+ template <__heterogeneous_hash_key<unordered_multiset> _Kt>
>+ size_type
>+ bucket(const _Kt& __key) const
>+ { return _M_h._M_bucket_tr(__key); }
>+#endif
>+ ///@}
>+
> ///@{
> /**
> * @brief Returns a read-only (constant) iterator pointing to the first
>diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def
>index c7709ba3a07..dbe95b8b79f 100644
>--- a/libstdc++-v3/include/bits/version.def
>+++ b/libstdc++-v3/include/bits/version.def
>@@ -1651,6 +1651,14 @@ ftms = {
> };
> };
>
>+ftms = {
>+ name = associative_heterogeneous_insertion;
>+ values = {
>+ v = 202306;
>+ cxxmin = 26;
>+ };
>+};
>+
> ftms = {
> name = is_scoped_enum;
> values = {
>diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h
>index c72cda506f1..eee99847490 100644
>--- a/libstdc++-v3/include/bits/version.h
>+++ b/libstdc++-v3/include/bits/version.h
>@@ -1821,6 +1821,16 @@
> #endif /* !defined(__cpp_lib_associative_heterogeneous_erasure) */
> #undef __glibcxx_want_associative_heterogeneous_erasure
>
>+#if !defined(__cpp_lib_associative_heterogeneous_insertion)
>+# if (__cplusplus > 202302L)
>+# define __glibcxx_associative_heterogeneous_insertion 202306L
>+# if defined(__glibcxx_want_all) || defined(__glibcxx_want_associative_heterogeneous_insertion)
>+# define __cpp_lib_associative_heterogeneous_insertion 202306L
>+# endif
>+# endif
>+#endif /* !defined(__cpp_lib_associative_heterogeneous_insertion) */
>+#undef __glibcxx_want_associative_heterogeneous_insertion
>+
> #if !defined(__cpp_lib_is_scoped_enum)
> # if (__cplusplus >= 202100L)
> # define __glibcxx_is_scoped_enum 202011L
>diff --git a/libstdc++-v3/include/std/map b/libstdc++-v3/include/std/map
>index 91612cf42c4..66edadbc6dc 100644
>--- a/libstdc++-v3/include/std/map
>+++ b/libstdc++-v3/include/std/map
>@@ -80,6 +80,7 @@
> #define __glibcxx_want_nonmember_container_access
> #define __glibcxx_want_tuple_like
> #define __glibcxx_want_associative_heterogeneous_erasure
>+#define __glibcxx_want_associative_heterogeneous_insertion
> #include <bits/version.h>
>
> #if __cplusplus >= 201703L
>diff --git a/libstdc++-v3/include/std/set b/libstdc++-v3/include/std/set
>index 28eef1fc490..dc550f1d0b6 100644
>--- a/libstdc++-v3/include/std/set
>+++ b/libstdc++-v3/include/std/set
>@@ -78,6 +78,7 @@
> #define __glibcxx_want_node_extract
> #define __glibcxx_want_nonmember_container_access
> #define __glibcxx_want_associative_heterogeneous_erasure
>+#define __glibcxx_want_associative_heterogeneous_insertion
> #include <bits/version.h>
>
> #if __cplusplus >= 201703L
>diff --git a/libstdc++-v3/include/std/unordered_map b/libstdc++-v3/include/std/unordered_map
>index f63be4104c5..e9cf191e749 100644
>--- a/libstdc++-v3/include/std/unordered_map
>+++ b/libstdc++-v3/include/std/unordered_map
>@@ -57,6 +57,7 @@
> #define __glibcxx_want_unordered_map_try_emplace
> #define __glibcxx_want_tuple_like
> #define __glibcxx_want_associative_heterogeneous_erasure
>+#define __glibcxx_want_associative_heterogeneous_insertion
> #include <bits/version.h>
>
> #if __cplusplus >= 201703L
>diff --git a/libstdc++-v3/include/std/unordered_set b/libstdc++-v3/include/std/unordered_set
>index 45e6a915eb9..ee16489290e 100644
>--- a/libstdc++-v3/include/std/unordered_set
>+++ b/libstdc++-v3/include/std/unordered_set
>@@ -55,6 +55,7 @@
> #define __glibcxx_want_node_extract
> #define __glibcxx_want_nonmember_container_access
> #define __glibcxx_want_associative_heterogeneous_erasure
>+#define __glibcxx_want_associative_heterogeneous_insertion
> #include <bits/version.h>
>
> #if __cplusplus >= 201703L
>diff --git a/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc
>new file mode 100644
>index 00000000000..b89ca93e000
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc
>@@ -0,0 +1,932 @@
>+// { dg-do run { target c++26 } }
>+
>+#include <map>
>+#include <string>
>+#include <string_view>
>+#include <utility>
>+#include <compare>
>+#include <cstring>
>+#include <testsuite_hooks.h>
>+
>+struct Y;
>+struct Z;
>+
>+struct X {
>+ std::string s;
>+ X(std::string_view str) : s(str) {}
>+ X(Y&&);
>+ X(const Y&);
>+ X(Z&&);
>+ X(const Z&);
>+ friend auto operator<=>(X const& a, X const& b) = default;
>+};
>+
>+struct Y {
>+ std::string s;
>+ Y() = default;
>+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+ Y(const Y& y) = default;
>+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
>+ Y& operator=(const Y& y) = default;
>+ Y(std::string_view sv) : s(sv) {}
>+ Y(int n) : s(std::string(n, 'a')) {}
>+ Y(const Y& a, const Y& b) : s(a.s + "1" + b.s) { }
>+ Y(const Y& a, Y&& b) : s(a.s + "2" + b.s) { b.s.clear(); }
>+ Y(Y&& a, const Y& b) : s(a.s + "3" + b.s) { a.s.clear(); }
>+ Y(Y&& a, Y&& b) : s(a.s + "4" + b.s) { a.s.clear(), b.s.clear(); }
>+ friend auto operator<=>(Y const& a, Y const& b) = default;
>+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.s; }
>+};
>+
>+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+X::X(const Y& y) : s(y.s) {}
>+
>+using cmp = std::less<void>;
>+
>+void test_at()
>+{
>+ std::map<X, Y, cmp> amap{cmp{}};
>+ amap.insert( {{Y{"abc"}, 1},
>+ {Y{"dee"}, 2}, {Y{"def"}, 3}, {Y{"deg"}, 4},
>+ {Y{"ghi"}, 5}});
>+
>+ Y y{"def"};
>+ try
>+ {
>+ VERIFY(3 == amap.at(y));
>+ VERIFY(amap.size() == 5);
>+ VERIFY(4 == (amap.at(std::move(y)) = 4));
>+ VERIFY(amap.size() == 5);
>+ VERIFY(y.s.size() == 3); // not moved from
>+ }
>+ catch(...) { VERIFY(false); }
>+ try
>+ {
>+ amap.at(Y{"dea"}) = 4;
>+ VERIFY(false); // Should have thrown.
>+ }
>+ catch (std::out_of_range&) { VERIFY(amap.size() == 5); }
>+ catch (...) { VERIFY(false); } // Wrong exception.
>+
>+ auto const& amapr{amap};
>+ Y z{"deh"};
>+ try
>+ {
>+ amapr.at(std::move(z));
>+ VERIFY(false); // Should have thrown.
>+ }
>+ catch (std::out_of_range&) { }
>+ catch (...) { VERIFY(false); } // Wrong exception.
>+ VERIFY(amapr.size() == 5);
>+ VERIFY(z.s.size() == 3); // not moved from
>+}
>+
>+void test_op_bracket()
>+{
>+ std::map<X, Y, cmp> amap{cmp{}};
>+ amap.insert({{Y{"abc"}, 1}, {Y{"def"}, 2}, {Y{"ghi"}, 3}});
>+ {
>+ Y z{"deg"};
>+ amap[z] = 4;
>+ VERIFY(amap.size() == 4);
>+ VERIFY(z.s.size() == 3); // pass by value, not moved from.
>+ amap[std::move(z)] = Y{5};
>+ VERIFY(amap.size() == 4);
>+ VERIFY(amap.at(z) == Y{5});
>+ VERIFY(z.s.size() == 3); // already there, not moved from.
>+ }
>+ {
>+ Y y{"deh"};
>+ Y& v = amap[std::move(y)];
>+ VERIFY(v == Y{});
>+ VERIFY(amap.size() == 5);
>+ VERIFY(amap.at(Y{"deh"}) == Y{});
>+ VERIFY(y.s.empty()); // moved from.
>+ }
>+ {
>+ Y x{"dei"};
>+ amap[std::move(x)] = Y{7};
>+ VERIFY(amap.size() == 6);
>+ VERIFY(amap.at(Y{"dei"}) == Y{7});
>+ VERIFY(x.s.empty()); // moved from
>+ }
>+}
>+
>+void test_try_emplace()
>+{
>+ std::map<X, Y, cmp> amap{cmp{}};
>+ amap.insert({{Y{"abc"}, 1}, {Y{"def"}, 2}, {Y{"ghi"}, 3}});
>+
>+ { // Fail, already there
>+ auto a = amap;
>+ auto [it, res] = a.try_emplace(Y{"def"}, Y{"xyz"});
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(a.at(Y{"def"}) == Y{2}); // unchanged
>+ }
>+ { // Fail, already there, move
>+ auto a = amap;
>+ Y x{"def"};
>+ Y y{"xyz"};
>+ auto [it, res] = a.try_emplace(std::move(x), std::move(y));
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(a.at(Y{"def"}) == Y{2}); // unchanged
>+ VERIFY(x.s.size() == 3); // not moved from
>+ VERIFY(y.s.size() == 3); // not moved from
>+ }
>+ { // Succeed, construct
>+ auto a = amap;
>+ {
>+ Y m{"m"}, n{"n"};
>+ auto [it, res] = a.try_emplace(Y{"deg"}, m, n);
>+ VERIFY(res);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->first == X{"deg"});
>+ VERIFY(it->second == Y{"m1n"});
>+ VERIFY(m.s.size() == 1);
>+ VERIFY(n.s.size() == 1);
>+ }
>+ {
>+ Y m{"m"}, n{"n"};
>+ auto [it, res] = a.try_emplace(Y{"deh"}, m, std::move(n));
>+ VERIFY(res);
>+ VERIFY(a.size() == 5);
>+ VERIFY(it->first == X{"deh"});
>+ VERIFY(it->second == Y{"m2n"});
>+ VERIFY(m.s.size() == 1);
>+ VERIFY(n.s.empty());
>+ }
>+ {
>+ Y m{"m"}, o{"o"};
>+ auto [it, res] = a.try_emplace(Y{"dei"}, std::move(m), o);
>+ VERIFY(res);
>+ VERIFY(a.size() == 6);
>+ VERIFY(it->first == X{"dei"});
>+ VERIFY(it->second == Y{"m3o"});
>+ VERIFY(m.s.empty());
>+ VERIFY(o.s.size() == 1);
>+ }
>+ {
>+ Y o{"o"}, p{"p"};
>+ auto [it, res] = a.try_emplace(Y{"dej"}, std::move(o), std::move(p));
>+ VERIFY(res);
>+ VERIFY(a.size() == 7);
>+ VERIFY(it->first == X{"dej"});
>+ VERIFY(it->second == Y{"o4p"});
>+ VERIFY(o.s.empty());
>+ VERIFY(p.s.empty());
>+ }
>+ {
>+ Y dek{"dek"};
>+ auto [it, res] = a.try_emplace(std::move(dek), Y("q"), Y("r"));
>+ VERIFY(res);
>+ VERIFY(a.size() == 8);
>+ VERIFY(dek.s.empty());
>+ VERIFY(it->first == X{"dek"});
>+ VERIFY(it->second == Y{"q4r"});
>+ }
>+ }
>+ { // Succeed, move
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto [it, res] = a.try_emplace(std::move(y), std::move(z));
>+ VERIFY(res);
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.empty()); // moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+ { // Hinted, fail
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->first == X{"def"});
>+ VERIFY(it->second == Y{2});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Hinted, fail, move
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->first == X{"def"});
>+ VERIFY(it->second == Y{2});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Hinted, succeed, construct
>+ auto a = amap;
>+ {
>+ Y m("m"), n("n");
>+ auto it = a.try_emplace(a.begin(), Y{"deg"}, m, n);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->first == X{"deg"});
>+ VERIFY(it->second == Y{"m1n"});
>+ VERIFY(m.s.size() == 1);
>+ VERIFY(n.s.size() == 1);
>+ }
>+ {
>+ Y m("m"), n("n");
>+ auto it = a.try_emplace(a.begin(), Y{"deh"}, m, std::move(n));
>+ VERIFY(a.size() == 5);
>+ VERIFY(it->first == X{"deh"});
>+ VERIFY(it->second == Y{"m2n"});
>+ VERIFY(m.s.size() == 1);
>+ VERIFY(n.s.empty());
>+ }
>+ {
>+ Y m("m"), o("o");
>+ auto it = a.try_emplace(a.begin(), Y{"dei"}, std::move(m), o);
>+ VERIFY(a.size() == 6);
>+ VERIFY(it->first == X{"dei"});
>+ VERIFY(it->second == Y{"m3o"});
>+ VERIFY(m.s.empty());
>+ VERIFY(o.s.size() == 1);
>+ }
>+ {
>+ Y o("o"), p("p");
>+ auto it = a.try_emplace(a.begin(), Y{"dej"}, std::move(o), std::move(p));
>+ VERIFY(a.size() == 7);
>+ VERIFY(it->first == X{"dej"});
>+ VERIFY(it->second == Y{"o4p"});
>+ VERIFY(o.s.empty());
>+ VERIFY(p.s.empty());
>+ }
>+ {
>+ Y dek("dek");
>+ auto it = a.try_emplace(a.begin(), std::move(dek), Y("q"), Y("r"));
>+ VERIFY(a.size() == 8);
>+ VERIFY(dek.s.empty());
>+ VERIFY(it->first == X{"dek"});
>+ VERIFY(it->second == Y{"q4r"});
>+ }
>+ }
>+ { // Hinted, succeed, move
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.empty()); // moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+}
>+
>+void test_insert_or_assign()
>+{
>+ std::map<X, Y, cmp> amap{cmp{}};
>+ amap.insert({{Y{"abc"}, 1}, {Y{"def"}, 2}, {Y{"ghi"}, 3}});
>+
>+ { // Already there, replace
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto [it, res] = a.insert_or_assign(y, z);
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(a.at(Y{"def"}) == Y{"xyz"});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Already there, move
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto [it, res] = a.insert_or_assign(std::move(y), std::move(z));
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(a.at(Y{"def"}) == Y{"xyz"});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+ { // Succeed, move
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto [it, res] = a.insert_or_assign(std::move(y), std::move(z));
>+ VERIFY(res);
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.empty()); // moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+ { // Hinted, already there, replace
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto it = a.insert_or_assign(a.begin(), y, z);
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->first == X{"def"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Hinted, already there, move
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto it = a.insert_or_assign(a.begin(), std::move(y), std::move(z));
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->first == X{"def"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+ { // Hinted, succeed
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto it = a.insert_or_assign(a.begin(), y, z);
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Hinted, succeed, move
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto it = a.insert_or_assign(a.begin(), std::move(y), std::move(z));
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.empty()); // moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+}
>+
>+struct Z {
>+ std::string s;
>+ mutable int compares = 0;
>+
>+ Z() = default;
>+ Z(Z&& z) : s(std::move(z.s)) { z.s.clear(); }
>+ Z(const Z& z) = default;
>+ Z& operator=(Z&& z) { s = std::move(z.s); z.s.clear(); return *this; }
>+ Z& operator=(const Z& z) = default;
>+ Z(std::string_view sv) : s(sv) {}
>+ Z(int n) : s(std::string(n, 'a')) {}
>+ friend auto operator<=>(Z const& a, Z const& b) = default;
>+ friend auto operator<=>(X const& a, Z const& b)
>+ { return ++b.compares, a.s.substr(0, b.s.size()) <=> b.s; }
>+};
>+
>+X::X(Z&& z) : s(std::move(z.s)) { z.s.clear(); }
>+X::X(const Z& z) : s(z.s) {}
>+
>+// A heterogeneous key type like Z here that compares equal
>+// if it matches just the first part of the key is allowed,
>+// which affects op[], try_emplace, and insert_or_assign.
>+
>+auto populate(auto a)
>+{
>+ const std::string vs[] = { "dec", "ded", "dee", "def", "deg", "deh", "dei" };
>+ for (auto const& v : vs)
>+ a[Y{v}] = Y{v};
>+ return a;
>+}
>+
>+void test_op_bracket_prefix()
>+{
>+ std::map<X, Y, cmp> amap{cmp{}};
>+ amap.insert({{Y{"abc"}, 1}, {Y{"def"}, 2}, {Y{"ghi"}, 3}});
>+ { // Already there, multiple matches
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"de"};
>+ a[std::move(z)] = Y{5};
>+ VERIFY(a.size() == 9);
>+ VERIFY(a.at(X{"dec"}) == Y{5}); // lower_bound match changed
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"});
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"});
>+ VERIFY(a.at(X{"def"}) == Y{"def"});
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"});
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"});
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"});
>+ VERIFY(z.s.size() == 2); // not moved from
>+ }
>+}
>+
>+void test_try_emplace_prefix()
>+{
>+ std::map<X, Y, cmp> amap{cmp{}};
>+ amap.insert({{Y{"abc"}, 1}, {Y{"def"}, 2}, {Y{"ghi"}, 3}});
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ {
>+ Z z{"de"};
>+ auto [it, res] = a.try_emplace(std::move(z), 5);
>+ VERIFY(a.size() == 9);
>+ VERIFY(!res);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{"dec"});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // lower_bound match unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ }
>+ {
>+ Z z{"df"};
>+ auto [it, res] = a.try_emplace(std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(res);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ }
>+ { // hinted
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"aaa"};
>+ auto it = a.try_emplace(a.begin(), std::move(z), 5);
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"aaa"});
>+ VERIFY(it->second == Y{5});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 1);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"de"};
>+ auto it = a.try_emplace(a.find(X{"dec"}), std::move(z), 5);
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{"dec"});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.begin(), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares > 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(std::next(a.begin()), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares > 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(std::prev(a.end()), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares == 2);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.end(), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares > 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.find(X{"dei"}), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares == 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.find(X{"dec"}), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares > 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ }
>+ { // hinted
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"de"};
>+ auto it = a.try_emplace(a.find(X{"dec"}), std::move(z), 5);
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{"dec"});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ VERIFY(z.compares == 3);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"de"};
>+ auto it = a.try_emplace(a.begin(), std::move(z), 5);
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{"dec"});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"de"};
>+ auto it = a.try_emplace(a.find(X{"dei"}), std::move(z), 5);
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{"dec"});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"de"};
>+ auto it = a.try_emplace(a.find(X{"ghi"}), std::move(z), 5);
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{"dec"});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"de"};
>+ auto it = a.try_emplace(a.end(), std::move(z), 5);
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{"dec"});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.begin(), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares > 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(std::next(a.begin()), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares > 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.find(X{"dei"}), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares == 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.find(X{"dec"}), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares > 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(std::prev(a.end()), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares == 2);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.end(), std::move(z), Y{6});
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{6});
>+ VERIFY(z.s.size() == 0); // moved from
>+ VERIFY(z.compares > 3);
>+ auto it2 = a.find(X{"dei"});
>+ VERIFY(it2 != a.end());
>+ ++it2;
>+ VERIFY(it2 != a.end());
>+ VERIFY(it2->first == X{"df"});
>+ }
>+ }
>+}
>+
>+void test_insert_or_assign_prefix()
>+{
>+ std::map<X, Y, cmp> amap{cmp{}};
>+ amap.insert({{Y{"abc"}, 1}, {Y{"def"}, 2}, {Y{"ghi"}, 3}});
>+
>+ { // Already there, replace
>+ {
>+ Z z{"de"};
>+ auto a = populate(amap);
>+ auto [it, res] = a.insert_or_assign(z, Y{5});
>+ VERIFY(!res);
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{5});
>+ VERIFY(a.at(Y{"dec"}) == Y{5}); // lower_bound changed
>+ VERIFY(a.at(Y{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(Y{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(Y{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(Y{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(Y{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(Y{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ }
>+ {
>+ Z z{"de"};
>+ auto a = populate(amap);
>+ auto [it, res] = a.insert_or_assign(std::move(z), Y{5});
>+ VERIFY(!res);
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{5});
>+ VERIFY(a.at(Y{"dec"}) == Y{5}); // lower_bound changed
>+ VERIFY(a.at(Y{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(Y{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(Y{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(Y{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(Y{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(Y{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ }
>+ }
>+ { // Hinted, already there, replace
>+ {
>+ Z z{"de"};
>+ auto a = populate(amap);
>+ auto it = a.insert_or_assign(a.find(X{"dec"}), z, Y{5});
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{5});
>+ VERIFY(a.at(Y{"dec"}) == Y{5}); // lower_bound changed
>+ VERIFY(a.at(Y{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(Y{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(Y{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(Y{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(Y{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(Y{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ Z z{"de"};
>+ auto a = populate(amap);
>+ auto it = a.insert_or_assign(a.end(), std::move(z), Y{5});
>+ VERIFY(a.size() == 9);
>+ VERIFY(it->first == X{"dec"});
>+ VERIFY(it->second == Y{5});
>+ VERIFY(a.at(Y{"dec"}) == Y{5}); // lower_bound changed
>+ VERIFY(a.at(Y{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(Y{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(Y{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(Y{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(Y{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(Y{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.size() == 2); // not moved from
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.find(X{"dei"}), std::move(z), 5);
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{5});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 3);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"df"};
>+ auto it = a.try_emplace(a.find(X{"ghi"}), std::move(z), 5);
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"df"});
>+ VERIFY(it->second == Y{5});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 2);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"jkl"};
>+ auto it = a.try_emplace(a.find(X{"ghi"}), std::move(z), 5);
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"jkl"});
>+ VERIFY(it->second == Y{5});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 2);
>+ }
>+ {
>+ auto a = populate(amap);
>+ VERIFY(a.size() == 9);
>+ Z z{"jkl"};
>+ auto it = a.try_emplace(a.end(), std::move(z), 5);
>+ VERIFY(a.size() == 10);
>+ VERIFY(it->first == X{"jkl"});
>+ VERIFY(it->second == Y{5});
>+ VERIFY(a.at(X{"dec"}) == Y{"dec"}); // unchanged
>+ VERIFY(a.at(X{"ded"}) == Y{"ded"}); // unchanged
>+ VERIFY(a.at(X{"dee"}) == Y{"dee"}); // unchanged
>+ VERIFY(a.at(X{"def"}) == Y{"def"}); // unchanged
>+ VERIFY(a.at(X{"deg"}) == Y{"deg"}); // unchanged
>+ VERIFY(a.at(X{"deh"}) == Y{"deh"}); // unchanged
>+ VERIFY(a.at(X{"dei"}) == Y{"dei"}); // unchanged
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 1);
>+ }
>+ }
>+}
>+
>+int main()
>+{
>+ test_at();
>+ test_op_bracket();
>+ test_try_emplace();
>+ test_insert_or_assign();
>+ test_op_bracket_prefix();
>+ test_try_emplace_prefix();
>+ test_insert_or_assign_prefix();
>+}
>diff --git a/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc b/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc
>new file mode 100644
>index 00000000000..5733e66fb2b
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc
>@@ -0,0 +1,376 @@
>+// { dg-do run { target c++26 } }
>+
>+#include <set>
>+#include <string>
>+#include <string_view>
>+#include <utility>
>+#include <compare>
>+#include <cstring>
>+#include <testsuite_hooks.h>
>+
>+struct Y;
>+struct Z;
>+
>+struct X {
>+ std::string s;
>+ X(std::string_view str) : s(str) {}
>+ X(Y&& y);
>+ X(const Y& y);
>+ X(Z&& z);
>+ X(const Z& z);
>+
>+ friend auto operator<=>(X const& a, X const& b) = default;
>+};
>+
>+struct Y {
>+ std::string s;
>+ Y() = default;
>+ Y(std::string_view sv) : s(sv) {}
>+ Y(int a, int b = 0) : s(std::string('a', a + b)) {}
>+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+ Y(const Y& y) = default;
>+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
>+ Y& operator=(const Y& y) = default;
>+ friend auto operator<=>(Y const& a, Y const& b) = default;
>+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.s; }
>+};
>+
>+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+X::X(const Y& y) : s(y.s) {}
>+
>+using cmp = std::less<void>;
>+
>+void test_root()
>+{
>+ std::set<X, cmp> aset{cmp{}};
>+ aset.insert(Y{"def"});
>+ VERIFY(aset.size() == 1);
>+ VERIFY(aset.contains(X{"def"}));
>+ aset.insert(Y{"abc"});
>+ VERIFY(aset.size() == 2);
>+ VERIFY(aset.contains(X{"abc"}));
>+ aset.insert(Y{"ghi"});
>+ VERIFY(aset.size() == 3);
>+ VERIFY(aset.contains(X{"ghi"}));
>+}
>+
>+void test_insert()
>+{
>+ std::set<X, cmp> aset{cmp{}};
>+ aset.insert({Y{"abc"}, Y{"def"}, Y{"ghi"}});
>+
>+ { // Fail
>+ auto a = aset;
>+ Y y{"def"};
>+ auto [it, res] = a.insert(y);
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->s == "def");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Fail, move
>+ auto a = aset;
>+ Y y{"def"};
>+ auto [it, res] = a.insert(std::move(y));
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->s == "def");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Succeed
>+ auto a = aset;
>+ Y y{"deg"};
>+ auto [it, res] = a.insert(y);
>+ VERIFY(res);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->s == "deg");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Succeed, move
>+ auto a = aset;
>+ Y y{"deg"};
>+ auto [it, res] = a.insert(std::move(y));
>+ VERIFY(res);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->s == "deg");
>+ VERIFY(y.s.empty()); // moved
>+ }
>+
>+
>+ { // Hinted, fail
>+ auto a = aset;
>+ Y y{"def"};
>+ auto it = a.insert(a.begin(), y);
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->s == "def");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Hinted, fail, move
>+ auto a = aset;
>+ Y y{"def"};
>+ auto it = a.insert(a.begin(), std::move(y));
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->s == "def");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Hinted, succeed
>+ auto a = aset;
>+ Y y{"deh"};
>+ auto it = a.insert(a.begin(), y);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->s == "deh");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Hinted, succeed, move
>+ auto a = aset;
>+ Y y{"deh"};
>+ auto it = a.insert(a.begin(), std::move(y));
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->s == "deh");
>+ VERIFY(y.s.empty()); // moved
>+ }
>+}
>+
>+struct Z {
>+ std::string s;
>+ mutable int compares = 0;
>+
>+ Z() = default;
>+ Z(Z&& z) : s(std::move(z.s)) { z.s.clear(); }
>+ Z(const Z& z) = default;
>+ Z& operator=(Z&& z) { s = std::move(z.s); z.s.clear(); return *this; }
>+ Z& operator=(const Z& z) = default;
>+ Z(std::string_view sv) : s(sv) {}
>+ Z(int n) : s(std::string(n, 'a')) {}
>+ friend auto operator<=>(Z const& a, Z const& b) = default;
>+ friend auto operator<=>(X const& a, Z const& b)
>+ { return ++b.compares, a.s.substr(0, b.s.size()) <=> b.s; }
>+};
>+
>+X::X(Z&& z) : s(std::move(z.s)) { z.s.clear(); }
>+X::X(const Z& z) : s(z.s) {}
>+
>+// A heterogeneous key type like Z here that compares equal
>+// if it matches just the first part of the key is allowed,
>+// which affects op[], try_emplace, and insert_or_assign.
>+
>+auto populate(auto a)
>+{
>+ const std::string vs[] = { "dec", "ded", "dee", "def", "deg", "deh", "dei" };
>+ for (auto const& v : vs)
>+ a.insert(Y{v});
>+ return a;
>+}
>+
>+void test_insert_prefix()
>+{
>+ std::set<X, cmp> aset{cmp{}};
>+ aset.insert({Y{"abc"}, Y{"def"}, Y{"ghi"}});
>+ {
>+ { // Already there, fail.
>+ Z z{"de"};
>+ auto a = populate(aset);
>+ auto [it, res] = a.insert(std::move(z));
>+ VERIFY(!res);
>+ VERIFY(a.size() == 9);
>+ VERIFY(*it == X{"dec"});
>+ VERIFY(!a.contains(Y{"de"}));
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.size() == 2); // not moved from
>+ VERIFY(z.compares > 3);
>+ }
>+ }
>+ {
>+ { // hinted, succeed
>+ Z z{"aaa"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.begin(), std::move(z));
>+ VERIFY(a.size() == 10);
>+ VERIFY(*it == X{"aaa"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 1);
>+ }
>+ }
>+ { // Hinted, already there, fail.
>+ {
>+ Z z{"de"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.begin(), std::move(z));
>+ VERIFY(a.size() == 9);
>+ VERIFY(*it == X{"dec"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.size() == 2);
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ Z z{"de"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.find(X{"dec"}), std::move(z));
>+ VERIFY(a.size() == 9);
>+ VERIFY(*it == X{"dec"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.size() == 2);
>+ VERIFY(z.compares == 3);
>+ }
>+ {
>+ Z z{"de"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.find(X{"def"}), std::move(z));
>+ VERIFY(a.size() == 9);
>+ VERIFY(*it == X{"dec"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.size() == 2);
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ Z z{"de"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.find(X{"dei"}), std::move(z));
>+ VERIFY(a.size() == 9);
>+ VERIFY(*it == X{"dec"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.size() == 2);
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ Z z{"df"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.find(X{"dei"}), std::move(z));
>+ VERIFY(a.size() == 10);
>+ VERIFY(*it == X{"df"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 3);
>+ }
>+ {
>+ Z z{"de"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.find(X{"ghi"}), std::move(z));
>+ VERIFY(a.size() == 9);
>+ VERIFY(*it == X{"dec"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.size() == 2);
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ Z z{"df"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.find(X{"ghi"}), std::move(z));
>+ VERIFY(a.size() == 10);
>+ VERIFY(*it == X{"df"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 2);
>+ }
>+ {
>+ Z z{"de"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.end(), std::move(z));
>+ VERIFY(a.size() == 9);
>+ VERIFY(*it == X{"dec"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.size() == 2);
>+ VERIFY(z.compares > 3);
>+ }
>+ {
>+ Z z{"jkl"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.find(X{"ghi"}), std::move(z));
>+ VERIFY(a.size() == 10);
>+ VERIFY(*it == X{"jkl"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 2);
>+ }
>+ {
>+ Z z{"jkl"};
>+ auto a = populate(aset);
>+ auto it = a.insert(a.end(), std::move(z));
>+ VERIFY(a.size() == 10);
>+ VERIFY(*it == X{"jkl"});
>+ VERIFY(a.contains(Y{"dec"}));
>+ VERIFY(a.contains(Y{"ded"}));
>+ VERIFY(a.contains(Y{"dee"}));
>+ VERIFY(a.contains(Y{"def"}));
>+ VERIFY(a.contains(Y{"deg"}));
>+ VERIFY(a.contains(Y{"deh"}));
>+ VERIFY(a.contains(Y{"dei"}));
>+ VERIFY(z.s.empty()); // moved from
>+ VERIFY(z.compares == 1);
>+ }
>+ }
>+}
>+
>+int main()
>+{
>+ test_root();
>+ test_insert();
>+ test_insert_prefix();
>+}
>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc
>new file mode 100644
>index 00000000000..c1d86b8eea3
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc
>@@ -0,0 +1,353 @@
>+// { dg-do run { target c++26 } }
>+
>+#include <unordered_map>
>+#include <string>
>+#include <string_view>
>+#include <utility>
>+#include <functional>
>+#include <compare>
>+#include <testsuite_hooks.h>
>+
>+struct Y;
>+
>+struct X {
>+ std::string s;
>+ X(std::string_view str) : s(str) {}
>+ X(Y&& y);
>+ X(const Y& y);
>+ friend bool operator==(X const& a, X const& b) = default;
>+};
>+
>+struct Y {
>+ std::string s;
>+ Y() = default;
>+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+ Y(const Y& y) = default;
>+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
>+ Y& operator=(const Y& y) = default;
>+ Y(std::string_view sv) : s(sv) {}
>+ Y(int n) : s(std::string('a', n)) {}
>+ Y(const Y& a, const Y& b) : s(a.s + "1" + b.s) { }
>+ Y(const Y& a, Y&& b) : s(a.s + "2" + b.s) { b.s.clear(); }
>+ Y(Y&& a, const Y& b) : s(a.s + "3" + b.s) { a.s.clear(); }
>+ Y(Y&& a, Y&& b) : s(a.s + "4" + b.s) { a.s.clear(), b.s.clear(); }
>+ friend bool operator==(Y const& a, Y const& b) = default;
>+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
>+};
>+
>+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+X::X(const Y& y) : s(y.s) {}
>+
>+struct Hash {
>+ using is_transparent = void;
>+ template <typename T>
>+ auto operator()(T const& t) const
>+ { return std::hash<decltype(T::s)>{}(t.s); }
>+};
>+
>+using Equal = std::equal_to<void>;
>+
>+void test_op_bracket()
>+{
>+ std::unordered_map<X, Y, Hash, Equal> amap;
>+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
>+
>+ Y x{"dei"}, y{"deh"}, z{"deg"};
>+ amap[z] = 4;
>+ VERIFY(amap.size() == 4);
>+ VERIFY(z.s.size() == 3); // not moved from.
>+
>+ amap[std::move(z)] = 5;
>+ VERIFY(amap.size() == 4);
>+ VERIFY(z.s.size() == 3); // not moved from.
>+
>+ VERIFY(amap[std::move(y)] == Y{});
>+ VERIFY(amap.size() == 5);
>+ VERIFY(y.s.empty()); // moved from.
>+
>+ amap[std::move(x)] = 7;
>+ VERIFY(amap.size() == 6);
>+ VERIFY(x.s.empty()); // moved from
>+}
>+
>+void test_at()
>+{
>+ std::unordered_map<X, Y, Hash, Equal> amap;
>+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
>+
>+ Y x{"def"};
>+ try
>+ {
>+ VERIFY(2 == amap.at(x));
>+ VERIFY(amap.size() == 3);
>+ VERIFY(x.s.size() == 3); // not moved from
>+ VERIFY(4 == (amap.at(x) = 4));
>+ VERIFY(amap.size() == 3);
>+ VERIFY(x.s.size() == 3); // not moved from
>+ }
>+ catch(...) { VERIFY(false); }
>+
>+ Y z{"deg"};
>+ try
>+ {
>+ amap.at(z) = 4;
>+ VERIFY(false); // Should have thrown.
>+ }
>+ catch (std::out_of_range&) { VERIFY(amap.size() == 3); }
>+ catch (...) { VERIFY(false); } // Wrong exception.
>+ VERIFY(z.s.size() == 3); // not moved from
>+
>+ Y y{"deh"};
>+ auto const& amapr{amap};
>+ try
>+ {
>+ amapr.at(y);
>+ VERIFY(false); // Should have thrown.
>+ }
>+ catch (std::out_of_range&) { }
>+ catch (...) { VERIFY(false); } // Wrong exception.
>+ VERIFY(amapr.size() == 3);
>+ VERIFY(y.s.size() == 3); // not moved from
>+}
>+
>+void test_try_emplace()
>+{
>+ std::unordered_map<X, Y, Hash, Equal> amap;
>+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
>+
>+ { // Fail, already there
>+ auto a = amap;
>+ auto [it, res] = a.try_emplace(Y{"def"}, Y{"xyz"});
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(a.at(Y{"def"}) == Y{2});
>+ }
>+ { // Fail, already there, move
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto [it, res] = a.try_emplace(std::move(y), std::move(z));
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(a.at(Y{"def"}) == Y{2});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Succeed, construct
>+ auto a = amap;
>+ Y m("m"), n("n"), o("o"), p("p"), dek("dek");
>+ {
>+ auto [it, res] = a.try_emplace(Y{"deg"}, m, n);
>+ VERIFY(res);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->first == X{"deg"});
>+ VERIFY(it->second == Y{"m1n"});
>+ VERIFY(m.s.size() == 1);
>+ VERIFY(n.s.size() == 1);
>+ }
>+ {
>+ auto [it, res] = a.try_emplace(Y{"deh"}, m, std::move(n));
>+ VERIFY(res);
>+ VERIFY(a.size() == 5);
>+ VERIFY(it->first == X{"deh"});
>+ VERIFY(it->second == Y{"m2n"});
>+ VERIFY(m.s.size() == 1);
>+ VERIFY(n.s.empty());
>+ }
>+ {
>+ auto [it, res] = a.try_emplace(Y{"dei"}, std::move(m), o);
>+ VERIFY(res);
>+ VERIFY(a.size() == 6);
>+ VERIFY(it->first == X{"dei"});
>+ VERIFY(it->second == Y{"m3o"});
>+ VERIFY(m.s.empty());
>+ VERIFY(o.s.size() == 1);
>+ }
>+ {
>+ auto [it, res] = a.try_emplace(Y{"dej"}, std::move(o), std::move(p));
>+ VERIFY(res);
>+ VERIFY(a.size() == 7);
>+ VERIFY(it->first == X{"dej"});
>+ VERIFY(it->second == Y{"o4p"});
>+ VERIFY(o.s.empty());
>+ VERIFY(p.s.empty());
>+ }
>+ {
>+ auto [it, res] = a.try_emplace(std::move(dek), Y("q"), Y("r"));
>+ VERIFY(res);
>+ VERIFY(a.size() == 8);
>+ VERIFY(dek.s.empty());
>+ VERIFY(it->first == X{"dek"});
>+ VERIFY(it->second == Y{"q4r"});
>+ }
>+ }
>+ { // Succeed, move
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto [it, res] = a.try_emplace(std::move(y), std::move(z));
>+ VERIFY(res);
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.empty()); // moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+ { // Hinted, fail
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->first == X{"def"});
>+ VERIFY(it->second == Y{2});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Hinted, fail, move
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->first == X{"def"});
>+ VERIFY(it->second == Y{2});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Hinted, succeed, construct
>+ auto a = amap;
>+ Y m("m"), n("n"), o("o"), p("p"), dek("dek");
>+ {
>+ auto it = a.try_emplace(a.begin(), Y{"deg"}, m, n);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->first == X{"deg"});
>+ VERIFY(it->second == Y{"m1n"});
>+ VERIFY(m.s.size() == 1);
>+ VERIFY(n.s.size() == 1);
>+ }
>+ {
>+ auto it = a.try_emplace(a.begin(), Y{"deh"}, m, std::move(n));
>+ VERIFY(a.size() == 5);
>+ VERIFY(it->first == X{"deh"});
>+ VERIFY(it->second == Y{"m2n"});
>+ VERIFY(m.s.size() == 1);
>+ VERIFY(n.s.empty());
>+ }
>+ {
>+ auto it = a.try_emplace(a.begin(), Y{"dei"}, std::move(m), o);
>+ VERIFY(a.size() == 6);
>+ VERIFY(it->first == X{"dei"});
>+ VERIFY(it->second == Y{"m3o"});
>+ VERIFY(m.s.empty());
>+ VERIFY(o.s.size() == 1);
>+ }
>+ {
>+ auto it = a.try_emplace(a.begin(), Y{"dej"}, std::move(o), std::move(p));
>+ VERIFY(a.size() == 7);
>+ VERIFY(it->first == X{"dej"});
>+ VERIFY(it->second == Y{"o4p"});
>+ VERIFY(o.s.empty());
>+ VERIFY(p.s.empty());
>+ }
>+ {
>+ auto it = a.try_emplace(a.begin(), std::move(dek), Y("q"), Y("r"));
>+ VERIFY(a.size() == 8);
>+ VERIFY(dek.s.empty());
>+ VERIFY(it->first == X{"dek"});
>+ VERIFY(it->second == Y{"q4r"});
>+ }
>+ }
>+ { // Hinted, succeed, move
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.empty()); // moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+}
>+
>+void test_insert_or_assign()
>+{
>+ std::unordered_map<X, Y, Hash, Equal> amap;
>+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
>+
>+ { // Already there, replace
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto [it, res] = a.insert_or_assign(y, z);
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(a.at(Y{"def"}) == Y{"xyz"});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Already there, move
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto [it, res] = a.insert_or_assign(std::move(y), std::move(z));
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(a.at(Y{"def"}) == Y{"xyz"});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+ { // Succeed, move
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto [it, res] = a.insert_or_assign(std::move(y), std::move(z));
>+ VERIFY(res);
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.empty()); // moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+ { // Hinted, already there, replace
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto it = a.insert_or_assign(a.begin(), y, z);
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->first == X{"def"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Hinted, already there, move
>+ auto a = amap;
>+ Y y{"def"}, z{"xyz"};
>+ auto it = a.insert_or_assign(a.begin(), std::move(y), std::move(z));
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->first == X{"def"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+ { // Hinted, succeed
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto it = a.insert_or_assign(a.begin(), y, z);
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.size() == 3); // not moved from
>+ VERIFY(z.s.size() == 3); // not moved from
>+ }
>+ { // Hinted, succeed, move
>+ auto a = amap;
>+ Y y{"tuv"}, z{"xyz"};
>+ auto it = a.insert_or_assign(a.begin(), std::move(y), std::move(z));
>+ VERIFY(it->first == X{"tuv"});
>+ VERIFY(it->second == Y{"xyz"});
>+ VERIFY(a.size() == 4);
>+ VERIFY(y.s.empty()); // moved from
>+ VERIFY(z.s.empty()); // moved from
>+ }
>+}
>+
>+int main()
>+{
>+ test_op_bracket();
>+ test_at();
>+ test_try_emplace();
>+ test_insert_or_assign();
>+}
>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc
>new file mode 100644
>index 00000000000..c0d120c992e
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc
>@@ -0,0 +1,57 @@
>+// { dg-do run { target c++26 } }
>+
>+#include <unordered_map>
>+#include <string>
>+#include <string_view>
>+#include <utility>
>+#include <functional>
>+#include <testsuite_hooks.h>
>+
>+struct Y;
>+
>+struct X {
>+ std::string s;
>+ X(std::string_view str) : s(str) {}
>+ X(Y&& y);
>+ X(const Y& y);
>+ friend bool operator==(X const& a, X const& b) = default;
>+};
>+
>+struct Y {
>+ std::string s;
>+ Y() = default;
>+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+ Y(const Y& y) = default;
>+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
>+ Y& operator=(const Y& y) = default;
>+ Y(std::string_view sv) : s(sv) {}
>+ Y(int a, int b = 0) : s(std::string('a', a + b)) {}
>+ friend bool operator==(Y const& a, Y const& b) = default;
>+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
>+};
>+
>+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+X::X(const Y& y) : s(y.s) {}
>+
>+struct Hash {
>+ using is_transparent = void;
>+ template <typename T>
>+ auto operator()(T const& t) const
>+ { return std::hash<decltype(T::s)>{}(t.s); }
>+};
>+
>+using Equal = std::equal_to<void>;
>+
>+void test_bucket()
>+{
>+ std::unordered_multimap<X, Y, Hash, Equal> amap;
>+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"def"}, 3}, {X{"ghi"}, 3}});
>+
>+ auto const& amapr{amap};
>+ VERIFY(amapr.bucket(X{"def"}) == amapr.bucket(Y{"def"}));
>+}
>+
>+int main()
>+{
>+ test_bucket();
>+}
>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc
>new file mode 100644
>index 00000000000..b10a88f3775
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc
>@@ -0,0 +1,56 @@
>+// { dg-do run { target c++26 } }
>+
>+#include <unordered_set>
>+#include <string>
>+#include <string_view>
>+#include <utility>
>+#include <functional>
>+#include <testsuite_hooks.h>
>+
>+struct Y;
>+
>+struct X {
>+ std::string s;
>+ X(Y&& y);
>+ X(const Y& y);
>+ X(std::string_view str) : s(str) {}
>+ friend bool operator==(X const& a, X const& b) = default;
>+};
>+
>+struct Y {
>+ std::string s;
>+ Y() = default;
>+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+ Y(const Y& y) = default;
>+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
>+ Y& operator=(const Y& y) = default;
>+ Y(std::string_view sv) : s(sv) {}
>+ friend bool operator==(Y const& a, Y const& b) = default;
>+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
>+};
>+
>+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+X::X(const Y& y) : s(y.s) {}
>+
>+struct Hash {
>+ using is_transparent = void;
>+ template <typename T>
>+ auto operator()(T const& t) const
>+ { return std::hash<decltype(T::s)>{}(t.s); }
>+};
>+
>+using Equal = std::equal_to<void>;
>+
>+void test_bucket()
>+{
>+ std::unordered_multiset<X, Hash, Equal> aset{};
>+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
>+
>+ auto const& asetr{aset};
>+ VERIFY(asetr.bucket(X{"def"}) == asetr.bucket(Y{"def"}));
>+}
>+
>+int main()
>+{
>+ test_bucket();
>+}
>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc
>new file mode 100644
>index 00000000000..e3ef537b657
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc
>@@ -0,0 +1,134 @@
>+// { dg-do run { target c++26 } }
>+
>+#include <unordered_set>
>+#include <string>
>+#include <string_view>
>+#include <utility>
>+#include <functional>
>+#include <testsuite_hooks.h>
>+
>+struct Y;
>+
>+struct X {
>+ std::string s;
>+ X(std::string_view str) : s(str) {}
>+ X(Y&& y);
>+ X(const Y& y);
>+ friend bool operator==(X const& a, X const& b) = default;
>+};
>+
>+struct Y {
>+ std::string s;
>+ Y() = default;
>+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+ Y(const Y& y) = default;
>+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
>+ Y& operator=(const Y& y) = default;
>+ Y(int a, int b = 0) : s(std::string('a', a + b)) {}
>+ Y(std::string_view sv) : s(sv) {}
>+ friend bool operator==(Y const& a, Y const& b) = default;
>+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
>+};
>+
>+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
>+X::X(const Y& y) : s(y.s) {}
>+
>+struct Hash {
>+ using is_transparent = void;
>+ template <typename T>
>+ auto operator()(T const& t) const { return std::hash<decltype(T::s)>{}(t.s); }
>+};
>+
>+using Equal = std::equal_to<void>;
>+
>+void test_insert()
>+{
>+ std::unordered_set<X, Hash, Equal> aset;
>+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
>+
>+ { // Fail
>+ auto a = aset;
>+ Y y{"def"};
>+ auto [it, res] = a.insert(y);
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->s == "def");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Fail, move
>+ auto a = aset;
>+ Y y{"def"};
>+ auto [it, res] = a.insert(std::move(y));
>+ VERIFY(!res);
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->s == "def");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Succeed
>+ auto a = aset;
>+ Y y{"deg"};
>+ auto [it, res] = a.insert(y);
>+ VERIFY(res);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->s == "deg");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Succeed, move
>+ auto a = aset;
>+ Y y{"deg"};
>+ auto [it, res] = a.insert(std::move(y));
>+ VERIFY(res);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->s == "deg");
>+ VERIFY(y.s.empty()); // moved
>+ }
>+
>+
>+ { // Hinted, fail
>+ auto a = aset;
>+ Y y{"def"};
>+ auto it = a.insert(a.begin(), y);
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->s == "def");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Hinted, fail, move
>+ auto a = aset;
>+ Y y{"def"};
>+ auto it = a.insert(a.begin(), std::move(y));
>+ VERIFY(a.size() == 3);
>+ VERIFY(it->s == "def");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Hinted, succeed
>+ auto a = aset;
>+ Y y{"deh"};
>+ auto it = a.insert(a.begin(), y);
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->s == "deh");
>+ VERIFY(y.s.size() == 3); // not moved
>+ }
>+ { // Hinted, succeed, move
>+ auto a = aset;
>+ Y y{"deh"};
>+ auto it = a.insert(a.begin(), std::move(y));
>+ VERIFY(a.size() == 4);
>+ VERIFY(it->s == "deh");
>+ VERIFY(y.s.empty()); // moved
>+ }
>+}
>+
>+void test_bucket()
>+{
>+ std::unordered_set<X, Hash, Equal> aset{};
>+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
>+
>+ auto const& asetr{aset};
>+ VERIFY(asetr.bucket(X{"def"}) == asetr.bucket(Y{"def"}));
>+}
>+
>+int main()
>+{
>+ test_insert();
>+ test_bucket();
>+}
>--
>2.52.0
>
>
More information about the Libstdc++
mailing list