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.
---
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);
+ __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};
+ return a;
+}
+
+void test_equal_range()
+{
+ std::map<X, Y, cmp> amap{cmp{}};
+ amap.insert({{Y{"abc"}, 1}, {Y{"def"}, 2}, {Y{"ghi"}, 3}});
+
+ {
+ 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}});
+
+ {
+ 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"}});
+
+ {
+ 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
