When a std::vector is automatically resized, by how much does the capacity increase?

[ElusiveTau]

When I step-debug through the code and look at Container.capacity() after every call to emplace(), the capacity sometimes increase by 0 (after inserting 4'th item) and sometimes increase by 1 (after inserting 5'th item).

I thought the capacity doubles every time resizing needs to be done.

Edited:
I ran it again using the "Run Code" feature of cpp.sh and got a different output. It looks like the reallocation scheme could be machine dependent.

#include <iostream>
#include <vector>

class A {
public: 
    A(std::vector<char> vtemp) : v(vtemp)
    {
        std::cout << "ctor called\n";
    }

    A(const A& other)
    {
        std::cout << "Copy ctor called. other.v[0]: " << other.v[0] << " \n";
        this->v = other.v;
    }
private:
    std::vector<char> v; 
};

int main()
{
    std::vector<A> ContainerA;
    auto it = ContainerA.begin();
    it = ContainerA.emplace(it, std::vector<char>{ '1' }); // {1} 
    it = ContainerA.emplace(it, std::vector<char>{ '2' }); // {2, 1}
    it = ContainerA.emplace(it, std::vector<char>{ '3' }); // {3, 2, 1}
    it = ContainerA.emplace(it, std::vector<char>{ '4' });
    it = ContainerA.emplace(it, std::vector<char>{ '5' });
    it = ContainerA.emplace(it, std::vector<char>{ '6' });
    it = ContainerA.emplace(it, std::vector<char>{ '7' });
    it = ContainerA.emplace(it, std::vector<char>{ '8' });
}

Output

ctor called
ctor called
Copy ctor called. other.v[0]: 1
ctor called
Copy ctor called. other.v[0]: 2
Copy ctor called. other.v[0]: 1
ctor called
Copy ctor called. other.v[0]: 3
Copy ctor called. other.v[0]: 2
Copy ctor called. other.v[0]: 1
ctor called
Copy ctor called. other.v[0]: 4
Copy ctor called. other.v[0]: 3
Copy ctor called. other.v[0]: 2
Copy ctor called. other.v[0]: 1
ctor called
Copy ctor called. other.v[0]: 1
ctor called
Copy ctor called. other.v[0]: 6
Copy ctor called. other.v[0]: 5
Copy ctor called. other.v[0]: 4
Copy ctor called. other.v[0]: 3
Copy ctor called. other.v[0]: 2
Copy ctor called. other.v[0]: 1
ctor called
Copy ctor called. other.v[0]: 1

[Ganado]

Indeed, the implementation of how exactly the re-allocations occur is not standardized.
Also, while I can't confirm this, I imagine that calling emplace_back would be more efficient than emplace (probably less checks need to be done, even if you're back inserting already).

Also, the constructor initializer list can be used for copy ctors as well.

[keskiverto]

1. It is up to implementation.
2. Your test case looks too complex / irrelevant.

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> cont;
    std::cout << "size=" << cont.size()
            << " cap=" << cont.capacity() << '\n';
    for ( int x=0; x<30; ++x ) {
        cont.push_back( x );
        std::cout << "size=" << cont.size()
                << " cap=" << cont.capacity() << '\n';
    }
}

size=0 cap=0
size=1 cap=1
size=2 cap=2
size=3 cap=4
size=4 cap=4
size=5 cap=8
size=6 cap=8
size=7 cap=8
size=8 cap=8
size=9 cap=16
size=10 cap=16
size=11 cap=16
size=12 cap=16
size=13 cap=16
size=14 cap=16
size=15 cap=16
size=16 cap=16
size=17 cap=32
size=18 cap=32
size=19 cap=32
size=20 cap=32
size=21 cap=32
size=22 cap=32
size=23 cap=32
size=24 cap=32
size=25 cap=32
size=26 cap=32
size=27 cap=32
size=28 cap=32
size=29 cap=32
size=30 cap=32

[jonnin]

I thought the capacity doubles every time resizing needs to be done.

It would be nice if we could give them the resize function or at least give them a multiplier eg 1.10 (10% increase) etc.
double every time can be extremely wasteful once you get into large data, using at worst about twice what is needed at times which is going to start to have impact with data > 1gb or so

