неоднозначная ошибка времени выполнения, приводящая к немедленному взлому программы sh - PullRequest
Новая
       6

неоднозначная ошибка времени выполнения, приводящая к немедленному взлому программы sh

0 голосов
/ 14 января 2020 
#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, программа работает нормально, но точно достигает бесконечного l oop! Я действительно не могу понять, почему if вызывает ошибку во время выполнения.

1 Ответ

1 голос
/ 14 января 2020

Проблема в следующем фрагменте: 

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

На основе диапазона для l oop используются итераторы в конце (см. this для получения дополнительной информации). Когда вы удаляете x из st, итератор l oop (указывающий на x) становится недействительным (это означает, что вы больше не должны его использовать), но в приведенном выше фрагменте он все равно увеличивается на конец l oop в фоновом режиме, что приводит к неопределенному поведению, отсюда и ошибка времени выполнения.

Взгляните на эту страницу , чтобы увидеть, как ее правильно реализовать. Применяя практику предыдущей ссылки к вашему коду: 

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';
}
...