olivier at woboq.com
Tue May 23 13:56:52 CEST 2017
Am Donnerstag, 18. Mai 2017, 10:58:23 CEST schrieb Ville Voutilainen:
> [...] the QUIP is here for review:
(Sorry for not replying to the QUIP, but discussions on gerrit are not so easy
Here are what what are the characteristics of QList:
a. Amortized O(1) append
b. Amortized O(1) prepend
c. Relatively fast insert even if elements are expensive to copy/move
d. Implicitly shared (copy-on-write)
e. Should expand to less binary code than QVector or other container because
most operation are done in qlist.cpp, common for very type. (I don't think
this was mentioned before)
f. The pointers to elements are kept valid on append/prepend/insert if the
list is not shared (detach) and the type is big enough.
g. It is inefficient because of the many allocations and bad cache behaviour.
In Qt 4.0, QList was made the default container for most purposes because of
the points a,b,c,d,e which where believed to be good characteristics for a
default sequence containers. I don't think f was an intended characteristic.
(Actually, I believe that people who rely on it just rely on an accidental
implementation detail / undefined behavior.)
And g was somehow ignored for some reason, or maybe it was tough that c was
more important for the default container.
The question is what to do in Qt 5.x and in Qt 6?
QList being used everywhere means people might rely on any of these point.
It was suggested to simply replace making QList being an alias to QVector in
Qt6. But we'd loose characteristics b,c,e,f.
We could get b. back if we make it possible for QVector to reserve memory in
front on prepend.
We could ignore c. as this might be less of a problem with move semantic
nowadays. We could also ignore e.
But not having f. might introduce nasty bugs that might not be seen easily in
big project while porting. So Marc suggested adding a QArrayList alias to
annotate code today that we know are relying on f. as a porting aide.
I think QArrayList does not solve the problem because I'd say most people will
not use it, they might not even know they rely on it. Their code works now,
and if we replace QList by QVector it will introduce subtle bugs anyway.
Another solution could be to keep QList as it, but deprecate it, and use
QVector everywhere in the API. We'd need to introduce implicit conversion
between QList and QVector to reduce the amount of source incompatibilities.
An alternative could be to develop a new data structure that keep the
good part of QList, while keeping good cache behavior. Maybe something modeled
In my opinion for Qt6, we should make prepend, takeFirst amortized O(1) in
QVector. And change the API to use QVector everywhere, with QList being a
deprecated alias to it. Ignore the fact that people can keep pointers to the
items. (Small behavior change that should not impact many usages.)
(For functions that do not take ownership of the vector, I'd make a new a
Woboq - Qt services and support - https://woboq.com - https://code.woboq.org
More information about the Development