C++ Vector数组优化

OrzMiku / 2023-08-20 / 原文

Vector数组优化

问题

这是一段没有优化的代码：

#include<iostream>
#include<vector>

class Entity {
public:
	int x, y;
public:
	Entity(int x, int y) 
	:x(x),y(y){}

	Entity(const Entity& e) 
	:x(e.x),y(e.y){
		std::cout << "Copied!" << std::endl;
	}
};

int main(int argc, char* argv[]) {
	std::vector<Entity> e;
	e.push_back(Entity(1,2));
	e.push_back(Entity(3,4));
	e.push_back(Entity(5,6));
}

这段代码最终输出了六个Copied。

// 将在main函数中创建的Entity对象copy到vector中
Copied!
// vector内存不够用了，增长，把原来内存中的Entity对象copy到新的vector中，再把新的Entity对象copy到vector中，就有了两个copy
Copied!
Copied!
// vector内存不够用了，增长，把原来内存中的Entity对象copy到新的vector中，再把新的Entity对象copy到vector中，就有了三个copy
Copied!
Copied!
Copied!

可见，效率很低。下面是优化方法（两个方法一起用）：

方法一

通过上面的分析可以得到，造成重复copy的原因是因为vector存不下了，要变长。如果一开始就指定vector的长度，就可以避免这个问题。

使用reserve方法来规定vector的长度：

#include<iostream>
#include<vector>

class Entity {
public:
	int x, y;
public:
	Entity(int x, int y) 
	:x(x),y(y){}

	Entity(const Entity& e) 
	:x(e.x),y(e.y){
		std::cout << "Copied!" << std::endl;
	}
};

int main(int argc, char* argv[]) {
	std::vector<Entity> e;
	e.reserve(10); // 规定可以放十个Entity
	e.push_back(Entity(1,2));
	e.push_back(Entity(3,4));
	e.push_back(Entity(5,6));
}

此时输出就只剩下三个Copied了。此时加上方法二，可以把这三个也优化掉：

方法二

剩下这三次复制，是因为要把main函数中创建的Entity对象copy到vector中。

可以使用emplace_back方法代替push_back方法，这样就不是在main函数中创建的Entity对象copy到vector中了。

#include<iostream>
#include<vector>

class Entity {
public:
	int x, y;
public:
	Entity(int x, int y) 
	:x(x),y(y){}

	Entity(const Entity& e) 
	:x(e.x),y(e.y){
		std::cout << "Copied!" << std::endl;
	}
};

int main(int argc, char* argv[]) {
	std::vector<Entity> e;
	e.reserve(10);
	e.emplace_back(1,2);
	e.emplace_back(3,4);
	e.emplace_back(5,6);
}

运行结果：什么都没有，省去了全部的复制。（当然，方法一有点牺牲空间换时间的意思，不过需要多少空间是大概可以估计的，可以把损失最小化）