c++ - std::map 中的容错键查找

Question

要求:

1. container which sorts itself based on numerically comparing the keys (e.g. std::map)
2. check existence of key based on float tolerance (e.g. map.find() and use custom comparator )
3. and the tricky one: the float tolerance used by the comparator may be changed by the user at runtime!

前两个可以使用带有自定义比较器的 map 来完成:

struct floatCompare : public std::binary_function<float,float,bool>
{
    bool operator()( const float &left, const float &right ) const
    {
        return (fabs(left - right) > 1e-3) && (left < right);
    }
};

typedef std::map< float, float, floatCompare > floatMap;

使用此实现，floatMap.find( 15.0001 ) 将在 map 中找到 15.0。

但是，假设用户不想要 1e-3 的 float 公差。 使此比较器函数在运行时使用可变容差的最简单方法是什么？每次更新 epsilon 时，我不介意根据新的比较器重新创建和重新排序 map 。

初始化后修改的其他帖子here并使用 float 作为键 here没有提供完整的解决方案。

Answer 1

创建后不能更改 map 的顺序(即使这里是浮点类型，你也应该只使用普通的旧 operator<)，你甚至不能使用“容忍”比较运算符，因为它可能违反 map 所需的严格弱排序以维持其状态。

但是您可以使用 lower_bound 和 upper_bound 进行容错搜索。要点是，您将创建一个类似于 equal_range 的包装函数，它为“值 - 公差”执行 lower_bound，然后为“值 + 公差”执行 upper_bound 并查看它是否创建符合条件的非空值范围。