Evan Laforge
I've wondered if it's faster to insert many keys by successive insertion, or by building another map and then unioning, and likewise with deletion. I eventually decided on successive, thinking a log n build + merge is going to be slower than a m*log n for successive insertion. So I wound up with:
If you don't already have the keys in a map, I don't think you gain much by building a map and then merging rather than just inserting them directly. It will produce extra garbage (unless you have some interest in the map you're building), and you have to make the same spine traversals in building the map as you would have inserting into the larger map (and then you have to traverse the larger map during merging). But again, thanks to Criterion, benchmarking is cheap and easy. No need to believe in the folklore or opinions of others :) Though, if the set of keys to be added is very large, then the build+merge approach would allow you to parallelize the building of the map (split the key set in "half" and build maps for each set, recursing as necessary; then either merge the new maps together before merging with the target map, or just merge them with the target map in serial). -- Live well, ~wren