https://github.com/llvmbot created https://github.com/llvm/llvm-project/pull/200270
Backport 72871f6fa1f1edc3df45d01b67f5093ff9d8e8b5 Requested by: @philnik777 >From b153316ba64ed4509f0f890086711eee3c41ebaa Mon Sep 17 00:00:00 2001 From: Nikolas Klauser <[email protected]> Date: Thu, 28 May 2026 19:35:34 +0200 Subject: [PATCH] [libc++] Fix multi{map,set}::extract not returning the first matching element (#199703) According to [associative.reqmts] `extract(k)` returns the _first_ element in the container with key equivalent to k. (cherry picked from commit 72871f6fa1f1edc3df45d01b67f5093ff9d8e8b5) --- libcxx/include/__tree | 4 ++-- .../multimap.modifiers/extract_key.pass.cpp | 13 +++++++++++++ .../associative/multiset/extract_key.pass.cpp | 13 +++++++++++++ 3 files changed, 28 insertions(+), 2 deletions(-) diff --git a/libcxx/include/__tree b/libcxx/include/__tree index eb17f7d36936c..ddeb82f91b8ad 100644 --- a/libcxx/include/__tree +++ b/libcxx/include/__tree @@ -2026,8 +2026,8 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(const_iterator __ template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key) { - iterator __it = find(__key); - if (__it == end()) + iterator __it = __lower_bound_multi(__key); + if (__it == end() || __value_comp_(__key, *__it)) return _NodeHandle(); return __node_handle_extract<_NodeHandle>(__it); } diff --git a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp index b3027b3b0f727..42184edbdb8b6 100644 --- a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp +++ b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp @@ -50,6 +50,19 @@ int main(int, char**) { test(m, std::begin(keys), std::end(keys)); } + { // Check that the first element is returned + std::multimap<int, int> m = {{1, 1}, {1, 2}, {1, 3}}; + auto ptr = std::addressof(m.begin()->first); + auto res = m.extract(1); + assert(std::addressof(res.key()) == ptr); + } + + { // Check that no element is returned if there is no match + std::multimap<int, int> m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; + auto res = m.extract(0); + assert(!res); + } + { std::multimap<Counter<int>, Counter<int>> m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; { diff --git a/libcxx/test/std/containers/associative/multiset/extract_key.pass.cpp b/libcxx/test/std/containers/associative/multiset/extract_key.pass.cpp index 24d98cfaaf31a..ec75a6c5d835c 100644 --- a/libcxx/test/std/containers/associative/multiset/extract_key.pass.cpp +++ b/libcxx/test/std/containers/associative/multiset/extract_key.pass.cpp @@ -48,6 +48,19 @@ int main(int, char**) { test(m, std::begin(keys), std::end(keys)); } + { // Check that the first element is returned + std::multiset<int> m = {1, 1, 1}; + auto ptr = std::addressof(*m.begin()); + auto res = m.extract(1); + assert(std::addressof(res.value()) == ptr); + } + + { // Check that no element is returned if there is no match + std::multiset<int> m = {1, 2, 3}; + auto res = m.extract(0); + assert(!res); + } + { std::multiset<Counter<int>> m = {1, 2, 3, 4, 5, 6}; { _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
