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.
> 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, and then you delete v, do you expect
> i to point to the new v 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: http://kogs-www.informatik.uni-hamburg.de/~koethe/ |
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk