学习 stls 和 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++ 的要求，但这就是我现在的样子：-）
我的解决方案
#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;
}
问候
结合两个答案的解决方案
修改功能：
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);
就像你在前奏中提到的，我会给GetMinLookUpForWindow一对迭代器传递范围和一个输出迭代器。
从迭代器和算法的角度思考是使您的代码更具可读性和可维护性的小飞跃之一。
即使你没有走这条路，你也应该在函数内部使用迭代器来循环。
您最初启动队列的第一部分非常复杂。您应该能够向它发射所有w项目，无论还是完全错过该步骤。
此外，priority_queue应该将您的队列维护到比较器，该比较器将为您对其进行排序，这似乎是您最终会得到的。
有多种可能性。我能想到的最简单的一个（并且不更改界面）是这样的：
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));
}
}
对于较长的窗口，您可以通过记住最后一个最小位置来稍微调整它（如果这真的更快，您必须进行测量）：
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）的问题在于，它们基于每个元素工作，并且不能让您轻松访问周围的元素。因此，完全避免循环可能会导致代码的可读性降低和更容易出错。