如何写一个遍历C++容器的循环？

今天要分析的主题，是一个看起来再简单不过的事情：如何写一个关于容器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)。
优点：安全简洁。

4. 小结

综上，写一个map的循环时，特别时在写底层框架时，一个简单的for循环变的隐患无数。要根据需求，容器结构，容器的大小，性能要求决定合适的方式，比较安全的方式我暂时也就总结以上四种。最后，再考虑下其它容器的情况？list、vector、unorderd_map？

有更好方案的可以留言或邮件：397157852@qq.com。示例代码地址：https://github.com/david-pp/david/blob/master/clion/cpp/loop.cpp

PS. 我们项目，由于这个本质问题导致的宕机多如牛毛，故总结并分享给各位，望慎重。