vectors vs. lists

Werner Trobin trobin at kde.org
Thu Feb 19 11:49:39 GMT 2004


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,:
> 
> for ( int i = 0 ; i < list.count() ; ++i )
>    doSomethingWith( list[i] );
> 
> is O(n^2). Whereas these:

While I agree with all of your points this O(n^2) statement is not true. 
Please check at() and especially locate() in QGList.

Ciao,
Werner




More information about the kde-core-devel mailing list