Sliding Window Aggregation
(ds/range_query/sliding_window_aggregation.hpp)
- View this file on GitHub
- Last update: 2026-07-16 20:44:42+09:00
- Include:
#include "ds/range_query/sliding_window_aggregation.hpp"
Overview
SlidingWindowAggregation<Monoid> maintains a queue and the monoid product of
all its elements. It is commonly called SWAG.
Elements are stored in two aggregate stacks. Each element moves from the back stack to the front stack at most once, giving amortized constant-time queue operations.
Swag<Monoid> is a shorter alias.
Ordering
The product follows queue order:
\[a_0 \mathbin{\mathrm{op}} a_1 \mathbin{\mathrm{op}} \cdots \mathbin{\mathrm{op}} a_{n-1}.\]The monoid does not need to be commutative. This matters for affine-function composition, matrices, and string concatenation.
Methods
| Method | Description | Complexity |
|---|---|---|
push(value), push_back(value)
|
Appends an element. | Amortized $O(1)$ |
pop(), pop_front()
|
Removes the oldest element. | Amortized $O(1)$ |
front() |
Returns the oldest element. | Amortized $O(1)$ |
back() |
Returns the newest element. | $O(1)$ |
prod(), all_prod()
|
Returns the ordered product, or the identity when empty. | $O(1)$ |
size() |
Returns the number of elements. | $O(1)$ |
empty() |
Returns whether the queue is empty. | $O(1)$ |
clear() |
Removes every element. | $O(N)$ |
reserve(capacity) |
Reserves both internal stacks. | $O(N)$ |
pop, pop_front, front, and back require a nonempty queue.
Example
This finds the minimum in every window of length three:
#include "ds/range_query/sliding_window_aggregation.hpp"
#include "monoid/min.hpp"
#include <iostream>
#include <vector>
int main() {
std::vector<int> values = {4, 2, 5, 1, 3};
m1une::ds::Swag<m1une::monoid::Min<int>> window;
for (int index = 0; index < int(values.size()); index++) {
window.push(values[index]);
if (window.size() > 3) window.pop();
if (window.size() == 3) std::cout << window.prod() << "\n";
}
}
Depends on
Verified with
Code
#ifndef M1UNE_DS_RANGE_QUERY_SLIDING_WINDOW_AGGREGATION_HPP
#define M1UNE_DS_RANGE_QUERY_SLIDING_WINDOW_AGGREGATION_HPP 1
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
#include "../../monoid/concept.hpp"
namespace m1une {
namespace ds {
// A queue supporting the ordered product of all elements in amortized O(1).
template <m1une::monoid::IsMonoid Monoid>
struct SlidingWindowAggregation {
using T = typename Monoid::value_type;
private:
struct Entry {
T value;
T product;
};
std::vector<Entry> _front;
std::vector<Entry> _back;
void move_to_front() {
if (!_front.empty()) return;
while (!_back.empty()) {
T value = std::move(_back.back().value);
_back.pop_back();
T product = _front.empty() ? value : Monoid::op(value, _front.back().product);
_front.push_back(Entry{
std::move(value),
std::move(product),
});
}
}
public:
SlidingWindowAggregation() = default;
explicit SlidingWindowAggregation(const std::vector<T>& values) {
reserve(values.size());
for (const T& value : values) push(value);
}
explicit SlidingWindowAggregation(std::vector<T>&& values) {
reserve(values.size());
for (T& value : values) push(std::move(value));
}
std::size_t size() const {
return _front.size() + _back.size();
}
bool empty() const {
return _front.empty() && _back.empty();
}
void reserve(std::size_t capacity) {
_front.reserve(capacity);
_back.reserve(capacity);
}
void clear() {
_front.clear();
_back.clear();
}
void push(T value) {
T product = _back.empty() ? value : Monoid::op(_back.back().product, value);
_back.push_back(Entry{
std::move(value),
std::move(product),
});
}
void push_back(T value) {
push(std::move(value));
}
// Removes the oldest element.
void pop() {
assert(!empty());
move_to_front();
_front.pop_back();
}
void pop_front() {
pop();
}
const T& front() {
assert(!empty());
move_to_front();
return _front.back().value;
}
const T& back() const {
assert(!empty());
if (!_back.empty()) return _back.back().value;
return _front.front().value;
}
// Returns the product in queue order, or the identity when empty.
T prod() const {
if (_front.empty()) {
return _back.empty() ? Monoid::id() : _back.back().product;
}
if (_back.empty()) return _front.back().product;
return Monoid::op(_front.back().product, _back.back().product);
}
T all_prod() const {
return prod();
}
};
template <m1une::monoid::IsMonoid Monoid>
using Swag = SlidingWindowAggregation<Monoid>;
} // namespace ds
} // namespace m1une
#endif // M1UNE_DS_RANGE_QUERY_SLIDING_WINDOW_AGGREGATION_HPP#line 1 "ds/range_query/sliding_window_aggregation.hpp"
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
#line 1 "monoid/concept.hpp"
#include <concepts>
namespace m1une {
namespace monoid {
// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
// 1. Must define `value_type`
typename M::value_type;
// 2. Must have a static method `id()` returning `value_type`
{ M::id() } -> std::same_as<typename M::value_type>;
// 3. Must have a static method `op(a, b)` returning `value_type`
{ M::op(a, b) } -> std::same_as<typename M::value_type>;
};
// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
{ M::inv(a) } -> std::same_as<typename M::value_type>;
};
// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;
} // namespace monoid
} // namespace m1une
#line 10 "ds/range_query/sliding_window_aggregation.hpp"
namespace m1une {
namespace ds {
// A queue supporting the ordered product of all elements in amortized O(1).
template <m1une::monoid::IsMonoid Monoid>
struct SlidingWindowAggregation {
using T = typename Monoid::value_type;
private:
struct Entry {
T value;
T product;
};
std::vector<Entry> _front;
std::vector<Entry> _back;
void move_to_front() {
if (!_front.empty()) return;
while (!_back.empty()) {
T value = std::move(_back.back().value);
_back.pop_back();
T product = _front.empty() ? value : Monoid::op(value, _front.back().product);
_front.push_back(Entry{
std::move(value),
std::move(product),
});
}
}
public:
SlidingWindowAggregation() = default;
explicit SlidingWindowAggregation(const std::vector<T>& values) {
reserve(values.size());
for (const T& value : values) push(value);
}
explicit SlidingWindowAggregation(std::vector<T>&& values) {
reserve(values.size());
for (T& value : values) push(std::move(value));
}
std::size_t size() const {
return _front.size() + _back.size();
}
bool empty() const {
return _front.empty() && _back.empty();
}
void reserve(std::size_t capacity) {
_front.reserve(capacity);
_back.reserve(capacity);
}
void clear() {
_front.clear();
_back.clear();
}
void push(T value) {
T product = _back.empty() ? value : Monoid::op(_back.back().product, value);
_back.push_back(Entry{
std::move(value),
std::move(product),
});
}
void push_back(T value) {
push(std::move(value));
}
// Removes the oldest element.
void pop() {
assert(!empty());
move_to_front();
_front.pop_back();
}
void pop_front() {
pop();
}
const T& front() {
assert(!empty());
move_to_front();
return _front.back().value;
}
const T& back() const {
assert(!empty());
if (!_back.empty()) return _back.back().value;
return _front.front().value;
}
// Returns the product in queue order, or the identity when empty.
T prod() const {
if (_front.empty()) {
return _back.empty() ? Monoid::id() : _back.back().product;
}
if (_back.empty()) return _front.back().product;
return Monoid::op(_front.back().product, _back.back().product);
}
T all_prod() const {
return prod();
}
};
template <m1une::monoid::IsMonoid Monoid>
using Swag = SlidingWindowAggregation<Monoid>;
} // namespace ds
} // namespace m1une