search

orlp / slotmap

Slotmap data structure for Rust
zlib License
1.12k stars 70 forks source link

Allow converting values, preserving keys #80

Open NickNick opened 2 years ago

NickNick commented 2 years ago

I have a slotmap like <FooID, FooV1> and now I'd like to make <FooID, FooV2>, without changing the keys. Is there some way I can do this? I couldn't figure it out. Thanks.

orlp commented 2 years ago

Right now there isn't a direct way to do this on a slotmap. You could have the keys allocated by one slotmap and then store the values in a SecondaryMap. You can have multiple SecondaryMaps with the same key, so creating a v2 shouldn't be an issue.

NeverGivinUp commented 2 years ago

Same requirement here. Though it took a lot of debugging to even notice the source of my problem...

I layout a graph. The layout happens in sequential process steps. In each step I need some shared and some different data. When I convert the nodes they get new keys. But the edges and other data structure still refer to the old indices. And since the keys are of the same type, this went unnoticed for a while and was really hard to debug, when I eventually noticed it.

Update the references to nodes (the keys) would take a lot of computing time. There usually are much more references to nodes than there are nodes.

I havn't looked into using a SecondaryMap yet. What is the impact of using SecondaryMap on cache locality?

NeverGivinUp commented 2 years ago

@orlp Using SecondaryMap works well, generally. And the conversion quite easy, too. I have some duplicate data now, but that isn't so bad, and could be remedied, if it proved problematic.

One problem I noted is that when iterating over the secondary map after removing an element from the primary, but not from the secondary, the removed element still is iterated.

orlp commented 2 years ago

@NeverGivinUp

One problem I noted is that when iterating over the secondary map after removing an element from the primary, but not from the secondary, the removed element still is iterated.

Yes, a SecondaryMap is completely independent from its primary map. It can re-use slots so old things get deleted automatically eventually if their space is needed, but nothing is guaranteed. If you want them to stay synced you have to perform a delete on a primary map and all secondary maps.

Note that I do think I will implement the following function in slotmap 2.0, when I have the time and energy to make it:

pub fn map<U, F>(self, f: F) -> SlotMap<K, U>
where F: FnMut((K, V) -> U)