C ++ устанавливает итератор, вызывающий ошибку. Выражение: карта / набор итераторов несовместимы

Question

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        set<int> list;
        vector<ll> vec;
        for (size_t i = 1; i <= n; i++) {
            list.insert(i);
        }
        bool more = true;
        while (more) {
            vec.clear();
            auto it = list.begin();
            if (list.size() == 1) {
                cout << "1 1" << endl;
                break;
            }
            vec.push_back(*it);
            ll num = *it;
            list.erase(it);
            int count = 1;
            auto itt = list.begin();
            bool y = false;
            for (itt; itt != list.end(); ) {   // ...(1)
                if (checkPrime(*itt)) {
                    vec.push_back(*itt);
                    num = *itt;
                    list.erase(itt);
                    count++;
                }
                else if (gcd(num, *itt) == 1) {
                    vec.push_back(*itt);
                    num = *itt;
                    list.erase(itt);
                    count++;
                }   
                else itt++;
            }
            if (count == 1) {
                cout << "2 1" << num << endl;
            }
            else {
                cout << count << " ";
                for (size_t i = 0; i < vec.size(); i++) {
                    cout << vec[i] << " ";
                }
                cout << endl;
            }
            if (list.size() == 1) more = false;
        }
    }
    return 0;
}

Эта программа пытается найти совпадающие числа в диапазоне. Но после каждой последней итерации в (1) это вызывает ошибку, утверждающую, что отладочное утверждение не удалось! Карта выражений / набор итераторов несовместимы. Почему это происходит? checkPrime и gcd являются функциями для проверки, является ли число простым или нет, и для поиска gcd из двух чисел соответственно.

Answer 1

Изменение контейнера во время его итерации не является тривиальной операцией. Когда вы стираете текущий итератор , он больше не является действительным итератором. Это создает несовместимую операцию после ее удаления:

list<int> l;
for (int i = 0; i < 10; i++) l.push_back(i);
for (auto it = l.begin(); it != l.end(); )
    l.erase(it);

После удаления текущего итератора:

1. текущий итератор становится недействительным
2. Место текущий занимает элемент следующий в списке (++).

Этот не вызывает ошибку:

list<int> l;
for (int i = 0; i < 10; i++) l.push_back(i);
for (auto it = l.begin(); it != l.end(); )
    l.erase(it++)

Обратите внимание, что вы не можете сделать это с вектором. Но с векторами вы можете сделать это:

    vector<int> v = {1,2,3,4,5,6,7,8,9,0};
    int current_position = 0;
    for (auto it = v.begin(); it != v.end(); it = v.begin() + current_position)
    {
        //some logic there in current position which can change
        v.erase(it);
    }

Еще более сложные вещи идут с картами и деревьями. Так вот, как вы должны стереть: list.erase (itt ++);

Кроме того, ваш код - небольшая ставка по сравнению с инженерным:

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        set<int> list;
        vector<ll> vec;
        for (size_t i = 1; i <= n; i++)  list.insert(i);
        bool more = true;

        if (list.size() == 1)
        {
            cout << "1 1" << endl;
            continue;
        }

        while (list.size() > 1)
        {
            vec.clear();
            auto it = list.begin();
            vec.push_back(*it);
            ll num = *it;
            list.erase(it);
            for (auto itt = list.begin(); itt != list.end(); )
            {
                if (checkPrime(*itt) || gcd(num, *itt) == 1)
                {
                    vec.push_back(*itt);
                    num = *itt;
                    list.erase(itt++);
                }
                else itt++;
            }
            if (vec.size() == 1)
                cout << "2 1" << num << endl;
            else
            {
                cout << vec.size() << " ";
                for (auto n : vec) cout << n << " ";
                cout << endl;
            }
        }
    }
    return 0;
}