Am Donnerstag, 18. Mai 2017, 10:58:23 CEST schrieb Ville Voutilainen: > [...] the QUIP is here for review: > https://codereview.qt-project.org/#/c/194984/
Thanks, (Sorry for not replying to the QUIP, but discussions on gerrit are not so easy to follow) 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 around std::deque. 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 QArrayView.) -- Olivier Woboq - Qt services and support - https://woboq.com - https://code.woboq.org _______________________________________________ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development