Container hierarchy vs. container types

[bearophile]

Andrei Alexandrescu:
> As far as I can tell such changes of containers are a design-time 
> decision, and extremely rarely (never as far as I remember) a runtime 
> decision to hide behind a binary interface.

In your post there's lot of stuff to think about. I can see you are trying to innovate, so here's a comment about data structures of the future. In Gcc 4.5 they have added a profile mode:

http://gcc.gnu.org/onlinedocs/libstdc++/manual/profile_mode.html
It gives you simple suggestions, based on simple statistics collected at run-time, about data structures choice.

Today data structures are mostly chosen at compile time by the programmer, but once the runtime has those statistics collected at run-time, you can think of feeding that data into the program itself at runtime, so data structures can adapt themselves. This can be useful for programs that run on servers, for minutes, hours or days, where they have to face different workloads as time passes.

Bye,
bearophile