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

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2006-07-30 14:26:39

Johan Råde wrote:
> 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.

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.

> There will be no ranks and no trees visible through
> the public interface of the class.

Why not? It is perfectly useful information in some algorithms and use 
cases. Specifically that information is why I wrote the my 
implementation. It allows bidirectional mapping of the index and value 
(through the iterator).

> The name of a class should reflect its interface
> and its observable behaviour,
> and not its implementation.

Yes. But you are limiting the implementation to reflect your use case.

PS. There have been many times when I wished I had access to the tree 
internals of map and set to improve the efficiency of some algorithms. 
So it's not just a problem in this case.

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo