How to better use STLs and functors for getting solution for sliding window minimum

Question

Learning stls and c++11

Was working through some of example and here is one which targets to get minimum for each sliding window for a given sequence.

Given below is my solution which I did in a very naive way, but it could definitely be improved by using stls, algorithms or any other c++11 feature.

I am not looking for complete code (but anyone interest could do that), instead for some advises which would help me

1. identify if `std::copy_if` or `back_inserter` could be used to construct result
2. if `std::transform` is the way to get the job done instead of `while's`
3. or any c++11 features would allow me to simplify more and exception safe program

I know it is kind of asking as kid for c++, but that is what I am now :-)

My Solution

#include <iostream>
#include <deque>
#include <string>
#include <vector>
#include <iterator>

/*
*  get minimum for each sliding window of size w
*
*  a = {1, 3, -1, -3, 5, 3, 6, 7};
*  w = 3
*  r = {-1, -3, -3, -3, 3, 3}
*/

void GetMinLookUpForWindow(const std::vector<int> &src, std::vector<int> &res, const size_t w) {

    std::deque<size_t> priority;
    for (int i = 0; i < w; ++i) {

        // initialization phase and push min for first window w
        if (!priority.empty() &&
            src[i] < src[priority.back()]) {
            priority.pop_back();
        }
        priority.push_back(i);
    }

    //iterate through rest of values and maintain min @front in deque
    for (int i = w; i < src.size(); ++i) {

        // required min element is at front ...
        res.push_back(src[priority.front()]);

        // pop all max from back
        while (!priority.empty() &&
            src[i] < src[priority.back()]) {
            priority.pop_back();
        }

        // pop all front till index out of current window
        while (!priority.empty() && priority.front() <= i - w) {
            priority.pop_front();
        }

        //  offer the current index
        priority.push_back(i);
    }

    // get the final element for last window
    res.push_back(src[priority.front()]);
}

int main()
{
    std::vector<int> vec({ 1, 3, -1, -3, 5, 3, 6, 7 });
    size_t w = 3;

    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    std::vector<int> res;

    GetMinLookUpForWindow(vec, res, w);

    std::copy(res.begin(), res.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

Regards,

Solution by combining both answers

Modified function:

void GetMinLookUpForWindowModified( std::pair<std::vector<int>::const_iterator, std::vector<int>::const_iterator> range,
                                    std::back_insert_iterator<std::vector<int>> op,
                                    size_t w) {

    for (auto it = range.first; it < range.second - w + 1; ++it, ++op) {
        auto it_min = std::min_element(it, it + w);
        op = *it_min;
    }
}

Callee code:

GetMinLookUpForWindowModified(make_pair(vec.begin(), vec.end()), std::back_inserter(res), w);

Answer 1

Like you mention in your prelude, I would pass GetMinLookUpForWindow a pair of iterators for range and an output iterator.

Thinking in terms of iterators and algorithms is one of those little leaps that make your code more readable and maintainable.

Even if you didn't go this route you should use iterators for loops inside your function.

The first section where you initially prime the queue is needlessly complex. You should just be able to fire either all w items at it regardless or miss out that step entirely.

Also priority_queue should maintain your queue to a comparator, which will sort it for you which is seemingly what you will end up with.