Performing recursion on a list C++

Question

I am trying to determine the maximum number of items I can remove from a list using std list to get the minimum size. However, it keeps ending up in bad memory access.

This is my recursive function:

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

It managed to get down to the desired size but the program would crash due to bad memory access.

The `std::list::erase` member function invalidates iterators. That seems to be the problem. — Ron, Feb 01 '18 at 13:13
@Wilson no, but it also returns the next iterator fromw which you should continue after erasing. — Quentin, Feb 01 '18 at 13:16
There's even an example [here](http://en.cppreference.com/w/cpp/container/list/erase) — Useless, Feb 01 '18 at 13:17

Jarod42 · Accepted Answer · 2018-02-01T13:35:25.787

6

Once you do mylist.erase(i);, i is invalided, so your ++i in the loop is UB.

Your code should look like:

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

In addition, final check should handle correctly when you remove last elements.

edited Feb 01 '18 at 13:35

answered Feb 01 '18 at 13:15

Jarod42

203,559
14
181
302

@UKMonkey: you increment `i` when you don't erase item (`else` branch). when you erase item (true branch), you retrieve next element (look at `i = mylist.erase(i);`) – Jarod42 Feb 01 '18 at 13:22
Yeah - I missed the fact that you're now expecting a `break` in the `remaining code` – UKMonkey Feb 01 '18 at 13:28
@UKMonkey: I added full loop content. I don't expect a `break` (possibly a `continue` if last else block become regular block. – Jarod42 Feb 01 '18 at 13:38
Thanks that worked! – lws803 Feb 01 '18 at 14:01

Performing recursion on a list C++

1 Answers1