On Monday, 3 June 2019 06:26:36 PDT Giuseppe D'Angelo via Development wrote: > > QList::prepend has O(1) amortized and O(n) worst case time complexity. > > QVector::prepend has O(mn) (always!) time complexity. > > > > If you are dealing with a large class or struct, e.g. 800 bytes, then the > > QVector operations are 100 times slower than the QList ones! > > This is just *false*. You're (deliberately?) ignoring the cost of memory > allocations and deallocations, hiding them in big-O constants, something > I already warned you about. I won't then waste time debunking this.
Don't forget that QVector is a direct memory access, which is easily predicted by the CPU, so it can read ahead. If you're iterating (accessing!) the elements in QList, you're accessing memory that may not be read-ahead, because it's indirect. It will depend on how the elements were added and the strategy of the memory allocator. Also, please consider the memory considerations. If you have 100 elements of 800 bytes, a QVector will allocate 100*800 + 24 bytes (plus 16 of overhead inside malloc, total 80032 bytes used), whereas QList will allocate 100 * (800 + 8 + malloc overhead) + malloc overhead, for a total of 82416 bytes, or 3% more. Now if your object is 80 bytes instead of 800, the memory usage increase is 29%. -- Thiago Macieira - thiago.macieira (AT) intel.com Software Architect - Intel System Software Products _______________________________________________ Development mailing list Development@qt-project.org https://lists.qt-project.org/listinfo/development