[数据结构与算法]C++ STL vector list set map容器循环通过迭代器删除元素注意事项

? ? ? 先说说写这篇博客的原因吧，同事转部门了，把他手头的工作交接给了我。他以前维护的一个模块，会将外部输入的数据缓存起来分段处理，处理完了就会清除缓存数据，最近出现了一个bug，缓存数据一直不清除，反复处理同样的一批数据，导致该处理的数据得不到处理，引起业务的中断。经过仔细分析代码，发现其清理策略存在缺陷，我就将清理策略进行了调整，程序能够执行到一个清理函数，结果在清除过程中出现了崩溃，经过分析发现是用迭代器清除list容器中的元素后迭代器没有更新，下一次继续使用这个无效的迭代器进行操作，从而引发崩溃，汗颜啊，代码大致逻辑如下：

using request_tuple = std::tuple<long, int>;
std::list<request_tuple>    m_que;

void OperList() {
	for (int i = 0; i < 10; i++) {
		m_que.push_back(request_tuple(i, i));//(std::make_tuple(i, i));
	}

	std::ostringstream os;
	char sp = '\t';
	std::for_each(m_que.begin(), m_que.end(), [&os, sp](request_tuple item){
		os << std::get<0>(item) << ' ' << std::get<1>(item) << sp;
	});
	std::cout << os.str() << std::endl;
	
	auto iter = m_que.begin();
	for (; iter != m_que.end();) {
		if (0 == std::get<0>(*iter) % 2) {
			m_que.erase(iter);
		}
		else {
			iter++;
		}
	}
	os.clear();
	os.str("");
	std::for_each(m_que.begin(), m_que.end(), [&os, sp](request_tuple item){
		os << std::get<0>(item) << ' ' << std::get<1>(item) << sp;
	});
	std::cout << os.str() << std::endl;
}

出问题的代码是 m_que.erase(iter);，m_que是一个list容器，用迭代器删除容器中满足条件的元素，删除后iter已经变成无效，但是没有更新其值，下一次循环使用iter时引起了崩溃。

介于此，本人就讲常用的vector，list，set，map容器通过迭代器删除元素的正确用法予以总结。

目录

1. vector

2. list

3. set

4. map

关于C++容器，详细可参考：容器库 - C++中文 - API参考文档

1. vector

template<

? ??class?T,
? ??class?Allocator?=?std::allocator<T>

>?class?vector;

　? vector是表示可以改变大小的数组的序列容器。就像数组一样，vector使用连续存储空间存储元素，这意味着它们的元素也可以使用指向其元素的指针进行偏移来访问，并与数组一样高效。但与数组不同的是， vector的大小可以动态变化，并且是由容器自动处理的。与其他动态序列容器（deques，lists和forward_lists）相比，vector可以非常高效地访问其元素（就像数组一样）并且相对高效地从其末尾添加或删除元素。 对于涉及在末尾以外的位置插入或删除元素的操作，性能比其他序列容器要差，并且与lists和forward_lists相比具有更少的迭代器和引用一致性与其他动态序列容器（deques，lists和forward_lists）相比，vector可以非常高效地访问其元素（就像数组一样）并且相对高效地从其末尾添加或删除元素。 对于涉及在末尾以外的位置插入或删除元素的操作，性能比其他序列容器要差，并且与lists和forward_lists相比具有更少的迭代器和引用一致性。迭代器删除方法如下：

std::vector<int> vec;
auto iter = vec.begin();
iter = vec.erase(iter);

2. list

template<

? ??class?T,
? ??class?Allocator?=?std::allocator<T>

>?class?list;

? ? ? ?list是一种序列容器，它允许在序列中的任意位置进行常数时间的插入和删除操作，并可以在两个方向上进行迭代（遍历）。list容器是基于双链表实现的，可以将其包含的每个元素存储在不同且不相关的存储位置上。通过链接到前一个元素和后一个元素的每个元素的关联关系在链表内部保持顺序。迭代器删除方法如下：

std::list<int> li;
auto iter = li.begin();
// list方法一删除

iter = li.erase(iter);
// list方法二删除
li.erase(iter++);

3. set

template<

? ??class?Key,
? ??class?Compare?=?std::less<Key>,
? ??class?Allocator?=?std::allocator<Key>

>?class?set;

std::set 是关联容器，含有 Key 类型对象的已排序集。用比较函数 比较 (Compare) 进行排序。搜索、移除和插入拥有对数复杂度。 set 通常以红黑树实现。迭代器删除方法如下：

std::set<int> si;
auto iter = si.begin();
// set方法一删除
iter = si.erase(iter);

// set方法二删除
si.erase(iter++);

4. map

template<

? ??class?Key,
? ??class?T,
? ??class?Compare?=?std::less<Key>,
? ??class?Allocator?=?std::allocator<std::pair<const?Key, T>?>

>?class?map;

std::map 是有序键值对容器，它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。std::map 是有序键值对容器，它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。迭代器删除方法如下：

std::map<int, bool> mi;
auto iter = mi.begin();
// map方法一删除
iter = mi.erase(iter);

// map方法二删除
mi.erase(iter++);

完整代码如下：
?

// UseStl.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <sstream>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <tuple>
#include <algorithm>

