Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can we use heterogeneous lookup comparator to perform a "partial-match" search on STL associative containers?

Tags:

c++

stl

c++14

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.

like image 326
abigagli Avatar asked Oct 08 '17 15:10

abigagli


1 Answers

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.

like image 71
Davis Herring Avatar answered Nov 20 '22 02:11

Davis Herring