c++ - stl 向量如何提供随机访问

Question

昨天晚上，我在工作中使用 std::vector，这个问题突然出现在我脑海中：vector 如何提供随机访问？

我试图研究代码但没有成功。任何人都可以提供一些指示吗？

谢谢，阿伦

score 20 · Accepted Answer

Vector 在底层使用连续内存，因此它提供与数组相同的随机访问方式：它知道起始地址和元素的大小，并进行一些指针数学运算。

score 12 · Accepted Answer

当然，这里有一些提示：

int *x, *y;

但说真的， avector在内部只是作为数组实现的。它提供了一个重载的索引运算符 ( []) 以允许您像访问数组一样访问它。

score 1 · Accepted Answer

至少两倍

实际上，许多实现使用因子 1.5 重要的是它是一个因子，所以你得到指数向量增长。

score 1 · Accepted Answer

Vector 通常使用动态数组实现[*] ...始终将数据存储在连续的内存块中，因此指针算法可用于 O(1) 访问任何（已经存在的）元素。

高效动态数组的诀窍（假设您还不知道）是始终将保留存储的大小至少增加一个常数因子（请参阅 Jerry Coffin 评论）。这样做的结果是，当我们添加无限数量的新元素时，为简单起见将因子设为 2，第一个元素在第 n 次添加时被复制，第 (2*n) 次添加和第 (4*n) 次添加和...

这个级数收敛，所以我们可以保证添加 N 个新元素需要 O(N) 时间。但是，任何给定的添加都可能需要重新分配和复制所有现有元素，因此没有任何延迟保证。

[*] 我不知道另一种机制可以达到所需的性能。任何人？

4 回答 4