为什么向量<向量<int>>比向量<pair<int,int>>“更重”？

Question

为什么向量<向量<int>>比向量<pair<int,int>>“更重”？

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

编码会议结束后，他们说使用对而不是向量是个好主意，并要求我详细说明之前所说的“更重”的含义。不幸的是，我无法详细说明。是的，我知道我们只能在一对中输入两个值，但在向量中可以输入更多值，并且当向量的大小==容量等时，该向量会自动调整大小，等等，但我应该如何回答他们的问题 - 为什么具体使用比vector<pair<int,int>> 更好vector<vector<int>>？在后一种情况下还做了哪些额外的事情？

Answer 1

Sam*_*hik 78

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

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

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

Run Code Online (Sandbox Code Playgroud)

这将为您提供一个连续的内存块，用于存储 2000 个整数。

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

Run Code Online (Sandbox Code Playgroud)

这将为您提供可容纳 1000 个向量的单个连续内存块。

这 1000 个中的每一个std::vector都会为您提供另一个连续的内存块，仅存储两个整数。

因此，对于该数据结构，它将由分散在各处的 1001 个内存块组成，而不是一个连续的内存块。无论如何，您无法保证所有这些内存块都是连续的，一个接一个。

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

此外，现代 CPU 非常非常擅长访问连续的内存块。迭代单个连续的内存块以加起来 2000int秒将比对一千多个不连贯的内存部分进行相同的操作要快得多。

最重要的是，你有 1000 个用于 `vector<int>` 对象的控制块，每个控制块的大小为 3 个指针（在正常实现上），指向这 1000 个分散的分配。在典型的 64 位系统上，除了动态分配簿记数据（每次分配可能至少有 8 个字节）之外，每 8 个字节的数据需要 24 个字节的开销。可能更多，特别是在“alignof(max_align_t)”为 16 的系统上，因此每个分配都是 16 字节对齐的。是的，所有这些间接寻址对于编译时 SIMD 优化以及实际上分散的 CPU 来说都是不利的。 (6认同)
关于成本的一点说明。如果您已经在 99 个位置进行了此操作，那么再添加一个位置的成本相对较低。（否则没有人会用 Python 编程！）但是，性能错误从 3 个变为 2 个会产生很大的影响，而从 2 个变为 1 个影响更大。最后，嗯... (5认同)

Answer 2

che*_*ner 30

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

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

（并不是要低估已接受答案中提到的性能优势，只是为了提供使用精确类型的纯粹语义参数。）

确切地。性能更好，因为类型更精确，因此我们可以使用更具体的算法和数据结构，而不是更通用的算法和数据结构（例如，简单地存储两个整数，而不是存储指向任意多个整数的数组的指针）。使用更精确的类型也能更好地表达意图。 (7认同)
`std::array<int,2>` 也完全没问题，并且执行相同的操作，因为它保存的是 `array` 对象本身内部的值，而不是指向它们的指针。（与“std::pair<int,int>”相同的对象表示）。你的论点同样适用于它；`,2` 大小是类型的一部分，而不是运行时变量数据。因此，尽管“std::array”通常可以容纳任意数量的整数，但模板的实例化可以恰好容纳两个，与“pair”相同。（它们必须是相同的类型，而“pair”支持不同的类型。但“pair<int,int>”则不然。） (2认同)

Answer 3

all*_*llo 18

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

但你可以在面试中建议的一个有趣的方面是使用std::array<int, 2>. 它应该具有类似的成本，因为std::pair<int, int>它将数字存储在固定大小的数组中。一个优点是 API，它允许使用a[0]代替a.first，并且当您可能需要存储（例如，在添加一些新功能后每个条目三个值）时也更容易泛化。

是的，它的正常实现将具有与 std::pair<int,int>` 相同的对象表示，并且应该编译为完全相同的 asm。使用对您的用例在语义上更有意义的选项；如果两个整数具有相似的含义，则“foo[i][0]”和“foo[i][1]”很好；如果 `foo[i].first` / `.second` 不相似，那么它们可能会很好。或者，您可以使用枚举或包装类为数组索引指定有意义的名称。（或者如果您想要有意义的成员名称，可能只使用自定义结构而不是“pair<>”或“array<>”！） (3认同)

Answer 4

nut*_*tax 14

为了简化解释，我们这样说

A[ a | b ] B[ c ] 意思是：a和b分别在块 A和块 Bc中。

这里的块是连续的内存块，所以a 旁边是 b

考虑到这一点，让我们看一个例子：内存使用情况 { { 1, 1 } , { 2, 2 }, ... }

为了std::vector<<std::vector<int>>

A[ size info | ptr to B ]

B[ [ size info | ptr to C ] | [ size info | ptr to D ] | ... ]

C[ 1 | 1 ]

D[ 2 | 2 ]

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

A[ size info | ptr to B ]

B[ [ 1 | 1 ] | [ 2 | 2 ] | ... ]

我认为这个例子非常清楚：在执行时少了一层间接 std::vector<std::pair<int, int>>。意义

内存消耗更少（您不需要额外的大小变量和指向每个元素块的指针）。

要获得所需的值，您需要执行更少的步骤（否则，您必须首先加载并读取指针，然后使用该地址加载所需的值）。

@YurkoFlisk：普通的`std::vector`实现有3个指针：数据、分配结束（`.reserve()`或自动增长）和“使用中”区域的结束（`.size() = .end） () - .begin()`)。实现*可以*使用指针和两个“size_t”成员，但实际上主流实现使用指针。无论哪种方式，“sizeof(std::vector<T>)”在典型的 64 位系统上为 24 个字节（或在 32 位系统上为 12 个字节），而“std::array<int,2>”或“ std::pair<int,int>` 每个都是 8 个字节。 (2认同)

@YurkoFlisk：所以 `std::vector` 每 8 个实际数据浪费 24 个字节，如果算上动态分配簿记的话，会浪费更多。更不用说可能会分散您的数据并引入一定程度的间接性。 (2认同)

Answer 5

小智 7

向量是动态调整大小的数组。您牺牲了一些性能以获得动态调整大小的能力。

向量组成的向量 ( vector<vector<int>>) 的外部向量及其每个元素都会产生性能开销。对于向量对 ( vector<pair<int, int>>)，则没有后者。一对始终具有固定大小，因此您不必担心必须根据需要调整其大小（并根据需要将其重新定位到内存中的另一个位置）。

归档时间：	3 年，3 月前
查看次数：	6622 次
最近记录：	3 年，2 月前

为什么向量&lt;向量&lt;int&gt;&gt;比向量&lt;pair&lt;int,int&gt;&gt;“更重”？

为什么向量<向量<int>>比向量<pair<int,int>>“更重”？