KeyedVecSet to support Vec<V> when V already includes K

[youknowone]

Description

Hi, I forked this project a while ago (I accidently opened #29) and implemented KeyedVecSet, which is a generalized version of VecSet or VecMap.

https://github.com/youknowone/vecset-rs/blob/main/src/keyed.rs#L46-L53

KeyedVecSet<K, V> is represented as Vec<V>, but V implements Keyed<K> to provide ability to retrieve K from V.

VecMap<K, V> is a specialized case of KeyedVecSet<K, (K, V)> when fn keyed(v: (K, V)) -> K. And VecSet<K> is a specialized case of KeyedVecSet<K, K>.

I had a use case of vectors which has key in the middle of the data. And this feature worked well for my use case for a while.

If you are interested in this feature, I'd like to contribute this feature back to vecmap-rs again.

Thanks for making a good project!

Additional Information

No response

[youknowone]

@martinohmann This is not a feature request. I will make a patch if you don't mind. Please let me know if you like or dislike the idea. Thanks!

[martinohmann]

@youknowone Apologies for the silence!

The idea sounds interesting, but it will also mean a quite substantial change to the crates' internals and API surface.

I have a couple of questions and also concerns. Maybe you can help me resolve these:

• Looking at your implementation it seems like VecMap<K, V> (and thus VecSet<T>) would keep the same memory layout as before if they would be implemented in terms of KeyedVecSet, is that correct?
• You added blanket implementations of Keyed for K and (K, V). Can you imagine use cases where these could prevent the implementation of Keyed for a custom type?
• The newly introduced API surface will be quite large and I was wondering how we could ensure that this stays maintainable. One opportunity worth exploring is whether it would be possible to implement VecSet<T> as a type alias for KeyedVecSet<T, T> or whether we could benefit from Deref implementations here. I was reluctant to implement Deref for VecMap and VecSet so far since this would expose the internal Vec, but with KeyedVecSet in the middle it might be worth thinking about that since we'd be in control of the exposed methods.
• Did you already had a chance to check how KeyedVecSet would interact with the MutableKeys extension trait? https://github.com/martinohmann/vecmap-rs/blob/main/src/map/mutable_keys.rs#L16-L132 Your fork does not seem to include that yet.

Overall I have to say that you seem to have put a lot of thought and work into it, great job! However, I'd like to better understand the impact of this first before we can talk about whether this can be part of vecmap-rs or not. In the end I'm maintaining this in my spare time and would like to keep the cost of maintaining it low 🙂.

[youknowone]

Thank you for the reply.

The idea sounds interesting, but it will also mean a quite substantial change to the crates' internals and API surface.

The goal is to keep the public interface of VecSet and VecMap the same as it is now. I will make sure of that when submitting patches. The internals will change significantly, yes.

• Looking at your implementation it seems like VecMap<K, V> (and thus VecSet<T>) would keep the same memory layout as before if they would be implemented in terms of KeyedVecSet, is that correct?

Yes, both of them keep the same layout because the internal representation of the new VecSet and VecMap is based on KeyedVecSet. KeyedVecSet itself is just a wrapper around Vec<V>.

• You added blanket implementations of Keyed for K and (K, V). Can you imagine use cases where these could prevent the implementation of Keyed for a custom type?

This prevents implementing Keyed for a (V, K) tuple. I consider that a caveat of current implementation. Introducing something like struct VecMapSlot((K, V)) and making struct VecMap<K, V>(KeyedVecSet<VecMapSlot((K, V))>) would resolve the issue.

• The newly introduced API surface will be quite large and I was wondering how we could ensure that this stays maintainable. One opportunity worth exploring is whether it would be possible to implement VecSet<T> as a type alias for KeyedVecSet<T, T> or whether we could benefit from Deref implementations here. I was reluctant to implement Deref for VecMap and VecSet so far since this would expose the internal Vec, but with KeyedVecSet in the middle it might be worth thinking about that since we'd be in control of the exposed methods.

A type alias is not possible, because V in KeyedVecSet<V> is directly exposed through mutable access interfaces, and K is part of the V. Currently, all mutable access APIs are marked as unsafe (not because of memory unsafety, but because they are logically critical). This is not the case for VecSet and VecMap. VecSet and VecMap can be a shallow wrapper of KeyedVecSet, but not alias.

Using Deref for this use case is a kind of abuse. I also sometimes implement it that way when there are no other options, but in this case we already have the clear types VecSet and VecMap, so there seems to be no need to abuse Deref.

My first design was to introduce another type like this:

trait Keyed ... {
    type MutBorrow;
    fn key(&self) -> &K;
    fn value(&self) -> Self::MutBorrow;
}

// Then working like:
impl Keyed<K> for (A, K, B) {
    type MutBorrow = (&mut A, &mut B);
    ...
}

This would be more complex, but it could effectively eliminate the need for the unsafe interface.

• Did you already had a chance to check how KeyedVecSet would interact with the MutableKeys extension trait? https://github.com/martinohmann/vecmap-rs/blob/main/src/map/mutable_keys.rs#L16-L132 Your fork does not seem to include that yet.

I haven’t yet, but I will check how it interacts. Thanks for pointing it out.

---

My current fork is refined to the point where it satisfies my personal requirements and demonstrates that VecSet and VecMap can work as wrappers around KeyedVecSet.

The details of Keyed and KeyedVecSet still need some refinement. I am prepared to spend more time to complete vecset, and I opened this issue to decide whether that time should go toward releasing vecset 0.1 with these parts polished, or toward contributing patches to vecmap. We don’t need to settle this immediately. If you believe this feature should be part of vecmap, I’d be happy to keep refining it in a vecmap-compatible direction and continue the discussion.

[youknowone]

Oh... I was forgetting about the key difference. vecmap-rs is unsorted(ordered). while my fork is sorted(unordered). That was the reason MutableKeys is removed in my fork.
In this repository, MutableKeys is possible to be implemented on KeyedVecSet.