Dave wrote:
As an aside, given the performance requirements that must be met, there
aren't too many data structures besides balanced binary search trees that
could be used to implement the associative containers. Someone had told me
once that "skip lists" might be an alternative, but I am not familiar with
them, so I can't corroborate that statement myself...
Skip lists are supposed to have favorable performance compared to most
types of balanced search tree (in one experiment I read about, only
non-recursive AVL did better, if I recall correctly).
However, skip lists have a random component, which means there's a
chance (remote though it is) that the performance will degrade severely.
This would probably be enough to make a map or set implementation using
skip lists not strictly compliant (though nobody would ever know the
difference, I think).
-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.