m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Monoid Concept
(monoid/concept.hpp)

Overview

m1une::monoid::IsMonoid is the C++20 concept used by generic data structures such as Segtree. It checks that a type exposes the interface needed by the library: a value type, an identity element, and a binary operation.

The concept checks the shape of the interface. The mathematical laws are still the user’s responsibility:

Concept Requirements

To satisfy m1une::monoid::IsMonoid, a type M must implement:

Built-in monoids also expose static constexpr bool commutative. Generic data structures may use it to select a faster representation. This member is deliberately optional and is not part of IsMonoid, so a contest-local monoid may omit it. An omitted flag is treated conservatively by data structures that inspect it.

Group

m1une::monoid::IsGroup extends IsMonoid with an inverse:

The concept checks only that inv exists. The type must satisfy the group laws, but op does not need to be commutative.

m1une::monoid::IsCommutativeGroup extends IsGroup. It has the same compile-time interface check because C++ concepts cannot prove commutativity; types used through it must additionally guarantee that op(a, b) == op(b, a).

Example

#include "monoid/concept.hpp"
#include <algorithm>

struct MinMonoid {
    using value_type = int;
    static constexpr int id() { return 1e9; }
    static constexpr int op(const int& a, const int& b) { return std::min(a, b); }
};

static_assert(m1une::monoid::IsMonoid<MinMonoid>);

Complexity

These concepts are compile-time interface checks and have no runtime cost.

Required by

Verified with

Code

#ifndef M1UNE_MONOID_CONCEPT_HPP
#define M1UNE_MONOID_CONCEPT_HPP 1

#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

#endif  // M1UNE_MONOID_CONCEPT_HPP
#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
Back to top page