fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <cassert>
  6.  
  7. template <
  8.         class Container,
  9.         class Operation,
  10.         class T = typename Container::value_type,
  11.         class size_type = typename Container::size_type>
  12. std::vector<T> sliding_window(const Container & input, size_type m, const Operation & operation) {
  13.     size_type input_size = input.size();
  14.     if (input_size < m)
  15.         return {};
  16.     std::vector<T> left_partial, right_partial = {input.back()};
  17.     left_partial.reserve(input_size);
  18.     right_partial.reserve(input_size + 1);
  19.     size_type idx = 0;
  20.     {
  21.         auto direct_it = input.begin();
  22.         auto reverse_it = input.rbegin();
  23.         for (; direct_it != input.end(); ++direct_it, ++reverse_it, ++idx) {
  24.             left_partial.push_back(idx % m
  25.                                ? operation(left_partial[idx - 1], *direct_it)
  26.                                : *direct_it);
  27.             right_partial.push_back((input_size - idx) % m
  28.                                 ? operation(right_partial[idx], *reverse_it)
  29.                                 : *reverse_it
  30.             );
  31.         }
  32.     }
  33.  
  34.     std::vector<T> result;
  35.     size_t result_size = input_size - m + 1;
  36.     result.reserve(result_size);
  37.     for (size_type i = 0; i < result_size; ++i) {
  38.         auto & left_part = right_partial[input_size - i];
  39.         auto & right_part = left_partial[i + m - 1];
  40.  
  41.         result.push_back(i % m
  42.                          ? operation(left_part, right_part)
  43.                          : left_part);
  44.     }
  45.     return result;
  46. }
  47.  
  48. int main(){
  49.     std::vector<int> v = {3, 10, 11, 10, 0, 0, 0, 1, 2, 3, 2};
  50.     auto result_max = sliding_window(v, 3, [] (int x, int y) {return std::max(x, y);});
  51.     assert((result_max == decltype(result_max){11, 11, 11, 10, 0, 1, 2, 3, 3}));
  52.  
  53.     auto result_sum = sliding_window(v, 3, [] (int x, int y) {return x + y;});
  54.     assert((result_sum == decltype(result_sum){24, 31, 21, 10, 0, 1, 3, 6, 7}));
  55.     return 0;
  56. }
  57.  
  58.  
  59.  
Success #stdin #stdout 0s 3412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WwI4uK
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!