Re-wrote my benchmark code from scratch a month or two ago with some help from Baptiste Wiche, have run over std::list, std::map, std::multiset, std::deque, std::vector, and for GCC, Chris's segmented_tree implementation. To be honest there's not much point comparing against segmented_tree, as the goals are totally different (efficient random access insertion for segtree, vs efficient unordered erasure/insertion/iteration without pointer invalidation colony), but there was some interest last time I wrote here. In addition I compared against other methods for ensuring pointer/index validity using deques and vectors, to see how those things pan out. Graphs are available here: http://www.plflib.org/colony.htm#benchmarks and here: http://www.plflib.org/stack.htm There are also MSVC 2013 results linked to in the first paragraph of the benchmarks. Comments are welcome, but please read the page first. Stack performs particularly well, outperforming all alternatives in both GCC/MSVC.