
Boost : 
From: David B. Held (dheld_at_[hidden])
Date: 20010712 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 redblack 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk