On Sat, Jun 30, 2012 at 6:27 AM, bearophile <bearophileh...@lycos.com>wrote:
> 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<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. [1] http://lafstern.org/matt/col1.pdf : Why you shouldn't use set (and what you should use instead) Regards, Brad Anderson