C++ check if any of the previous 5 or next 5 elements equal a value

Question

Is there an easy way to do this without a for loop or lots of ifs and elses.

So for example..

for (i=0;i<arr.size;i++) 
    if (any of the values from i-5 to i+5, ignoring i = value) 
    {
        // Do stuff ...
    }

Do I need set a nested loop from -5 to +5. Or can I used std::any_of perhaps

Answer 1

Despite on how the description may look, the complexity is linear since the inner loop (if any) iterates a constant number of times (and does not depend on the number of the data).

Since you suggest your data have an array form (contiguous and randomly indexable) and using nested loops is in fact the easyest and most straightorward way to benefit of all optimization capabilities and processor caching. Whatever "dynamically sorted" container sill perform poorly, due to the distributed nature of the data.

I will most likely do

for(size_t i=5; i<N-5-1; ++i)
{
    int good=0; //will count the successful comparisons
    for(size_t j=i-5; j<=i+5; ++j) 
    {
        if(i==j) continue; //skip the i on i case
        if(array[j]==value) ++good;
    }
    if(good==10) do_stuff(i);
}

The inner loop executes entirely on cached data (and does not depend on N, so it does not contribute in the complexity). With nowadays CPU works probably faster tan trying to sort somehow the data in set-like container (with non contiguous storage).

Despite on the elegance of many begin/end approach, the old KISS indexing wins.

You can parametrize the array[j]==value predicate as well as the 5 (and 10 == 2*5) with no cost (a template function will be inlined), making this even more general.

if you don't want to branch the inner loop, you can even make it faster with

for(size_t i=5; i<N-5-1; ++i)
{
    int good=0; //will count the successful comparisons
    for(size_t j=i-5; j<i; ++j) good+=(array[j]==value);
    for(size_t j=i+1; j<=i+5; ++j) good+=(array[j]==value);
    if(good==10) do_stuff(i);
}

Where the 11 elements loop is split in two halves (avoiding to check for j==i) and the increment on good is "computed" functionally, with no branches. This will also lead to faster execution on predictive piping processors.

---

EDIT

Looks like I misunderstood that only one equal value is enough (not all).

If that's the case, you can check for good!=0, but you can even short-cut:

for(size_t i=5; i<N-5-1; ++i)
{
    bool good=false; //will count the successful comparisons
    for(size_t j=i-5; j<i && !good; ++j) good|=(array[j]==value);
    for(size_t j=i+1; j<=i+5  && !good; ++j) good|=(array[j]==value);
    if(good) do_stuff(i);
}

This will break the loops as soon a match is found, but makes the loop no more unrollable. Removing && !good will not cut off the loops, but may be running them till the end is faster than checking to cut or not.

If you shortcut cut the loops, you can use = instead of |=, if you don't shortcut, using a bool has no advantage: |= by a compiler stand point is more complicated than +=

Answer 2

In terms of readability, I prefer the doubled for loops.

In terms of performance, I would use the following which runs the minimal n+5 iterations (for scope = 5) without additional data structures.
All in all O(n) complexity and O(1) memory.

void checkArray(int arr[], int n, int value) {
    const int scope = 5;

    int closestBeforeI = -1;
    int closestAfterI = -1;

    for (int i = 0; i < scope && i < n; ++i) {
        if (arr[i] == value) {
            closestAfterI = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (closestAfterI == i) {   // exclude self index
            closestAfterI = -1;
        }
        if (closestAfterI == -1 && i + scope < n // closest after not set & i + scope is within range
                && arr[i + scope] == value) {
            closestAfterI = i + scope;
        }

        if (closestBeforeI != -1 && closestBeforeI + scope >= i
                || closestAfterI != -1) {
            do_stuff(i);
        }

        if (arr[i] == value) {
            closestBeforeI = i;
        }
    }
}

worked fine for this main:

int main()
{
    const int n = 14;
    int arr[] = {1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2};
    int value = 2;
    // should be true for indices: 0, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12

    checkArray(arr, n, value);

    return 0;
}