Double-ended vector – is it useful?

I feel like it would be possible to leave the heavy lifting to the underlying page tables. Presuming you are running a 64-bit system, you have a enormous practically unused address space. Until you access the allocated memory it doesn't actually occupy any physical RAM.

The virtual address gets associated with the physical RAM in 4KB pages. So if you just allocate an a region twice as large as you will ever need, and start writing in the middle, you will never be wasting more than 8KB of real RAM. No copying, no reallocation, just keep track somewhere of the head and tail.

Other than the momentary panic of those who notice how much memory is being "used", what are the downsides of this approach? The 8KB is unlikely to ever be a problem. I haven't seen many people taking this approach to memory management, and other than stigma, I'm not sure why. Is it that everyone still wants to support 32-bit systems?

This is an interesting article, and a "devector" is something I've never heard of or considered before, so I'll leave critique of the data structure itself to others. But I have some constructive criticism of how the data is presented. Since the graphs / performance comparisons are such a large part of the post, I think it's relevant.

First of all, and most simply, when presenting multiple charts please use the same colors for the same lines on each chart. Here, the charts without the "vector" line use a different color scheme, making it harder to compare them at a glance.

Second, absolute timings don't matter here, only relative timings do, so showing absolute time on the Y-axis doesn't really make sense. Instead, I would use percentage from a baseline of one of the data structures. I think choosing the "deque" line for that purpose would make the most sense, given that it's the standard data structure from double-ended access.

Here's a rough version of what that looks like for the first chart -- https://goo.gl/bg5mrN -- Hopefully it makes the relative speeds of the different solutions more clear (I only put in the data for "deque" and "devector").

So if you have a million vectors then you have wasted 8GB. It only makes sense if you have a few large vectors.

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.

(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.)

I have already made this concept a year ago: https://github.com/orlp/devector.

I never finished the implementation though. Exception safe programming of standard containers is incredibly annoying (feel free to inspect the source code to see what I mean).