数据安排与操作方式：vector的扩容操作

简介：

https://www.toutiao.com/article/7152049468647408163/?log_from=1a78066138c89_1665306154327

vectro的数据安排以及操作方式，与array数组非常相似。

array是静态空间，一旦配置了就不能改变；

vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。

vector维护的是一个连续性空间，所以vector支持随机存取，可以像数组一样使用"[]"。

vector的数据结构：

vector使用的迭代器

vector示意图

vector的erase：

vector的erase操作效果

vector的插入操作：

备用空间充足

备用空间充足

备用空间不足

注意：插入数据动态扩容的大小不一定是放大一倍，放大的数为：max(old_size,n)

通过下面的示例可以看出vector在插入数据时capacity的变化规律(IDE:visual studio 2022)：

vector的扩容操作：

vector的扩容方式有两种，下面详细分析一下他们的差异。

①vector的resize：

既分配了空间，也创建了对象，会调用构造函数。

void resize(size_type new_size, const T& x) {

if (new_size < size())

erase(begin() + new_size, end());

else

insert(end(), new_size - size(), x);

}

void resize(size_type new_size) { resize(new_size, T()); }

由此可以看出：resize()既修改capacity大小，也修改size大小。

②vector的reserve：

reserve()表示容器预留空间，但不是真正的创建对象，需要通过insert()或push_back()等操作创建对象。

template <class ForwardIterator>

iterator allocate_and_copy(size_type n,

ForwardIterator first, ForwardIterator last) {

iterator result = data_allocator::allocate(n);//创建n个元素的新空间

__STL_TRY {

uninitialized_copy(first, last, result);//把vector旧空间中的所有有效数据(las-first条数据)，顺序拷贝到vector的新空间里，

return result;

}

__STL_UNWIND(data_allocator::deallocate(result, n));

}

void reserve(size_type n) {

if (capacity() < n) {

const size_type old_size = size();

iterator tmp = allocate_and_copy(n, start, finish);

destroy(start, finish);//析构vector旧空间中的所有有效数据(las-first条数据)

deallocate();//释放vector旧空间

start = tmp;

finish = tmp + old_size;//vector的实际元素个数还是和以前一样，没有变化

end_of_storage = start + n;//vector总容积大小增加了n个元素

}

}

由此可以看出：reserve()只修改capacity大小，不修改size大小。

通过下面的示例可以看出vector在resize和reserve处理下的差异(IDE:visual studio 2022)：

因此，在只需要足够的空间而不需要生成对象时（通常是为了节约插入元素的时间），应该选择reserve方法进行扩容。

示例代码：

#include<iostream>

#include <vector>

using namespace std;

void fun_vector_test()

{

//构造数据

vector<int> ver_obj;

cout << " vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

cout << "插入数据:" << endl;

ver_obj.push_back(5); cout << "push_back(5) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(10); cout << "push_back(10) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(15); cout << "push_back(15) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(20); cout << "push_back(20) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(25); cout << "push_back(25) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(30); cout << "push_back(30) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(35); cout << "push_back(35) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(40); cout << "push_back(40) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(45); cout << "push_back(45) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(50); cout << "push_back(50) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(55); cout << "push_back(55) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(60); cout << "push_back(60) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(65); cout << "push_back(65) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(70); cout << "push_back(70) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(75); cout << "push_back(75) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(80); cout << "push_back(80) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(85); cout << "push_back(85) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(90); cout << "push_back(90) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(95); cout << "push_back(95) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(100); cout << "push_back(100) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(101); cout << "push_back(101) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(102); cout << "push_back(102) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(103); cout << "push_back(103) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(104); cout << "push_back(104) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(105); cout << "push_back(105) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(106); cout << "push_back(106) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(107); cout << "push_back(107) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(108); cout << "push_back(108) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(109); cout << "push_back(109) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

ver_obj.push_back(200); cout << "push_back(200) vector 实际元素个数:" << ver_obj.size() << " vector bucket的总数capacity:" << ver_obj.capacity() << endl;

cout <<"打印信息:" << endl;

auto iter_print = ver_obj.begin();

for (; iter_print != ver_obj.end(); ++iter_print)

{

cout <<" "<< * iter_print;

}

cout << endl;

ver_obj.reserve(10); cout << " vector 调整reserve为10 capacity:" << ver_obj.capacity() << " vector 实际元素个数:" << ver_obj.size() << endl;

iter_print = ver_obj.begin();

for (; iter_print != ver_obj.end(); ++iter_print)

{

cout << " " << *iter_print;

}

cout << endl;

try

{

ver_obj.resize(10); cout << " vector 调整resize为10 capacity:" << ver_obj.capacity() << " vector 实际元素个数:" << ver_obj.size() << endl;

}

catch (const std::exception& e)

{

cout << " vector 调整resize为10 exception:" << e.what() << endl;

}

iter_print = ver_obj.begin();

for (; iter_print != ver_obj.end(); ++iter_print)

{

cout << " " << *iter_print;

}

cout << endl;

ver_obj.resize(80); cout << " vector 调整resize为80 capacity:" << ver_obj.capacity() << " vector 实际元素个数:" << ver_obj.size() << endl;

iter_print = ver_obj.begin();

for (; iter_print != ver_obj.end(); ++iter_print)

{

cout << " " << *iter_print;

}

cout << endl;

ver_obj.reserve(100); cout << " vector 调整reserve为100 capacity:" << ver_obj.capacity() << " vector 实际元素个数:" << ver_obj.size() << endl;

iter_print = ver_obj.begin();

for (; iter_print != ver_obj.end(); ++iter_print)

{

cout << " " << *iter_print;

}

cout << endl;

ver_obj.resize(100); cout << " vector 调整resize为100 capacity:" << ver_obj.capacity() << " vector 实际元素个数:" << ver_obj.size() << endl;

iter_print = ver_obj.begin();

for (; iter_print != ver_obj.end(); ++iter_print)

{

cout << " " << *iter_print;

}

cout << endl;

ver_obj.reserve(150); cout << " vector 调整reserve为150 capacity:" << ver_obj.capacity() << " vector 实际元素个数:" << ver_obj.size() << endl;

iter_print = ver_obj.begin();

for (; iter_print != ver_obj.end(); ++iter_print)

{

cout << " " << *iter_print;

}

cout << endl;

}

int main()

{

fun_vector_test();

return 0;

}