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