CODEWITHSUNDEEP
c++
Ambarish Sridharanarayanan
Ambarish Sridharanarayanan

Reputation: 699

C++ algorithm for sliding window on container

I found myself writing a hand-crafted while-loop today like so:

std::list<T> foo; // In my case, map, but list is simpler
auto currentPoint = std::begin(foo);
while (true) {
    // Let's say the container has > 0 elements
    auto nextPoint = std::next(currentPoint);
    if (nextPoint == std::end(foo))
        break;

    // Do stuff with *currentPoint and *nextPoint
    currentPoint = nextPoint;
}

Following Sean Parent's advice (no raw loops), I tried to replace that while-loop with a standard algorithm and a nice lambda, but I couldn't find a suitable algorithm that would iterate through the map on a sliding window (2-elements at a time). A simple for_each with next doesn't work, as for_each passes a reference to the element to the lambda, and I can't call next on it.

std::for_each(
    std::begin(skylineMap),
    // Let's say the container has > 0 elements
    std::prev(std::end(skylineMap)),
    [&](const typename decltype(skylineMap)::value_type &currentPoint) {
        auto nextPoint = ???; // next(currentPoint) wouldn't work, of course
        // Do stuff with currentPoint and nextPoint
    }
);

EDIT: Remove example of operation I wanted to do; the example seemed to confuse more than clarify.

Upvotes: 2

Views: 4016

Answers (1)

Ben Voigt
Ben Voigt

Reputation: 283664

There are several options for doing this with pre-existing functions.

One is to use a zip-type function, such as the std::transform overload with 5 arguments, and two ranges: [c.begin() + 1, c.end()) and [c.begin(), c.end() - 1). Or for_each with boost::zip_iterator. This is mostly only useful for windows of size 2.

Another is to use for_each with boost::counting_iterator, so that your callback actually receives an iterator that it can advance to access adjacent elements. This would be useful when your callback knows the size of the range it wants to use.

You can also combine them, using boost::zip_iterator on boost::counting_iterator to pass a [begin, end) pair of iterators to the callback. That's useful because it lets the caller determine the window size.

For a one-off, I would just write the for-loop.

And finally, if you use this often you can package up that for-loop into your own algorithm function -- they are straight-forward templates. This will probably be have much lower complexity than using any of the above.

Upvotes: 3

Related Questions