LGTM.
On Fri, Jul 3, 2026 at 5:15 PM Nathan Myers <[email protected]> wrote:
> Changes in v2:
> - Adjust whitespace, one operation per line.
> - Delete redundant apparatus in tests.
>
Just make sure not to include this in actual commit message.
>
> As shipped, the heterogeneous-key members equal_range of rbtree
> containers map, multimap, set, and multiset walk the entire range
> calling the predicate, in violation of the requirement for
> logarithmic complexity. This patch revises them to match the
> behavior of the non-heterogeneous multimap and multiset members,
> and provides tests to verify it.
>
> Tested -m64, -m32, arm64.
>
Similarly here.
>
> libstdc++-v3/Changelog:
> PR libstdc++/118851
> * include/bits/stl_tree.h (_M_equal_range_tr): Rewrite to match
> non-heterogeneous equal_range implementation.
> * testsuite/23_containers/map/operations/hetero/equal_range.cc:
> New test.
> *
> testsuite/23_containers/multimap/operations/hetero/equal_range.cc:
> Same.
> *
> testsuite/23_containers/multiset/operations/hetero/equal_range.cc:
> Same.
> * testsuite/23_containers/set/operations/hetero/equal_range.cc:
> Same.
> ---
> libstdc++-v3/include/bits/stl_tree.h | 29 ++++--
> .../map/operations/hetero/equal_range.cc | 90 +++++++++++++++++++
> .../multimap/operations/hetero/equal_range.cc | 90 +++++++++++++++++++
> .../multiset/operations/hetero/equal_range.cc | 90 +++++++++++++++++++
> .../set/operations/hetero/equal_range.cc | 90 +++++++++++++++++++
> 5 files changed, 383 insertions(+), 6 deletions(-)
> create mode 100644
> libstdc++-v3/testsuite/23_containers/map/operations/hetero/equal_range.cc
> create mode 100644
> libstdc++-v3/testsuite/23_containers/multimap/operations/hetero/equal_range.cc
> create mode 100644
> libstdc++-v3/testsuite/23_containers/multiset/operations/hetero/equal_range.cc
> create mode 100644
> libstdc++-v3/testsuite/23_containers/set/operations/hetero/equal_range.cc
>
> diff --git a/libstdc++-v3/include/bits/stl_tree.h
> b/libstdc++-v3/include/bits/stl_tree.h
> index a7781b72114..313ee816002 100644
> --- a/libstdc++-v3/include/bits/stl_tree.h
> +++ b/libstdc++-v3/include/bits/stl_tree.h
> @@ -2026,12 +2026,29 @@ namespace __rb_tree
> pair<const_iterator, const_iterator>
> _M_equal_range_tr(const _Kt& __k) const
> {
> - const_iterator __low(_M_lower_bound_tr(__k));
> - auto __high = __low;
> - auto& __cmp = _M_impl._M_key_compare;
> - while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
> - ++__high;
> - return { __low, __high };
> + auto __x = _M_begin();
> + auto __y = _M_end();
> + while (__x)
> + {
> + if (_M_key_compare(_S_key(__x), __k))
> + __x = _S_right(__x);
> + else if (_M_key_compare(__k, _S_key(__x)))
> + {
> + __y = __x;
> + __x = _S_left(__x);
> + }
> + else
> + {
> + auto __xu(__x);
> + auto __yu(__y);
> + __y = __x;
> + __x = _S_left(__x);
> + __xu = _S_right(__xu);
> + return { const_iterator(_M_lower_bound_tr(__x, __y,
> __k)),
> + const_iterator(_M_upper_bound_tr(__xu, __yu,
> __k)) };
> + }
> + }
> + return { const_iterator(__y), const_iterator(__y) };
> }
> #endif // __glibcxx_generic_associative_lookup
>
> diff --git
> a/libstdc++-v3/testsuite/23_containers/map/operations/hetero/equal_range.cc
> b/libstdc++-v3/testsuite/23_containers/map/operations/hetero/equal_range.cc
> new file mode 100644
> index 00000000000..3ed6ff62ba8
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/map/operations/hetero/equal_range.cc
> @@ -0,0 +1,90 @@
> +// { dg-do run { target c++14 } }
> +
> +#include <map>
> +#include <string>
> +#include <utility>
> +#include <functional>
> +#include <testsuite_hooks.h>
> +
> +struct Z;
> +
> +struct X {
> + std::string s;
> + X(std::string str) : s(str) {}
> + X(Z&&);
> + X(const Z&);
> + friend bool operator<(X const& a, X const& b) { return a.s < b.s; }
> + friend bool operator==(X const& a, X const& b) { return a.s == b.s; }
> +};
> +
> +using cmp = std::less<void>;
> +
> +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 s) : s(s) {}
> + Z(int n) : s(std::string(n, 'a')) {}
> + friend bool operator<(Z const& a, Z const& b) { return a.s < b.s; }
> + friend bool operator<(X const& a, Z const& b)
> + { return ++b.compares, a.s.substr(0, b.s.size()) < b.s; }
> + friend bool operator<(Z const& a, X const& b)
> + { return ++a.compares, a.s < b.s.substr(0, a.s.size()); }
> +};
> +
> +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.
> +
> +template <typename T>
> +T populate(T a)
> +{
> + const std::string vs[] = { "dec", "ded", "dee", "def", "deg", "deh",
> "dei" };
> + for (auto const& v : vs)
> + a[v] = v+v;
> + return a;
> +}
> +
> +void test_equal_range()
> +{
> + std::map<X, std::string, cmp> amap{cmp{}};
> + amap.insert({{X{"abc"}, {"xyz"}}, {X{"def"}, {"uvw"}}, {X{"ghi"},
> {"rst"}}});
> +
> + {
> + auto a = populate(amap);
> + VERIFY(a.size() == 9);
> + Z z{"de"};
> + auto it = a.equal_range(z);
> + VERIFY(it.first != a.end());
> + VERIFY(it.second != a.end());
> + VERIFY(it.first->first == std::string("dec"));
> + VERIFY(it.second->first == std::string("ghi"));
> +
> + VERIFY(z.compares == 7);
> + }
> + {
> + auto a = populate(amap);
> + VERIFY(a.size() == 9);
> + Z z{"de"};
> + auto const& ca = a;
> + auto it = ca.equal_range(z);
> + VERIFY(it.first != ca.end());
> + VERIFY(it.second != ca.end());
> + VERIFY(it.first->first == std::string("dec"));
> + VERIFY(it.second->first == std::string("ghi"));
> +
> + VERIFY(z.compares == 7);
> + }
> +}
> +
> +int main()
> +{
> + test_equal_range();
> +}
> diff --git
> a/libstdc++-v3/testsuite/23_containers/multimap/operations/hetero/equal_range.cc
> b/libstdc++-v3/testsuite/23_containers/multimap/operations/hetero/equal_range.cc
> new file mode 100644
> index 00000000000..490407c244d
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/multimap/operations/hetero/equal_range.cc
> @@ -0,0 +1,90 @@
> +// { dg-do run { target c++14 } }
> +
> +#include <map>
> +#include <string>
> +#include <utility>
> +#include <functional>
> +#include <testsuite_hooks.h>
> +
> +struct Z;
> +
> +struct X {
> + std::string s;
> + X(std::string str) : s(str) {}
> + X(Z&&);
> + X(const Z&);
> + friend bool operator<(X const& a, X const& b) { return a.s < b.s; }
> + friend bool operator==(X const& a, X const& b) { return a.s == b.s; }
> +};
> +
> +using cmp = std::less<void>;
> +
> +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 sv) : s(sv) {}
> + Z(int n) : s(std::string(n, 'a')) {}
> + friend bool operator<(Z const& a, Z const& b) { return a.s < b.s; }
> + friend bool operator<(X const& a, Z const& b)
> + { return ++b.compares, a.s.substr(0, b.s.size()) < b.s; }
> + friend bool operator<(Z const& a, X const& b)
> + { return ++a.compares, a.s < b.s.substr(0, a.s.size()); }
> +};
> +
> +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.
> +
> +template <typename T>
> +T populate(T a)
> +{
> + const std::string vs[] = { "dec", "ded", "dee", "def", "deg", "deh",
> "dei" };
> + for (auto const& v : vs)
> + a.insert({X{v}, {v+v}});
> + return a;
> +}
> +
> +void test_equal_range()
> +{
> + std::multimap<X, std::string, cmp> amap{cmp{}};
> + amap.insert({{X{"abc"}, {"xyz"}}, {X{"def"}, {"uvw"}}, {X{"ghi"},
> {"rst"}}});
> +
> + {
> + auto a = populate(amap);
> + VERIFY(a.size() == 10);
> + Z z{"de"};
> + auto it = a.equal_range(z);
> + VERIFY(it.first != a.end());
> + VERIFY(it.second != a.end());
> + VERIFY(it.first->first == std::string("dec"));
> + VERIFY(it.second->first == std::string("ghi"));
> +
> + VERIFY(z.compares == 7);
> + }
> + {
> + auto a = populate(amap);
> + VERIFY(a.size() == 10);
> + Z z{"de"};
> + auto const& ca = a;
> + auto it = ca.equal_range(z);
> + VERIFY(it.first != ca.end());
> + VERIFY(it.second != ca.end());
> + VERIFY(it.first->first == std::string("dec"));
> + VERIFY(it.second->first == std::string("ghi"));
> +
> + VERIFY(z.compares == 7);
> + }
> +}
> +
> +int main()
> +{
> + test_equal_range();
> +}
> diff --git
> a/libstdc++-v3/testsuite/23_containers/multiset/operations/hetero/equal_range.cc
> b/libstdc++-v3/testsuite/23_containers/multiset/operations/hetero/equal_range.cc
> new file mode 100644
> index 00000000000..a9a479a78cd
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/multiset/operations/hetero/equal_range.cc
> @@ -0,0 +1,90 @@
> +// { dg-do run { target c++14 } }
> +
> +#include <set>
> +#include <string>
> +#include <utility>
> +#include <functional>
> +#include <testsuite_hooks.h>
> +
> +struct Z;
> +
> +struct X {
> + std::string s;
> + X(std::string str) : s(str) {}
> + X(Z&&);
> + X(const Z&);
> + friend bool operator<(X const& a, X const& b) { return a.s < b.s; }
> + friend bool operator==(X const& a, X const& b) { return a.s == b.s; }
> +};
> +
> +using cmp = std::less<void>;
> +
> +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 sv) : s(sv) {}
> + Z(int n) : s(std::string(n, 'a')) {}
> + friend bool operator<(Z const& a, Z const& b) { return a.s < b.s; }
> + friend bool operator<(X const& a, Z const& b)
> + { return ++b.compares, a.s.substr(0, b.s.size()) < b.s; }
> + friend bool operator<(Z const& a, X const& b)
> + { return ++a.compares, a.s < b.s.substr(0, a.s.size()); }
> +};
> +
> +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.
> +
> +template <typename T>
> +T populate(T a)
> +{
> + const std::string vs[] = { "dec", "ded", "dee", "def", "deg", "deh",
> "dei" };
> + for (auto const& v : vs)
> + a.insert(X{v});
> + return a;
> +}
> +
> +void test_equal_range()
> +{
> + std::multiset<X, cmp> aset{cmp{}};
> + aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
> +
> + {
> + auto a = populate(aset);
> + VERIFY(a.size() == 10);
> + Z z{"de"};
> + auto it = a.equal_range(z);
> + VERIFY(it.first != a.end());
> + VERIFY(it.second != a.end());
> + VERIFY(*it.first == std::string("dec"));
> + VERIFY(*it.second == std::string("ghi"));
> +
> + VERIFY(z.compares == 7);
> + }
> + {
> + auto a = populate(aset);
> + VERIFY(a.size() == 10);
> + Z z{"de"};
> + auto const& ca = a;
> + auto it = ca.equal_range(z);
> + VERIFY(it.first != ca.end());
> + VERIFY(it.second != ca.end());
> + VERIFY(*it.first == std::string("dec"));
> + VERIFY(*it.second == std::string("ghi"));
> +
> + VERIFY(z.compares == 7);
> + }
> +}
> +
> +int main()
> +{
> + test_equal_range();
> +}
> diff --git
> a/libstdc++-v3/testsuite/23_containers/set/operations/hetero/equal_range.cc
> b/libstdc++-v3/testsuite/23_containers/set/operations/hetero/equal_range.cc
> new file mode 100644
> index 00000000000..1c9e7a33518
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/set/operations/hetero/equal_range.cc
> @@ -0,0 +1,90 @@
> +// { dg-do run { target c++14 } }
> +
> +#include <set>
> +#include <string>
> +#include <utility>
> +#include <functional>
> +#include <testsuite_hooks.h>
> +
> +struct Z;
> +
> +struct X {
> + std::string s;
> + X(std::string str) : s(str) {}
> + X(Z&&);
> + X(const Z&);
> + friend bool operator<(X const& a, X const& b) { return a.s < b.s; }
> + friend bool operator==(X const& a, X const& b) { return a.s == b.s; }
> +};
> +
> +using cmp = std::less<void>;
> +
> +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 sv) : s(sv) {}
> + Z(int n) : s(std::string(n, 'a')) {}
> + friend bool operator<(Z const& a, Z const& b) { return a.s < b.s; }
> + friend bool operator<(X const& a, Z const& b)
> + { return ++b.compares, a.s.substr(0, b.s.size()) < b.s; }
> + friend bool operator<(Z const& a, X const& b)
> + { return ++a.compares, a.s < b.s.substr(0, a.s.size()); }
> +};
> +
> +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.
> +
> +template <typename T>
> +T populate(T a)
> +{
> + const std::string vs[] = { "dec", "ded", "dee", "def", "deg", "deh",
> "dei" };
> + for (auto const& v : vs)
> + a.insert(X{v});
> + return a;
> +}
> +
> +void test_equal_range()
> +{
> + std::set<X, cmp> aset{cmp{}};
> + aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
> +
> + {
> + auto a = populate(aset);
> + VERIFY(a.size() == 9);
> + Z z{"de"};
> + auto it = a.equal_range(z);
> + VERIFY(it.first != a.end());
> + VERIFY(it.second != a.end());
> + VERIFY(*it.first == std::string("dec"));
> + VERIFY(*it.second == std::string("ghi"));
> +
> + VERIFY(z.compares == 7);
> + }
> + {
> + auto a = populate(aset);
> + VERIFY(a.size() == 9);
> + Z z{"de"};
> + auto const& ca = a;
> + auto it = ca.equal_range(z);
> + VERIFY(it.first != ca.end());
> + VERIFY(it.second != ca.end());
> + VERIFY(*it.first == std::string("dec"));
> + VERIFY(*it.second == std::string("ghi"));
> +
> + VERIFY(z.compares == 7);
> + }
> +}
> +
> +int main()
> +{
> + test_equal_range();
> +}
> --
> 2.54.0
>
>
