Please teach me if you know any algorithm which has no hole, O(1)
deletion, preserving insertion order, and efficient and fast as array.
I would think the goal here would be to re-order once in a while to remove the holes. But that would take time, of course, so you wouldn't want to do it on every deletion. But when?
One option: maybe too specialized, but it could re-pack the array when an indexing operation is made -- since that operation is O(N) anyway. And that would then address the issue of performance for multiple indexing operations -- if you made a bunch of indexing operation in a row without deleting (which would be the case, if this is an alternative to making a copy in a Sequence first), then the first one would repack the internal array (presumably faster than making a copy) and the rest would have O(1) access.
Given that this use case doesn't appear to be very important, I doubt it's worth it, but it seems it would be possible.
Another thought -- could the re-packing happen whenever the entire dict is iterated through? Though maybe there's no way to know when that's going to happen -- all you get are the individual calls for the next one, yes?
> About the hole, I was thinking that in theory the problem can be circumvented using a modified version of lookdict.
lookdict searches for a key and returns its position in the ma_keys array. I suppose it's possible to do the contrary: search for the index and return the key.
What do you think (theoretically speaking)?
but isn't searching for the index going to require iterating through the array until you find it? i.e. that O(N) operation we're trying to avoid?
-CHB