Re: [boost] Interest in O(log n) linear list?

Rene Rivera wrote: et had been named red_and_black_tree.

If given the chance there would be an std::red_black_tree, which is used as an implementation detail of the associative containers. Or more preferable one could specialize map and set to use any associative container implementation of your liking. But until there is a standard tree interfaces this won't happen.

I agree. My ideal container library would have low level container classes such as vector, deque, list, red_and_black_tree, hash_container and higher level adapter classes such as random_access_container, stack, queue, map, multimap, set, multiset It should be possible to instantiate each adapter classes with several different container classes. --Johan Råde