On Wed, Jul 1, 2026 at 1:33 AM Nathan Myers <[email protected]> wrote:
> 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.
>
> 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.
> ---
LGTM only small nitpicks comments.
You didn't mention running tests.
> libstdc++-v3/include/bits/stl_tree.h | 23 +++-
> .../map/operations/hetero/equal_range.cc | 114 ++++++++++++++++++
> .../multimap/operations/hetero/equal_range.cc | 114 ++++++++++++++++++
> .../multiset/operations/hetero/equal_range.cc | 114 ++++++++++++++++++
> .../set/operations/hetero/equal_range.cc | 114 ++++++++++++++++++
> 5 files changed, 473 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..14dc4ca1416 100644
> --- a/libstdc++-v3/include/bits/stl_tree.h
> +++ b/libstdc++-v3/include/bits/stl_tree.h
> @@ -2026,12 +2026,23 @@ 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(), __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), __yu(__y);
>
Why not integrate the two line below and have:
auto __xu = _S_right(__x), __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..d11a052b3f7
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/map/operations/hetero/equal_range.cc
> @@ -0,0 +1,114 @@
> +// { dg-do run { target c++14 } }
> +
> +#include <map>
> +#include <string>
> +#include <utility>
> +#include <functional>
> +#include <testsuite_hooks.h>
> +
> +struct Y;
> +struct Z;
> +
> +struct X {
> + std::string s;
> + X(std::string str) : s(str) {}
> + X(Y&&);
> + X(const Y&);
> + 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; }
> +};
> +
> +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;
> + explicit Y(std::string s) : s(s) {}
> + 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 bool operator<(Y const& a, Y const& b) { return a.s < b.s; }
> + friend bool operator<(X const& a, Y const& b) { return a.s < b.s; }
> + friend bool operator<(Y const& a, X 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>;
> +
> +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[Y{v}] = Y{v};
>
Why not to use emplace here?
> + return a;
> +}
> +
> +void test_equal_range()
> +{
> + std::map<X, Y, cmp> amap{cmp{}};
> + amap.insert({{Y{"abc"}, 1}, {Y{"def"}, 2}, {Y{"ghi"}, 3}});
>
Do we need to use Y here? As far as can see, this does
std::string -> Y -> X for the key. Couldn't we pass the string-literal
directly. And if we change the value type to int, we could remove
Completely fill out the test file.
> +
> + {
> + 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..e8558f480e9
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/multimap/operations/hetero/equal_range.cc
> @@ -0,0 +1,114 @@
> +// { dg-do run { target c++14 } }
> +
> +#include <map>
> +#include <string>
> +#include <utility>
> +#include <functional>
> +#include <testsuite_hooks.h>
> +
> +struct Y;
> +struct Z;
> +
> +struct X {
> + std::string s;
> + X(std::string str) : s(str) {}
> + X(Y&&);
> + X(const Y&);
> + 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; }
> +};
> +
> +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 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 bool operator<(Y const& a, Y const& b) { return a.s < b.s; }
> + friend bool operator<(X const& a, Y const& b) { return a.s < b.s; }
> + friend bool operator<(Y const& a, X 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>;
> +
> +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(std::pair<const Y, Y>{Y{v}, Y{v}});
> + return a;
> +}
> +
> +void test_equal_range()
> +{
> + std::multimap<X, Y, cmp> amap{cmp{}};
> + amap.insert({{Y{"abc"}, 1}, {Y{"def"}, 2}, {Y{"ghi"}, 3}});
>
// Same comment about Y here here.
> +
> + {
> + 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..052c218c097
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/multiset/operations/hetero/equal_range.cc
> @@ -0,0 +1,114 @@
> +// { dg-do run { target c++14 } }
> +
> +#include <set>
> +#include <string>
> +#include <utility>
> +#include <functional>
> +#include <testsuite_hooks.h>
> +
> +struct Y;
> +struct Z;
> +
> +struct X {
> + std::string s;
> + X(std::string str) : s(str) {}
> + X(Y&&);
> + X(const Y&);
> + 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; }
> +};
> +
> +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 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 bool operator<(Y const& a, Y const& b) { return a.s < b.s; }
> + friend bool operator<(X const& a, Y const& b) { return a.s < b.s; }
> + friend bool operator<(Y const& a, X 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>;
> +
> +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(Y{v});
> + return a;
> +}
> +
> +void test_equal_range()
> +{
> + std::multiset<X, cmp> aset{cmp{}};
> + aset.insert({Y{"abc"}, Y{"def"}, Y{"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..1ba59140fdc
> --- /dev/null
> +++
> b/libstdc++-v3/testsuite/23_containers/set/operations/hetero/equal_range.cc
> @@ -0,0 +1,114 @@
> +// { dg-do run { target c++14 } }
> +
> +#include <set>
> +#include <string>
> +#include <utility>
> +#include <functional>
> +#include <testsuite_hooks.h>
> +
> +struct Y;
> +struct Z;
> +
> +struct X {
> + std::string s;
> + X(std::string str) : s(str) {}
> + X(Y&&);
> + X(const Y&);
> + 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; }
> +};
> +
> +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 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 bool operator<(Y const& a, Y const& b) { return a.s < b.s; }
> + friend bool operator<(X const& a, Y const& b) { return a.s < b.s; }
> + friend bool operator<(Y const& a, X 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>;
> +
> +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(Y{v});
> + return a;
> +}
> +
> +void test_equal_range()
> +{
> + std::set<X, cmp> aset{cmp{}};
> + aset.insert({Y{"abc"}, Y{"def"}, Y{"ghi"}});
>
Same comments regarding Y to rest of the teest.
> +
> + {
> + 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
>
>
