今天要分析的主题,是一个看起来再简单不过的事情:如何写一个关于容器std::map的循环?这谁不会啊,懂点C++和STL不就手到擒来嘛,但是这个写不好的循环曾宕机无数(至少在我所在项目是这样)。
0.初印象
假设有数据结构Item及其容器对象items:
struct Item { uint32_t id; std::string name; uint32_t data[1024]; };std::map<uint32_t, Item> items = { {1, {1, "David1"}}, {6, {6, "David6"}}, {8, {8, "David8"}}, {11, {11, "David11"}}, {13, {13, "David13"}}, {15, {15, "David15"}}, {17, {17, "David17"}}, {22, {22, "David22"}}, {25, {25, "David25"}}, {27, {27, "David27"}}, };
写一个清理掉键值为偶数的元素的循环,这还不是小菜一碟嘛,来上代码:
for (auto it = items.begin(); it != items.end(); ++it) { if (it->first % 2 == 0) items.erase(it); }
很不幸,宕掉了!还记得C++标准库手册和Effective STL怎么教导我们吗?在遍历map容器时,erase会使得当前迭代器失效,从而++it时就会有异常,宕机还是死循环就听天由命了! 正确的写法应该是:
1> C++11标准之前:先把当前的it值传递到erase,然后it指向下一个元素,最后erase清掉之前传递的迭代器指向的元素。
for (auto it = items.begin(); it != items.end();) { if (it->first % 2 == 0) items.erase(it++); else it++; }
2> C++11标准之后:为了和其它容器erase形式保持一致,erase的返回指向下一个元素的迭代器。
for (auto it = items.begin(); it != items.end();) { if (it->first % 2 == 0) it = items.erase(it); else it++; }
好了,好了!收工了,只要记住遍历map时,如果要删除元素就按上面形式写不就没事嘛!这么简单的代码,都能宕机,简直是一群呆瓜!
客官,稍等,好戏才刚开始上演,不妨继续听我分析!
2. 遍历容器时对当前容器都可以进行哪些操作?
首先来看下,STL中的map是用红黑树实现的,上面items对象的数据结构大概就张这个样子:
红黑树
我们想一下,在遍历一个map的循环体中都可以干什么?再往深了说,就是在遍历这个红黑树时,对当前这个树都能进行哪些操作?我把它归位下面几个操作:
读写:读和写当前正在遍历的元素。
添加:添加一个元素,可能位于正着遍历的元素之前或之后。
删除:删除正在遍历的元素、之前的元素、之后的元素。
清空:遍历时把自己给清空了。
这些操作的结果会是怎样?
1> 读写操作。对此不多说,极大多数遍历的目的就是此,代码极易理解。如:
for (auto it = items.begin(); it != items.end(); ++it) { it->second.name += ".Wang"; // 修改名字 std::cout << it->second.id << " - " << it->second.name << std::endl; // 输出}
2> 添加操作。添加在当前元素之后的,后面会循环到;添加在当前元素之前的,后面是循环不到的。
for (auto it = items.begin(); it != items.end(); ++it) { if (it->first == 8) { // 当前节点之后添加 items[9].name = "David9"; items[9].id = 9; // 当前节点之前添加 items[7].name = "David7"; items[7].id = 7; } // 节点7的的信息是不会被输出 // 节点9的信息会输出 std::cout << "loop: " << it->first << "-" << it->second.name << std::endl; }
3> 删除操作。删除操作最易出错,当以读写操作式的循环写时,删掉当前元素就会有异常,删掉之前或之后的都没什么问题,删掉之后的后续的遍历当然不会循环到。
for (auto it = items.begin(); it != items.end(); ++it) { if (it->first == 8) { items.erase(6); // OK items.erase(11);// OK items.erase(8); // 宕机:删除了当前元素,迭代器失效 } }
4> 清空操作。清空操作可以看作是一种特殊的删除,当然包含了删除当前元素,所以下面形式的循环必定会有异常。
for (auto it = items.begin(); it != items.end(); ++it) { if (it->first == 8) { items.clear(); // 宕机:直接清空时也删除了当前元素 } }
综上示例,可以得出下面的结论:
在遍历map容器时,循环体里面执行的代码,对当然的容器进行读写和添加都没什么问题,删除时要谨慎,避免清空!
2. 藏比较深的隐患
上面的结论都记住了,能保证不出错吗?上面的代码片段都比较短小,很容易识别宕机隐患,但是设想一下一个底层框架,对map进行循环,循环体里面执行某种回调,这种回调完全就是由上层应用程序同学编写,随意嵌好几层函数,不小心动到底层正着遍历的容器(删除某个元素、清空整个容器),这样的循环代码就是一颗定时炸弹。运气好些,逻辑错误,运气差些,宕机死循环来招呼你。
假设要你封装一个对items的foreach,你会怎么做?
1> 最直接最基础的方法。隐患:回调删除当前遍历的元素就会异常。
void foreach_items(const std::function<void(Item &)> &cb) { for (auto it = items.begin(); it != items.end(); ++it) { cb(it->second); } }
有隐患的代码:
foreach_items([](Item &item) { if (item.id == 8) { items.erase(8); // 删掉当前的 } });
2> 听了Effective STL忠告的同学,可能会这样写:
void foreach_items(const std::function<void(Item &)> &cb) { for (auto it = items.begin(); it != items.end();) { auto tmp = it++; cb(tmp->second); } }
高枕无忧吗?再看下下面有隐患的代码:
foreach_crash2([](const Item &item) { if (item.id == 8) { items.erase(11); // 删掉下一个 } });
8紧接着后面是11,为了防止it迭代器失效,在遍历前已经进行了it++。但是也保不准回调里面哪位踩雷的同学,删掉紧接着的元素,这也使得上层循环里面的it++也失效,再次异常!!
不好意思,让你烧脑了,这种情况一般隐藏的比较深,上层逻辑只要不删到下一个元素就没事。遍历一个map时删除map元素就像你在做一件事情时,老是有人捅刀子的感觉一样。
3.安全的遍历
继续思考,如何封装一个对items的foreach并保证没隐患?这也不行,那也不行,你妹的C++就是这么坑人?试问:没有垃圾回收的任何一种语言,在遍历一个容器时候删除当前容器的内容,合适吗?安全吗?我觉得这个锅C++不背。废话少说,既然选择了C++,继续想辙吧!
1> 上面第一种方法,最基础的。这种是最高效,复杂度O(n)。在循环体中不删除当前容器的任意一个元素,能保证这条铁律,那就不会有问题。当然,人为遵守约定是最不靠谱的事情,一般不同的框架有不同的方法,大概的思路都是要删除时打个标记,真正的删除延后处理,使用时判定一下当前元素是否有效即可。有点像自己实现一套垃圾回收的机制。
一个简单的示范(没有设标记,只是延后删除):
std::set<uint32_t> deleted;for (auto it = items.begin(); it != items.end(); ++it) { if (it->first % 2 == 0) deleted.insert(it->first); }for (auto key: delted) items.erase(key);
2> 使用当前容器的拷贝进行遍历。
void foreach_item(const std::function<void(Item &)> &cb) { std::map<uint32_t, Item> copy = items; for (auto it = copy.begin(); it != copy.end(); ++it) { cb(it->second); } }
优点:
可以安全遍历,回调立马想干啥干啥。
缺点:
容器内容较多时,一个COPY的代价也不低。
回调修改it->second时,会导致逻辑错误,原始的items中的元素并没有发生变化。除非it->second是一个对象的指针。
上一个回调对原始容器的操作,反应不到下一个回到执行时。比如对元素6的回调是删除items里面的8,但是由于做了一个临时拷贝,结果元素8照样执行,按理来说,6之前删掉了8,8后续就不能被执行。PS.往往回调依赖设计成这样的是非常不合理的,尽量避免。
3> 复制一份键直集合,然后使用键值集合进行遍历。上面的几个缺点得以改进:
仅COPY键值
修改内容也会立即有效
回调依赖也不受影响
void foreach_item(const std::function<void(Item &)> &cb) { std::set<uint32_t> keys; for (auto &it : items) keys.insert(it.first); for (auto key : keys) { auto it = items.find(key); if (it != items.end()) cb(it->second); } }
缺点:复杂度变为O(n*logn),同时还多了一份键值拷贝。
4> 每次循环时根据键值找下一个元素的迭代器。之前不是说过循环体里面,出错的老是在下一个迭代器吗 ,那我们是否可以记下键值,执行完回调,再利用键值找到下一个元素的迭代器即可。正向循环使用upper_bound,逆向循环使用lower_bound。
void foreach_item(const std::function<void(Item &)> &cb) { for (auto it = items.begin(); it != items.end();) { uint32_t key = it->first; cb(it->second); it = items.upper_bound(key); } }
缺点:复杂度变为O(n*logn)。
优点:安全简洁。
作者:davidpp
链接:https://www.jianshu.com/p/0b6eda9e4278
共同學習,寫下你的評論
評論加載中...
作者其他優質文章