Boost logo

Boost :

From: Ullrich Koethe (u.koethe_at_[hidden])
Date: 2001-07-12 16:43:26

"David B. Held" wrote:
> >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?

Of course, but in many applications lookup dominates over insert/erase.
In addition, for typical dictionary sizes, the constant factors in the
O() cause a map to be slower than a sorted vector even in case of many
inserts/erases (despite the fact that the former has better asymptotic
complexity). So it's a good thing to have a vactor-based dictionary at
your disposal. See Matt Austerns article in C++ Report (sorry, I don't
remember the exact reference).

> 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'?

For a dictionary, it's pretty clear that you want the iterator to point
to 'c' all the time. That's one reason I proposed to wrap the
internal_iterator into dictionary_iterator.

| |
| Ullrich Koethe Universität Hamburg / University of Hamburg |
| FB Informatik / Dept. of Computer Science |
| AB Kognitive Systeme / Cognitive Systems Group |
| |
| Phone: +49 (0)40 42883-2573 Vogt-Koelln-Str. 30 |
| Fax: +49 (0)40 42883-2572 D - 22527 Hamburg |
| Email: u.koethe_at_[hidden] Germany |
| koethe_at_[hidden] |
| WWW: |

Boost list run by bdawes at, gregod at, cpdaniel at, john at