[SOLVED] Get all blocks of contiguous same numbers for an array

I want to show a solution using C++ language elements.

Everything that I saw here is (except the usage of std::cout) pure C-code. And that is a pity, because C++ is much more powerful and has a lot of "of-the-shell" usable algorithms.

So, as a first note. You should not use C-Style arrays in C++. There can be no argument, to not use a std::array instead. Or, for use cases with dynamic memory management, a std::vector. Using a std::vector is nearly always the better solution.

Anyway. C++ will also still work with C-Style arrays. In my example below, I made heavy use of C++ functionality and can still work with C-Style arrays. Because of this programming style, I can exchange the C-Style array with modern C++ STL containers later, and, the program will still run.

But let us first see the code, which I will explain later.

#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>

// Test data
int arr[] = { 2, 3, -1, -1, -1, 4, -1, -1 };
unsigned int result[(sizeof(arr) / sizeof(arr[0]))/2];

// A predicate function that checks for 2 elements to be -1
bool twoMinusOnes(const int i, const int j) {
    return i == -1 && j == -1;
}

// Test program
int main() {

    // Here we count, how many contiguos blocks of -1 are available
    unsigned int blockCounter = 0;

    // Some iterator to the begin and end of a -1 block in a source data
    decltype(std::begin(arr)) beginOfBlock{};
    decltype(std::begin(arr)) endOfBlock{};

    // Find all blocks with contiguos -1 in a simple for loop
    for (   beginOfBlock = std::adjacent_find(std::begin(arr), std::end(arr), twoMinusOnes); // Initial value. Start searching from beginning
            beginOfBlock != std::end(arr);                                                   // Check end condition 
            beginOfBlock = std::adjacent_find(endOfBlock, std::end(arr), twoMinusOnes)) {    // find next block

        // Ok. std::adjacent_found a block with at lease 2 repeating -1 for us
        // Now, find the position, where this block ends
        endOfBlock = std::adjacent_find(beginOfBlock, std::end(arr), std::not_equal_to<int>());

        // Set iterator to past the end of the contiguous -1 block (if we are not at the end)
        if (endOfBlock != std::end(arr)) std::advance(endOfBlock, 1);

        // Store number of elements in this block
        result[blockCounter++] = std::distance(beginOfBlock, endOfBlock);
    }

    // Show result to user. Number of blocks and number of elements in each block
    for (unsigned int i{}; i < blockCounter; ++i)
        std::cout << "Block " << i + 1 << " has " << result[i] << " elements\n";

    return 0;
}

OK, what are we doing here?

First, we define an array with the source data that shall be examined. Second, we also define a "result" array, with a fixed maximum size, equal to half the number of elements of the first array. This, because the there cannot be more consecutive -1 blocks.

Ok, then we define a so called predicate function, which simply checks if both given elements are -1. That is what we are looking for in our source array. The predicate function can then later be used in C++ standard algorithms.

In main, we initialize a blockCounter which will show us the number of contiguous -1 blocks found.

Then we see:

decltype(std::begin(arr)) beginOfBlock{};
decltype(std::begin(arr)) endOfBlock{};

This will define an iterator, regardless of the used C++ STL container. For our int[] array, it will be a int* (So, we could have also written int *beginOfBlock;.

This is a very flexible approach and will allow us the use different containers later.

Next we start a for loop, to find all blocks of contiguous -1s.

For this we use a dedicated function that has been designed to find adjacent elements with a certain property: std::adjacent:find. Please see here for the reference description. Standard is to find equal elements. But we use our predicate function to find 2 consecutive -1s.

So, the init statement of the for-loop, looks for such a block, starting from the beginning of the container. The "condition" of the for, checks, if a block could be found or not.

And the "iteration_expression" looks for the next block, after the first block has been evealuated.

This is a normal for loop and rather straight forward.

In the loop body, we have only 3 statements:

Search for the end of the current found -1 block
Because the function will return the first element of a pair, it will point to the last -1 of the found block. We will increment the position to point to the next element after the found -1 block (but only, if we are not yet at the end of the array)
We store the resulting number of elements in one block

That is all. Very simple and compact code.

At the end we show the gathered results on the console.

That is basically it. Only a few statements needed, because of the reuse of existing functions from the standard C++ library.

And to show you, how versatile such a function is, you can include the header vector and then replace your C-Style arrays simply by:

// Test data
std::vector arr{ 2, 3, -1, -1, -1, 4, -1, -1 };
std::vector<size_t> result(arr.size()/2);

And the program will work as before.

I would strongly recommend to you to start using C++ language elements, if you want to learn C++

In case of questions, please ask.