Boost logo

Boost :

From: David B. Held (dheld_at_[hidden])
Date: 2004-03-18 03:15:57

"Rene Rivera" <grafik.list_at_[hidden]> wrote in message
> [...]
> I look at the implementation and it doesn't do what a rank tree does.
> It does make it easier to base a rank tree implementation against it.
> The part that is missing is keeping track of the rank of nodes as the
> tree changes, the constant time op, that lets one have the logN ops
> later on. [ Unless I missed something -- So correct me at will ;-) ]

Hmm...are you sure? Did you look at the rotate_right() and rotate_left()
functions? The "indexes" wouldn't be correct if you didn't adjust them
on insert/delete. Essentially, what I call "index" is probably what you
call "rank".

> It also looks to me that there is a much better way to support the
> custom index aspect of assoc containers with something I thought
> about recently, tuple_adaptor... The idea is to have a tuple
> compatible interface that can access a subset of a larger structure.
> You can then use the tuple adaptor as the comparison/index.
> Basically abstracting out the "index" like functionality you have. Here
> are some notes I made up about it last week...
> [...]

Actually, this sounds almost exactly like what Joaquin's IndexedSet
does. You might want to take a closer look at that if you haven't
already. I probably will soon so I can give it a thorough review.


Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (
Version: 6.0.581 / Virus Database: 368 - Release Date: 2/9/2004

Boost list run by bdawes at, gregod at, cpdaniel at, john at