vectors vs. lists

[David Faure]

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,:
> > 
> > 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.

I almost had the same remark... and then I realized that although you are correct
for QPtrList/QPtrQueue/QPtrStack, Marc is correct about QValueList.

Q_INLINE_TEMPLATES Q_TYPENAME QValueListPrivate<T>::NodePtr QValueListPrivate<T>::at( size_type i ) const
{
    Q_ASSERT( i <= nodes );
    NodePtr p = node->next;
    for( size_type x = 0; x < i; ++x )
        p = p->next;
    return p;
}

=> don't use for(int i = 0; ...) and at(i) with a QValueList, use iterators!

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