From kde-core-devel  Thu Feb 19 11:57:40 2004
From: David Faure <faure () kde ! org>
Date: Thu, 19 Feb 2004 11:57:40 +0000
To: kde-core-devel
Subject: Re: vectors vs. lists
Message-Id: <200402191257.40626.faure () kde ! org>
X-MARC-Message: https://marc.info/?l=kde-core-devel&m=107719186722845

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@kde.org, sponsored by Trolltech to work on KDE,
Konqueror (http://www.konqueror.org), and KOffice (http://www.koffice.org).