コンテナに対する関数 (sorted, max, sum など)
(src/base/container_func.hpp)

View this file on GitHub
Last update: 2026-10-13 06:07:05+09:00
Include: #include "src/base/container_func.hpp"

コンテナ全体を受け取る Python 風の関数です。begin()、end() を持つコンテナならたいてい使えます。

コンテナが同名のメンバ関数を持つ場合は、そちらを呼びます。find、count、lower_bound、upper_bound は std::set などではメンバ関数を、それ以外では std:: のアルゴリズムを使います。

std::vector<int> v = {3, 1, 4, 1, 5};
auto w = sorted(v);            // {1, 1, 3, 4, 5}
int s = sum(v), mx = max(v);   // 14, 5
int i = bisect_left(w, 3);     // 2
bool b = contains(v, 4);       // true

並べ替え

関数	説明
`sorted(c, reverse = false)` / `sorted(c, comp)`	ソートしたコピーを返す
`reversed(c)`	逆順にしたコピーを返す
`sort(c, reverse = false)` / `sort(c, comp)`	その場でソート
`sort_by_key(c, key)`	`key(x)` の昇順にその場でソート
`reverse(c)`	その場で逆順にする

集計

関数	説明
`max(c)` / `min(c)`	最大値 / 最小値 (`set` などソート済みのコンテナでは $O(1)$)。`max({a, b, c})` のように初期化子リストも渡せる
`sum(c)`	総和
`product(c)`	総積
`product_xor(c)`	総 xor
`gcd(c)`	全要素の gcd (空なら 0)
`average(c)`	平均 (`sum(c) / size`、整数型なら切り捨て)
`median(c)`	中央値 (要素数が偶数なら中央 2 つの平均)
`mex(c)`	含まれない最小の非負整数
`maximum_subarray(c)`	空でない連続部分列の和の最大値
`maximum_subarray(c, init)`	空の部分列 (和 `init`) も許した連続部分列の和の最大値

検索

関数	説明
`find(c, x)`	`x` を指すイテレータ
`count(c, x)`	`x` の個数
`contains(c, x)`	`x` を含むか
`index(c, x)`	`x` が最初に現れる位置 (なければ `size`)
`lower_bound(c, x)` / `upper_bound(c, x)`	イテレータを返す
`bisect_left(c, x)` / `bisect_right(c, x)`	添字を返す (Python の `bisect`)

Depends on

型特性 (src/base/traits.hpp)

Verified with

Code

#pragma once

/**
 * @file container_func.hpp
 * @brief コンテナに対する関数 (sorted, max, sum など)
 */

#include <algorithm>
#include <cassert>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <numeric>
#include <vector>
#include "traits.hpp"