using namespace std;

using request_tuple = std::tuple<long, int>;
std::list<request_tuple>    m_que;

void ErrorOperList() {
	for (int i = 0; i < 10; i++) {
		m_que.push_back(request_tuple(i, i));//(std::make_tuple(i, i));
	}

	std::ostringstream os;
	char sp = '\t';
	std::for_each(m_que.begin(), m_que.end(), [&os, sp](request_tuple item){
		os << std::get<0>(item) << ' ' << std::get<1>(item) << sp;
	});
	std::cout << os.str() << std::endl;
	
	auto iter = m_que.begin();
	for (; iter != m_que.end();) {
		if (0 == std::get<0>(*iter) % 2) {
			m_que.erase(iter);
		}
		else {
			iter++;
		}
	}
	os.clear();
	os.str("");
	std::for_each(m_que.begin(), m_que.end(), [&os, sp](request_tuple item){
		os << std::get<0>(item) << ' ' << std::get<1>(item) << sp;
	});
	std::cout << os.str() << std::endl;
}


void OperVector() {
	int arr[15] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 14, 13, 12, 11};
	std::vector<int> vec;
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
		vec.push_back(arr[i]);
	}
	std::for_each(vec.begin(), vec.end(), [](const int& num){
		std::cout << num << ' ';
	});
	std::cout << endl;

	auto iter = vec.begin();
	for (; iter != vec.end();) {
		if (0 == *iter % 2) {
			std::cout << *iter << std::endl;
			iter = vec.erase(iter);
		}
		else {
			iter++;
		}
	}
	std::for_each(vec.begin(), vec.end(), [](const int& num){
		std::cout << num << ' ';
	});
	std::cout << endl;
}

void OperList() {
	int arr[15] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 14, 13, 12, 11 };
	std::list<int> li;
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
		li.push_back(arr[i]);
	}
	std::for_each(li.begin(), li.end(), [](const int& num){
		std::cout << num << ' ';
	});
	std::cout << endl;

	bool erase_type = true;
	auto iter = li.begin();
	for (; iter != li.end();) {
		if (0 == *iter % 2) {
			if (erase_type) {
				std::cout << "erase_type true ::" << *iter << std::endl;
				// list方法一删除
				iter = li.erase(iter);
				erase_type = false;
			}
			else {
				std::cout << "erase_type false ::" << *iter << std::endl;
				// list方法二删除
				li.erase(iter++);
				erase_type = true;
			}
		}
		else {
			iter++;
		}
	}
	std::for_each(li.begin(), li.end(), [](const int& num){
		std::cout << num << ' ';
	});
	std::cout << endl;
}

void OperSet() {
	int arr[15] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 14, 13, 12, 11 };
	std::set<int> si;
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
		si.insert(arr[i]);
	}
	std::for_each(si.begin(), si.end(), [](const int& num){
		std::cout << num << ' ';
	});
	std::cout << endl;

	bool erase_type = true;
	auto iter = si.begin();
	for (; iter != si.end();) {
		if (0 == *iter % 2) {
			if (erase_type) {
				std::cout << "erase_type true ::" << *iter << std::endl;
				// set方法一删除
				iter = si.erase(iter);
				erase_type = false;
			}
			else {
				std::cout << "erase_type false ::" << *iter << std::endl;
				// set方法二删除
				si.erase(iter++);
				erase_type = true;
			}
		}
		else {
			iter++;
		}
	}
	std::for_each(si.begin(), si.end(), [](const int& num){
		std::cout << num << ' ';
	});
	std::cout << endl;
}

void OperMap() {
	int arr[15] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 14, 13, 12, 11 };
	std::map<int, bool> mi;
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
		mi.insert(std::pair<int, bool>(arr[i], true));
	}
	std::for_each(mi.begin(), mi.end(), [](const std::pair<int, bool>& item){
		std::cout << item.first << ' ';
	});
	std::cout << endl;

	bool erase_type = true;
	auto iter = mi.begin();
	for (; iter != mi.end();) {
		if (0 == iter->first % 2) {
			if (erase_type) {
				std::cout << "erase_type true ::" << iter->first << std::endl;
				// map方法一删除
				iter = mi.erase(iter);
				erase_type = false;
			}
			else {
				std::cout << "erase_type false ::" << iter->first << std::endl;
				// map方法二删除
				mi.erase(iter++);
				erase_type = true;
			}
		}
		else {
			iter++;
		}
	}

	std::for_each(mi.begin(), mi.end(), [](const std::pair<int, bool>& item){
		std::cout << item.first << ' ';
	});
	std::cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	std::cout << __cplusplus << std::endl;
	//std::cout << argc << " " << argv[0] << std::endl;
	std::cout << "迭代器删除vector中元素" << std::endl;
	OperVector();
	std::cout << "迭代器删除list中元素" << std::endl;
	OperList();
	std::cout << "迭代器删除set中元素" << std::endl;
	OperSet();
	std::cout << "迭代器删除map中元素" << std::endl;
	OperMap();

	return 0;
}

运行结果如下：

总结：通过以上可以看出vector，list，set，map容器均可以通过如下方式借助迭代器删除元素。

iter = container.erase(iter);