> Merging a list takes O(1) time Depends on the list implementation. I assume we are talking C++ lists? in that case yeah, I can see how you'd instead do a `s

> Merging a list takes O(1) time Depends on the list implementation. I assume we are talking C++ lists? in that case yeah, I can see how you'd instead do a `splice` of sublists. I was thinking more in terms of something like a `vector` in which case adding the sublists in requires copying values from one vector to the source vector. That (especially if done wrong) can involve allocating potentially more than once to drop the results in. But, for the record, there are lock free algorithms that don't require a mutex to add values into a list. You basically CAS the tail pointer with your new value. That being said, I concede that for a list a mutex is probably the wrong choice. It's a better choice in Java which has constraints that prevent (easily) splicing together 2 lists. For the dictionary, implementation is key. A good segmented dictionary is going to be hard to beat.