Problem binary searching into vector of structs

1

Hi,

rust noob here. I'm happily coding along, but now hit a snag: my attempt to find an element of a vector of structs is cut short by an error message I find no workaround for. Can somebody explain to me what goes on here? I'm really at a loss.

struct CompoundSegment
{
    relative_end: f64
}

fn main() {
   let segments = vec![CompoundSegment{relative_end: 0.5}, CompoundSegment{relative_end: 1.0}];
   let needle = 0.3;
   let pos = segments.binary_search_by(
            |segment| segment.relative_end.cmp(&needle));
   println!("{:?}", pos);
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0599]: no method named `cmp` found for type `f64` in the current scope
  --> src/main.rs:10:44
   |
10 |             |segment| segment.relative_end.cmp(&needle));
   |                                            ^^^ method not found in `f64`
   |
   = note: the method `cmp` exists but the following trait bounds were not satisfied:
           `f64: std::iter::Iterator`
           which is required by `&mut f64: std::iter::Iterator`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0599`.
error: could not compile `playground`.

To learn more, run the command again with --verbose.
2

This is because float point numbers are not totally ordered because of NaN. You can do this:

let pos = segments.binary_search_by(
    |segment| segment.relative_end.partial_cmp(&needle).expect("NaN"));

This will panic if anything in the vector is NaN.

2 Likes
3

Amazing. I’ve encountered a few quirks of IEE754 before, but this one was new.

I wonder about the error I got. I obviously googled it (and explained it), but didn’t find this. Is this just something one has to know, or how can we derive the solution form the error?

4

The compiler's suggestion is leading the wrong way here, unfortunately. It's seemingly talking about Iterator::cmp and not Ord::cmp, and identifying which was meant isn't that clear-cut, when there are multiple traits with a method of the same name.

So indeed, we'd have to understand ourselves that Ord::cmp was not available, since the compiler didn't want to mention it in this case. The reason is that floats don't implement Ord, because of the comparison rules of NaN. I guess this is the sort of interesting thing you'll learn about floats once in Rust, and now you know.

By the way, the comparison operators <, <=, >, >= are assoicated with the PartialOrd trait, and floats implement that.

5

Those ask a related but fundamentally different question than Ord::cmp.
The latter asks "how exactly do the 2 arguments relate to one another?", the answer to which is one of less than, equal, or more than, all of which are encoded in the std::cmp::Ordering enum.
The former however, each ask a more specific question: "is argument 0 less than/less than or equal to/greater than/greater than or equal to argument 1?", the answer to which is 1 bit wide: either true or false.

Because they ask and answer a different question, their use cases are different too.

6

or for any other language that implements floats that conform to the IEEE 754 standard.

In other words, this is a property of the IEEE 754 standard, not of Rust or C/++ or any other language with a conforming implementation.

7

Yep. What you learn in Rust is the implication it has for PartialOrd and Ord impls.

1 Like
8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.