Why does Vec<T> expect &T as the argument to binary_search?

user_845567 0
Viewed 145

This question is predicated on the assumption that a friendly/ergonomic API in rust should prefer a reference to a type Q where T: Borrow<Q> instead of expecting &T directly. In my experience working with the API of other collection types like HashMap, this definitely seems to be the case. That said...

How come the binary_search method on Vec<T> is not defined that way? Currently, on stable, the binary_search implementation is as follows:

pub fn binary_search(&self, x: &T) -> Result<usize, usize>
where
    T: Ord,
{
    self.binary_search_by(|p| p.cmp(x))
}

It seems like the following would be a better implementation:

pub fn binary_search_modified<Q>(&self, x: &Q) -> Result<usize, usize>
where
    T: Borrow<Q>,
    Q: Ord + ?Sized,
{
    self.binary_search_by(|p| p.borrow().cmp(x))
}

A comparison of the two APIs above:

let mut v: Vec<String> = Vec::new();
v.push("A".into());
v.push("B".into());
v.push("D".into());
let _ = v.binary_search("C"); // Compilation error!
let _ = v.binary_search(&String::from("C")); // Fine allocate and convert it to the exact type, I guess
let _ = v.binary_search_modified("C"); // Far nicer API, does the same thing
let _ = v.binary_search_modified(&String::from("C")); // Backwards compatible

As a more general question, what considerations go into deciding if a method should accept &T or &Q ... where T: Borrow<Q>?

rust
1 Answers

You are right that binary_search() and a few other methods like contains() could be generalized to accept any type that can be borrowed as T, but unfortunately Rust 1.0 was released with the less general signature. And while it looks like using Borrow is strictly more general, attempts to implement that change broke type inference in too many cases.

There are countless Github issues, PRs and forum discussion on this topic. If you want to follow the history of the attempts to fix this, I suggest starting at the PR finally reverting the attempts to make binary_search() more general and working your way backwards.

Regarding your more general question, my advice would be the same as for any API design question: think about the use cases. Using an additional type parameter makes the code somewhat more complex, and the documentation and compiler errors become less obvious. For methods on a trait, the type parameter will render the trait unusuable for trait objects. So if you can think of convincing use cases for the more general version using Borrow, go for it, but in the absence of a convincing use case it's better to avoid it.

user_2796270
Related