The right way to reserve or compress a vector for a known future capacity requirement

Question

I wrote a lot of software modules around the general theme of a long-lived vector, which should update the content several times (at an undefined frequency).

Idiomatic implementation:

void LongLived::reconfigure(const InputT& whatever_input) { m_vector.clear(); m_vector.reserve(whatever_input.size()); populate(m_vector, whatever_input); } 

Note that an idiomatic implementation will never reduce the capacity of the internal buffer. What if it’s not normal? Just use shrink_to_fit() , I thought:

 void LongLived::reconfigure(const InputT& whatever_input) { m_vector.clear(); m_vector.reserve(whatever_input.size()); m_vector.shrink_to_fit(whatever_input.size()); // ← Here populate(m_vector, whatever_input); } 

Oh, how good it would be ... But, to my surprise, it does not compile because shrink_to_fit() does not accept a number!

It is assumed that the shrink_to_fit() path shrink_to_fit() to be that you are filling the vector first. Then you call shrink_to_fit() , which will get the capacity requirement from the number of elements in the vector after the fact, but this is clearly suboptimal if I could say it in advance, because now all this content should be moving.

Purpose: I would like to use the vector_reserve_or_shrink() function in this context:

 void LongLived::reconfigure(const InputT& whatever_input) { m_vector.clear(); vector_reserve_or_shrink(m_vector, whatever_input.size()); // ← Implement this! populate(m_vector, whatever_input); } 

I'm actually not obsessed with shaving every unused byte from a vector. Rather, I would be happy to leave it to some implementation defined as shrink_to_fit() , which might know something about the quirks of the dispenser and might do nothing. Thus, you do not run the risk of making an abstraction inversion that negates any lower levels of optimization. For example, let's say that the granularity of the allocator is 16: then a vectorial implementation can give you 15 bytes for free when you ask one, as far as I know, that it would be simply counterproductive to try to return.

Answer 1

Use something like this:

 template <typename VECTOR> void setCapacity(VECTOR &vector, std::size_t capacity) { if (capacity < vector.size()) capacity = vector.size(); if (vector.capacity() > capacity) { VECTOR v; v.reserve(capacity); std::size_t size = vector.size(); for (std::size_t i = 0; i < size; i++) { v.emplace_back(std::move(vector[i])); } vector.swap(v); } else { vector.reserve(capacity); } } 

It sets the vector capacity (if possible), while preserving the elements. And this is just one highlight.

Answer 2

 template<class V> void hard_reserve( V& v, std::size_t capacity ){ if (v.capacity() > capacity) v.shrink_to_fit(); v.reserve(capacity); } 

it is not ideal in some corner cases, but it will be corner cases of an already corner case, and std does not provide containers suitable for many corner cases.

Answer 3

 void LongLived::reconfigure(const InputT& whatever_input) { m_vector.clear(); m_vector.shrink_to_fit(); m_vector.reserve(whatever_input.size()); populate(m_vector, whatever_input); } 

shrink_to_fit on an empty vector works pretty well on all implementations as far as I know. This does not lead to a new memory allocation. The only allocation will be made reserve .

No T elements will be copied, and this avoids a memory peak for storing two memory blocks due to redistribution.

Instead of using shrink_to_fit to free memory, you can also clear the vector by replacing it in an extra function (or area). It also avoids a memory peak for storing two buffers.

 void free_vector(std::vector<T> & vec, std::size_t new_size) { std::vector<T> new_vec; vec.swap(new_vec); } 

Answer 4

shrink_to_fit can - but does not have to - reduce the bandwidth of the vector to it size . Therefore, if you are looking for a method that reduces the throughput of vectors in an “optimal” way, shrink_to_fit might be the right choice.

Of course, shrink_to_fit does not accept a parameter, since the vector size is taken as a reference. So, you just need to clear , then fill reserve to fill in the desired size, and finally shrink_to_fit :

 void LongLived::reconfigure(const InputT& whatever_input) { m_vector.clear(); m_vector.reserve(whatever_input.size()); populate(m_vector, whatever_input); m_vector.shrink_to_fit(); }