遍历set陷入死循环：两段相似C++代码为何表现迥异？

这个问题的核心在于你在遍历set的过程中插入新元素，而新元素的位置导致遍历被无限延长。我们来一步步拆解原因：

异常代码死循环的本质 #

先看你的异常代码逻辑：

int arr[5] = {3, 1, 3, 5, 6};
int main() {
    int T = 1;
    set<int> s;
    for (int tc = 0; tc < T; tc++) {
        s.emplace(0);
        for (auto x : arr) {
            auto end = s.end();
            for (auto it = s.begin(); it != end; it++) {
                s.emplace(*it+x); // 问题出在这里
            }
        }
    }
    return 0;
}

当你处理第一个x=3时，初始s={0}，end指向0的下一个位置（即set的末尾）。遍历it=0，插入0+3=3，此时s={0,3}。这一步没问题，遍历很快结束。

但处理第二个x=1时：

1. 你先保存了end = s.end()（此时指向3的下一个位置）
2. 开始遍历it从0出发：
   • 插入0+1=1，这个元素会被插入到0和3之间，此时s={0,1,3}
   • it++走到1，而it仍然不等于之前保存的end（因为end还是指向原来3的下一个位置，现在1在end之前）
   • 继续插入1+1=2，插入到1和3之间，s={0,1,2,3}
   • it++走到2，依旧不等于end，插入2+1=3（已存在，无变化）
   • it++走到3，还是不等于end，插入3+1=4，s变成{0,1,2,3,4}
   • 接下来it++走到4，仍然不等于end，插入5... 以此类推

因为你插入的*it+x都是大于当前*it的正数（arr里全是正数），这些新元素会被插入到当前it的后方，也就是在你之前保存的end之前的位置。遍历过程中it会不断遇到新插入的元素，永远无法到达最初保存的end，最终陷入死循环。

正常代码为什么能运行？ #

再看正常代码：

using namespace std;
int main() {
    int arr[5] = {3,1,3,5,6}, sum=20;
    set<int> s;
    s.emplace(sum);
    for (auto x : arr) {
        auto end = s.end();
        for (auto it = s.begin(); it != end; it++) {
            s.emplace(*it-x); // 这里是减法
        }
    }
    return 0;
}

这里你插入的是*it -x，x是正数，所以新元素小于当前*it，会被插入到当前it的前方（set是有序容器，小元素在左边）。

比如初始s={20}，处理x=3：

• 插入20-3=17，s={17,20}
• it从17走到20，此时it等于最初保存的end，遍历结束

后续处理其他x时，新插入的元素都在当前遍历的it的左侧，it是从左往右走，不会碰到这些新元素，所以遍历只会覆盖初始的set元素，不会无限延长，自然不会死循环。

修复异常代码的方案 #

要解决死循环，你需要在遍历前先把当前set的元素复制到一个临时容器中，然后遍历这个临时容器，再往原set插入新元素。这样就不会因为插入新元素而影响遍历范围：

int arr[5] = {3, 1, 3, 5, 6};
int main() {
    int T = 1;
    set<int> s;
    for (int tc = 0; tc < T; tc++) {
        s.emplace(0);
        for (auto x : arr) {
            // 先复制当前set的所有元素到临时vector
            vector<int> temp(s.begin(), s.end());
            // 遍历临时容器，插入新元素
            for (auto num : temp) {
                s.emplace(num + x);
            }
        }
    }
    // 此时s就是所有子集的和
    return 0;
}

这样，每次处理x时，你遍历的是处理x之前的set元素，不会被新插入的元素干扰，自然能正常生成所有子集的和。

内容的提问来源于stack exchange，提问作者fian Elf