vector<vector<int>>怎么比vector<pair<int“重”，int>>？

Question

在最近的一次采访中，我建议使用vector<pair<int,int>>而不是vector<vector<int>>，因为我们只想为向量中的每个条目存储两个值。我说的是“我们应该使用vector<pair<int,int>>而不是vector<vector<int>>，因为后者比前者更重”。

在编码过程结束后，他们说在向量上使用对是个好主意，并要求我更早地解释我所说的“更重”是什么意思。不幸的是，我没能详细说明。是的，我知道我们只能在一对中输入两个值，但是在向量中可以输入更多的值，当它的size==capacity等等时，这个向量会自动调整大小，但是我应该如何回答他们的问题--为什么特别地使用vector<pair<int,int>>比vector<vector<int>>更好？在后一种情况下，还会做什么额外的事情？

Answer 1

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

假设您有1000个将要使用的值。

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

这将为2000个整数获得一个连续的内存块。

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

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

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

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

每次动态内存分配都要付出一定的代价。费用很小，但加起来非常非常快。一分钱很容易被忽视。一千便士就足以让你在星巴克喝杯咖啡了。

此外，现代CPU非常非常擅长访问连续的内存块。在一个连续的内存块上迭代以加2000个int将比在上千个不连接的内存段上进行相同的迭代要快得多。

Answer 2

您可以在不引用任何特定语言的情况下回答这个问题。这个问题需要存储两个元组的序列.当然，您所选择的类型应该能够存储2元组，但也不能存储其他大小的元组。因此，如果两种类型都能够存储所需的值，则更倾向于不太可能存储不想要的值的类型。

vector<int>允许您存储2元素向量，但也可以存储空向量、单例向量、3元素向量、4元素向量等。pair<int,int>更精确，因为它只能存储精确的两个值。

(为了不低估所接受的答案中提到的性能好处，只为使用精确类型提供了纯粹的语义论证。)

Answer 3

正如其他人所提到的，例如，std::vector<int>添加了元素数量的计数器。

但是你可以在面试中提出的一个有趣的方面是使用std::array<int, 2>。它应该具有与std::pair<int, int>相似的成本，因为它会将数字存储在一个固定大小的数组中。一个优点是API，它允许使用a[0]而不是a.first，并且在需要存储时也更容易泛化，例如，在添加了一些新特性之后，每个条目存储三个值。