c std::vector 是如何工作的？

Question

添加和删除元素如何“重新调整”数据？矢量的大小是如何计算的（我相信它会被跟踪）？任何其他了解向量的其他资源将不胜感激。

原文由 Alan 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

In terms of sizing, there are two values of interest for a std::vector : size , and capacity (accessed via .size() and .capacity() ）。

.size() 是向量中包含的元素数量，而 .capacity() 是在重新分配内存之前可以添加到向量中的元素数量。

如果你 .push_back() 一个元素，大小将增加一，直到你达到容量。一旦达到容量，大多数（所有？）实现都会重新分配内存，使容量翻倍。

您可以使用 .reserve() 保留容量。例如：

 std::vector<int> A;
A.reserve(1);        // A: size:0, capacity:1  {[],x}
A.push_back(0);      // A: size:1, capacity:1  {[0]}
A.push_back(1);      // A: size:2, capacity:2  {[0,1]}
A.push_back(2);      // A: size:3, capacity:4  {[0,1,2],x}
A.push_back(3);      // A: size:4, capacity:4  {[0,1,2,3]}
A.push_back(4);      // A: size:5, capacity:8  {[0,1,2,3,4],x,x,x}

内存的重新分配将发生在第 4、5 和 7 行。

原文由 MarkD 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

大约一年前，我用 C++ 写了一个向量。它是一个具有设定大小（例如 16 个字符）的数组，在需要时会按该数量进行扩展。也就是说，如果默认大小是 16 个字符并且您需要存储 Hi my name is Bobby ，那么它将数组的大小加倍到 32 个字符，然后将 char 数组存储在那里。

原文由 Caleb Hearth 发布，翻译遵循 CC BY-SA 2.5 许可协议