Re: Indexed Map container

From: dheld_at_[hidden]
Date: 2001-06-03 13:39:19

--- In boost_at_y..., "John E. Potter" <jpotter_at_f...> wrote:
> 
> Given all of that, the inverse function position of key will find a
> use also.  Maybe m.pos(iter).

Yes, I thought of this originally, but since I didn't have an 
immediate need for it, I didn't bother to implement it.  However, it 
should be there for completeness.

> Yes, distance(m.begin(), iter) would get it in O(N), but it should
> be available in O(lgN).

No, because ++iter *itself* can be O(log n).  If iter points to the 
predecessor of the root node, for instance, it is the rightmost child 
of root's left subtree.  To get the successor, one must climb the 
parent nodes all the way to the top, which is clearly O(log n).  Of 
course, if iter has a right subtree of size 1, then ++iter will be O
(1).  But that doesn't change the fact that ++iter is O(log n) in the 
general case, and thus distance(m.begin(), iter) is O(n log n), which 
is abominable for frequent indexing operations.

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

Yes, I originally started out with two ints that represented the size 
of the left and right subtree, then realized that one int 
representing the index of the node within it's subtree's vector 
representation would suffice.  However, one of the rotate operations 
requires knowing the size of a right subtree.  The size of the left 
subtree is just equal to the index, but unless you store the size of 
the whole subtree (or the right explicitly), you have to descend the 
right subtree (in particular, find the rightmost child of the 
subtree) to get its size.  This is clearly O(log n).  But rotate can 
be called O(log n) times in the course of an insert or delete, so 
that would make insert and delete O(log^2 n), which is not terribly 
bad; but I opted for retaining the complexity characteristics of 
std::map and added a size field instead.  If the general concensus is 
that the time sacrifice is worth the storage saved, I will revert the 
implementation to just one int.

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

I'm not familiar with this.  Would you mind giving a bit of a summary?

Dave