为什么std :: vector连续？ [英] Why is std::vector contiguous?

问题描述

除了标准定义它是连续的，为什么std :: vector连续？

如果它的空间不足，它需要重新分配一个

如果不连续，该怎么办？当存储填满时，它将只分配一个新块并保留旧块。当通过迭代器访问时，它将做简单的>，&检查索引所在的块并返回它。这样，它不需要每次空间用完时复制数组。

这真的会工作/更好吗？ cd>如果 std :: vector didn，那么我们可能会失去一些东西？

解决方案

邻接性保证使得更容易与预期连续数组的现有代码进行交互操作，而且提供非常好的性能，因为它是缓存友好的。 （对于中等大小，在中间插入/删除实际上非常快。）

在扩展时复制数组是令人惊讶的便宜 - 如果你追加到一个向量一个百万个元素一次一个，每个元素将被平均大约复制一次。

Besides the fact that the standard defines it to be contiguous, why is std::vector contiguous?

If it runs out of space, it needs to reallocate a new block and copy the old block to the new one before continuing.

What if it wasn't contiguous? When the storage fills up, it would just allocate a new block and keep the old block. When accessing through an iterator, it would do simple >, < checks to see which block the index is in and return it. This way it doesnt need to copy the array every time it runs out of space.

Would this really work/be better? or am i missing something?

解决方案

If std::vector didn't guarantee contiguousness, a new container would be invented which did.

The contiguity guarantee makes it easier to inter-operate with existing code that expects a contiguous array, and also gives very good performance because it is cache-friendly. (Inserting/deleting in the middle is in practice very fast for moderate sizes because of this.)

Copying the array on expansion is surprisingly cheap - if you append to a vector a million elements one at a time, each element will have been copied on average around once.

这篇关于为什么std :: vector连续？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！