[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-core-devel
Subject: Re: vectors vs. lists
From: David Faure <faure () kde ! org>
Date: 2004-02-19 11:57:40
Message-ID: 200402191257.40626.faure () kde ! org
[Download RAW message or body]
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).
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic