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

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

Answer 3

的载体通常具有三个指针。如果矢量从未被使用过，它们都是0或NULL。

• 一个向量的第一个元素。 （这是开始（）迭代）
• 一到的最后一个元素的矢量+ 1（这是结束（）迭代）
• 还有一到最后分配但未被使用的元件+ 1（这个减去开始（）是容量）

当插入一个元素，向量分配一些存储和设置其指针。它可能分配1个元素，或者可能分配4个元素。或50.

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

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

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

Answer 4

std::vector的实现在C++ 0x和稍后引入移动语义（请参见What are move semantics?作为简介）稍作修改。

当将一个元素增加到一个std::vector这已经是满的，则该vector被调整大小，其包括分配一个新的，更大的存储器区域中，现有的数据移动到新vector，删除旧vector空间的过程，然后添加新元素。

std::vector是标准模板库中的集合类。将对象放入vector中，将其取出或在将项目添加到完整的vector时执行调整大小都要求对象的类支持赋值运算符，复制构造函数和移动语义。 （参见type requirements for std::vector以及std::vector works with classes that are not default constructible?联系）想std::vector

的一种方式是为C样式指定的类型的连续元素array当vector被定义，有一些额外的功能将其集成到标准模板库产品。将vector与标准array分开的是vector将随着项目的添加而动态增长。 （有关分歧一些讨论见std::vector and c-style arrays以及When would you use an array rather than a vector/string?。）

使用std::vector允许使用其他标准模板库组件，如算法，所以使用std::vector了一个C风格array带有相当多的优点，当你到使用已经存在的功能。

如果提前知道最大值，您可以指定初始大小。 （请参阅Set both elements and initial capacity of std::vector以及Choice between vector::resize() and vector::reserve()）

std::vector的基本知识物理表示形式是一组使用从堆中分配的内存的指针集。这些指针允许用于访问存储在所述vector的元素，从vector删除元素，遍历vector，确定元件的数量，来确定其大小的实际操作等

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

使用现代C++移动语义，std::vector的开销已经减少，因此它通常是默认的容器，可用于大多数应用程序，正如Bjarne Stroustrup在他的书“The C++ Programming Language 4th Edition” +11。