Hacker News Reader

HNHacker News

Top New Best Ask Show Jobs

Comment by gmadsen | Hacker News Reader

Parent Full thread

gmadsen·

what? ha, that is the text book approach to reallocating an array for additional values to get log complexity

View on HN

I'm not so sure I'd want a 2GB vector to grow to 4GB, etc.

Why not?

O(n^2) time for n push_back calls would be worse, so some sort of multiplication/exponential growth is required for the "fits all" default vector and its default growth strategy.

Old versions of MSVC used a 3/2 growth factor which led to less extreme jumps for large vectors, although also a lot more copies when filling a small vector. I'm not sure if that's still true.

In such extreme cases you can (and should) use your own allocation strategy.

Yeah, but I'm not entirely clear how I'd for example get std::vector to use a mmap'ed range, that I could zero-copy grow.

Also in that case I might want to grow it by a fixed amount, once it grows past a certain threshold.

It's a shame one needs to write another vector implementation just for that.

Why wouldn't writing an allocator class be enough for mmap?

Probably not, because the allocators don't expose the "extend" or "realloc" concept, so all you'll see from within your allocator is a request for an entire new region that vector wants in order to copy the new stuff into.

To implement a growing allocation , you'll have to create a custom vector, pretty much.

How would you ensure nothing was used in the region after the original allocation?

I think you mean amortized constant complexity, or O(1).

Reply on news.ycombinator.com