Monoid Wrapper
(monoid/wrapper.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "monoid/wrapper.hpp"

Overview

An adapter struct that easily generates a monoid from given functions or stateless lambdas using C++20 Non-Type Template Parameters (NTTP). This is extremely useful in competitive programming contests to define custom monoids (e.g., for Segment Trees) with minimal boilerplate code.

Template Parameters

• T: The underlying data type of the monoid.
• Op: A callable object (function pointer or stateless lambda) that takes two arguments of type T and returns a value of type T.
• Id: A callable object (function pointer or stateless lambda) that takes no arguments and returns the identity element of type T.
• Commutative: Whether Op is commutative. Defaults to false.

Example

In C++20, you can pass lambdas directly in the template arguments. This allows you to define a monoid completely inline.

#include "monoid/wrapper.hpp"

// Define a Monoid for XOR sum inline
using XorMonoid = m1une::monoid::Wrapper<int, [](int a, int b) { return a ^ b; }, []() { return 0; }, true>;

// Now `XorMonoid` can be passed to data structures like Segtree
// Segtree<XorMonoid> seg(n);

You can also define the lambdas separately if the operations are complex:

constexpr auto custom_op = [](long long a, long long b) { return a + b; };
constexpr auto custom_id = []() { return 0LL; };
using CustomMonoid = m1une::monoid::Wrapper<long long, custom_op, custom_id>;

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, commutative, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_WRAPPER_HPP
#define M1UNE_MONOID_WRAPPER_HPP 1

namespace m1une {
namespace monoid {

// Wrapper struct to generate a Monoid using Non-Type Template Parameters (NTTP).
// Useful for quickly defining monoids using custom functions or constexpr lambdas during contests.
template <typename T, auto Op, auto Id, bool Commutative = false>
struct Wrapper {
    using value_type = T;
    static constexpr bool commutative = Commutative;

    // Returns the identity element by invoking the provided `Id` function.
    static constexpr T id() {
        return Id();
    }

    // Returns the result of the binary operation by invoking the provided `Op` function.
    static constexpr T op(const T& a, const T& b) {
        return Op(a, b);
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_WRAPPER_HPP

#line 1 "monoid/wrapper.hpp"



namespace m1une {
namespace monoid {

// Wrapper struct to generate a Monoid using Non-Type Template Parameters (NTTP).
// Useful for quickly defining monoids using custom functions or constexpr lambdas during contests.
template <typename T, auto Op, auto Id, bool Commutative = false>
struct Wrapper {
    using value_type = T;
    static constexpr bool commutative = Commutative;

    // Returns the identity element by invoking the provided `Id` function.
    static constexpr T id() {
        return Id();
    }

    // Returns the result of the binary operation by invoking the provided `Op` function.
    static constexpr T op(const T& a, const T& b) {
        return Op(a, b);
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page