Re: [boost] challenge: stable_vector

From: David B. Held (dheld_at_[hidden])
Date: 2001-07-12 16:25:32

>Acording to various measurements (most notably by Matt Austern, IIRC), a
>sorted vector is often much faster than a map.
>
>Ulli

I guess that depends on which operation dominates, no?  A sorted vector
cannot possibly insert or delete in better than O(n) time (unless you did a
lazy sort, of course), compared to O(log n) for a map.  But I suppose that a
data dictionary will probably be mostly static once built, and thus find()
will probably be the most common operation.  The advantage of vector is that
a binary search is basically exactly log n, whereas map need only be O(log
n), which may end up being 2 log n in the worst case for a typical
implementation (using a red-black tree of height 2 log n).  You could be
clever about how you build your dictionary if it is fairly static, but that
requires knowledge of the representation, which I suppose should not be
relied upon. ;)  But at least you get stable iterators.

On the other hand, I'm not sure what it means for a vector to have stable
iterators.  If you have a vector v like so:

[a, b, c, d]

and you have an iterator i to v[2], and then you delete v[1], do you expect
i to point to the new v[2] or to 'c'?  I can think of applications where you
might expect either one.  The problem with stable iterators to vector is the
explicit knowledge of the position of elements.

Dave