Is there an equivalent to C++ comparator objects for BTreeMap and other things that rely on Ord?

Question

I can't seem to accomplish the same things with the Ord trait that I was able to with C++ comparator objects. Take this simplification of more complicated scenarios for example:

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);

I want a comparator to have some runtime context, like an epsilon value. I can't figure out how you would do this with BTreeMap since I can't add state to the Ord trait. Is there some technique I haven't figured out yet to do the equivalent?

EDIT

I had a typo in my example that prevented me from realizing the C++ didn't actually work. I'm reevaluating the problem.

Answer 1

There is a reason why floating point types do not implement Ord. The internals of BTreeMap make assumptions about implementors of Ord, which allow it to be more efficient, but if those assumptions turn out to be incorrect, then it can lead to Undefined Behaviour, because these assumptions are relied upon in unsafe code. Floating points cannot satisfy these assumptions because of the existence of NaN, values that represent infinity and the nature of floating point arithmetic which means the "same" number can have different binary representations.

Your C++ code is likely to suffer from the same issues, but sometimes code with Undefined Behaviour just seems to work. Until one day when it doesn't - that's just the nature of Undefined Behaviour!

Floating points are good for representing measures or where the values can have massively varying orders of magnitude. If you do a calculation about the distances between cities and the numbers are off by a few nanometres, you don't care. You'll never have to find another city that is exactly the same distance as London is from New York. More likely you'll be happy to search for a city that is the same distance to the nearest 1 km - a number that you can compare as an integer.

Which brings me to the question of why are you using floating point numbers as keys? What does it mean to you and what are you trying to store there? Is f64::NAN a value that you want to be valid? Is 45.00000000001 the "same" as 45.00000000001001? Are you just as likely to be storing very large numbers as very tiny numbers? Is exact equality something that makes sense for these numbers? Are they the result of a computation, which could have rounding errors?

It's not possible to tell you what to do here, but I can suggest that you look at your real problem and model it in a way that reflects your real constraints. If you only care about a specific precision, then round the numbers to that precision and store them in a fixed-point type, or an integer, or perhaps a rational, all of which implement Ord.

Based on your C++ code, it looks like you are happy with a precision of 0.001. So you can store your keys as integers - you'll just have to remember to do the conversion and multiply/divide by 1000 as appropriate. You'll have to deal with the possibility of NaN and infinities, but you'll do it in safe code, so you won't have to worry about UB.

Here is how you could use the num-rational crate to get something with similar behaviour to your C++ code:

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 2

I think you should use your own type and implement yourself Ord trait:

#[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)));
}

But I think it doesn't match the requirement for a BTreeMap.

Answer 3

The way to do that in rust is to wrap your key in a newtype and implement Ord the way you want it:

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);
}

playground

Note that this will only work if the keys are finite and spaced by more than EPSILON.