Tobias Pankrath:

But I would generally avoid SList.

It's not good.

And in general linked lists are quite overrated. On modern CPUs it's not easy to find situations where a linked list is better than a dynamic array or a chunked array (that is a dynamic array of pointers to arrays. It's often used to implement deques, etc).

Regarding arrays, maybe a StableVector will be good to have in Phobos:
http://www.boost.org/doc/libs/1_50_0_beta1/doc/html/container/non_standard_containers.html#container.non_standard_containers.stable_vector

Bye,
bearophile

I also think flat_map/_set from that same boost library would be great additions when the time comes to add new stuff to std.container. Red black trees are kind of a niche container[1]. I replaced almost all of my usage of C++'s std::set and std::map with flat_map and flat_set and saw better memory use and far fewer cache misses (assuming I was reading the profiler correctly). It was win-win since I rarely needed std::set/::map's exclusive features (iterator stability, log N insertions). I believe I've read Andrei added something just like these to Loki.