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

Question

C++ 教科书和线程，例如 these说 vector 元素在内存中是物理上连续的。

但是当我们执行像 v.push_back(3.14) 这样的操作时，我会假设 STL 正在使用 new 运算符来获取更多内存来存储新元素 3.14引入到载体中。

现在假设大小为 4 的 vector 存储在标记为 0x7, 0x8, 0x9, 0xA 的计算机存储单元中。如果单元格 0xB 包含一些其他不相关的数据，3.14 将如何进入该单元格？这是否意味着单元格 0xB 将被复制到其他地方，并被删除以为 3.14 腾出空间？

Answer 1

简短的回答是将保存 vector 数据的整个数组移动到它有空间增长的位置。 vector 类保留了一个比技术上需要的更大的数组来保存 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() 方法返回 vector 保留的数组的大小，而 size() 方法返回数组中元素的数量实际上在使用中。 capacity() 将始终返回大于或等于 size() 的数字。您可以使用 reserve() 方法更改支持数组的大小:

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

请注意，size()、capacity()、reserve() 以及所有相关方法都引用了该类型的各个实例 vector 持有。例如，如果 vec 的类型参数 T 是一个占用 10 字节内存的结构，则 vec.capacity() 返回 400 表示该 vector 实际保留了 4000 字节的内存(400 x 10 = 4000)。

那么如果添加到 vector 的元素多于它的容量会发生什么？在这种情况下，vector 分配一个新的后备数组(通常是旧数组大小的两倍)，复制旧数组到新数组，然后释放旧数组。在伪代码中:

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;
}

所以整个数据存储被移动到内存中的一个新位置，该位置有足够的空间来存储当前数据和一些新元素。如果分配的空间比实际需要的空间多得多，一些 vector 也可能会动态减小其支持数组的大小。