c++ - C++ 设置迭代器导致错误。表达式：map/set 迭代器不兼容

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 的函数。

标签： c++set

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