DataStructure/sliding_window.hpp

View this file on GitHub
Last update: 2020-07-26 22:31:04+09:00
Include: #include "DataStructure/sliding_window.hpp"

Verified with

Verify/sliding_window.test.cpp

Code

#pragma once

#include <deque>
#include <functional>

template <class T>
struct SlidingWindow {
    using Cmp = std::function<bool(T, T)>;

    std::deque<std::pair<T, int>> window;
    Cmp cmp;
    int l, r;

    explicit SlidingWindow(Cmp cmp)
        : window(), cmp(cmp), l(0), r(0) {}

    void push(T val) {
        while (!window.empty() && cmp(val, window.back().first)) {
            window.pop_back();
        }
        window.emplace_back(val, r++);
    }

    T get() {
        return window.front().first;
    }

    void pop() {
        if (window.front().second == l++) {
            window.pop_front();
        }
    }
};

#line 2 "DataStructure/sliding_window.hpp"

#include <deque>
#include <functional>

template <class T>
struct SlidingWindow {
    using Cmp = std::function<bool(T, T)>;

    std::deque<std::pair<T, int>> window;
    Cmp cmp;
    int l, r;

    explicit SlidingWindow(Cmp cmp)
        : window(), cmp(cmp), l(0), r(0) {}

    void push(T val) {
        while (!window.empty() && cmp(val, window.back().first)) {
            window.pop_back();
        }
        window.emplace_back(val, r++);
    }

    T get() {
        return window.front().first;
    }

    void pop() {
        if (window.front().second == l++) {
            window.pop_front();
        }
    }
};