向量如何比向量“重”？

Question

在最近的一次采访中，我建议使用向量

编码过程结束后，他们说在向量上使用pair是个好主意，并要求我详细说明我之前所说的“更重”是什么意思。不幸的是，我无法详细说明。是的，我知道我们只能在一对中输入两个值，但在一个向量中可以输入更多的值，并且当向量的大小==容量等时，该向量会自动调整大小。但是我应该如何回答他们的问题？为什么具体使用<代码>向量

Answer 1

你可以回答这个问题，而不用参考任何特定的语言。这个问题需要存储一个2元组序列。当然，您选择的类型应该能够存储2个元组，但也不能存储其他大小的元组。因此，给定两种都能够存储所需值的类型，最好选择存储不需要的值能力较差的类型。

<代码>矢量

（不要低估公认答案中提到的性能优势，只是为了提供使用精确类型的纯语义论据。）

Answer 2

每个向量都是动态分配的单个连续内存区域。

假设您将使用1000个值。

std::vector<std::pair<int, int>>

这为您提供了一个单独的、连续的内存块，用于2000个整数。

std::vector<std::vector<int>>

这将获得1000个向量的单个连续内存块。

这1000个std：：vector中的每一个只为两个整数获得另一个连续的内存块。

因此，对于这个数据结构，它将由分散在各处的1001个内存块组成，而不是一个连续的内存块。你不能保证所有这些内存块都会一个接一个地连续。

每次动态内存分配都是有代价的。成本相当小，但增长非常快。一分钱很容易被忽视。1000便士应该足够你在星巴克喝一杯咖啡了。

此外，现代CPU非常非常善于访问连续的内存块。在一个连续的内存块上迭代以累积2000个int将比在1000个不相连的内存段上进行同样的操作快得多。