Support shrinking capacity of slot maps.

[olson-sean-k]

Is it possible for SlotMap and HopSlotMap to support shrinking their capacity? Some Rust collections support this with shrink_to_fit APIs, such as Vec::shrink_to, Vec::shrink_to_fit, and BeachMap::shrink_to_fit.

It looks like a similar idea was mentioned in #38, but it seems the fundamental problem was a bit different in that case.

[orlp]

I don't think this is possible while maintaining key integrity. In order for a key to be correctly rejected as removed we must retain that slot to do so. The function would only help with truly never-used capacity, which there wouldn't be a lot of if you didn't manually reserve a lot to begin with.

If you have some method to replace all keys saved in your data structure(s)¸ what you can do instead is create a new SlotMap, reserve exactly enough for the amount of elements, and insert all elements one by one. E.g.:

{
    let mut shrink_sm = SlotMap::with_capacity(sm.len());
    let new_keys: HashMap<_,_> = sm.drain().map(|orig_key, val| {
        (orig_key, shrink_sm.insert(val))
    }).collect();
    // Iterate over all your data structures using new_keys to replace the old by new keys.
    std::mem::swap(&mut sm, &mut shrink_sm);
}

However this is at your own 'risk' because if you miss replacing a key that key now is essentially a dangling key. It might get rejected or spuriously refer to something else than its original value depending on the state of the slotmap. However it's still 'safe', no uninitialized or invalid values are returned, just not what was originally associated with that key.

[olson-sean-k]

I don't think this is possible while maintaining key integrity. In order for a key to be correctly rejected as removed we must retain that slot to do so.

Gotcha, that makes sense.

If you have some method to replace all keys saved in your data structure(s)¸ what you can do instead is create a new SlotMap, reserve exactly enough for the amount of elements, and insert all elements one by one.

This is exactly what I did before opening this issue. :smile: That made me wonder if shrink_to_fit is possible. The approach you've described seems reasonable and maybe a bit too contrived for a dedicated API in slotmap, so I'll stick to that.

Thanks for the explanation and examples! I'll go ahead and close this.