vectors vs. lists

[David Faure]

On Thursday 19 February 2004 13:02, Adriaan de Groot wrote:
> On Thursday 19 February 2004 12:49, Werner Trobin wrote:
> > On Thursday 19 February 2004 10:46, Marc Mutz wrote:
> > > It's really funny how STL-trained people default to std::vector<> in all
> > > their code, and you see std::list<> only very rarely, but you see
> > > QValueList used as a default in KDE/Qt, and in ways that involve
> > > indexing (O(n)! vs. O(1) in QVV). This loop, btw,:
> >
> > While I agree with all of your points this O(n^2) statement is not true.
> > Please check at() and especially locate() in QGList.
> 
> The Qt 3.2 docs say "uses a linear search and may be slow" - although I seem 
> to remember that at some point the list had a "current item" and that it used 
> linear search from the start, the end, or the current item depending on what 
> was closest.

That's exactly what Werner is talking about, QGList::locate().
Still, as Marc pointed out privately: 
if you implement an algorithm on it using antiparallel iteration with indexing 
instead of iterators (e.g. quicksort), then you get n^2 again.

And it isn't valid behavior on classes with correct constness, like QValueList,
it's only done on the old const-wise broken QPtr* classes.

-- 
David Faure, faure at kde.org, sponsored by Trolltech to work on KDE,
Konqueror (http://www.konqueror.org), and KOffice (http://www.koffice.org).