stl向量如何随机访问

Question

昨天晚上我为我的工作使用了std :: vector，这个问题突然出现在我脑海里：vector如何给随机访问？

我试图查看代码，但不成功。任何人都可以提供一些建议吗？

感谢， 阿伦

Answer 1

当然，这里有一些指针：

int *x, *y; 

但严重的是，一个vector内部只是实现为一个数组。它提供了一个超载索引操作符（[]），允许您像访问数组一样访问它。

Answer 2

向量使用下面的连续内存，因此它以与数组本身相同的方式给予随机访问：它知道元素的起始地址和大小，并执行一些指针数学运算。

Answer 3

向量通常使用动态数组实现[*] ...在任何时候数据都存储在一个连续的内存块中，因此指针运算可用于O（1）访问任何（已存在的）元件。

高效动态数组的技巧（假设你还不知道它），总是将保留存储的大小至少增加一个常数（请参阅Jerry Coffin注释）。这样做的结果是，当我们添加不定数量的新元素时，为了简单起见，将因子设为2，将第一个元素复制到第n个添加，并且将第（2 * n）个添加和第（4 * n）个添加和...

该系列收敛，所以我们可以保证添加N个新元素需要O（N）时间。但是，任何给定的添加可能需要重新分配以及所有现有元素的副本，因此没有任何延迟保证。

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

Answer 4

至少两个

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