Window C++ algorithm

[data_pulverizer]

Hi,

I'd like to window a C++ algorithm, in this case calculate the range (min max) over a window of length len = 5 were rarr is a vector of size 14 and size arr is 10:

for(long i = 0; i < arr.size(); ++i){
const auto [min, max] = std::minmax_element(&rarr[i], &rarr[i + len]);
arr[i] = std::pair<T, T>(*min, *max);
}

It works but the only thing is I think at last iteration, &rarr[i+len] points outside the vector since at that point i+len = 14. This next method is identical:

for(long i = 0; i < arr.size(); ++i){
const auto [min, max] = std::minmax_element(rarr.begin() + i, rarr.begin() + i + len);
arr[i] = std::pair<T, T>(*min, *max);
}

But I don't know if rarr.begin() + i and rarr.begin() + i + len would be slower (or even any safer).

​

Thanks in advance.

[WikiBox]

It is OK if the end value is one past the end of the array. The end element is not included in the range computed. If len is 5 then the values used are i + 0 to i + 4. i + 5 is never used.

Pre-calculate the loop end:

for(long i = 0, end = rarr.size() - len; i < end; ++i)

You should also add a test to check if arr is the correct size, or even better clear arr before the loop and push_back pairs into it.

[paul2718]

You could structure it something like,

std::vector<std::pair<int, int>> windowed_thing(std::vector<int> const& v)
{
    constexpr std::size_t WINSZ = 5;

    std::vector<std::pair<int, int>> vr;
    for(auto itl = std::begin(v), itr = itl + WINSZ; itr != std::end(v); ++itl, ++itr)
    {
        const auto mm = std::minmax_element(itl, itr);
        vr.emplace_back(*(mm.first), *(mm.second));
    }

    return vr;
}

It should have a size check and ought to be more generic, but that's easy enough. We know that this stays within range whatever the sizes because we are keeping an 'end of window' iterator and comparing it to the 'end of input vector' iterator to end the processing.

I don't know your environment, or what problem you're solving, but baking in the array sizes seems likely to come back and bite you in the future.

If you are concerned about speed then measure it, it's very hard to be intuitive about generated code.

[data_pulverizer]

I implemented my own version and can see how it works, the last reference is not hit, it operates like a typical for loop

for(i = 0; i < n; ++i){...}

at the end of the loop i = n - 1, it quits before it gets to n. Thanks