3 ms·
simple vector implementations will do a full realloc and recopy when you run out of space. so O(1) amortized but O(N) every so often. another implementation st
by dilap 4y ago
simple vector implementations will do a full realloc and recopy when you run out of space. so O(1) amortized but O(N) every so often.
another implementation strategy, at the cost of using some extra memory, is to allocate the new space, but only copy over a bit at a time, each time a new element is added -- so every add is still O(1). no long pauses.
(well, assuming the memory alloc is still fast. which i think it should be in practice? tho i'm not super familiar w/ that stuff.)
just curious, do you think that solution would have worked for your situation too?
- kabdib 4y agoThat's exactly the strategy that was tipping over. Once you start resizing vectors of tens of megabytes, it's kind of over. You can start playing games by accelerating capacity allocation when a vector rapidly starts growing extremely large. This doesn't solve the problem that vectors sometimes guarantee too much for what you need.
- dilap 4y agoAh thanks, I didn't read closely enough the first time.