时间戳

首页 > 解决方案 > C++中的无序集

c++ - C++中的无序集

问题描述

如果我为双精度提供自定义比较，我是否必须覆盖哈希？例如这段代码

#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 \n";

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

产生（在http://cpp.sh/中，使用 MS VS Studio 2019 时，所有重复值似乎都保留了）

Hash set 

1

0.99999999999989997

3.2000000000000002

1.2

1.00000000000001

它似乎过滤掉了 1.0 + 1e-13 和 1.0 - 1e-13，但它根据比较函数留下了其他重复值。

标签： c++unordered-set

解决方案

您不希望为此进行散列：您需要一种保留相关顺序拓扑的数据结构，而不是故意将输入打乱以使其尽可能统一的数据结构。虽然可以将散列与分箱结合使用，但对于您的问题，一个简单的有序列表或集合就足够了。

如果您可以存储所有数字，您可以对它们进行排序，然后跳过它们，跳过那些太接近的数字（这仍然承认在比较哪些值方面存在一些歧义）。否则，如果冲突的数量很高，请使用 astd::set并在每次插入之前检查相邻的值（同样，插入顺序会影响结果存在一些随意性）。

推荐阅读