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?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk