By how much does vector::resize increase capacity?

Question

As far as I know the C++ standard does not specify exactly how vector capacity is increased when vector::resize requires an increase. But is there a "typical" implementation?

Specifically: I don't know how large my vector needs to be. Further, the elements come in random order. So for each element I have this:

if ( index >= vector.size() ) {
    vector.resize ( index + 1 );
}
vector.at ( index ) = element;

If the elements come in increasing index order, will the vector capacity be increased by one for each call to resize (in a typical implementation)? I'm hoping not...

possible duplicate of [Standard container re-allocation multipliers across popular toolchains](http://stackoverflow.com/questions/5404489/standard-container-re-allocation-multipliers-across-popular-toolchains) — Lightness Races in Orbit, Dec 22 '11 at 12:57
@TomalakGeret'kal: This is a different question. There are no guaranteed asymptotics for repeated `resize()`s. — Kerrek SB, Dec 22 '11 at 13:04
@KerrekSB: It's exactly the same question. "By how much will my container's capacity increase in implementation?" — Lightness Races in Orbit, Dec 22 '11 at 13:10
@TomalakGeret'kal: Not quite: That question concerns `push_back`, and `push_back` has mandatory complexity guarantees (i.e. amortized constant) -- this in turn forces the implementation to grow the storage geometrically. There's no comparable requirement that would affect the `resize()` situation. — Kerrek SB, Dec 22 '11 at 13:11
@KerrekSB: That's a factor of an answer, not of the question. — Lightness Races in Orbit, Dec 22 '11 at 13:15
@TomalakGeret'kal: I'm not sure - the question asks for "the actual multipliers", but what I'm saying is that there's no connection between `resize()` and any "multipliers", since there's no requirement that allocation induced by `resize()` follow any particular scheme. That's a different context, non? — Kerrek SB, Dec 22 '11 at 13:19
@KerrekSB: Well, whatever. :) I've decided it could go either way. — Lightness Races in Orbit, Dec 22 '11 at 13:26

score 4 · Accepted Answer · answered Dec 22 '11 at 13:07

4

The standard makes no guarantees about the asymptotics of repeated calls to resize(). It is entirely feasible that the container will simply grow the capacity to precisely the required target size. In fact, this would probably be the desirable behaviour (i.e. the least wasteful) in the majority of standard use cases for resize() (e.g. where it's just used once).

If you're worried, just implement your own geometric growth:

if (index + 1 > v.size()
{
    if (v.capacity() < index + 1)
    {
        v.reserve(2 * (index + 1));   // I had 2 * capacity() here first, but
                                      // I think this version is better
    }
    v.resize(index + 1);
}

answered Dec 22 '11 at 13:07

Kerrek SB

464,522
92
875
1,084

And, after inserting all items, OP could shrink the vector again to save memory, if that's an issue at all. – arne Dec 22 '11 at 13:22
@arne: [Not guaranteed](http://stackoverflow.com/questions/7829018/can-we-rely-on-the-reduce-capacity-trick). – Lightness Races in Orbit Dec 22 '11 at 13:27
@TomalakGeret'kal: What about `v.resize(v.size())`? I suspect it's not guaranteed to reduce the size, but it may. – arne Dec 22 '11 at 13:32
I think you're pretty much *guaranteed* that nobody shrinks the size, ever, with the possible exception of `shrink_to_fit()`, isn't that so? – Kerrek SB Dec 22 '11 at 13:43
@TomalakGeret'kal: OK, I see. That's definitely something to keep in mind with memory intensive applications... – arne Dec 22 '11 at 13:52
`v.resize(v.size())` is guaranteed not to relocate the existing elements. There's pretty much no way it can free any memory since the `Alloc` interface that vector uses to allocate memory doesn't have a `realloc` function. Prior to C++11, the idiom to shrink a vector was `vector(v).swap(v);`, but that's obsolete now because it copies all the members, it can't move them. – Steve Jessop Dec 22 '11 at 14:30

user1071136 · Answer 2 · 2011-12-22T13:14:58.690

As you mentioned, what resize does exactly depends on your implementation (and may change between different versions of the same implementation).

On compliant implementations, push_back causes the capacity to double each time it has to be increased, and this has to do with the amortized complexity of a series of push_back's. If it were to increase the capacity by 1 each time, the complexity for N additions would be O(N^2), whereas if push_back doubles the capacity each time, the complexity for the same series of additions would only be O(N) - a big deal.

As for you question - if you know in advance the maximal index, just pre-allocate. Otherwise, I think you're better off with std::map:

map<int, T> M;
for (...) {
  M[index] = element;
}

This will have complexity O(N log N) for N additions, but won't waste memory on indices which do not have corresponding element's.

Note that the capacity doesn't have to double, any constant strictly larger than 1 will do. — avakar, Dec 22 '11 at 13:24
unless your stroed objects are rather large, map will waste more memory (each map entry has overhead of a few pointers, then add overhead of the allocator). — seb, Mar 01 '18 at 13:44

By how much does vector::resize increase capacity?

2 Answers2