Giuseppe D'Angelo wrote: > Also nobody says that middle insertions of removals should be "extra > cheap".
This is a very common operation for a random-access, ordered but not auto- sorted, array/vector-type list. The "array of pointers" data structure is an effective compromise to make this reasonably cheap (though still O(n)) while keeping the O(1) random access. >> * Accessing the i-th element is performed in guaranteed O(1) time. > > For "bad" types for QList, that O(1) is hiding two indirections. Only > one with QVector. That's a huge cost you're not talking about. It's a factor 2, vs. a factor sizeof(T)/sizeof(T*) in the opposite direction for the middle insertions/removals. For any nontrivial class, sizeof(T)/sizeof(T*) can be a lot larger than 2. >> * Inserting an element performs at most 1 heap allocation. (This is the >> only >> performance metric that can change, but the changing from the usual 1 >> to 0 is a very welcome optimization for the cases it applies to.) > > Inserting an element of a wrong type performs *at least* 1 heap > allocation. Consider: > >> ListContainer<WrongType> list; list.reserve(1000); /* insert 1000 >> elements */ > > This performs (at least?) 1001 heap allocations with QList and 1 with > QVector. This performs only 1 allocation with QList. The documentation says: "Note that the reservation applies only to the internal pointer array." Looking at the code, the reserved pointers are simply not initialized at all (not even zeroed). The actual 1000 allocations of the WrongType elements are only done if and when you actually insert them. Therefore, you get the behavior I explained: insert does 1 allocation for a "wrong" type (or 2 in the rare event it needs to grow the pointer array), 0 for a "good" type (or 1 in the rare event it needs to grow the array). The latter matching the behavior of QVector, of course. Kevin Kofler _______________________________________________ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development