c++ - 调整大小并保留 vector

Question

主要问题

即使 vector 的容量大于其大小，调整大小是否会影响性能？

---

例如，我想编写如下伪代码的代码

const size_t size_a = 2;
const size_t i_max = 3;
vector<int> a(size_a) = random_vector;
vector<int> b;

for (size_t i=0; i<i_max; i++){
    patch_a_at_the_end_of_b;
}

因此，b 每次循环都会更改其大小，但它会单调增加，并且我知道 b 的最终大小。

---

首先，我创建一个函数 concat(a,b)，以便将 a 修补到 b 的末尾。

void concat(const vector<int> a, vector<int> &b){
    const size_t size_b = b.size();
    b.resize(size_b+a.size());
    for(size_t i=0; i<a.size(); i++)
        b[size_b + i] = a[i];
}

请注意，每次 b 被 concat 调用时，我们都会调整 vector 的大小。

然后，我在主函数的 for 循环前面添加 b.reserve 。

const size_t size_a = 2;
const size_t i_max = 3;
vector<int> a(size_a) = random_vector;
vector<int> b;
b.reserve(size_a*i_max);

for (size_t i=0; i<i_max; i++){
    concat(a,b);
}

---

Answer 1

std::vector 操作的规范可能提供了这个问题的大部分答案。

首先，resize()被指定为void resize(size_type n, value_type val = value_type())，有要求；

• 如果n小于当前大小，则附加元素将被删除并销毁(即，如果元素具有析构函数，则调用析构函数)。
• 如果 n 大于当前容器大小，则通过在末尾插入所需数量的元素来扩展内容，以达到 n 的大小。如果指定了 val，则新元素将被初始化为 val 的拷贝，否则，它们将被值初始化。
• 如果n也大于(强调我的)当前容器容量，则会自动重新分配已分配的存储空间。

请注意，如果容器尺寸减小，则没有任何关于减少容器容量的说明。

现在，reserve(size_type n)被指定为请求 vector 容量为n个或更多元素，并有要求

• 如果 n 大于当前 vector 容量，该函数会导致 容器重新分配其存储空间，将其容量增加到 n (或更大)。
• 在所有其他情况下，函数调用不会导致重新分配，并且 vector 容量不受影响。
• 此函数对 vector 大小没有影响，也不能改变其元素。

这里的第二点可以解释为 reserve() 不能用于减少容量。

注意:我在上面进行了解释，但它本质上是对 resize() 和 reserve()< 标准要求的总结。

将这些点放在一起:需要使用 resize()(或任何其他增加 vector 大小的操作)来增加 vector 容量的唯一情况是新大小超过当前容量。

除此之外，还存在实现质量问题。然而，一种合乎逻辑的实现方式是:

• resize()(以及其他增加 vector 大小的操作)永远不会增加容量，除非新大小超过当前容量
• reserve() 永远不会减少容量

在这样的实现中，在执行增加 vector 大小的操作之前调用 reserve() 将带来性能优势(消除实际重新分配的需要，除非大小增长到超过使用指定的容量reserve())。

如果实现使用不同的方法，例如在任何阶段减少容器的容量(例如，如果调用 resize() 减少了大小，它也会减少容量)。这样做可能是为了尽量减少容器的总内存使用量(即，只要 vector 本身存在，就不保留分配的额外容量)。如果 vector 的大小发生振荡(例如，在某些情况下增加，在其他情况下减少)，这会导致性能下降。