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

Here is a C++11 version (using auto, lambdas and move semantics) that uses std::vector for an arbitrary value of type T:

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <vector>

template<std::size_t N, typename T>
std::vector<T> collapse_consecutive(std::vector<T> v, T const& value)
{
    if (v.size() <= N) return v;

    for (auto it = v.begin(); it != std::prev(v.end(), N); ++it) {
        if (*it == value) {
            // find first following mismatch
            auto jt = std::find_if(it, v.end(), [&](T const& elem) {               
               return elem != value;
            });
            // keep first N matches, remove rest of matches
            if (std::distance(std::next(it, N), jt) > 0)               
                v.erase(std::remove(std::next(it, N), jt, value), jt);
        }
    }
    std::for_each(v.begin(), v.end(), [](int const& elem) { std::cout << elem << ", "; });
    std::cout << "\n";
    return v;
}

int main()
{
   std::vector<int> v = {7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8};

  collapse_consecutive<0>(v, 0);
  collapse_consecutive<1>(v, 0);
  collapse_consecutive<2>(v, 0);
  collapse_consecutive<3>(v, 0);
  collapse_consecutive<4>(v, 0);
  collapse_consecutive<5>(v, 0);  
}

Output on LiveWorkSpace

stdout: 
7, 12, 2, 27, 10, 8, 
7, 0, 12, 0, 2, 0, 27, 10, 0, 8, 
7, 0, 12, 0, 0, 2, 0, 0, 27, 10, 0, 0, 8, 
7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 8, 
7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8, 
7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8, 

Answer 3

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.

Answer 4

Easiest way would be to return a std::vector<int> and use push_back so you don't have to worry about allocating the right size array.

template<typename Iter>
std::vector<int> filter_zeroes(Iter start, Iter end, const size_t num_zeroes)
{
    std::vector<int> output;
    size_t zero_count = 0;
    while (start != end)
    {
        if (*start != 0)
        {
            output.push_back(*start);
            zero_count = 0;
        }
        else if (zero_count < num_zeroes)
        {
            output.push_back(*start);
            ++zero_count;
        }
        ++start;
    }
}

You could make this method a lot more generic. Change int to typename ValueType and 0 to ValueType value_to_remove, and you're on the way to std::algorithm level of genericness...

Answer 5

You can do by passing a functor to list::remove_if. Example below.

#include <iostream>
#include <list>

std::list<int> origL{7, 0, 12, 0, 0, 2, 0, 0, 0, 27, 10, 0, 0, 0, 0, 8};

template <typename T>
struct remove_more_than_n_consecutive_zeros
{
    int n;
    int i;
    F(int n) : n(n), i(0) { }

    bool operator()(const T &element) {
        if (0 == element) {
            ++i;
            return i > n;
        }
        else 
        {
            i = 0;
            return false;
        }
    }
};

int main()
{
    for (int i = 0; i < 5; ++i) {
        std::list<int> L = origL;
        L.remove_if(remove_more_than_n_consecutive_zeros<int>(i));
        for (int x : L) { std::cout << x << " "; }
        std::cout << std::endl;
    }
}

Answer 6

It's essentially a state machine, so you could probably do something clever with std::regex, but here's a straightforward implementation.

void TrimConsecutiveValues(int value, int cKeep, std::list<int> &list) {
  int cSeen = 0;
  auto it = list.begin();
  while (it != list.end()) {
    if (*it == value) {
      if (cSeen < cKeep) {
        ++cSeen;
        ++it;
      } else {
        it = list.erase(it);
      }
    } else {
      cSeen = 0;
      ++it;
    }
  }
}