是否有相当于BTreeMap的C++比较器对象和依赖Ord的其他东西？

Question

我似乎Ord无法用C++比较器对象的特性完成同样的事情.以简化更复杂的方案为例:

int epsilon = 0.001;
auto less = [epsilon](const double a, const double b) {
                if (fabs(a - b) > epsilon) {
                    return a < b;
                }
                else {
                    return false;
                }
            };
std::map<float, int, decltype(less)> myMap(less);
myMap.insert(std::make_pair(1.0, 1));
myMap.insert(std::make_pair(2.0, 2));
myMap.insert(std::make_pair(3.0, 3));

auto found = myMap.find(1.0001);
assert(found != myMap.end());
assert(found->second == 1);

我想比较器有一些运行时上下文,比如epsilon值.我无法弄清楚你将如何做到这一点,BTreeMap因为我不能添加状态到Ord特征.是否有一些技术我还没想到要做同等的事情？

编辑

我的例子中有一个拼写错误,使我无法意识到C++实际上并没有起作用.我正在重新评估这个问题.

Answer 1

浮点类型没有实现的原因Ord.BTreeMap对实现者做出假设的内部Ord结构允许它更有效,但如果这些假设结果不正确,那么它可能导致未定义的行为,因为这些假设在unsafe代码中是依赖的.浮点不能满足这些假设,因为存在NaN表示无穷大的值和浮点算术的性质,这意味着"相同"数可以具有不同的二进制表示.

您的C++代码可能会遇到相同的问题,但有时使用未定义行为的代码似乎有效.直到有一天它没有 - 这只是未定义行为的本质!

浮点有利于表示度量或者值可以具有大幅度变化的数量级.如果你计算一下城市之间的距离并且数字偏离几纳米,你就不在乎了.你永远不会找到另一个与伦敦距离纽约完全相同的城市.更有可能您会很乐意搜索距离最近的1公里相同距离的城市 - 您可以将其作为整数进行比较.

这让我想到为什么你使用浮点数作为键？这对你来说意味着什么,你想在那里储存什么？是f64::NAN要有效的值？和45.00000000001"相同"一样45.00000000001001吗？您是否有可能将非常大的数字存储为非常小的数字？确切的平等是否对这些数字有意义？它们是计算的结果,可能有舍入误差吗？

这里不可能告诉你该做什么,但我可以建议你看一下你真正的问题,并以反映你真实约束的方式对它进行建模.如果你只关心一个特定的精度,那么将数字四舍五入到那个精度,并将它们存储在一个定点类型,或一个整数,或者一个理性的,所有这些都实现Ord.

基于您的C++代码,看起来您对精确度感到满意0.001.因此,您可以将键存储为整数 - 您只需要记住进行转换并在适当时乘以/除以1000.你必须处理可能性NaN和无限性,但你会用安​​全的代码来做,所以你不必担心UB.

以下是如何使用num-rationalcrate来获得与C++代码类似的行为:

extern crate num_rational; // 0.2.1

use num_rational::Rational64;
use std::collections::BTreeMap;

fn in_thousandths(n: f64) -> Rational64 {
    // you may want to include further validation here to deal with `NaN` or infinities
    let denom = 1000;
    Rational64::new_raw((n * denom as f64) as i64, denom)
}

fn main() {
    let mut map = BTreeMap::new();

    map.insert(in_thousandths(1.0), 1);
    map.insert(in_thousandths(2.0), 2);
    map.insert(in_thousandths(3.0), 3);

    let value = map.get(&1.into());
    assert_eq!(Some(&1), value);
}