Tracking Issue for Equivalent and Comparable traits

Feature gate: #![feature(comparable_trait)]

This is a tracking issue for adding the Comparable trait to core, to be used by BTreeMap.

See the https://docs.rs/equivalent/latest/equivalent/ trait.

The Equivalent and Comparable traits allow for more generalised accessors for BTreeMap or HashMap than what Borrow + Ord/Borrow + Eq can allow today.

Public API

// core::cmp

pub(crate) trait Equivalent<Q: ?Sized> {
    fn equivalent(&self, key: &Q) -> bool;
}

impl<K: ?Sized, Q: ?Sized> Equivalent<Q> for K
where
    K: Borrow<Q>,
    Q: Eq,
{
}

pub(crate) trait Comparable<Q: ?Sized>: Equivalent<Q> {
    fn compare(&self, key: &Q) -> Ordering;
}

impl<K: ?Sized, Q: ?Sized> Comparable<Q> for K
where
    K: Borrow<Q>,
    Q: Ord,
{
}

// alloc::collections::btree
impl<K, V> BTreeMap<K, V> {
    fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        Q: ?Sized,
        K: Comparable<Q>;
}

Steps / History

(Remember to update the S-tracking-* label when checking boxes.)

• Implementation: #144506
• Final comment period (FCP)^1
• Stabilization PR

Unresolved Questions

• Should we use K: Comparable<Q> or Q: Comparable<K>. https://github.com/indexmap-rs/equivalent/issues/5

Start by reading the implementation referenced in PR #144506 and the proposed APIs under core::cmp and alloc::collections::btree. Review the unresolved Comparable direction and the linked equivalent trait discussion; this tracking issue is done only after implementation, final comment period, and stabilization are complete.