[PATCH] libstdc++: make trees hetero equal_range O(lg n) [PR118851]
Nathan Myers
ncm@cantrip.org
Fri Jul 3 13:10:28 GMT 2026
Thank you both.
On 7/3/26 8:48 AM, Jonathan Wakely wrote:
> On Wed, 1 Jul 2026 at 08:12, Tomasz Kaminski <tkaminsk@redhat.com> wrote:
>> On Wed, Jul 1, 2026 at 1:33 AM Nathan Myers <ncm@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
>>>
>
More information about the Libstdc++
mailing list