So I was looking at support for heterogeneous lookup in STL's associative containers (since C++14) and got a bit confused about what we can do and what we shouldn't.
The following snippet
#include <algorithm>
#include <iostream>
#include <set>
struct partial_compare : std::less<>
{
//"full" key_type comparison done by std::less
using less<>::operator();
//"sequence-partitioning" comparison: only check pair's first member
bool operator ()(std::pair<int, int> const &lhs, int rhs) const
{
return lhs.first < rhs;
}
bool operator ()(int lhs, std::pair<int, int> const &rhs) const
{
return lhs < rhs.first;
}
};
int main()
{
//Using std::set's lookup
{
std::cout << "std::set's equal_range:\n";
std::set <std::pair<int, int>, partial_compare> s{{1,0},{1,1},{1,2},{1,3},{2,0}};
auto r = s.equal_range (1);
for (auto it = r.first; it != r.second; ++it)
{
std::cout << it->first << ", " << it->second << '\n';
}
std::cout << "std::set's lower_bound + iteration on equivalent keys:\n";
auto lb = s.lower_bound(1);
while (lb != std::end(s) && !s.key_comp()(lb->first, 1) && !s.key_comp()(1, lb->first))
{
std::cout << lb->first << ", " << lb->second << '\n';
++lb;
}
}
//Using algorithms on std::set
{
std::cout << "std::equal_range\n";
std::set <std::pair<int, int>> s{{1,0},{1,1},{1,2},{1,3},{2,0}};
auto r = std::equal_range (std::begin(s), std::end(s), 1, partial_compare{});
for (auto it = r.first; it != r.second; ++it)
{
std::cout << it->first << ", " << it->second << '\n';
}
}
return 0;
}
Produces the following output when compiled with clang-5/libc++:
std::set's equal_range:
1, 1
std::set's lower_bound + iteration on equivalent keys:
1, 0
1, 1
1, 2
1, 3
std::equal_range
1, 0
1, 1
1, 2
1, 3
And the following when compiled with gcc-7.1.0:
std::set's equal_range:
1, 0
1, 1
1, 2
1, 3
std::set's lower_bound + iteration on equivalent keys:
1, 0
1, 1
1, 2
1, 3
std::equal_range
1, 0
1, 1
1, 2
1, 3
By reading the initial N3465 proposal, I think that what I'm doing here should be fine and conceptually identical to what's in the proposal's initial example: a "partial-match" during lookup, relying on "the notion of sequence partitioning".
Now, if I'm understanding correctly, what actually ended up in the standard is N3657, but that doesn't seem to change the concept as it "just" focuses on ensuring heterogeneous lookup member templates are only made available when the provided comparator "is_transparent".
So, I can't really understand why using std::set's equal_range
member template in clang/libc++ doesn't produce the same results of gcc's or the equivalent "lower_bound
+ scan".
Am I missing something and using heterogeneous lookup in this way is actually violating the standard (and then clang is right and the difference between equal_range
and lower_bound
+ scan might be due to UB), or is clang/libc++ wrong?
EDIT: After reading the now accepted answer, I was able to find the relevant bug report for libc++.
There's also a specific question about the difference in behavior of equal_range
template members between libc++ and libstdc++ here on SO that I didn't find while doing my search.
Not sure if this should be deleted or closed, as the one I've linked doesn't have an accepted answer.
This is a bug in libc++: its equal_range implementation (at r315179) immediately returns both iterators upon finding an "equal" element even with heterogeneous comparison.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With