vector的erase竞品：erase_if

最近在做项目的时候经常需要遍历一遍vector容器然后删除其中一些元素，但vector的删除时间复杂度是o(n)。原则上是用list会更好但我后续还需要下标访问的功能所以只能硬着头皮用vector.erase,但今天在翻看c++20新版本的一些特性的时候发现这个erase_if,使用简单而且速度超快,但具体不知道怎么实现的。

erase和erase_if

erase的用法大家应该都清楚的，我这边就随便写一段例程：下面展示一些 内联代码片。

// erase
vector<int> vec1(300000);
for (int i = 0; i < vec1.size();i++) {
	vec1[i] = i;
}

for (auto it = vec1.begin(); it != vec1.end();) {
	if ((*it) % 10 == 0) {
		it = vec1.erase(it);
	}
	else {
		it++;
	}
}

erase_if的接口很简单，就是一个容器和一个函数对象，具体可以去cppreference上查一下。

// erase
vector<int> vec1(300000);
for (int i = 0; i < vec1.size();i++) {
	vec1[i] = i;
}

erase_if(vec1, [](int n) {
	return n % 10 == 0;
});

我自己电脑上出来的结果出来的结果大概是erase_if比erase快1000多倍···这个可能有点夸张了，我在公司试出来的结果差不多也就几十倍，但确实能证明这个函数很好用，很高效。

在发现这个函数之前，我还有一种自己整出来的方法，比较麻烦但是比vector的erase还是要快一些的。

// erase
vector<int> vec1(300000);
for (int i = 0; i < vec1.size();i++) {
	vec1[i] = i;
}

int ii = 0;
for (int i = 0; i < vec1.size(); i++) {
	if (i % 10 != 0) {
		vec1[ii++] = vec1[i];
	}
}
vec1.resize(ii);

这个方法就是直接在原来vector的基础上做赋值操作，避开了插入删除的o(n)操作，让速度变得很快，最后用resize整一下size，就搞定了。

int main() {
	
	vector<int> vec1(300000);
	for (int i = 0; i < vec1.size();i++) {
		vec1[i] = i;
	}

	int ii = 0;
	for (int i = 0; i < vec1.size(); i++) {
		if (i % 10 != 0) {
			vec1[ii++] = vec1[i];
		}
	}
	vec1.resize(ii);


	for (auto it = vec1.begin(); it != vec1.end();) {
		if ((*it)%10==0) {
			it = vec1.erase(it);
		}
		else {
			it++;
		}
	}

	erase_if(vec1, [](int n) {
		return n % 10 == 0;
	});


	cout << endl;
	return 0;
}