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

Question

Learning stls and c++11

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

下面给出的是我以非常幼稚的方式完成的解决方案，但它肯定可以通过使用 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 应该将您的队列维护到一个比较器，它会为您排序，这似乎是您最终会得到的。

Answer 2

有多种可能性。我能想到的最简单的（并且不改变界面）是这样的：

void GetMinLookUpForWindow(const std::vector<int> &src, std::vector<int> &res, const size_t w) {
    for (auto it = src.begin(); it < src.end() - w +1; ++it) {
        res.push_back(*std::min_element(it, it +w));            
    }   
}

对于更长的 windows，您可以通过记住最后的最小位置来稍微调整一下（如果这真的更快，您将不得不测量）：

template<class IT>
IT minIterator(IT l, IT r) {
    return *l < *r ? l : r;
}

void GetMinLookUpForWindow(const std::vector<int> &src, std::vector<int> &res, const size_t w) {
    auto it_min = std::min_element(src.begin(), src.begin() + w);   
    for (auto it = src.begin(), end = src.end() - (w - 1); it < end; ++it) 
    {
        if (it_min >= it) {
            //if last minimum element is still in the window, we only have to check it against the new addition
            it_min = minIterator(it_min, it + (w - 1));
        } else {
            it_min = std::min_element(it, it + w );
        }           
        res.push_back(*it_min);         
    }   
}

我个人也会将界面更改为：

template<class C>
std::vector<typename C::value_type> GetMinLookUpForWindow(C src, const size_t w)

或（更像 STL）

template<class IT_IN, class IT_OUT >
void GetMinLookUpForWindow(IT_IN start, IT_IN end, IT_OUT res, const size_t w)

您提到的大多数算法（例如 std::copy_if 或 std::transform）的问题是，它们以每个元素为基础工作，并且无法让您轻松访问周围的元素。因此，完全避免循环可能会导致代码的可读性降低和更容易出错。

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

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

c++

algorithm

c++11

stl

stl-algorithm