Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk