In C++, how can I delete all zeros except for x of them in every run of consecutive zeros within a list?

Question

For every run of x or more consecutive zeros in a list in C++, I would like to delete all zeros in the run except for x of them. If x = 0, then delete all zeros.

I was thinking of a C++ function that took a list, list<int> L, and a number, int x, as inputs.

For example, let L = {7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8}.

• If x = 0, then return L = {7, 12, 2, 27, 10, 8}
• If x = 1, then return L = {7, 0, 12, 0, 2, 0, 27, 10, 0, 8}
• If x = 2, then return L = {7, 0, 12, 0, 0, 2, 0, 0, 27, 10, 0, 0, 8}
• If x = 3, then return L = {7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 8}
• If x = 4, then return L = {7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8} (Same as original L)
• If x >= 5, then return original L as there are no runs of 5 or more consecutive zeros.

Several months ago, I asked the same question above using Python (stackoverflow.com/questions/11732554/...) and received excellent answers. Now I would like to complete this task in C++.

Any help would be sincerely appreciated.

Answer 1

Here's some code that should do the job:

void DeleteAllZerosInARow(std::list<int>& theList, int x)
{
    if(x == 0)
    {
        theList.remove(0);
        return;
    }

    int streak = 0;
    std::list<int>::iterator itor = theList.begin();
    while(itor != theList.end())
    {
        if(*itor == 0)
            ++streak;
        else
            streak = 0;

        if(streak > x)
            itor = theList.erase(itor);
        else
            ++itor;
    }
}

Basically, you count how many zeros you have in a row, and delete them if you're > x, otherwise continue iterating the list.

Giving the following output:

• 0 : 7,12,2,27,10,8
• 1 : 7,0,12,0,2,0,27,10,0,8
• 2 : 7,0,12,0,0,2,0,0,27,10,0,0,8
• 3 : 7,0,12,0,0,2,0,0,0,27,10,0,0,0,8
• 4 : 7,0,12,0,0,2,0,0,0,27,10,0,0,0,0,8
• 5 : 7,0,12,0,0,2,0,0,0,27,10,0,0,0,0,8

It depends on your style, remove_if might be the more C++ish way to do it, but I find it clearer to manipulate the values directly and it doesn't involve a new data type (a struct to keep track of the number of 0 you encountered).

The reason why the code doesn't work using NTL::ZZ is simply that there is no implicit conversion between an int, 0, and a NTL::ZZ big number, therefore it cannot remove(0). What you can do though could be something along the lines of:

if(x == 0)
{
    static ZZ zero; // default value is 0, static so that it is only constructed once
    theList.remove(zero); // remove all items who are equal to "zero"
    return;
}

Answer 2

For case 0 you can use std::remove, and for case 1 you can use std::unique with a predicate that only applies it to 0. For greater values, either devise a sneaky stateful predicate to use with unique or borrow its logic to apply to larger sequences.