Tracking Issue for `BTreeSet` entry APIs

[cuviper]

Feature gate: #![feature(btree_set_entry)]

This is a tracking issue for Entry and entry-like methods on BTreeSet.

Public API

impl<T, A: Allocator + Clone> BTreeSet<T, A> {
    pub fn get_or_insert(&mut self, value: T) -> &T
    where
        T: Ord,
    {...}
    pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T
    where
        T: Borrow<Q> + Ord,
        Q: Ord,
        F: FnOnce(&Q) -> T,
    {...}

    pub fn entry(&mut self, value: T) -> Entry<'_, T, A>
    where
        T: Ord,
    {...}
}

pub enum Entry<'a, T, A: Allocator + Clone = Global> {
    Occupied(OccupiedEntry<'a, T, A>),
    Vacant(VacantEntry<'a, T, A>),
}
pub struct OccupiedEntry<'a, T, A: Allocator + Clone = Global> {...}
pub struct VacantEntry<'a, T, A: Allocator + Clone = Global> {...}

impl<T: Debug + Ord, A: Allocator + Clone> Debug for Entry<'_, T, A> {...}
impl<T: Debug + Ord, A: Allocator + Clone> Debug for OccupiedEntry<'_, T, A> {...}
impl<T: Debug + Ord, A: Allocator + Clone> Debug for VacantEntry<'_, T, A> {...}

impl<'a, T: Ord, A: Allocator + Clone> Entry<'a, T, A> {
    pub fn insert(self) -> OccupiedEntry<'a, T, A> {...}
    pub fn or_insert(self) {...}
    pub fn get(&self) -> &T {...}
}

impl<'a, T: Ord, A: Allocator + Clone> OccupiedEntry<'a, T, A> {
    pub fn get(&self) -> &T {...}
    pub fn remove(self) -> T {...}
}

impl<'a, T: Ord, A: Allocator + Clone> VacantEntry<'a, T, A> {
    pub fn get(&self) -> &T {...}
    pub fn into_value(self) -> T {...}
    pub fn insert(self) {...}
}

Steps / History

• Implementation: Add BTreeSet entry APIs to match HashSet #133548
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• None yet.

See also #60896 for HashSet.

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[sunshowers]

I have a fun use case for this related to https://docs.rs/iddqd: as part of it I need a sorted set with a custom comparator which must be passed in (data required for comparisons cannot really be stored on the elements themselves).

I'm currently using a thread-local for this purpose, but I realized that Borrow provides just enough flexibility to make this possible without a thread-local.

For the three basic operations, find, insert, and remove:

• find and remove work on stable Rust today.
• insert does not work because it accepts a concrete T, not a borrowed form of it. However, as of rustc 1.89.0-nightly (4d051fb30 2025-05-18), get_or_insert_with works great for my purpose.

I've written up some notes at https://github.com/oxidecomputer/iddqd/blob/37da27bc6eb62f23e19f947b0487e01bd17bf209/crates/iddqd/src/support/btree_table.rs#L21-L66, and I have a PoC showing get_or_insert_with working with nightly Rust and removing a bunch of unsafe code: oxidecomputer/iddqd#16

I know this is pushing the limits of what's legal with BTreeSet, but it would be really cool to have get_or_insert_with available.