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

From: Johan Råde (rade_at_[hidden])
Date: 2006-07-30 13:31:59

Cromwell Enage wrote:
> --- Johan Råde wrote:
>> "rank_tree" is not a good name.
>> It focuses on the implementation.
> 
> rank_tree is fine for the name of the class.
> 
>> What matters to the user is that it is a
>>
>> 1. sequential container with
>> 2. O(log(n)) look-up and
>> 3. O(log(n)) insertion
> 
> What's needed is a new Container concept that covers
> these requirements.
> 

No. rank_tree is definitely not a good name.
It is as if set had been named red_and_black_tree.
There will be no ranks and no trees visible through
the public interface of the class.
The name of a class should reflect its interface
and its observable behaviour,
and not its implementation.

Aside from this detail, I think this class is an excellent idea.
If you need a sequential container with fast access and fast insertion,
then there is no good option in STL and Boost today.
I will use this class.

--Johan Råde