Re:Double-ended vector – is it useful?
by twotwotwo on Monday May 23, 2016 @01:59AM
(#11752180)
Qt's QList is like what this describes: it tracks where the first and last used items are in the allocated region, so both prepends and appends are amortized constant time.
Peeking at the code, Qt's even using the same general approach described in the post ("When there is still a lot of room left in the buffer, we should move elements toward the middle, and not reallocate straight away."): it moves items into the middle if the backing array is under 1/3 full.
When QList first came out, I think the team said they got there by trying different implementations and measuring what worked best on average in the real app code they had. That at least suggests that to the author's question "is it useful?", somebody thought yes.
Peeking at the code, Qt's even using the same general approach described in the post ("When there is still a lot of room left in the buffer, we should move elements toward the middle, and not reallocate straight away."): it moves items into the middle if the backing array is under 1/3 full.
When QList first came out, I think the team said they got there by trying different implementations and measuring what worked best on average in the real app code they had. That at least suggests that to the author's question "is it useful?", somebody thought yes.
(The code I peeked at is at https://github.com/radekp/qt/blob/master/src/corelib/tools/q..., header at https://github.com/radekp/qt/blob/master/src/corelib/tools/q..., and docs (possibly for a newer version) at http://doc.qt.io/qt-5/qlist.html#prepend.)