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

[m-ou-se]

@rfcbot merge

[rfcbot]

Team member @m-ou-se has proposed to merge this. The next step is review by the rest of the tagged team members:

• @Amanieu
• @BurntSushi
• @dtolnay
• @joshtriplett
• @m-ou-se
• @sfackler
• @yaahc

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

The RFC will be merged soon.

[JohnTitor]

It has been stabilized (#83362), closing.