Есть ли эквивалентные объекты компаратора C ++ для BTreeMap и других вещей, которые зависят от 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.Есть ли какая-то техника, которую я еще не понял, чтобы сделать эквивалент?

РЕДАКТИРОВАТЬ

В моем примере была опечатка, которая помешала мне понять, что С ++на самом деле не работает.Я переоцениваю проблему.

Answer 1

Способ сделать это в ржавчине - завернуть ключ в новый тип и реализовать Ord так, как вы этого хотите:

use std::cmp::Ordering;
use std::collections::BTreeMap;

const EPSILON: f64 = 0.001;

struct MyFloat (f64);

impl Ord for MyFloat {
    fn cmp (&self, other: &MyFloat) -> Ordering {
        if (self.0 - other.0).abs() < EPSILON {
            // I assume that this is what you wanted even though the C++ example
            // does the opposite
            Ordering::Equal
        } else if self.0 < other.0 {
            Ordering::Less
        } else {
            Ordering::Greater
        }
    }
}

impl PartialOrd for MyFloat {
    fn partial_cmp (&self, other: &MyFloat) -> Option<Ordering> {
        Some (self.cmp (other))
    }
}

impl PartialEq for MyFloat {
    fn eq (&self, other: &MyFloat) -> bool {
        (self.0 - other.0).abs() < EPSILON
    }
}

impl Eq for MyFloat {}

fn main() {
    let mut map = BTreeMap::new();
    map.insert (MyFloat (1.0), 1);
    map.insert (MyFloat (2.0), 2);
    map.insert (MyFloat (3.0), 3);

    let found = map.get (&MyFloat (1.00001));
    println!("Found: {:?}", found);
}

детская площадка

Обратите внимание, что это будет работать, только если ключи конечны и разнесены более чем на EPSILON.

Answer 2

Существует причина, по которой типы с плавающей запятой не поддерживают Ord.Внутренние элементы BTreeMap делают предположения о разработчиках Ord, которые позволяют ему быть более эффективным, но если эти предположения оказываются неверными, то это может привести к неопределенному поведению, поскольку эти предположения основаны на unsafe кодПлавающие точки не могут удовлетворить эти предположения из-за существования NaN, значений, которые представляют бесконечность, и природы арифметики с плавающей запятой, которая означает, что «одно и то же» число может иметь различные двоичные представления.

Вероятно, ваш код C ++страдать от тех же проблем, но иногда кажется, что код с неопределенным поведением просто работает.До тех пор, пока однажды это не произойдет - это просто природа неопределенного поведения!

Плавающие точки хороши для представления мер или в тех случаях, когда значения могут иметь сильно различающиеся порядки величин.Если вы сделаете расчет расстояний между городами, а цифры будут отклоняться на несколько нанометров, вам все равно.Вам никогда не придется искать другой город, который будет точно на том же расстоянии, что и Лондон от Нью-Йорка.Скорее всего, вы будете рады найти город, который находится на таком же расстоянии до ближайшего 1 км - число, которое вы можете сравнить как целое число.

Что подводит меня к вопросу , почему вы используете числа с плавающей запятой в качестве ключей?Что это значит для вас и что вы пытаетесь там хранить?Является ли f64::NAN значением, которое вы хотите использовать?Является ли 45.00000000001 "таким же", как 45.00000000001001?Вы с такой же вероятностью будете хранить очень большие числа, как очень маленькие?Точное равенство имеет смысл для этих чисел?Являются ли они результатом вычислений, в которых могут быть ошибки округления?

Невозможно сказать вам, что здесь делать, но я могу предложить вам взглянуть на свою реальную проблему и смоделировать ее так, чтобы она отражалаваши реальные ограничения.Если вы заботитесь только о конкретной точности, то округлите числа до этой точности и сохраните их в типе с фиксированной точкой , или целом числе, или, возможно, рациональном , все из которыхреализовать Ord.

Исходя из вашего кода C ++, похоже, что вы довольны точностью 0.001.Таким образом, вы можете хранить свои ключи как целые числа - вам просто нужно помнить, чтобы выполнить преобразование и умножить / разделить на 1000 в зависимости от ситуации.Вам придется иметь дело с возможностью NaN и бесконечностями, но вы будете делать это в безопасном коде, поэтому вам не придется беспокоиться о UB.

Вот как вы можете использоватьnum-rational Ящик, чтобы получить что-то похожее на ваш код 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);
}

Answer 3

Я думаю, вы должны использовать свой собственный тип и реализовать свою черту Ord:

#[derive(PartialOrd, Debug)]
struct MyNumber {
    value: f64,
}

impl MyNumber {
    const EPSILON: f64 = 0.001;
    fn new(value: f64) -> Self {
        Self { value }
    }
}

impl PartialEq for MyNumber {
    fn eq(&self, other: &MyNumber) -> bool {
        if f64::abs(self.value - other.value) < MyNumber::EPSILON {
            return true;
        } else {
            return false;
        }
    }
}

impl Eq for MyNumber {}

use std::cmp::Ordering;

impl Ord for MyNumber {
    fn cmp(&self, other: &MyNumber) -> Ordering {
        if self == other {
            Ordering::Equal
        } else if self < other {
            Ordering::Less
        } else {
            Ordering::Greater
        }
    }
}

fn main() {
    use std::collections::BTreeMap;

    let mut map = BTreeMap::new();
    map.insert(MyNumber::new(1.0), 1);
    map.insert(MyNumber::new(2.0), 2);
    map.insert(MyNumber::new(3.0), 3);

    println!("{:?}", map.get(&MyNumber::new(1.0001)));
}

Но я думаю, что она не соответствует требованию для BTreeMap.