不明确的运行时错误导致程序立即崩溃

Question

#include <bits/stdc++.h>

using namespace std;
int freq[101034];
int main() {

  int n;
  cin >> n;
  set<int> st;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    freq[x]++;
    st.insert(x);
  }
  while (!st.empty()) {
    for (auto x : st) {
      if (freq[x] <= 0) {
        st.erase(x);
        continue;
      }
      cout << x << ' ';
      freq[x]--;
    }
    cout << '\n';
  }
  return 0;
}

我试图解决的问题：给定一个 n 到 10^5 的整数数组，每个元素到 10^5，任务是打印没有排序的数组重复，然后删除打印的数组元素，然后重复直到数组为空。

例如数组 [1, 1, 2, 3, 4, 4] 这应该打印出来

1 2 3 4 
1 4

我维护了一个频率数组来保存每个元素频率，上面的代码导致运行时错误。程序崩溃。我试过去掉if语句，程序运行正常，但肯定会死循环！我真的想不通为什么 if 会导致运行时错误。

Answer 1

问题出在这段代码中：

while (!st.empty()) {
    for (auto x : st) {
      if (freq[x] <= 0) {
        st.erase(x);
        continue;
      }
      cout << x << ' ';
      freq[x]--;
    }
    cout << '\n';
}

基于范围的 for 循环在后面使用迭代器（有关详细信息，请参阅 this）。当你从 st 中删除 x 时，循环迭代器（指向 x）变得无效（这意味着你不能再使用它了），但在上面的代码片段中，它仍然得到在后台循环结束时递增，导致未定义的行为，因此出现运行时错误。

查看 this page 了解您应该如何正确实施它。将前面 link 的做法应用到您的代码中：

while (!st.empty()) {
    for (auto it = cbegin(st); it != cend(st);) {
        auto x = *it;
        if (freq[x] <= 0) {
            it = st.erase(it);
        } else {
            ++it;
            cout << x << ' ';
            freq[x]--;
        }
    }
    cout << '\n';
}

不明确的运行时错误导致程序立即崩溃

ambiguous runtime error causing the program to crash immediately

c++

crash

runtime