Move into std

[jplatte]

I think that there could be problems w.r.t. inference, but has moving the traits from this crate into std been considered? I couldn't find any issues on the main rust repo about it.

[cuviper]

I think that there could be problems w.r.t. inference,

FWIW, I noted that in indexmap-rs/indexmap#253 (comment), it actually seems to work better if K and Q are reversed, but I ended up not pursuing that further, in sort of a "worse is better" moment to just get something done. If experience shows that it really is better that way, that could be equivalent v2, or maybe a change to make when importing the idea to the standard library.

but has moving the traits from this crate into std been considered? I couldn't find any issues on the main rust repo about it.

I have not, nor would I likely have time for that, but it may make sense to see if it gets any real community use as an external crate first. Of course there are also users who will ignore it until it's in the standard library. If you're interested, feel free to propose this yourself!

[jplatte]

Yeah, it's a bit annoying having to swap the std HashMap for hashbrown::HashMap just to get this, but I might end up doing it. I will likely also not have time to seriously drive an effort of moving this stuff into std, was mostly curious whether I had missed an existing effort that I could follow.

Thanks!

[JakkuSakura]

it actually seems to work better if K and Q are reversed

It would be easier to implement Equivalent if it's inversed
Current:

enum Key {
  K(u32, ExternalKey)
}
impl Equivalent<Key> for (u32, ExternalKey) {
    ..
}

Inversed:

enum Key {
  K(u32, ExternalKey)
}
impl Equivalent<(u32, ExternalKey)> for Key {
    ..
}

Update: disregard this. I forgot there is the orphan rule with relaxed clause.

[clarfonthey]

Just poking in here since this was pointed out by rust-lang/rust#27242 (comment)

As far as crates.io is concerned, only 8 crates directly depend on equivalent, which makes it seem like not many crates have run into a problem where Equivalent works but Borrow doesn't. It would be nice for folks to offer compelling examples of where this trait was useful for them (since I don't doubt they exist), since right now very little data is easily available on how many people are using this.

Like, I think it'd be nice to have this in the standard library, but there's not really a compelling set of data to say it's needed there.

[GrigorenkoPV]

where Equivalent works but Borrow doesn't. It would be nice for folks to offer compelling examples of where this trait was useful for them

https://github.com/droundy/internment/blob/8a5feb354d023a7c69f3889e9e737099ec0e4ea7/src/boxedset.rs#L49-L63

I think this one can be rewritten using these two traits, but not with std's Borrow and how it is currently used in HashMap.

Essentially we have HashSet<Box> and we want to do a lookup using &str. This would be possible if we had HashSet, but we need a Box for address stability. Currently this uses the raw_entry API, but I think it would be possible to rewrite it using something like

struct Newtype<T>(Box<T>);

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

type BoxedSet<T> = HashSet<NewType<T>>;

UPD: No, it's not possible. You have to do Equivalent<Newtype<Q>> for K, but the orphan rule won't let you. So yes,

it actually seems to work better if K and Q are reversed,

[al8n]

I also want this crate to be moved into std, not only for HashMap, but also the Comparable trait for BTreeMap, the traits in this crate improve the flexibility of lookup comparing the current Borrow trait.

I opened a PR which uses Comparable trait instead of Borrow in crossbeam-skiplist, the flexibility given by the Comparable trait shows that around 10% performance improvement for the lookup.

[conradludgate]

Here's a usecase for Comparable which Borrow doesn't properly satisfy:

I want to represent a Map<K, Set<V>>. However, when there's usually very few values associated with a given key, that becomes a very cache and alloc inefficient data structure.

What I would like to do is make use of range queries with Set<(K, V)>, where I can use a range query over (k+0,0)..(k+1,0), so to speak. However, if K is not an integral type, there might not be an easy way to represent the "+1" value. Similarly, there might not be an easy way to represent the "0" value for V.

A way I found to make this work with std (which is wasteful and uses an incorrect implementation of Borrow) is: playground

struct MultiMap<K, V>(BTreeSet<KeyValue<K, V>>);

// The bool here is how we represent `k+1`. 
// `(k, false)` is `k+0`, `(k, true)` is `k+1`.
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug)]
struct Key<K>(K, bool);

#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug)]
struct KeyValue<K, V>(Key<K>, V);

// We borrow just the key, which is how we represent `(k, 0)` for our comparisons.
impl<K, V> Borrow<Key<K>> for KeyValue<K, V> {
    fn borrow(&self) -> &Key<K> {
        &self.0
    }
}

impl<K: Ord, V: Ord> MultiMap<K, V> {
    pub fn get(&self, key: K) -> impl Iterator<Item = &V> where K: Clone {
        // Note that we also need `K: Clone` to represent both bounds.
        // Get the range from k+0..k+1.
        self.0.range(Key(key.clone(), false)..Key(key, true)).map(|KeyValue(_, v)| v)
    }
}

This violates the rules of Borrow as KeyValue(k, v0).borrow() == KeyValue(k, v1).borrow() it does not hold that KeyValue(k, v0) == KeyValue(k, v1).

With comparable this becomes a lot more trivial (using the flipped version of the Comparable trait):

// No longer need the KeyValue new-type.
struct MultiMap<K, V>(BTreeSet<(K, V)>);

struct Key<'a, K>(&'a K, bool);

impl<'a, K: Ord, V> Comparable<Key<'a, K>> for (K, V) {
    fn compare(&self, key: &Key<'a, K>) -> std::cmp::Ordering {
        self.0.cmp(&key.0).then(false.cmp(&key.1))
    }
}

impl<K: Ord, V: Ord> MultiMap<K, V> {
    pub fn get(&self, key: &K) -> impl Iterator<Item = &V> {
        // we can actually include references now, so we no longer need Clone.
        self.0.range(Key(key, false)..Key(key, true)).map(|(_, v)| v)
    }
}

As far as I can tell, there's no btree implementation that offers using Comparable today (besides the skiplist above, which is a very specific usecase and quite different to BTreeMap). I don't think that's not because Comparable isn't useful - I think it's because writing a good BTreeMap is not easy and the std one is good enough. Also, hashtables do often overshadow btrees.

[conradludgate]

cc rust-lang/rust#145986