"reserve or shrink" 已知未来容量需求的向量的正确方法

Question

我围绕长寿命矢量的共同主题编写了无数软件模块，有时（以未指定的频率）必须更新其内容。

惯用实现：

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

    m_vector.reserve(whatever_input.size());

    populate(m_vector, whatever_input);
}

请注意，惯用的实现将永远不会减少其内部缓冲区的容量。如果这不行怎么办？就用shrink_to_fit()，我想：

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);
}

哦，那该多好……但令我惊讶的是，它无法编译，因为 shrink_to_fit() 不接受数字！

应该使用shrink_to_fit()的方式，显然是先填充向量。然后，你调用 shrink_to_fit()，这将在事后从向量中的元素数量中推导出容量需求，但如果我可以事先告诉它，那显然是次优的，因为现在，所有的内容必须移动。

Objective: 我想在这种情况下使用函数 vector_reserve_or_shrink():

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);
}

我实际上并不痴迷于从向量中删除每个未使用的字节。相反，我很乐意将它留给像 shrink_to_fit() 这样定义的实现，它可能知道分配器的一些怪癖，并且可能选择什么也不做。这样，就不会冒着 abstraction inversion 否定任何较低级别优化的风险。例如，假设分配器的粒度是 16：然后，向量实现可能会在您要求一个时免费给您 15 个字节，据我所知，这只会适得其反。

Answer 1

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

它在某些极端情况下并不完美，但那些将是已经存在的极端情况的极端情况，并且std不提供适合多角度的容器。

Answer 2

shrink_to_fit 可以（但没有义务）将向量的容量减少到 size。因此，如果您正在寻找以 "optimal" 方式减少向量容量的方法，shrink_to_fit 可能是正确的选择。

当然，shrink_to_fit不带参数，因为向量的大小是作为参考的。所以你唯一需要做的就是 clear，然后 reserve，填充以填充所需的大小，最后 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();
}

Answer 3

使用这样的东西：

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);
    }
}

它将向量容量设置为capacity（如果可能），同时保留元素。而且它只做一次分配。

Answer 4

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 在空向量上对所有实现都非常有效。它不会导致新的内存分配。唯一的分配将由 reserve 完成。

不会复制任何元素T并且避免了由于重新分配而保留两个内存块的内存峰值。

除了使用 shrink_to_fit 来释放内存之外，还可以通过交换一个额外的函数（或作用域）来清除向量。这也避免了持有两个缓冲区的内存峰值。

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

"reserve or shrink" 已知未来容量需求的向量的正确方法

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

c++

stdvector