在列表C++上执行递归

Question

我试图确定我可以使用标准列表从列表中删除的最大项目数,以获得最小大小.但是,它最终会导致内存访问不良.

这是我的递归函数:

int step (list<int> mylist) {
    int count = mylist.size();
    // Terminations
    if (!checkRemaining(mylist)) {
        return mylist.size();
    }
    if (mylist.empty()) {
        return 0;
    }
    //printf("mysize: %d\n", mylist.size());

    // Else we do not terminate first
    for (auto i=mylist.begin(); i != prev(mylist.end()); ++i)
    {
        if ((*i + *next(i))%2 == 0) // Problem starts from here, bad access
        {
            mylist.erase(next(i));
            mylist.erase(i);
            printf("this size %lu\n", mylist.size());

            list<int> tempList = mylist;
            for (auto it = tempList.begin(); it != tempList.end(); it++) {
                printf("%d ", *it);
            }
            printf("\n");

            int temp = step (tempList);
            if (temp < count) count = temp;
        }
    }

    return count;
}

它设法达到了所需的大小,但由于内存访问不良,程序会崩溃.

Answer 1

一旦你这样做mylist.erase(i);,i就会失效,所以你++i的循环就是UB.

您的代码应如下所示:

for (auto i = mylist.begin(); i != mylist.end() && i != prev(mylist.end()); /* Empty */)
{
    if ((*i + *next(i)) % 2 == 0)
    {
        mylist.erase(next(i));
        i = mylist.erase(i);
        // maybe you want prev(i) if i != mylist.begin()

#ifdef DEBUG
        std::cout << "this size " << mylist.size() << "\n";
        for (const auto& e : myList) {
            std::cout << e << " ";
        }
        std::cout << "\n";
#endif
        count = std::min(count, step(myList));
    } else {
        ++i;
    }
}

此外,删除最后一个元素时,应正确处理最终检查.