How to merge/count adjacent 1's within an std:array using std?

Question

Let say I've an std:array<int> such as:

0 1 1 1 0 1 1 0

I'd like to use std (if possible) to do this in c++11:

• sum adjacent 1's
• erase the summed value
• transform 0 to 1

So getting this result for the example above:

1 3 1 2 1

Thanks

Answer 1

You could apply this logic with a single pass through the input values, while creating the result vector:

• If the current value is a 1, and also the previous value was a 1, then increment the last value that was already added to the result vector, which is a counter for adjacent 1-bits
• In all other cases, append a new entry to the result vector, which is the same as the current value, except that a 0 becomes 1. If we were reading a 0, then this is what we want, and if we were reading a 1, then this is the initial value of a counter that might get incremented in the next iterations. Anything else, like -1, is copied as-is.

As to std::array: as this is a fixed size data type, and the size of the result is unknown beforehand, I would use vectors instead. But I added the code to convert the array to a vector. If your requirements don't insist on array, you could of course have your input represented by a std::vector from the very start:

#include <iostream>
#include <array>
#include <vector>

std::vector<int> convert(std::vector<int> bin) {
    std::vector<int> v;
    bool prevWasOne = false;
    for (auto bit : bin) {
        if (bit == 1 && prevWasOne) { // Adjacent 1s?
            v.back()++;
        } else {
            v.push_back(bit ? bit : 1); // 0? Then 1, else copy value
        }
        prevWasOne = bit == 1;
    }
    return v;
}

// Example run:
int main() {
    std::array<int, 8> arr = {0, 1, 1, 1, 0, 1, 1, 0};
    // Convert array to vector
    std::vector<int> vec(std::begin(arr), std::end(arr));
    // Apply conversion
    std::vector<int> result = convert(vec);
    // Output the result
    for (auto val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}