3 ms·
In most situations, you use persistent data structures where you only have to copy the modified leaves. If you really need your type to be backed by a contiguo
by hither_shores 4y ago
In most situations, you use persistent data structures where you only have to copy the modified leaves.
If you really need your type to be backed by a contiguous block of memory, you batch updates (stencils, SIMD, etc.)
- AnimalMuppet 4y agoBut if you modify the leaf, don't you also have to modify the branch node that points to the leaf, so that it points to the new one? And every node from there to the root?
- hither_shores 4y agoYes, you (or rather, core library developers) need to pick a data structure appropriate to your access patterns: linked lists for iteration, search trees for concatenation, finger trees for random access, and so on. But you should be doing this anyway for clarity, even if you face no performance constraints.