std::vector 的向下调整大小

Question

C++标准似乎没有对resize(n)（其中 n < size()）或 clear() 对容量产生的副作用做出任何说明。

它确实有关于push_back和pop_back的摊销成本的说明 - O(1)。

我可以想象一种实现方式，它会按照 CLRS 算法中常规的容量更改方式来处理（例如，在扩大时加倍，在将size缩小到capacity()/4以下时减半）。 (Cormen Lieserson Rivest Stein)

是否有人可以提供任何实现限制的参考资料？

- pgast

Answer 1

使用resize()减小vector的大小不会影响其容量，它也不会释放内存。

从vector中释放内存的标准惯用语是将其与一个空的临时vector进行swap()： std::vector<T>().swap(vec);。如果您想要向下调整大小，则需要从原始vector复制到一个新的本地临时vector，然后将生成的vector与原始vector进行交换。

更新：C++11添加了成员函数shrink_to_fit()，用于此目的，它是将capacity()非绑定请求减少到size()。

- mattnewport

---

我理解他在询问调整大小对内存使用的影响 - 他特别询问了调整大小对容量的影响。标准没有明确规定这种情况下的结果，但我能想到的唯一原因是希望释放未使用的内存。使用临时交换技巧是实现这一目的的惯用方式。 - mattnewport

标准规定了这些操作的结果，即使没有明确说明会导致capacity()减少，因此它不会减少。 - MSalters

在某些环境中，在初始“构建”阶段之后禁止分配或释放内存。只要确保向量在操作期间不尝试分配或释放内存，它们就可以在此环境中使用。因此，这个问题在这种情况下是相关的（这也是我来到这里的原因）。 - davidA

使用g++和libstdc++ 10，std::vector::shrink_to_fit会进行新的分配。每次调用shrink_to_fit()时，myvector.data()都会产生不同的地址。 - Max Power

Answer 2

实际上，标准确实指定了应该发生什么：

这是来自vector的示例，但所有容器（list，deque等）的主题都是相同的。

23.2.4.2 vector capacity [lib.vector.capacity]

void resize(size_type sz, T c = T());

6）影响：

if (sz > size())
    insert(end(), sz-size(), c);
else if (sz < size())
    erase(begin()+sz, end());
else
    ; //do nothing

也就是说：如果传递给 resize 的大小小于元素数量，这些元素将从容器中被删除。关于 capacity()，它取决于 erase() 的行为。

我无法在标准中找到它，但我很确定 clear() 被定义为：

void clear()
{
    erase(begin(), end());
}

因此，clear() 对 capacity() 的影响也与 erase() 对其的影响有关。根据标准：

23.2.4.3 向量修改器 [lib.vector.modifiers]

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

4) 复杂度：T 的析构函数被调用的次数等于被删除元素的数量。

这意味着元素将被销毁，但内存将保持不变。erase() 对容量没有影响，因此 resize() 和 clear() 也没有影响。

- GManNickG

---

现在已经将向下的 resize 文档化为等同于一系列 pop_back() 调用而不是 erase。这是否会取消容量不变的保证？（请参见 https://dev59.com/0nnZa4cB1Zd3GeqPlRDt） - Ben Voigt

Answer 3

容量永远不会减少。我不确定标准是否明确规定了这一点，但是它是暗示的：如果n < capacity()，则resize(n)不得使向量元素的迭代器和引用失效。

- avakar

Answer 4

我查了一下gcc（mingw），唯一释放向量容量的方法是mattnewport所说的。 用其他临时向量进行交换。 这段代码适用于gcc。

template<typename C> void shrinkContainer(C &container) {
    if (container.size() != container.capacity()) {
        C tmp = container;
        swap(container, tmp);
    }
    //container.size() == container.capacity()
}

- Fantastory