Can the total element size of a dynamic array, be decreased at run-time?

[Peter87]

dhayden wrote:

The number of reallocations upon deletion would depend on when you decide to shrink it and by how much, just as it does on when you expand it.

Yeah, but if you use the vector like a stack, where you have it grow and shrink all the time, it would be wasteful with all those (re)allocations. As it is now, when the capacity does not shrink, you would have a few reallocations in the beginning but after a while you would hardly have any at all.

Here is an example to demonstrate my concern. On the y-axis you see the size (▓) and capacity (░), and on the x-axis you have time. The arrows shows when a reallocation happens. The first graph doubles the capacity when necessary without reducing the capacity. The second graph is the same as the first graph except that it reduces the capacity when the size drops below half the capacity.

                 ↑
8                ░░░░░░░░░░░░░░░
7                ░░░░░░░░░░░░░░░
6                ░░▓░░░░░░░░░░░░
5    ↑           ░▓▓▓░░░░░▓░░░░░
4    ░░▓░▓░░░░░░░▓▓▓▓▓░░░▓▓▓░░░░
3  ↑ ░▓▓▓▓▓░░░░░▓▓▓▓▓▓▓░▓▓▓▓▓░░░
2 ↑▓░▓▓▓▓▓▓▓░░░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░░
1 ▓▓▓▓▓▓▓▓▓▓▓░▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░

                 ↑
8                ░░░░░          
7                ░░░░░   ↑      
6                ░░▓░░   ░░░░  
5    ↑          ↑░▓▓▓░   ░▓░░  
4    ░░▓░▓░░    ░▓▓▓▓▓↓  ▓▓▓░   
3  ↑ ░▓▓▓▓▓░   ↑▓▓▓▓▓▓▓░▓▓▓▓▓↓  
2 ↑▓░▓▓▓▓▓▓▓↓ ↑▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░
1 ▓▓▓▓▓▓▓▓▓▓▓↓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓↓

As you can see the first graph only needed 4 reallocations and if the size never grows above 8 it will never have to reallocate again. The second graph reallocated 13 times and would probably have to continue doing frequent reallocations for as long as it's used.

dhayden wrote:

One thing I find odd though is that the section on shrink_to_fit() makes no statement about iterators and references. I'd think that shrink_to_fit() would invalidate both if it decides to reallocate.

I also think it's odd. If a reallocation happens it will invalidate everything, but it doesn't say it's allowed to happen. There are obviously implementations that will reallocate when shrink_to_fit() are called (are there any that don't) so the safest assumption right now is probably to assume everything will be invalidated.

C++14 §23.3.6.3/6

Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence.

[JLBorges]

In general, it is a bad idea to try to shrink a vector periodically (unless the program is short on memory).

If shrinking the random access container is a frequent requirement, std::deque would typically be a better choice than std::vector