Re: [PATCH] libstdc++: make trees hetero equal_range O(lg n) [PR118851]

[Nathan Myers]

Thank you both.

On 7/3/26 8:48 AM, Jonathan Wakely wrote:

On Wed, 1 Jul 2026 at 08:12, Tomasz Kaminski <tkami...@redhat.com> wrote:

On Wed, Jul 1, 2026 at 1:33 AM Nathan Myers <n...@cantrip.org> 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.

Ran tests on -m64, -m32, and arm64.
I will add that to the commit message.

  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;

If we did that, we should make the same change in the non-transparent
equal_range overloads as well.
I think that could be done separately in a follow-up (and preferably
stop assigning to both __y and __x in a single statement using the
comma operator).

Ack.

+                 __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?

And why use Y{v} for the key instead of just v?

Y has no real role in these tests.
It will not appear in the next patch.

+  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.

Ack.

+
+  {
+    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