std :: map中的容错键查找

Question

要求:

1. 容器根据数字比较键进行排序(例如std :: map)
2. 根据浮动容差检查密钥是否存在(例如map.find()并使用自定义比较器)
3. 而且棘手的是:比较器使用的浮动公差可以由用户在运行时更改!

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

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)将在地图中找到15.0.

但是,假设用户不希望浮动容差为1e-3.使比较器函数在运行时使用可变容差的最简单方法是什么？我不介意每次更新epsilon时都会根据新的比较器重新创建和重新排序地图.

在这里初始化之后修改的其他帖子以及使用浮动作为键在这里没有提供完整的解决方案.

Answer 1

你不能改变map它创建之后的顺序(你应该在这里使用普通的旧operator<浮点类型),你甚至不能使用"容忍"比较运算符,因为它可能违反了所要求的严格 -弱秩序map以维持其状态.

但是你可以用lower_bound和进行宽容搜索upper_bound.要点是,你可以创建一个包装函数很像equal_range,做了lower_bound的"价值-宽容",然后在upper_bound对"价值+宽容",看看它是否创造符合条件的值的非空的范围.

Answer 2

一旦实例化后,您就无法更改元素的排序方式map.如果您要找到一些技术黑客(例如实现一个可以在运行时更改的容差的自定义比较器),它将唤起未定义的行为.

更改排序的主要替代方法是使用不同的排序方案创建另一个映射.这个其他映射可以是索引映射,其中键以不同的方式排序,并且值不是元素本身,而是主映射中的索引.

或者也许你真正想做的不是改变顺序,而是保持顺序并改变搜索参数.

你可以做,有几种方法可以做到.

一种是简单地使用map::lower_bound- 一次使用公差的下限,一次使用公差的上限,刚好超过公差的结束.例如,如果要查找15.0公差为1e-5.您可以lower_bound使用14.99995然后再使用15.00005(我的数学可能会在此处)来查找该范围内的元素.

另一个是使用std::find_if自定义函子,lambda或std::function.您可以通过以下方式声明仿函数:在构造时获取公差和值,并执行检入operator().

由于这是一个家庭作业问题,我将留下实际执行所有这些的繁琐细节.:)