CODEWITHSUNDEEP
c++stdvector
user2394284
user2394284

Reputation: 6018

Right way to "reserve or shrink" a vector to a known future capacity need

I've written countless software modules around the common theme of a long lived vector that some times (at unspecified frequency) must have its content updated.

Idiomatic implementation:

void LongLived::reconfigure(const InputT& whatever_input)
{
    m_vector.clear();

    m_vector.reserve(whatever_input.size());

    populate(m_vector, whatever_input);
}

Notice that the idiomatic implementation will never reduce the capacity of its internal buffer. What if this is not ok? 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 nice that would be… But to my surprise, it doesn't compile, because shrink_to_fit() doesn't take a number!

The way shrink_to_fit() is supposed to be used, apparently, is that you fill the vector first. Then, you call shrink_to_fit(), which is going to derive the capacity need from the number of elements in the vector after the fact, but that is clearly suboptimal if I could have told it that beforehand, because now, all that content has to be moved.

Objective: I would like a function vector_reserve_or_shrink() to be used 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 not actually obsessed with shaving every unused byte off the vector. Rather, I would be glad to leave it up to something implementation defined like shrink_to_fit(), which might know something about the quirks of the allocator, and may choose to do nothing. This way, one doesn't risk making an abstraction inversion that negates any lower level optimizations. For example, say the allocator's granularity is 16: Then, the vector implementation might like to give you 15 bytes for free when you ask for one, for all I know, which would just be counterproductive to try to give back.

Upvotes: 6

Views: 1739

Answers (4)

Tunichtgut
Tunichtgut

Reputation: 311

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 quite good on all implementations as far as i know. It doesn't lead to a new memory allocation. The only allocation will be done by reserve.

No elements Twill be copied and it avoids the memory peak of keeping two blocks of memory due to reallocation.

Instead of using shrink_to_fit to free the memory it is also possible to clear the vector by swap in an extra function (or scope). This also avoids the memory peak of holding two buffers.

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

Upvotes: 1

geza
geza

Reputation: 29952

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 vector capacity to capacity (if possible), while retaining elements. And it only does one allocation.

Upvotes: 4

Stephan Lechner
Stephan Lechner

Reputation: 35154

shrink_to_fit may - but is not obliged to - reduce the capacity of the vector to it's size. So if you are looking for method that reduces a vectors capacity in an "optimal" manner, shrink_to_fit might be the right choice.

Of course, shrink_to_fit does not take a parameter, since the vector's size is taken as reference. So the only thing you need to do is to clear, then reserve, populate in order to fill up the 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();
}

Upvotes: 1

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275385

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

it isn't perfect in some corner cases, but those will be corner cases of an already corner case, and std does not provide containers suitable for the many angled one.

Upvotes: 2

Related Questions