Tracking Issue for VecDeque binary search functions

[vojtechkral]

Feature gate: #![feature(vecdeque_binary_search)]

This is a tracking issue for VecDeque::binary_search{,_by,_by_key}(), formerly RFC rust-lang/rfcs#2997

Public API

// alloc::collections::vec_deque

impl<T> VecDeque<T> {
    pub fn binary_search(&self, x: &T) -> Result<usize, usize>
    where
        T: Ord;

    pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>
    where
        F: FnMut(&'a T) -> Ordering;

    pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, f: F) -> Result<usize, usize>
    where
        F: FnMut(&'a T) -> B,
        B: Ord;

    pub fn partition_point<P>(&self, mut pred: P) -> usize
    where
        P: FnMut(&T) -> bool;
}

Steps / History

• Implementation: liballoc: VecDeque: Add binary search functions #77751
• Final commenting period (FCP)
• Stabilization PR: Stabilize vecdeque_binary_search #83362

Unresolved Questions

• Stop at Equal like we do for []? Tracking Issue for VecDeque binary search functions #78021 (comment)
• Add partition_point too, just like [] has?

[m-ou-se]

We recently changed slice::binary_search_by to stop directly at Ordering::Equal, and added slice::partition_point for a binary search that only considers less and greater than. Maybe we should do the same for VecDeque.

[vojtechkral]

@m-ou-se Okay, I can do that...

[vojtechkral]

@m-ou-se I added the quick return for Ordering::Equal (locally in my branch so far), but I'm not sure about partition_point(). Do you think that's useful for a VecDeque too?

[m-ou-se]

I added the quick return for Ordering::Equal (locally in my branch so far)

Feel free to send that as a PR and assign me with r? @m-ou-se.

I'm not sure about partition_point(). Do you think that's useful for a VecDeque too?

I don't have a very strong opinion on that. I think it might be useful, but I'd be fine with starting the FCP for just the three VecDeque::binary_search* functions.

[vojtechkral]

Sorry about the radio silence, I've added partition_point() as well, will create the PR tomorrow...
PR: #84145