On Tue, Apr 28, 2020 at 12:25:32AM +0200, Jean-Michaël Celerier wrote: > > As starters, there are 85 occurences of QList::takeFirst() in Qt > > Creator source code. Replacing these with QVector replaces a O(1) > > operation with an O(n) operation. > > Apologies if I'm wrong, but isn't QList::erase (and anything > derivative) always O(N) ?
Not in 5.x https://codereview.qt-project.org/gitweb?p=qt/qtbase.git;a=blob;f=src/corelib/tools/qlist.cpp;h=5d5da20752aa3d21e06330094095702019f53c93;hb=refs/heads/5.15.0#l272 For offset == 0 the memmove is of length 0, only d->begin is bumped. > With a lower cost than std::vector for things with sizeof > 8, sure, > but still. Even when inserting in the middle, where both QList and QVector insertion is formally O(n), QList on large data only memmoves size/2 pointers, QVector's size/2 operations can be arbitrarily expensive, depending on the exact nature of the stored items. > And, given that 98% of QList usage seems to fall into the "good" case > of sizeof<= 8, wouldn't that make zero change when switching to QVector > ? There would be no difference in those cases if the premise were right. But it isn't. If you have ideally movable items in the QVector case (i.e. item move costs equal to one pointer move, and the move loop optimized the same as the explicit memmove), and choose a random position in the container to insert from a uniform distribution, the expected cost of item shuffling due to the insertion is for QList only half the cost as for QVector. This ratio decreases further, i.e. becomes even more in favour of QList, when the items are not ideally movable. Andre' _______________________________________________ Development mailing list [email protected] https://lists.qt-project.org/listinfo/development
