关于在C++中使用std :: vector的基本问题

Question

像这样的 C++教科书和线程说,向量元素在内存中是物理上连续的.

但是当我们进行操作时,v.push_back(3.14)我会假设STL正在使用new运算符来获取更多内存来存储刚引入向量的新元素3.14.

现在说大小为4的向量存储在标记的计算机存储单元中0x7, 0x8, 0x9, 0xA.如果单元格0xB包含其他一些不相关的数据,那么将如何3.14进入此单元格？这是否意味着单元格0xB将被复制到其他地方,为了腾出空间而被删除3.14？

Answer 1

简短的回答是,包含矢量数据的整个数组被移动到有空间增长的位置.向量类保留的数组大于技术上保持向量中元素数量所需的数组.例如:

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(),和所有相关的方法指的是矢量持有类型的单个实例.例如,如果vec类型参数T是占用10内存字节的结构,则vec.capacity()返回400意味着该向量实际上具有4000reserved(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;
}

因此整个数据存储被移动到内存中的新位置,该位置具有足够的空间来存储当前数据以及许多新元素.如果分配的空间比实际需要的多得多,则某些向量也可以动态地减小其后备阵列的大小.

Answer 2

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

通常,std::vector每次需要分配更大的缓冲区时,实现会增加内部缓冲区的容量.

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

Answer 3

当std :: vector为值分配内存时,它会分配超过它需要的内存; 你可以通过电话找出多少capacity.当该容量用完时,它会分配一个更大的块,同样大于它需要的块,并复制从旧内存到新内存的所有内容; 然后它释放旧的记忆.