C++常用方法和技巧——vector性能提升技巧

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

规律：每次扩容都是增加当前空间的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" });
	}
}

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

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

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

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

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

五 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验证时电脑比较繁忙，后续再重测。