我知道当我们将项目插入 vector 时,它的容量可能会因非线性因素而增加。在 gcc 中,它的容量加倍。但我想知道为什么当我从 vector 中删除项目时,容量不会减少。我试图找出原因。它“似乎”C++ 标准没有对这种减少说任何话(做或不做)。
根据我的理解,理想情况下,当 vector 大小达到其删除项容量的 1/4 时,该 vector 可以缩小其容量的 1/2 以实现恒定的摊销空间分配/取消分配复杂度。
我的问题是为什么C++标准没有规定缩容策略?不指定任何相关内容的语言设计目标是什么?有人对此有想法吗?
最佳答案
It 'seems' C++ standard does not say any word about this reduction (either to do or not)
这不是真的,因为 vector::erase
的复杂性描述明确指定了将执行的操作。
来自 §23.3.6.5/4 [vector.modifiers]
iterator erase(const_iterator position); iterator erase(const_iterator first, const_iterator last);
Complexity: The destructor of
T
is called the number of times equal to the number of the elements erased, but the move assignment operator ofT
is called the number of times equal to the number of elements in the vector after the erased elements.
这会阻止实现减少容量,因为这意味着重新分配存储并将所有剩余元素移动到新内存。
而且,如果您要问为什么标准本身不指定允许在删除元素时减少容量的实现,那么只能猜测原因。
从性能的角度来看,让
vector
在删除时花时间重新分配和移动元素可能被认为不够重要减少容量还会增加由于内存分配失败导致异常的可能性。
您可以尝试通过调用 vector::shrink_to_fit
自行减少容量,但请注意此调用是非绑定(bind)的,并且允许实现忽略它。
另一种减少容量的可能性是将元素移动到一个临时的 vector
中,然后将其交换
回到原来的状态。
decltype(vec)(std::make_move_iterator(vec.begin()),
std::make_move_iterator(vec.end())).swap(vec);
但即使使用第二种方法,也无法阻止实现过度分配存储。
关于c++ - 为什么 std::vector 项目删除不会减少其容量?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24708480/