Re: [boost] [countertree] New Version

Subject: Re: [boost] [countertree] New Version
From: Marsh Ray (marsh_at_[hidden])
Date: 2011-05-02 13:12:35

On 05/01/2011 04:08 PM, Francisco José Tapia wrote:
>
> Technically this library is an implementation of a binary red-black counter
> tree. Colloquially is a balanced tree with an additional counter in each
> leaf. This permit the access to the elements by the position, like in a
> vector. It is a random access container.

This sounds really useful. I was wanting something like this the other day.

I was working on some code for processing named items. Sometimes 
processing of an item will discover other items needing to be processed. 
We don't want to process an item twice.
So I wrote something like:

std::set<string> names_todo;
std::set<string> names_done;
names_todo.insert( initial set of names );
while ( ! names_todo.empty() )
{
     string name = remove_first_element(names_todo); // by ref

     // adds names to 'todo' and 'done' sets.
     process_name(name, names_todo, names_done); // by ref
}

But unfortunately always removing the "first" element of a tree is 
pretty much the worst-case in terms of rebalancing overhead. Probably 
most algorithms use a stack for the 'todo' list but I was passing in a 
set anyway and thought it might benefit from the deduplication.

However, with your container I'd have decent access to an arbitrary 
element of the set. Then the part that was remove_first_element(set&) 
could instead be "remove randomly selected element from set". This way 
I'd expect average case rather than worst-case performance.

What would be even cooler though would be operations like "give me an 
element among those most efficient to remove" and "most efficient to 
insert before/after".

- Marsh