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?

Answer 1

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.

Answer 2

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).