#define METHOD_EXPAND(func)                                        \
    template <typename T, ENABLE_IF_T(has_##func##_v<T>)>          \
    inline constexpr auto func(const T &t) -> decltype(t.func()) { \
        return t.func();                                           \
    }

#define METHOD_AND_FUNC_ARG_EXPAND(func)                                     \
    template <typename T, typename U, ENABLE_IF_T(has_##func##_v<T, U>)>     \
    inline constexpr auto func(const T &t, const U &u)                       \
        -> decltype(t.func(u)) {                                             \
        return t.func(u);                                                    \
    }                                                                        \
    template <typename T, typename U, ENABLE_IF_T(not has_##func##_v<T, U>)> \
    inline constexpr auto func(const T &t, const U &u)                       \
        -> decltype(std::func(t.begin(), t.end(), u)) {                      \
        return std::func(t.begin(), t.end(), u);                             \
    }

METHOD_EXPAND(reversed)
template <class C, ENABLE_IF_T(not has_reversed_v<C>)>
inline constexpr C reversed(C t) {
    std::reverse(t.begin(), t.end());
    return t;
}

METHOD_EXPAND(sorted)
template <class C, ENABLE_IF_T(not has_sorted_v<C>)>
inline constexpr C sorted(C t, bool reverse = false) {
    std::sort(t.begin(), t.end());
    if (reverse) std::reverse(t.begin(), t.end());
    return t;
}
template <class C, class F, ENABLE_IF_T(not has_sorted_v<C> and std::is_invocable_r_v<bool, F, mem_value_type<C>, mem_value_type<C>>)>
inline constexpr C sorted(C t, F f) {
    std::sort(t.begin(), t.end(), f);
    return t;
}

template <class C>
inline constexpr void sort(C &t, bool reverse = false) {
    std::sort(t.begin(), t.end());
    if (reverse) std::reverse(t.begin(), t.end());
}
template <class C, class F, ENABLE_IF_T(std::is_invocable_r_v<bool, F, mem_value_type<C>, mem_value_type<C>>)>
inline constexpr void sort(C &t, F f) {
    std::sort(t.begin(), t.end(), f);
}
template <class C, class F, ENABLE_IF_T(std::is_invocable_v<F, mem_value_type<C>>)>
inline constexpr void sort_by_key(C &t, F f) {
    std::sort(t.begin(), t.end(), [&](const mem_value_type<C> &left, const mem_value_type<C> &right) {
        return f(left) < f(right);
    });
}

template <class C>
inline constexpr void reverse(C &t) {
    std::reverse(t.begin(), t.end());
}

METHOD_EXPAND(max)
template <class C, ENABLE_IF_T(not has_max_v<C> and is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> max(const C &v) {
    assert(v.begin() != v.end());
    return *v.rbegin();
}
template <class C, ENABLE_IF_T(not has_max_v<C> and not is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> max(const C &v) {
    assert(v.begin() != v.end());
    return *std::max_element(v.begin(), v.end());
}
template <typename T>
inline constexpr T max(const std::initializer_list<T> &v) {
    return std::max(v);
}

METHOD_EXPAND(min)
template <class C, ENABLE_IF_T(not has_min_v<C> and is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> min(const C &v) {
    assert(v.begin() != v.end());
    return *v.begin();
}
template <class C, ENABLE_IF_T(not has_min_v<C> and not is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> min(const C &v) {
    assert(v.begin() != v.end());
    return *std::min_element(v.begin(), v.end());
}
template <typename T>
inline constexpr T min(const std::initializer_list<T> &v) {
    return std::min(v);
}

METHOD_EXPAND(sum)
template <class C, ENABLE_IF_T(not has_sum_v<C>)>
inline constexpr mem_value_type<C> sum(const C &v) {
    return std::accumulate(v.begin(), v.end(), mem_value_type<C>{});
}
template <typename T>
inline constexpr T sum(const std::initializer_list<T> &v) {
    return std::accumulate(v.begin(), v.end(), T{});
}

METHOD_EXPAND(product)
template <class C, ENABLE_IF_T(not has_product_v<C>)>
inline constexpr mem_value_type<C> product(const C &v) {
    return std::accumulate(v.begin(), v.end(), mem_value_type<C>{1}, std::multiplies<mem_value_type<C>>());
}
template <typename T>
inline constexpr T product(const std::initializer_list<T> &v) {
    return std::accumulate(v.begin(), v.end(), T{1}, std::multiplies<T>());
}

METHOD_EXPAND(product_xor)
template <class C, ENABLE_IF_T(not has_product_xor_v<C>)>
inline constexpr mem_value_type<C> product_xor(const C &v) {
    return std::accumulate(v.begin(), v.end(), mem_value_type<C>{0}, std::bit_xor<mem_value_type<C>>());
}
template <typename T>
inline constexpr T product_xor(const std::initializer_list<T> &v) {
    return std::accumulate(v.begin(), v.end(), T{0}, std::bit_xor<T>());
}

template <class C>
inline constexpr mem_value_type<C> maximum_subarray(const C &v) {
    assert(not v.empty());
    auto itr = v.begin();
    mem_value_type<C> tmp = *itr++;
    mem_value_type<C> res = tmp;
    while (itr != v.end()) {
        tmp += *itr;
        if (tmp < *itr) tmp = *itr;
        if (res < tmp) res = tmp;
        ++itr;
    }
    return res;
}
template <class C>
inline constexpr mem_value_type<C> maximum_subarray(const C &v, mem_value_type<C> init) {
    mem_value_type<C> res = init, tmp = init;
    for (const auto &a : v) {
        tmp += a;
        if (tmp < init) tmp = init;
        if (res < tmp) res = tmp;
    }
    return res;
}

METHOD_AND_FUNC_ARG_EXPAND(count)
METHOD_AND_FUNC_ARG_EXPAND(find)
METHOD_AND_FUNC_ARG_EXPAND(lower_bound)
METHOD_AND_FUNC_ARG_EXPAND(upper_bound)

template <class C, typename T>
inline constexpr bool contains(const C &c, const T &t) {
    return find(c, t) != c.end();
}

template <class C>
inline constexpr mem_value_type<C> gcd(const C &v) {
    mem_value_type<C> init(0);
    for (const auto &e : v) init = std::gcd(init, e);
    return init;
}

template <class C>
inline constexpr mem_value_type<C> average(const C &v) {
    assert(v.size());
    return sum(v) / v.size();
}

template <class C>
inline constexpr mem_value_type<C> median(const C &v) {
    assert(not v.empty());
    std::vector<size_t> u(v.size());
    std::iota(u.begin(), u.end(), 0);
    std::sort(u.begin(), u.end(), [&](size_t a, size_t b) {
        return v[a] < v[b];
    });
    if (v.size() & 1) {
        return v[u[v.size() / 2]];
    }
    // C++20
    // return std::midpoint(v[u[v.size() / 2]], v[u[v.size() / 2 - 1]]);
    return (v[u[v.size() / 2]] + v[u[v.size() / 2 - 1]]) / 2;
}

template <class C, typename U>
inline constexpr std::ptrdiff_t index(const C &v, const U &x) {
    return std::distance(v.begin(), find(v, x));
}

template <class C, ENABLE_IF_T(std::is_integral_v<mem_value_type<C>>)>
inline constexpr mem_value_type<C> mex(const C &v) {
    std::vector<bool> b(v.size() + 1);
    for (const auto &a : v) {
        if (0 <= a and static_cast<size_t>(a) < b.size()) {
            b[a] = true;
        }
    }
    mem_value_type<C> ret = 0;  // b の要素数は v より 1 多いので、下のループで必ず見つかる
    for (size_t i = 0; i < b.size(); i++) {
        if (not b[i]) {
            ret = i;
            break;
        }
    }
    return ret;
}

template <class C>
inline constexpr mem_difference_type<C> bisect_left(const C &v, const mem_value_type<C> &x) {
    return std::distance(v.begin(), lower_bound(v, x));
}
template <class C>
inline constexpr mem_difference_type<C> bisect_right(const C &v, const mem_value_type<C> &x) {
    return std::distance(v.begin(), upper_bound(v, x));
}

#line 2 "src/base/container_func.hpp"

/**
 * @file container_func.hpp
 * @brief コンテナに対する関数 (sorted, max, sum など)
 */

#include <algorithm>
#include <cassert>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <numeric>
#include <vector>
#line 2 "src/base/traits.hpp"

/**
 * @file traits.hpp
 * @brief 型特性
 */

#include <cstddef>
#line 10 "src/base/traits.hpp"
#include <set>
#include <type_traits>
#include <utility>

namespace detail {
using std::begin, std::end;

template <class T, class = void>
struct is_range_impl : std::false_type {};
template <class T>
struct is_range_impl<T, std::void_t<decltype(begin(std::declval<T&>()), end(std::declval<T&>()))>> : std::true_type {};
}  // namespace detail

template <class T>
struct is_range : detail::is_range_impl<T>::type {};
template <class T>
inline constexpr bool is_range_v = is_range<T>::value;

#define HAS_METHOD(func_name)                                                              \
    namespace detail {                                                                     \
    template <class T, class = void>                                                       \
    struct has_##func_name##_impl : std::false_type {};                                    \
    template <class T>                                                                     \
    struct has_##func_name##_impl<T, std::void_t<decltype(std::declval<T>().func_name())>> \
        : std::true_type {};                                                               \
    }                                                                                      \
    template <class T>                                                                     \
    struct has_##func_name : detail::has_##func_name##_impl<T>::type {};                   \
    template <class T>                                                                     \
    inline constexpr bool has_##func_name##_v = has_##func_name<T>::value;

#define HAS_METHOD_ARG(func_name)                                                                              \
    namespace detail {                                                                                         \
    template <class T, typename U, class = void>                                                               \
    struct has_##func_name##_impl : std::false_type {};                                                        \
    template <class T, typename U>                                                                             \
    struct has_##func_name##_impl<T, U, std::void_t<decltype(std::declval<T>().func_name(std::declval<U>()))>> \
        : std::true_type {};                                                                                   \
    }                                                                                                          \
    template <class T, typename U>                                                                             \
    struct has_##func_name : detail::has_##func_name##_impl<T, U>::type {};                                    \
    template <class T, typename U>                                                                             \
    inline constexpr bool has_##func_name##_v = has_##func_name<T, U>::value;

HAS_METHOD(repr)
HAS_METHOD(type_str)
HAS_METHOD(initializer_str)
HAS_METHOD(max)
HAS_METHOD(min)
HAS_METHOD(reversed)
HAS_METHOD(sorted)
HAS_METHOD(sum)
HAS_METHOD(product)
HAS_METHOD(product_xor)
HAS_METHOD_ARG(count)
HAS_METHOD_ARG(find)
HAS_METHOD_ARG(lower_bound)
HAS_METHOD_ARG(upper_bound)

#define ENABLE_IF_T_IMPL(expr) std::enable_if_t<expr, std::nullptr_t> = nullptr
#define ENABLE_IF_T(...) ENABLE_IF_T_IMPL((__VA_ARGS__))

template <class C>
using mem_value_type = typename C::value_type;
template <class C>
using mem_difference_type = typename C::difference_type;

namespace detail {
template <class T, class = void>
struct is_sorted_container_impl : std::false_type {};
template <class T>
struct is_sorted_container_impl<std::set<T>> : std::true_type {};
template <class T>
struct is_sorted_container_impl<std::multiset<T>> : std::true_type {};
}  // namespace detail
template <class T>
struct is_sorted_container : detail::is_sorted_container_impl<T>::type {};
template <class T>
inline constexpr bool is_sorted_container_v = is_sorted_container<T>::value;
#line 16 "src/base/container_func.hpp"

#define METHOD_EXPAND(func)                                        \
    template <typename T, ENABLE_IF_T(has_##func##_v<T>)>          \
    inline constexpr auto func(const T &t) -> decltype(t.func()) { \
        return t.func();                                           \
    }

#define METHOD_AND_FUNC_ARG_EXPAND(func)                                     \
    template <typename T, typename U, ENABLE_IF_T(has_##func##_v<T, U>)>     \
    inline constexpr auto func(const T &t, const U &u)                       \
        -> decltype(t.func(u)) {                                             \
        return t.func(u);                                                    \
    }                                                                        \
    template <typename T, typename U, ENABLE_IF_T(not has_##func##_v<T, U>)> \
    inline constexpr auto func(const T &t, const U &u)                       \
        -> decltype(std::func(t.begin(), t.end(), u)) {                      \
        return std::func(t.begin(), t.end(), u);                             \
    }

METHOD_EXPAND(reversed)
template <class C, ENABLE_IF_T(not has_reversed_v<C>)>
inline constexpr C reversed(C t) {
    std::reverse(t.begin(), t.end());
    return t;
}

METHOD_EXPAND(sorted)
template <class C, ENABLE_IF_T(not has_sorted_v<C>)>
inline constexpr C sorted(C t, bool reverse = false) {
    std::sort(t.begin(), t.end());
    if (reverse) std::reverse(t.begin(), t.end());
    return t;
}
template <class C, class F, ENABLE_IF_T(not has_sorted_v<C> and std::is_invocable_r_v<bool, F, mem_value_type<C>, mem_value_type<C>>)>
inline constexpr C sorted(C t, F f) {
    std::sort(t.begin(), t.end(), f);
    return t;
}

template <class C>
inline constexpr void sort(C &t, bool reverse = false) {
    std::sort(t.begin(), t.end());
    if (reverse) std::reverse(t.begin(), t.end());
}
template <class C, class F, ENABLE_IF_T(std::is_invocable_r_v<bool, F, mem_value_type<C>, mem_value_type<C>>)>
inline constexpr void sort(C &t, F f) {
    std::sort(t.begin(), t.end(), f);
}
template <class C, class F, ENABLE_IF_T(std::is_invocable_v<F, mem_value_type<C>>)>
inline constexpr void sort_by_key(C &t, F f) {
    std::sort(t.begin(), t.end(), [&](const mem_value_type<C> &left, const mem_value_type<C> &right) {
        return f(left) < f(right);
    });
}

template <class C>
inline constexpr void reverse(C &t) {
    std::reverse(t.begin(), t.end());
}

METHOD_EXPAND(max)
template <class C, ENABLE_IF_T(not has_max_v<C> and is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> max(const C &v) {
    assert(v.begin() != v.end());
    return *v.rbegin();
}
template <class C, ENABLE_IF_T(not has_max_v<C> and not is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> max(const C &v) {
    assert(v.begin() != v.end());
    return *std::max_element(v.begin(), v.end());
}
template <typename T>
inline constexpr T max(const std::initializer_list<T> &v) {
    return std::max(v);
}

METHOD_EXPAND(min)
template <class C, ENABLE_IF_T(not has_min_v<C> and is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> min(const C &v) {
    assert(v.begin() != v.end());
    return *v.begin();
}
template <class C, ENABLE_IF_T(not has_min_v<C> and not is_sorted_container_v<C>)>
inline constexpr mem_value_type<C> min(const C &v) {
    assert(v.begin() != v.end());
    return *std::min_element(v.begin(), v.end());
}
template <typename T>
inline constexpr T min(const std::initializer_list<T> &v) {
    return std::min(v);
}

METHOD_EXPAND(sum)
template <class C, ENABLE_IF_T(not has_sum_v<C>)>
inline constexpr mem_value_type<C> sum(const C &v) {
    return std::accumulate(v.begin(), v.end(), mem_value_type<C>{});
}
template <typename T>
inline constexpr T sum(const std::initializer_list<T> &v) {
    return std::accumulate(v.begin(), v.end(), T{});
}

METHOD_EXPAND(product)
template <class C, ENABLE_IF_T(not has_product_v<C>)>
inline constexpr mem_value_type<C> product(const C &v) {
    return std::accumulate(v.begin(), v.end(), mem_value_type<C>{1}, std::multiplies<mem_value_type<C>>());
}
template <typename T>
inline constexpr T product(const std::initializer_list<T> &v) {
    return std::accumulate(v.begin(), v.end(), T{1}, std::multiplies<T>());
}

METHOD_EXPAND(product_xor)
template <class C, ENABLE_IF_T(not has_product_xor_v<C>)>
inline constexpr mem_value_type<C> product_xor(const C &v) {
    return std::accumulate(v.begin(), v.end(), mem_value_type<C>{0}, std::bit_xor<mem_value_type<C>>());
}
template <typename T>
inline constexpr T product_xor(const std::initializer_list<T> &v) {
    return std::accumulate(v.begin(), v.end(), T{0}, std::bit_xor<T>());
}

template <class C>
inline constexpr mem_value_type<C> maximum_subarray(const C &v) {
    assert(not v.empty());
    auto itr = v.begin();
    mem_value_type<C> tmp = *itr++;
    mem_value_type<C> res = tmp;
    while (itr != v.end()) {
        tmp += *itr;
        if (tmp < *itr) tmp = *itr;
        if (res < tmp) res = tmp;
        ++itr;
    }
    return res;
}
template <class C>
inline constexpr mem_value_type<C> maximum_subarray(const C &v, mem_value_type<C> init) {
    mem_value_type<C> res = init, tmp = init;
    for (const auto &a : v) {
        tmp += a;
        if (tmp < init) tmp = init;
        if (res < tmp) res = tmp;
    }
    return res;
}

METHOD_AND_FUNC_ARG_EXPAND(count)
METHOD_AND_FUNC_ARG_EXPAND(find)
METHOD_AND_FUNC_ARG_EXPAND(lower_bound)
METHOD_AND_FUNC_ARG_EXPAND(upper_bound)

template <class C, typename T>
inline constexpr bool contains(const C &c, const T &t) {
    return find(c, t) != c.end();
}

template <class C>
inline constexpr mem_value_type<C> gcd(const C &v) {
    mem_value_type<C> init(0);
    for (const auto &e : v) init = std::gcd(init, e);
    return init;
}

template <class C>
inline constexpr mem_value_type<C> average(const C &v) {
    assert(v.size());
    return sum(v) / v.size();
}

template <class C>
inline constexpr mem_value_type<C> median(const C &v) {
    assert(not v.empty());
    std::vector<size_t> u(v.size());
    std::iota(u.begin(), u.end(), 0);
    std::sort(u.begin(), u.end(), [&](size_t a, size_t b) {
        return v[a] < v[b];
    });
    if (v.size() & 1) {
        return v[u[v.size() / 2]];
    }
    // C++20
    // return std::midpoint(v[u[v.size() / 2]], v[u[v.size() / 2 - 1]]);
    return (v[u[v.size() / 2]] + v[u[v.size() / 2 - 1]]) / 2;
}

template <class C, typename U>
inline constexpr std::ptrdiff_t index(const C &v, const U &x) {
    return std::distance(v.begin(), find(v, x));
}

template <class C, ENABLE_IF_T(std::is_integral_v<mem_value_type<C>>)>
inline constexpr mem_value_type<C> mex(const C &v) {
    std::vector<bool> b(v.size() + 1);
    for (const auto &a : v) {
        if (0 <= a and static_cast<size_t>(a) < b.size()) {
            b[a] = true;
        }
    }
    mem_value_type<C> ret = 0;  // b の要素数は v より 1 多いので、下のループで必ず見つかる
    for (size_t i = 0; i < b.size(); i++) {
        if (not b[i]) {
            ret = i;
            break;
        }
    }
    return ret;
}

template <class C>
inline constexpr mem_difference_type<C> bisect_left(const C &v, const mem_value_type<C> &x) {
    return std::distance(v.begin(), lower_bound(v, x));
}
template <class C>
inline constexpr mem_difference_type<C> bisect_right(const C &v, const mem_value_type<C> &x) {
    return std::distance(v.begin(), upper_bound(v, x));
}

shogo-library

コンテナに対する関数 (sorted, max, sum など)
(src/base/container_func.hpp)

並べ替え

集計

検索

関連

Depends on

Verified with

Code

コンテナに対する関数 (sorted, max, sum など) (src/base/container_func.hpp)

並べ替え

集計

検索

関連

Depends on

Verified with

Code

コンテナに対する関数 (sorted, max, sum など)
(src/base/container_func.hpp)