You can't sort by any parameter. I had the defects in a vector_tree, and divide the number of defects between the number or cores of the machine, assign to each core their defects and begin to process. The possibility of insert and delete in any position at log(N), was very useful. As you can imagine, the complexity was bigger than the described here, but I thing this is not place for to show a detailed specification of the project.
Interesting that we both have background in chip design. So I surmise that you wanted to simulate equal probability that an electron interact with a defect by generating a random index into your countertree data structure holding defect elements. It's not clear to me why you needed to insert into the middle, however. If you weren't sorting by any parameter why not just push_back each new element onto a vector? Threading obviously brings in a lot of complexity, but I don't see how the countertree solves any of those problems. I could implement fast lookup and randomized indexing into a set using a std::vector and std::set that are cross referenced. First randomly select a vector index with equal then randomly select the set element based upon is value and the distribution function. When removing an element from the set swap its vector element to the end and pop_back() updaing set element index for the swapped end element. Perhaps there is some application where indexes needs to be ordered the same as the set, which would then pretty much require countertree to be made efficient.
About the statefull allocators. I have my own idea, but I need to study more in order to have a founded opinion. The suballocator can be transformed in statefull allocators with a few changes in the actual code, but I need to think about the utility and the problems related.
The list merge/split and thread safety/local being the two problems that spring immediately to my mind. It is because there are problems that we need a library. Regards, Luke