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

Question

如何添加和删除元素"重新缩放"数据？如何计算矢量的大小(我相信它是跟踪的)？任何其他额外的资源来了解矢量将不胜感激.

Answer 1

在大小调整方面,有两个感兴趣的值std::vector:size和capacity(通过.size()和访问.capacity()).

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

如果你.push_back()是一个元素,大小将增加1,直到你达到容量.一旦达到容量,大多数(所有？)实现,重新分配内存,使容量加倍.

您可以使用.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行.

Answer 2

矢量通常有三个指针.如果从未使用过向量,则它们都是0或NULL.

• 一到矢量的第一个元素.(这是begin()迭代器)
• 向量的最后一个元素+ 1.(这是end()迭代器)
• 还有一个到最后分配但未使用的元素+ 1.(这减去begin()就是容量)

插入元素时,向量会分配一些存储空间并设置其指针.它可能分配1个元素,或者它可能分配4个元素.或者50.

然后它插入元素并递增最后一个元素指针.

当您插入的元素多于分配的元素时,向量必须获得更多内存.它出去了,得到了一些.如果内存位置发生变化,则必须将所有元素复制到新空间并释放旧空间.

调整大小的常见选择是每次需要更多内存时将分配加倍.

Answer 3

std::vectorC++0x的实现略有变化，后来引入了移动语义（请参阅什么是移动语义？有关介绍）。

向std::vector已满的元素添加元素时，vector会调整大小，这涉及分配新的更大内存区域、将现有数据移动到新元素vector、删除旧vector空间，然后添加新元素的过程。

std::vector是标准模板库中的一个集合类。将对象放入vector、取出对象或vector在将项目添加到完整时执行调整大小vector都要求对象的类支持赋值运算符、复制构造函数和移动语义。（有关详细信息，请参阅std::vector 的类型要求以及std::vector 适用于不可默认构造的类？）

一种方法std::vector是array将vector其定义为具有一些附加功能以将其集成到标准模板库产品中时指定类型的连续元素的C 样式。avector与标准的array区别在于 avector将随着项目的添加而动态增长。（有关差异的一些讨论，请参阅std::vector 和 c 样式数组以及何时使用数组而不是向量/字符串？）

Usingstd::vector允许使用其他标准模板库组件，例如算法，因此当您开始使用已经存在的功能时，使用std::vector与 C 风格相比具有相当多的优势array。

如果提前知道最大值，您可以指定初始大小。（见设置两个元件和std ::向量的初始容量以及矢量::调整大小（）和矢量::储备之间选择（） ）

std::vector物理表示的基础是一组使用从堆分配的内存的指针。这些指针允许访问存储在 中的vector元素、从 中删除元素vector、迭代vector、确定元素数量、确定其大小等的实际操作。

由于物理表示是连续内存，删除项目可能会导致移动剩余项目以关闭删除操作产生的任何漏洞。

使用现代 C++ 移动语义， 的开销std::vector已减少，因此它通常是用于大多数应用程序的默认容器，正如 Bjarne Stroustrup 在其讨论 C++11 的《C++ 编程语言第 4 版》一书中所推荐的那样。