vectors vs. lists

[Marc Mutz]

On Thursday 19 February 2004 13:17, Waldo Bastian wrote:
> On Thu February 19 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).
>
> No, it is O(n) as well, see the implementation of
> QGList::locate( uint index )

See other mails.

> Which brings me to my next point:
> * Don't optimize without profiling / benchmarking, there is a real
> risk that you make matters worse, not better.
<snip>

I completely agree with you, except that is misses my point:

KDE and Qt programs currently default to QValueList, even if it is 
obviously stupid and wrong. And why? Because Qt uses QValueVector 
(almost?) nowhere.

Do I understand you correctly that you do /not/ agree that QValueVector 
or std::vector is the better _default_ container compared to QValueList 
and std::list?

I.e., don't you agree to this:

1.
> Bottomline: If you can choose the container class to use, prefer
> QValueVector over QValueList. And QValueVector<T*> over QPtrList<T>,
> if you don't need the autodelete feature of QPtrList<>
<snip arguments>

2.
> Basically, only use the list types if you know that vectors are
> unsuitable.

3.
> Tha janitorial job would involve finding wrong uses of QValueList
> and fixing them to use QValueVector.

(note: _wrong_)

Marc

-- 
History teaches that grave threats to liberty often come in times of
urgency, when constitutional rights seem too extravagant to endure.
                                  -- Justice Thurgood Marshall, 1989
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20040219/c89085ca/attachment.sig>