[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-freeqt
Subject:    Re: [freeqt] QVector
From:       Nick Huxley <bootsy () liverpool ! ac ! uk>
Date:       2000-08-18 9:16:43
[Download RAW message or body]


>That's what Qt does (it actually calls the system qsort(), which is a
>hack in itself; the comparison function requires a global variable, which
>is not thread safe), but that's not _necessarily_ the best idea.  It
>might be better, for example, to use a stable sort, but I don't know how
>important stability is.

Really these classes should all have two sort options qsort for overall
speed and heapsort for stability. Heapsort is an in place sort that isn't
as fast as qsort on average but never goes above a certain complexity at
the worst case. Qsort has a worse case of N^2!! This is very important when
the longest possible time must never occur. QT has to my knowledge only the
qsort which is a poor decision IMHO. The STL has both.

Looking through the sort code sent to me there  is also the problem of
stupid global macros which are needed in C but not C++.

i.e. #define swap(a,b) /*etc  */

and #define max(a,b) /*etc*/

for this sort of thing I think we should be using template definitions.
Maybe we have them already in the code base, I'm not sure. If people think
it is good idea to use templates for swap, max, min and maybe even sort
then I'm quite willing to write them if they aren't available yet. The
first two are trivial anyway. That also gives some compatability with the
STL. 

Any thoughts

Nick

[prev in list] [next in list] [prev in thread] [next in thread]