3 ms·
If there’s a lot of churn on the tree, does fragmentation rear its head? Or does the version in the key come into play here?
by mattgreenrocks 5y ago
If there’s a lot of churn on the tree, does fragmentation rear its head? Or does the version in the key come into play here?
- nightcracker 5y agoThere is no fragmentation whatsoever in the traditional sense (unusable gaps left due to size mismatches), because a slotmap only stores a single type of value. Thus every slot is interchangeable and memory can always be reused. For iteration however, there can be holes that need to be ignored, if the current number of elements in the slotmap is significantly lower than the the maximum capacity. If iteration needs to be very fast (for e.g. game engines) I do have a solution for that, which is the DenseSlotMap. It uses one extra layer of indirection for random access, but stores the actual data values contiguously in a vector, thus iteration is always fast.
- mattgreenrocks 5y agoYes, holes is a better term. Was wondering if double pointers (as they were) were used, looks like it was right. Thank you for the reply!