3 ms·
With all these attributes, yes; Thanks, I've updated my original comment to reflect this. If you give up insertion order, you can move the latest insertion to
by beagle3 8y ago
With all these attributes, yes; Thanks, I've updated my original comment to reflect this.
If you give up insertion order, you can move the latest insertion to the deleted place, and you're back to O(1).
If you give up the O(1) keys and values list access, you can add a "deleted" bit to every entry to say that it is indeed deleted, but then you can't reuse keys() and values() as-is. Some operations, such as "apply-to-values" can use the vectors with the deleted values, but in general they cannot.
In my experience, deleting from a dict is about 1:10 less frequent, in the sense that the vast majority of dicts never experience a deletion. YMMV, obviously.
Over 3 decades of programming professionally, the K tradeoffs make way more sense to me than the Smalltalk ones.
- aidenn0 8y agoI agree; there are a lot of tradeoffs you can make for the map type, and having O(1) amortized deletion usually comes at a cost of making all the other operations slower (either by a constant factor, or asymptotically). I do wish more people were aware of this because (as you say) deletions are much more rare. Often compilers will use a non-standard map for just this reason (symbol tables basically never delete).
- majewsky 8y ago> the vast majority of dicts never experience a deletion Come to think of it, I cannot recall when I last used the delete() function in Go, even though I write a lot of Go code.