c++ - 如何更好地使用 STL 和仿函数来获得滑动窗口最小值的解决方案

Question

Learning stls and c++11

正在研究一些示例，这里是一个目标是为给定序列的每个滑动窗口获取最小值。

下面给出的是我以非常幼稚的方式完成的解决方案，但它肯定可以通过使用 STLs、算法或任何其他 c++11 功能来改进。

我不是在寻找完整的代码(但任何有兴趣的人都可以这样做)，而是寻求一些对我有帮助的建议

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

我知道这有点像小时候要求 C++，但这就是我现在的样子:-)

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;
}

问候，

Solution by combining both answers

修改函数:

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;
    }
}

被叫代码:

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

Answer 1

就像您在序言中提到的那样，我会向 GetMinLookUpForWindow 传递一对范围迭代器和一个输出迭代器。

从迭代器和算法的角度思考是让您的代码更具可读性和可维护性的小飞跃之一。

即使您没有走这条路，您也应该在函数内使用迭代器进行循环。

您最初准备队列的第一部分不必要地复杂。您应该能够不顾一切地向它发射所有 w 元素，或者完全错过该步骤。

此外，priority_queue 应该将您的队列维护到一个比较器，它会为您排序，这似乎是您最终会得到的结果。