C++ vector reduce allocation size

Question

When does a C++ vector dynamically reduce its allocated size in practice.

I know that the allocated space doubles upon an insert into a full vector, but it's not clear to me when the allocation is reduced. The classical hysteresis is to halve the allocation size upon removal from a 1/4-full vector.

The standard does not mandate the capacity to double upon reallocation. It only implies that the growth must be geometric to achieve amortized constant time insertion. But any growth factor α > 1 will qualify for that. — 5gon12eder, Mar 20 '15 at 20:39

score 7 · Accepted Answer · answered Mar 20 '15 at 20:28

7

It will never shrink the allocated memory in the absence of explicit direction to do so.

In C++11 there is a shrink_to_fit call that will ask the implementation to do this, but it may not reduce the allocated memory. In prior versions you have to create a new copy and swap away the old one.

answered Mar 20 '15 at 20:28

Mark B

95,107
10
109
188

3

even `shrink_to_fit` is not guaranteed to reduce the capacity (it is a non-binding request). – vsoftco Mar 20 '15 at 20:29
1

The "prior versions" technique will commonly have the form `std::vector(vec).swap(vec);` – Drew Dormann Mar 20 '15 at 20:32
2

@DrewDormann: [And they _still_ don't hold any guarantee!](http://stackoverflow.com/q/7829018/560648) – Lightness Races in Orbit Mar 20 '15 at 20:41

score 2 · Answer 2 · answered Mar 20 '15 at 20:40

At least in my compiler, vectors do not appear to reduce their allocated space. When I run:

        std::vector<int> v;
        for(unsigned x=0;x<20;++x)
        {
            v.push_back(x);
            out << "elements: " << v.size() << ", capacity: " << v.capacity() << std::endl;
        }
        for(unsigned x=v.size();x>0;--x)
        {
            v.pop_back();
            out << "elements: " << v.size() << ", capacity: " << v.capacity() << std::endl;
        }

What is returned is:

    elements: 1, capacity: 1
    elements: 2, capacity: 2
    elements: 3, capacity: 4
    elements: 4, capacity: 4
    elements: 5, capacity: 8
    elements: 6, capacity: 8
    elements: 7, capacity: 8
    elements: 8, capacity: 8
    elements: 9, capacity: 16
    elements: 10, capacity: 16
    elements: 11, capacity: 16
    elements: 12, capacity: 16
    elements: 13, capacity: 16
    elements: 14, capacity: 16
    elements: 15, capacity: 16
    elements: 16, capacity: 16
    elements: 17, capacity: 32
    elements: 18, capacity: 32
    elements: 19, capacity: 32
    elements: 20, capacity: 32
    elements: 19, capacity: 32
    elements: 18, capacity: 32
    elements: 17, capacity: 32
    elements: 16, capacity: 32
    elements: 15, capacity: 32
    elements: 14, capacity: 32
    elements: 13, capacity: 32
    elements: 12, capacity: 32
    elements: 11, capacity: 32
    elements: 10, capacity: 32
    elements: 9, capacity: 32
    elements: 8, capacity: 32
    elements: 7, capacity: 32
    elements: 6, capacity: 32
    elements: 5, capacity: 32
    elements: 4, capacity: 32
    elements: 3, capacity: 32
    elements: 2, capacity: 32
    elements: 1, capacity: 32
    elements: 0, capacity: 32

they don't automatically reduce the capacity for optimization reasons (it takes time). — vsoftco, Mar 20 '15 at 20:41

score 0 · Answer 3 · answered Sep 29 '16 at 21:15

0

Befor C++11 you could empty vector by assigning it a new value:

vector<int> x;
x.resize(500);
x = vector<int>(); // assigning a copy of new empty vector will shrink memory usage

answered Sep 29 '16 at 21:15

Sergey

1,552
20
18

C++ vector reduce allocation size

3 Answers3