Re: [boost] challenge: stable_vector

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.

Ulli
 ________________________________________________________________
|                                                                |
| Ullrich Koethe  Universität Hamburg / University of Hamburg    |
|                 FB Informatik / Dept. of Computer Science      |
|                 AB Kognitive Systeme / Cognitive Systems Group |
|                                                                |
| Phone: [phone]                Vogt-Koelln-Str. 30 |
| Fax:   [phone]                D - 22527 Hamburg   |
| Email: u.koethe_at_[hidden]               Germany             |
|        koethe_at_[hidden]                        |
| WWW:   http://kogs-www.informatik.uni-hamburg.de/~koethe/      |
|________________________________________________________________|