binary_search methods should use Borrow

[osa1]

binary_search() takes a reference of the element instead of using Borrow instances. This is causing problems:

1. &String doesn't make any sense. I should be able to just use &s where s is a String to search in a Vec<String>.
2. Current API sometimes causes redundant allocations (e.g. when I have a &str at hand, I need to allocate a String)
3. API is inconsistent in that some other containers use Borrow for this purpose. E.g. HashMap. As a guideline, I think lookup functions of containers should just use Borrow always.

[huonw]

&String doesn't make any sense. I should be able to just use &s where s is a String to search in a Vec.

Hm, could you clarify this point? &String makes perfect sense, and using &s works fine. The following code compiles and runs:

fn main() {
    let v = vec!["abc".to_string(), "def".to_string()];

    let s: String = "def".to_string();
    println!("{:?}", v.binary_search(&s));
}

---

Also, it's worth noting that binary_search_by exists, and means that there's no fundamental issue with the functionality, it just requires a little more typing:

fn main() {
    let v = vec!["abc".to_string(), "def".to_string()];

    let s: &str = "def";
    println!("{:?}", v.binary_search_by(|x| x.as_str().cmp(s)));
}

(Don't get me wrong, it would be nicer if Borrow worked with the sugary version.)

[huonw]

Nominating for libs team discussion: we should be able to relax the parameter here, but seems worth discussing. (It is formally a minor change, and I suspect that not many people are relying on this function for type inference.)

[osa1]

Hm, could you clarify this point? &String makes perfect sense, and using &s works fine.

I didn't mean it doesn't work or anything like that. I just meant that if I want to pass a read-only reference to a string I'd use &str instead of &String, unless the string will be modified, in which case I'd use &mut String. I don't see any advantage of &String over &str, but it has disadvantages, like, if you have &str you need an allocation, but you can easily get a &str from String without any allocations.

[huonw]

Ah, ok, thanks for scaling back the hyperbole ;) You are correct that &str is strictly more flexible than &String, and the only reason for &String to occur is generic functionality e.g. this example (though obviously Borrow changes that), or calling clone, etc.

[alexcrichton]

The libs team discussed this issue during triage today and the conclusion was that we probably want to do this as it basically means "more code works" at only the slight cost of readability in the docs.

Before this is done, however, we'd like to see a bit of a small survey of the rest of the standard library that this pattern could also apply. For example the contains method on slices could likely also receive this treatment, and there are perhaps other applicable locations for this as well.

[brson]

All we need to do here is the survey @alexcrichton suggested, then make the patch.

[christophebiocca]

I just looked over the standard library and the following are candidates for this change:

Slice

• contains
• binary_search
• binary_search_by_key (Not sure about this one)

Clone

• clone_from

Ord, PartialOrd and PartialEq

The cmp, partial_cmp, eq and ne methods could use this, but as they are public traits this would not (?) be backwards compatible. Also it looks like most of the possible pairs of &str and friends have already been added to all traits except Eq (which has no flexibility for RHS).

LinkedList

• contains

VecDequeue

• contains

[christophebiocca]

Turns out clone_from has the same backcompat issues, as implementers can choose to override the default implementation from the trait.