The main utility of the vector_tree is when you must insert or delete many elements in central positions. It is not worst or best than others data structures, it is different. It is only an option more, with different features than other data structures. If you consider it useful, use .Only that
That's the problem, it shouldn't be up to us to figure out if your library is useful. We've all been happily coding in C++ for 10+ years without it. We know how to solve every programming problem we are presented with without the use of your library. Sometimes it is obvious, but in this case it isn't obvious to me where I would want to use your library. You need to provide some kind of motivation for why you think the library is needed. Something like "when you are doing xyz and you run into problem A you end up settling for solution S, but my library is a better solution because of t, u, v." Your iterators are not random access iterators because O(1) iterator arithmetic is a requirement of the standard. Calling std::sort or std::binary_search on a tree seems completely wrong. The tree is a search data structure, why would we want to call an algorithm that doesn't know how to take advantage of the tree data structure? You say you wanted to be able to call these stl algorithms on your iterator types, but you didn't explain why. I can't think of a single programming activity xyz where I run into problem A where your library is a better solution than solution S that I would normally apply, but I shouldn't have to. You should know why you wrote your library and be able to tell us.
About the C++11 stateful allocators, I need a bite of time for to study in deep , and provide you something more than a trivial opinion Sorry!
It is pretty important to figure out how what you're doing relates to the new standard. It takes a while for boost libraries to be accepted and released. Use of the new standard will be even more prevalent by the time your library would be getting widespread exposure. Keeping a small object arena around to recycle elements instead of going always to the allocator is a good idea. I'm pretty sure we can do it with the C++11 stl by baking it into the stateful allocator. It would be much more useful as a general allocator than as a feature of yet another implementation of a few containers. Regards, Luke