4 ms·
what? ha, that is the text book approach to reallocating an array for additional values to get log complexity
by gmadsen 8y ago
what? ha, that is the text book approach to reallocating an array for additional values to get log complexity
- vardump 8y agoI'm not so sure I'd want a 2GB vector to grow to 4GB, etc.
- jhasse 8y agoWhy not?
- dbaupp 8y agoO(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.
- BeeOnRope 8y agoOld 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.
- ChrisSD 8y agoIn such extreme cases you can (and should) use your own allocation strategy.
- vardump 8y agoYeah, 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.
- ChrisSD 8y agoWhy wouldn't writing an allocator class be enough for mmap?
- BeeOnRope 8y agoProbably 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.
- Timmah 8y agoHow would you ensure nothing was used in the region after the original allocation?
- mortehu 8y agoI think you mean amortized constant complexity, or O(1).