Unordered set in c++

Question

If I provide a custom compare for double, do I have to override the hash? E.g. this piece of code

#include <iostream>
#include <unordered_set>
#include <set>
#include <cmath>

int main()
{
    auto comp = [](double x, double y) { return fabs(x - y) < 1e-10; };
    

    std::unordered_set<double, std::hash<double>, decltype(comp)> theSet(2, std::hash<double>(), comp);

    std::cout.precision(17);
    
    theSet.insert(1.0);
    theSet.insert(1.0 + 1e-13);
    theSet.insert(1.0 - 1e-13);
    theSet.insert(1.2);
    theSet.insert(1.00000000000001);
    theSet.insert(3.2);

    std::cout << "Hash set 
";

    for (const auto& setEl : theSet)
    {
        std::cout << setEl << "
";
    }   
}

Produces (in http://cpp.sh/, when using MS VS Studio 2019 all repeated values seem to remain)

Hash set 

1

0.99999999999989997

3.2000000000000002

1.2

1.00000000000001

It seems to filter out 1.0 + 1e-13 and 1.0 - 1e-13, but it leaves the other repeated values according to the comparison function.

question from:https://stackoverflow.com/questions/65937736/unordered-set-in-c

Answer 1

You don’t want hashing for this: you want a data structure that preserves the relevant order topology, not one that deliberately scrambles the input to be as uniform as possible. While it is possible to use hashing in conjunction with binning, for your problem a simple ordered list or set is sufficient.

If you can store all the numbers, you can just sort them and then walk over them skipping ones that are too close (which still admits some ambiguity in terms of which values to compare). Otherwise, if the number of collisions is high, use a std::set and check the adjacent values prior to each insertion (again, there is some arbitrariness in that the insertion order affects the result).