4 ms·
"On the contrary, perhaps the most interesting task we ever do with a list is iterate over it and vectors kick ass there." You need to populate a sequence befo
by betterunix 13y ago
"On the contrary, perhaps the most interesting task we ever do with a list is iterate over it and vectors kick ass there."
You need to populate a sequence before you can iterate over it, and that is where the poor asymptotic performance becomes a problem. An example that came up on HN a few weeks ago is this: insert a bunch of elements into a sequence, while maintaining some order (i.e. the sequence must be in order after each insertion). Sure, vectors outperform linked lists on this task -- but both are crushed by a priority queue (even if it is just a pairing heap built from linked lists), and even a balanced binary tree will do better at reasonable scales.
- mpyne 13y agoSure, but I think the issue is that 'reasonable scales' are growing larger and larger due to the improvement in constant factors associated with use of vectors. Especially if you already know the size you need to allocate it can be quicker to dump the data into the vector and then sort it than to branch hither-and-yon while maintaining an ordering invariant during push_back(). Of course there's probably some kind of cache-aware binary heap that gives the best of both worlds (algorithmic complexity and constant factor improvements), but vector<> already works now without needing fancy things like Judy arrays. The real answer (as ever) is probably to profile to be sure.