A different multiplier for the memory management of std::vector

Question

I've been playing with dynamic array structures, and I've noticed that the g++ standard library's vector implementation increases the capacity of an std::vector by doubling it on each push_back() invoked after the current capacity has been filled up. I think it was somewhere on stackoverflow that somebody mentioned that a Microsoft compiler uses 1.5 as the multiplier. I'm curious, are these values hardcoded or can I set a custom multiplier somewhere?

See related question http://stackoverflow.com/questions/7774938/in-c-will-the-vector-function-push-back-increase-the-size-of-an-empty-array — Mihai8, Apr 15 '13 at 22:53
Or other related question: http://stackoverflow.com/questions/5232198/about-vectors-growth — scones, Apr 15 '13 at 22:55
From looking at the libstdc++ source, the code for deciding how much increase the capacity seems to be the function `_M_check_len` on line 1239 [here](http://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a01069_source.html#l01239). It returns the new capacity as the current size plus the maximum of its current size or a passed in minimum value (up to some maximum size value). — David Brown, Apr 15 '13 at 23:03
@DavidBrown: did I miss something or is `vector` and `deque` the same thing in libstdc++? The OP asks about `vector`. — Mats Petersson, Apr 15 '13 at 23:05
@MatsPetersson sorry, I got my links mixed up, should be right now. — David Brown, Apr 15 '13 at 23:06

Mats Petersson · Answer 1 · 2013-04-15T23:39:08.527

1

I'm fairly certain that it is an "implementation detail, not required to be disclosed" and I expect it doesn't have to be a constant either, it could be something like this:

std::vector::grow()
{
    if (size <= 100)
    {
       newsize = size * 2;
    }
    else if (size <= 10000)
    {
       newsize = size * 3 / 2;  /* 1.5x */
    }
    else
    {
       newsize = size * 5 / 4;  /* 1.2x */
    }
    .... allocate a "newsize" chunk of memory etc ... 
}

As far as I know, there is no interface to "set the multiplier". It is up to each implementation to choose a growth rate. When numbers get really large, 2x is a little more wasteful, and you risk "running out of virtual space" (e.g. go over the limit of 2GB with 512M elements in a vector of int, which may not work as a single allocation in a 32-bit system).

edited Apr 15 '13 at 23:39

answered Apr 15 '13 at 22:57

Mats Petersson

126,704
14
140
227

And that is indeed something that each implementation will do "whichever way it fancies". – Mats Petersson Apr 15 '13 at 23:01
Thanks for the answer. It seems g++ seems to keep it at 2, probably for reasons mentioned by Kerrek SB. (Anyway, you'd need a 512M array of ints to cross the 2GiB barrier. (Can't fix it for you as Stackoverflow doesn't allow single-letter edits -- a stupid policy on an engineering forum, if you ask me. )). – Petr Skocik Apr 15 '13 at 23:36
The growth of a vector has to be (super) exponential to meet the complexity requirements. That means a constant factor _or higher_. Squaring the capacity on each reallocation is wasteful but legal. So practically the complexity requirement boils down to constant growth. – MSalters Apr 16 '13 at 06:49

score 1 · Answer 2 · answered Apr 15 '13 at 23:04

The standard does not require that you be provided a way to customize the multiplier, though of course you can write your own collection or override one and do whatever you want with it. Here is Microsoft's implementation, from VS 2012:

void _Reserve(size_type _Count)
    {   // ensure room for _Count new elements, grow exponentially
    size_type _Size = size();
    if (max_size() - _Count < _Size)
        _Xlen();
    else if ((_Size += _Count) <= capacity())
        ;
    else
        reserve(_Grow_to(_Size));
    }

You can see that they always grow by size()--thus doubling the capacity, and that it's not a value you (as a programmer) are intended to override.

You need to look at `_Grow_to` to determine what's going on. At the point where it's called, `_Size` is the minimum that's needed, not the new size. — Pete Becker, Apr 16 '13 at 00:13
@PeteBecker You're right, I missed that. I'll dig in and update my answer. — Nate Hekman, Apr 16 '13 at 01:34

score 1 · Answer 3 · answered Apr 15 '13 at 23:51

can I set a custom multiplier somewhere?

Other answers have already dealt with this (and the rest of your question) in a direct sense, so I won't bother repeating any of that. However, if you want to control the growth of a vector yourself, use std::vector::reserve. If you call this any time you are about to insert an element to an already full vector, then you can achieve the same result (albeit with a little extra overhead as you will need a redundant conditional to check the size).

A different multiplier for the memory management of std::vector

3 Answers3

Linked