一 std::vector扩容和减容

	std::vector<int> arr;
	for (int i = 0;i < 100;++i)
	{
		arr.push_back(i);
		std::cout << "capacity=" << arr.capacity() << ",size=" << arr.size() << std::endl;
	}

msvc编译

gcc编译

规律:每次扩容都是增加当前空间的50%(msvc)或100%(gcc)

//在vs2019查看扩容源码
size_type _Calculate_growth(const size_type _Newsize) const {
	// given _Oldcapacity and _Newsize, calculate geometric growth
	const size_type _Oldcapacity = capacity();
	const auto _Max = max_size();
	if (_Oldcapacity > _Max - _Oldcapacity / 2) {
			return _Max; // geometric growth would overflow
	}
	const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
	if (_Geometric < _Newsize) {
			return _Newsize; // geometric growth would be insufficient
	}
	return _Geometric; // geometric growth is sufficient
}

比如,当前容量是42,并已填满,需要再填入22个量。用push_back逐个添加,将经历两次扩容,第1次42+42/2=63,第2次扩容63+63/2=94;

存在问题:1)经历两次扩容,即经历两次内存分配。2)容量浪费。

扩容步骤:

1. 分配一个新的内存块,其容量是当前容量的数倍(msvc是1.5倍,即扩容50%)

2. 从容器原来占用的内存中将元素拷贝到新分配的内存中;

3. 释放原有内存中的对象;

4. 释放原有内存。

删除容器中数据的时候(不论clear()还是erase)(),缓冲区大小并不会改变,仅仅只是清除了其中的数据,只有在析构函数调用的时候vector才会自动释放缓冲区。或者使用vector.shrink_to_fit()减容.

struct S
{
int i = 0;
char s[100];
}
//自动扩容
void fillVector(std::vector<S>& v,long c= 500000)
{
	for (auto i = 0L;i < c;i++)
	{
			v.push_back(S{ i,"123" });
	}
}
//用resize构造,再逐个赋值。
void fillVector_2(std::vector<S>& v, long c = 500000)
{
	v.resize(c);
	for (auto i = 0L;i < c;i++)
	{
			v[i].i = i;
	}
}
//用reserve扩容,再逐个构造。
void fillVector_3(std::vector<S>& v, long c = 500000)
{
	v.reserve(c);
	for (auto i = 0L;i < c;i++)
	{
		v.push_back(S{ i,"123" });
	}
}

在不同环境中的执行结果:

技巧:

  • 通过扩容保留vector的大小,避免不必要的重新分配和复制周期(vector所需容量较少,就没有必要了)。
  • clear()或erase()清除内容而不释放内存,释放内存使用shrink_to_fit()

二 std::vector赋值

用一个vector给另一个vector赋值

std::vector<S> res1, des1;
std::vector<S> res2, des2;
std::vector<S> res3, des3;
fillVector_2(res1);
fillVector_2(res2);
fillVector_2(res3);

Time t;		//计算时间用的
t.start();
des1 = res1; // =
std::cout <<"=赋值 :"<< t.stop() <<"ms"<< std::endl;

t.start();
des2.insert(des2.end(), res2.begin(), res2.end());//insert
std::cout << "insert赋值 :" << t.stop() << "ms" << std::endl;

int count = res3.size();
t.start();
for (int i = 0;i < count;++i) //push_back
{
		des3.push_back(res3[i]);
}
std::cout <<"push_back赋值:"<< t.stop() << "ms" << std::endl;

在不同环境中的执行结果:

技巧:

= 赋值是最佳选择

三 std:: vector取值

iterator 、at 和 [] 的性能差异

Time t;			//计算时间用的
std::vector<S> vec;
fillVector_2(vec);
std::cout << "capacity=" << vec.capacity() << ",size=" << vec.size() << std::endl;
t.start();
for (auto it = vec.begin(); it != vec.end(); ++it)
{
			int v = it->i; //使用迭代器取值
}
std::cout << "iterator:"<<t.stop() <<"ms"<< std::endl;

int count = vec.size();
t.start();
for (unsigned i = 0; i < count; ++i)
{
			int v = vec.at(i).i; //使用at
}
std::cout << "at() :" << t.stop() << "ms" << std::endl;
t.start();
for (unsigned i = 0; i < count; ++i)
{
				auto v = vec[i].i; //使用下标
}
std::cout << "[] :" << t.stop() << "ms" << std::endl;

在不同环境中的执行结果:

技巧:

iterator取值最慢, 取下标[]更快

四 std::vector前插、std::vector后插 和std::list插入

std::vector<S> vec;
vec.resize(500000);
std::vector<S> vec1;
vec1.resize(500000);
std::list<S> lst;
lst.resize(500000);
std::vector<S> vec2;
vec2.resize(10000); //10000个

Time t;				//计算时间用的
t.start();
std::cout << "capacity=" << vec.capacity() << ",size=" << vec.size() << std::endl;
vec.insert(vec.begin(), vec2.begin(), vec2.end());			//insert begin
std::cout << "vector 前插:" << t.stop() << "ms" << std::endl;
std::cout << "capacity=" << vec.capacity() << ",size=" << vec.size() << std::endl;
std::cout << std::endl;

t.start();
std::cout << "capacity=" << vec1.capacity() << ",size=" << vec1.size() << std::endl;
vec1.insert(vec1.end(), vec2.begin(), vec2.end());			//insert end
std::cout << "vector 后插:" << t.stop() << "ms" << std::endl;
std::cout << "capacity=" << vec1.capacity() << ",size=" << vec1.size() << std::endl;
std::cout << std::endl;

t.start();
std::cout << "size=" << lst.size() << std::endl;
lst.insert(lst.begin(), vec2.begin(), vec2.end());//insert begin
std::cout << "list 前插:" << t.stop() << "ms" << std::endl;
std::cout << "size=" << lst.size() << std::endl;

在不同环境中的执行结果:

技巧:

  • 在大量插入操作处理,优选list,不用vector.
  • vector的插入操作,能准确扩容的话,应先扩好容。
  • vector尽量不做前插处理

五 std::vector::push_back和 std::vector::emplace_back

struct S
{
int i = 0;
char s[100000];		//为了效果更明显, 扩一下S的大小。
}
std::vector<S> vec;
fillVector_2(vec);
std::vector<S> vec1;
fillVector_2(vec1); //初始化vector

int count = vec.size();
int pushcount = 500000;
vec.reserve(count + pushcount);
vec1.reserve(count + pushcount); //先扩容

Time t;
t.start();
std::cout << "capacity=" << vec.capacity() << ",size=" << vec.size() << std::endl;
for (int i = 0;i < pushcount;i++)
{
		vec.emplace_back(i + count + 1, "12345"); //emplace_back 后插
}
std::cout << "emplace_back 后插:" << t.stop() << "ms" << std::endl;
std::cout << "capacity=" << vec.capacity() << ",size=" << vec.size() << std::endl;
std::cout << std::endl;

t.start();
std::cout << "capacity=" << vec1.capacity() << ",size=" << vec1.size() << std::endl;
for (int i = 0;i < pushcount;i++)
{
		vec1.push_back(S{ i + count + 1, "12345" });//push_back 后插
}
std::cout << "push_back 后插:" << t.stop() << "ms" << std::endl;
std::cout << "capacity=" << vec1.capacity() << ",size=" << vec1.size() << std::endl;

在不同环境中的执行结果:

vs2019中环境,release测试结果确实比debug慢,可能是release验证时电脑比较繁忙,后续再重测。

技巧:

构造函数比较耗时的结构,优选emplace_back().

加客服微信:qiushu0517,开通VIP下载权限!