https://gcc.gnu.org/g:94d5ca4583876ca0fd2978b24f1fbc93a53b8373
commit r16-7889-g94d5ca4583876ca0fd2978b24f1fbc93a53b8373 Author: Nathan Myers <[email protected]> Date: Mon Jan 12 22:49:59 2026 -0500 libstdc++: container heterogeneous insertion (P2363) [PR117402] 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. libstdc++-v3/ChangeLog: PR libstdc++/117402 * include/bits/stl_map.h (operator[], at (2x), try_emplace (2x), insert_or_assign (2x)): Add overloads. * 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. * 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. Diff: --- libstdc++-v3/include/bits/hashtable.h | 27 + libstdc++-v3/include/bits/hashtable_policy.h | 26 +- libstdc++-v3/include/bits/stl_map.h | 135 ++- libstdc++-v3/include/bits/stl_set.h | 35 + libstdc++-v3/include/bits/stl_tree.h | 146 +++- libstdc++-v3/include/bits/unordered_map.h | 105 ++- libstdc++-v3/include/bits/unordered_set.h | 68 +- 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 + .../23_containers/map/modifiers/hetero/insert.cc | 932 +++++++++++++++++++++ .../23_containers/set/modifiers/hetero/insert.cc | 376 +++++++++ .../unordered_map/modifiers/hetero/insert.cc | 353 ++++++++ .../unordered_multimap/modifiers/hetero/insert.cc | 57 ++ .../unordered_multiset/modifiers/hetero/insert.cc | 56 ++ .../unordered_set/modifiers/hetero/insert.cc | 134 +++ 19 files changed, 2445 insertions(+), 27 deletions(-) diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 48695c013f38..f4211eba516f 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 6d7bde1e785e..79c36e4a02bf 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 4cb0c982c3db..72a7392dbb77 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -522,6 +522,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * 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. */ mapped_type& @@ -560,6 +563,13 @@ _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. /** @@ -568,6 +578,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * @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. + * + * If a heterogeneous key __k matches a range of elements, the + * first is chosen. */ mapped_type& at(const key_type& __k) @@ -578,6 +591,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,6 +612,18 @@ _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 /** @@ -746,6 +783,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * 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. */ template <typename... _Args> @@ -781,6 +821,26 @@ _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. * @@ -806,6 +866,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints * for more on @a hinting. * + * 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 taken). */ template <typename... _Args> @@ -845,6 +908,26 @@ _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 @@ -896,7 +979,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER return _M_t._M_emplace_unique(std::forward<_Pair>(__x)); } #endif - /// @} + ///@} #if __cplusplus >= 201103L /** @@ -1046,6 +1129,31 @@ _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 @@ -1064,6 +1172,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * If the %pair was already in the %map, the .second of the %pair * is assigned from __obj. * + * If a heterogeneous key __k matches a range of elements, the first + * is chosen. + * * Insertion requires logarithmic time. */ template <typename _Obj> @@ -1105,6 +1216,28 @@ _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 diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h index d3a4c0891109..14825cc05acb 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -548,6 +548,22 @@ _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 @@ -565,6 +581,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * For more on @a hinting, see: * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints * + * 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 taken). */ iterator @@ -577,6 +596,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_t._M_insert_unique_(__position, std::move(__x)); } #endif +#ifdef __glibcxx_associative_heterogeneous_insertion // C++26 + template <__heterogeneous_tree_key<set> _Kt> + iterator + insert(const_iterator __position, _Kt&& __k) + { + auto [__left, __node] = + _M_t._M_get_insert_hint_unique_pos_tr(__position, __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. diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 5d361b55028f..632df6d4bfc0 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 9b74cba8675a..229179933f3b 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 ///@{ @@ -839,6 +894,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.erase(__position); } ///@} + ///@{ /** * @brief Erases elements according to the provided key. * @param __x Key of element to be erased. @@ -861,6 +917,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER erase(_Kt&& __key) { return _M_h._M_erase_tr(__key); } #endif + ///@} /** * @brief Erases a [__first,__last) range of elements from an @@ -1089,6 +1146,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 +1169,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 +1209,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 +1219,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. @@ -1928,6 +2017,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.erase(__position); } ///@} + ///@{ /** * @brief Erases elements according to the provided key. * @param __x Key of elements to be erased. @@ -1946,9 +2036,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #ifdef __glibcxx_associative_heterogeneous_erasure // C++23 template <__heterogeneous_hash_key<unordered_multimap> _Kt> size_type - erase(_Kt&& __key) - { return _M_h._M_erase_tr(__key); } + erase(_Kt&& __x) + { return _M_h._M_erase_tr(__x); } #endif + ///@} + /** * @brief Erases a [__first,__last) range of elements from an @@ -2176,6 +2268,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 +2278,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 22b2ad9caf44..3585fe2c7144 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 ///@} /** @@ -761,9 +775,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED template<typename _Kt> auto - find(const _Kt& __k) - -> decltype(_M_h._M_find_tr(__k)) - { return _M_h._M_find_tr(__k); } + find(const _Kt& __x) + -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } #endif const_iterator @@ -773,9 +787,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED template<typename _Kt> auto - find(const _Kt& __k) const - -> decltype(_M_h._M_find_tr(__k)) - { return _M_h._M_find_tr(__k); } + find(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } #endif ///@} @@ -796,9 +810,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED template<typename _Kt> auto - count(const _Kt& __k) const - -> decltype(_M_h._M_count_tr(__k)) - { return _M_h._M_count_tr(__k); } + count(const _Kt& __x) const + -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } #endif ///@} @@ -815,9 +829,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Kt> auto - contains(const _Kt& __k) const - -> decltype(_M_h._M_find_tr(__k), void(), true) - { return _M_h._M_find_tr(__k) != _M_h.end(); } + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } ///@} #endif @@ -837,9 +851,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED template<typename _Kt> auto - equal_range(const _Kt& __k) - -> decltype(_M_h._M_equal_range_tr(__k)) - { return _M_h._M_equal_range_tr(__k); } + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } #endif std::pair<const_iterator, const_iterator> @@ -849,9 +863,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED template<typename _Kt> auto - equal_range(const _Kt& __k) const - -> decltype(_M_h._M_equal_range_tr(__k)) - { return _M_h._M_equal_range_tr(__k); } + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } #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 c7709ba3a070..dbe95b8b79fd 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 c72cda506f1e..eee998474907 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 91612cf42c48..66edadbc6dcc 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 28eef1fc490b..dc550f1d0b6c 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 f63be4104c59..e9cf191e749f 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 45e6a915eb9c..ee16489290e5 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 000000000000..56db9902b39a --- /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 000000000000..5733e66fb2bd --- /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 000000000000..c1d86b8eea34 --- /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 000000000000..c0d120c992ec --- /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 000000000000..b10a88f37754 --- /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 000000000000..e3ef537b6570 --- /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(); +}
