vectors vs. lists

[Marc Mutz]

Hi!

Here's a nice Janitor's job:

I've recently stumbled across patches to KMail that use QValueList<int> 
and don't do much more than appending, iterating or even indexing into 
it. I'm sure there's more of this all over KDE since nearly everyone I 
talked to in the last weeks about this was surprised. TT did a _very_ 
bad thing: Their API is full of *List, but sports very nearly no 
*Vector's.

Now, all of you with an algorithm and datastructures training just sit 
back and think about this a few seconds.

QValueList<> is a doubly linked list. Basically, you have a memory 
overhead of 2*sizeof(void*) for the linking and, a malloc() for each 
insertion, which is not only slow, but also has a noticable memory 
overhead, esp. for such small sizes. Calculating the exact size of a 
QValueList<int> with - say - 1000 entries is left as an excercise to 
the reader.

Consider QValueVector. It lays out it's object in a continuous chunk of 
memory. 1 malloc(), no overhead. So what's the drawback? The drawback 
is that inserting elements in the middle or the front involves invoking 
the copy ctor for each element following the insertion point. Plus the 
reallocation if the reserved capacity is exceeded. But in most cases, 
this is not relevant, such as with the append-and-iterate scenario, or 
with trival copy ctors (such as int has), or even if you only have a 
small number of items, say a few dozen, anyway. If you know the 
approximate size of the result beforehand, you can avoid frequent 
reallocations by using reserve(). Don't use QValueVector<T>( size_type, 
const T& ), though, as that will call the copy ctor for each element. 
Use reserve() and push_back()[1].

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:

for ( List::const_iterator it = list.begin() ; it != list.end() ; ++it )
  doSomethingWith( *it );
for ( int i = 0 ; i < vector.size() ; ++i )
  doSomethingWith( vector[i] );

are O(n). 

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<> (the most visible 
difference is that QPtrList<T> needs the type of the template argument 
to be complete, while QValueFoo<T*> does not (fwd decl suffices), and 
QPtrList won't be anymore in Qt4).

Basically, only use the list types if you know that vectors are 
unsuitable (due to frequent insertions in the middle, altough those can 
often be removed by copying into another container (think sorting)).

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

Marc

[1] I personally use STL-copmatible methods and iteration where 
available, since those are standardised and won't go away with the next 
Qt version.

-- 
There's a lot of "throwing the baby out with the bathwater" going on,
but the bathwater is so foul that many companies don't mind the
occasional loss of baby. -- Bruce Schneier on spam filters,
                            Crypto-Gram 07/2003
-------------- 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/9d66d815/attachment.sig>