not much we can do about it, though.

[ne555]

> not much we can do about it, though.
.reserve()

[ElusiveTau]

keskivert wrote:

Your test case looks too complex / irrelevant.

That's because the code I'd used wasn't an example to demonstrate how the capacity changes when reallocation occurs. I was actually interested in the number of times A's copy-constructor gets called and was surprised when it was called immediately after the second call to emplace().

As I'd figured out, this happened because of automatic resizing. After some step-debugging, I thought how incredibly wasteful the number of copy-ctor invocation just to emplace 8 elements and came here to ask about it.

I agree, your example is more concise at illustrating the allocation scheme. My code snippet does show when copy-ctor is called to copy over old elements when reallocation occurs. On my system, the output is:

size=0 cap=0
size=1 cap=1
size=2 cap=2
size=3 cap=3
size=4 cap=4
size=5 cap=6
size=6 cap=6
size=7 cap=9
size=8 cap=9
size=9 cap=9
size=10 cap=13
size=11 cap=13
size=12 cap=13
size=13 cap=13
size=14 cap=19
size=15 cap=19
size=16 cap=19
size=17 cap=19
size=18 cap=19
size=19 cap=19
size=20 cap=28
size=21 cap=28
size=22 cap=28
size=23 cap=28
size=24 cap=28
size=25 cap=28
size=26 cap=28
size=27 cap=28
size=28 cap=28
size=29 cap=42
size=30 cap=42

Reserving memory is a good idea.

[mbozzi]

I thought the capacity doubles every time resizing needs to be done.

Here's a fairly interesting discussion about the 3 mainstream implementations & why doubling is theoretically poor:
http://cplusplus.com/forum/general/212529/

As I'd figured out, this happened because of automatic resizing. After some step-debugging, I thought how incredibly wasteful the number of copy-ctor invocation just to emplace 8 elements and came here to ask about it.

This class probably would benefit from a move constructor. Don't forget to make it noexcept.

[keskiverto]

That's because the code I'd used wasn't an example to demonstrate how the capacity changes when reallocation occurs. I was actually interested in the number of times A's copy-constructor gets called and was surprised when it was called immediately after the second call to emplace().

The copies (or moves) are coupled to the reallocations. Showing both shines more light:

#include <vector>
#include <iostream>

struct A {
    A(int a) : a{a}
    {
        std::cout << "ctor: " << a << '\n';
    }

    A(const A& rhs)
    {
        a = rhs.a;
        std::cout << "CP: " << a << ' ';
    }
private:
    int a; 
};

int main()
{
    std::vector<A> cont;
    std::cout << "size=" << cont.size()
            << " cap=" << cont.capacity() << '\n';
    for ( int x=0; x<10; ++x ) {
        cont.emplace_back( x );
        std::cout << "# size=" << cont.size()
                << " cap=" << cont.capacity() << '\n';
    }
}

size=0 cap=0
ctor: 0
# size=1 cap=1
ctor: 1
CP: 0 # size=2 cap=2
ctor: 2
CP: 0 CP: 1 # size=3 cap=4
ctor: 3
# size=4 cap=4
ctor: 4
CP: 0 CP: 1 CP: 2 CP: 3 # size=5 cap=8
ctor: 5
# size=6 cap=8
ctor: 6
# size=7 cap=8
ctor: 7
# size=8 cap=8
ctor: 8
CP: 0 CP: 1 CP: 2 CP: 3 CP: 4 CP: 5 CP: 6 CP: 7 # size=9 cap=16
ctor: 9
# size=10 cap=16

Your platform allocates 0, 1, 2, 3, 4, 6, 9, 13, ...
While it can be seen from the mere copies, seeing the capacity too helps.

[dhayden]

The restriction on the implementation is that push_back() must take constant amortized time. That means the vector can't grow by a constant amount. It must(?) grow by some multiple of the current size.

If you're worried about memory usage for a large vector, use reserve(). In my experience, you usually have an order-of-magnitude idea of the vector's size ahead of time. Reserve that much space, read the data into the vector, then call reserve again to trim it to an appropriate size.

[ne555]

.reserve() does not .shrink()
also, question your necessity for shrinking