Boost logo

Boost :

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-06-03 08:19:24

On Sun, 3 Jun 2001 dheld_at_[hidden] wrote:

> An associative vector allows me to do this in good time, but the
> complexity charateristics of the other common operations (i.e. insert
> and delete) is undesirable. A std::map allows me to do this as well,
> but the complexity cost of iteration is exorbitant. For this
> application (and many other similar ones, I suspect), the indexed map
> is a respectable tradeoff between insert, delete, associative lookup
> and indexed lookup (all O(log n)).

Given all of that, the inverse function position of key will find a
use also. Maybe m.pos(iter). Yes, distance(m.begin(), iter) would
get it in O(N), but it should be available in O(lgN). I know that
all of this can be done with a single int added to the node. Will
be interested in your use of two.

I wonder if Dietmar is thinking property map at this point. :)


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