C++中std::vector的基本问题

Question

C++课本和线程，比如这些，都说明vector元素在内存中是物理连续的。

但是当我们执行v.push_back(3.14)这样的操作时，我会认为STL使用new运算符获得更多内存来存储新元素3.14。

现在假设大小为4的向量存储在计算机内存单元0x7, 0x8, 0x9, 0xA中。如果单元格0xB包含其他不相关的数据，那么3.14会进入该单元格吗？这是否意味着单元格0xB将被复制到其他地方，或被清除以腾出空间给3.14？

- smilingbuddha

---

http://en.wikipedia.org/wiki/Vector_(C%2B%2B)#Capacity_and_reallocation - Laserallan

Answer 1

简而言之，存储向量数据的整个数组被移动到有空间扩展的位置。vector类保留比实际所需更大的数组来容纳向量中的元素数量。例如：

vector< int > vec;
for( int i = 0; i < 100; i++ )
    vec.push_back( i );

cout << vec.size(); // prints "100"
cout << vec.capacity(); // prints some value greater than or equal to 100

capacity()方法返回向量分配的数组大小，而size()方法返回实际使用的数组元素数量。capacity()总是会返回一个大于或等于size()的数值。您可以使用reserve()方法来改变支持数组的大小：

vec.reserve( 400 );
cout << vec.capacity(); // returns "400"

请注意，size()、capacity()、reserve()以及所有相关方法都是指向vector所持有的类型的个体实例。例如，如果vec的类型参数T是一个占用10个字节的结构体，则vec.capacity()返回400意味着向量实际上预留了4000字节的内存（400 x 10 = 4000）。

那么如果向向量中添加的元素超过其容量会发生什么呢？在这种情况下，向量将分配一个新的后备数组（通常是旧数组大小的两倍），将旧数组复制到新数组中，然后释放旧数组。伪代码如下：

if(capacity() < size() + items_added)
{
    size_t sz = capacity();
    while(sz < size() + items_added) 
       sz*=2;
    T* new_data = new T[sz]; 
    for( int i = 0; i < size(); i++ )
        new_data[ i ] = old_data[ i ];
    delete[] old_data;
    old_data = new_data;
}

因此，整个数据存储区域被移动到一个新的内存位置，该位置具有足够的空间来存储当前数据以及一些新元素。如果向量分配的空间远远超过实际需要的空间，一些向量也可能会动态减小其支持数组的大小。

- Chris Vig

---

你的伪代码中是否意味着 if( capacity() < size() + items_added) { new_data = new T[ capacity() * 2 ]; .. } ？ - Ajeet Ganga

@Ajeet - 不行，因为while循环即使对于任意数量的items_added也能正常工作。例如，考虑capacity() = 10且items_added = 12000的情况。简单的if会导致数组溢出。 - Chris Vig

@Chris Vig：不应该是 size_t sz = capacity(); while(sz<size()+items_added) sz*=2; T* newData = new T[sz] for... 这样只会有一份副本。 - Ajeet Ganga

Ajeet - 是的，说得好。我发表的内容远非优化算法，我只是试图举例说明幕后可能发生的情况。我同意你的实现更好。 - Chris Vig

Answer 2

std::vector 首先分配一个更大的缓冲区，然后将 "旧" 缓冲区中的现有元素复制到 "新" 缓冲区中，然后删除 "旧缓冲区"，最后将新元素添加到 "新" 缓冲区中。

通常，std::vector 实现通过每次需要分配更大的缓冲区时将容量加倍来增加其内部缓冲区。

正如 Chris 提到的那样，每次缓冲区增长时，所有现有迭代器都会失效。

- Gregory Pakosz

---

此外，所有现有的迭代器都会失效。 :-) - C. K. Young

只有在容量超过时才会进行分配。您可以使用 "reserve" 来定义特定的容量。如果您从未超过该容量，则不会发生重新分配或迭代器无效化。 - Nicol Bolas

Answer 3

当std::vector为值分配内存时，它会分配比实际需要更多的内存；你可以通过调用capacity来找出分配了多少内存。当使用完此容量后，它会再次分配一个更大的块，大小仍然比所需的大，并将所有内容从旧内存复制到新内存；然后释放旧内存。

- Mark Ransom

Answer 4

如果没有足够的空间添加新元素，将分配更多的空间（正如您正确指出的那样），并将旧数据复制到新位置。因此，单元格0xB仍将包含旧值（因为它可能在其他地方有指向它的指针，移动它会造成混乱），但是整个相关向量将移动到新位置。

- yhager

---

虽然这是正确的，但您完全没有理解OP的问题。 - Karl Knechtel

我的意思是它将被重新分配到其他地方，那里有足够的内存来容纳向量。我错过了什么？ - yhager

你错过了它被重新分配到其他地方的部分，以及数据被复制到新的分配位置并相应地重置指针的部分。也就是说，解释为什么“0xB槽”中实际上有什么并不重要的部分。也就是实际回答问题的部分。 - Karl Knechtel

OP已经提到了一个假设，即正在使用“new”，因此如果这一点很清楚，那么OP一开始就不会有问题了。 - Karl Knechtel

@Karl，我编辑了答案，希望它更好地解释了发生了什么。感谢您的建设性评论。 - yhager

Answer 5

在C++中，内存不会像您描述的那样“管理” - 单元格0x0B的内容不会被移动。如果这样做，任何现有的指针都将变为无效！（唯一可能的方式是语言没有指针并且仅使用引用进行类似的功能。）

std::vector分配一个新的、更大的缓冲区，并将值3.14存储到缓冲区的“末尾”。

通常，对于优化的this->push_back()，std::vector分配大约两倍于其this->size()的内存。这确保了合理的内存交换以获得更好的性能。因此，不能保证3.14会导致this->resize()，只有当this->size() < this->capacity()时，才可能将其放入this->buffer[this->size()++]中。

- Mateen Ulhaq

Answer 6

一个向量是一组内存。典型的实现是它会分配比所需更多的内存。如果这个占用空间需要扩展到其他任何内存位置，整个向量将被复制。旧的内容将被释放。向量的内存位于堆栈上，请注意这一点。另外，最好在使用时说明所需的最大尺寸。

- Ed Heal

---

向量内存是什么？ - Lightness Races in Orbit