Changes in v12
- Strip doxygen improvements.
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 | 135 ++-
libstdc++-v3/include/bits/stl_set.h | 35 +
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, 2420 insertions(+), 7 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>
