Re: [boost] Re: Indexed Map container

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. :)

John