値の個数を数える多重集合 (Counter)
(src/data_structures/counter.hpp)

• View this file on GitHub
• Last update: 2026-10-13 06:02:01+09:00
• Include: #include "src/data_structures/counter.hpp"

値ごとの個数を std::map で管理する多重集合 Counter<T> です (Python の collections.Counter)。個数が 0 になった値は自動で取り除かれます。

std::vector<int> v = {3, 1, 3, 2, 3};
Counter<int> c(v);
c[1] += 2;                        // 1 を 2 個追加
long long k = c[3];               // 3
auto top = c.most_common();       // 個数の多い順
for (auto [x, cnt] : c) { }       // 値の昇順に走査
Counter<int> d = c + Counter<int>(3);  // 3 を 1 個足した Counter

メンバ

n は異なる値の個数です。

メンバ	説明	計算量
Counter<T> c	空の Counter	$O(1)$
Counter<T> c(x)	値 x が 1 個	$O(1)$
Counter<T> c{ {x, k}, ... }	値 x が k 個、… で初期化
Counter<T> c(v)	コンテナ v の要素を数える	$O(\lvert v \rvert \log n)$
c[x] / c.get(x)	x の個数 (なければ 0)	$O(\log n)$
c[x] = k / c.set(x, k)	x の個数を k にする (k >= 0)	$O(\log n)$
c[x] += k、c[x] -= k / c.inc(x, k)	x の個数を増減する (負になると assert で落ちる)	$O(\log n)$
c + d、c += d	個数を足し合わせる	$O(m \log (n + m))$ ($m$ は d の異なる値の個数)
c - d、c -= d	個数を引く (負になると assert で落ちる)	$O(m \log n)$
for (auto [x, cnt] : c)	{値, 個数} を値の昇順に走査	$O(n)$
c.size()	異なる値の個数	$O(1)$
c.most_common()	{値, 個数} のリスト。個数の降順、同数なら値の昇順	$O(n \log n)$
c.data	中身の std::map<T, long long> (値の昇順に走査できる)

Verified with

• test/aoj/0029.test.cpp
• test/aoj/itp2-7-d.test.cpp
• test/unittest/counter.test.cpp
• test/yosupo/associative-array.test.cpp

Code

#pragma once

/**
 * @file counter.hpp
 * @brief 値の個数を数える多重集合 (Counter)
 */

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <map>
#include <type_traits>
#include <utility>
#include <vector>

template <typename T>
struct Counter {
    using key_type = T;
    using mapped_type = long long;
    using value_type = std::pair<key_type, mapped_type>;
    std::map<key_type, mapped_type> data;

    void inc(const key_type& key, const mapped_type& t) {
        data[key] += t;
        auto itr = data.find(key);
        assert(itr->second >= 0);
        if (itr->second == 0) {
            data.erase(itr);
        }
    }
    Counter() = default;
    explicit Counter(const key_type& x) : data{{x, 1}} {}
    /**
     * @brief 範囲の要素を数える
     * Counter 自身と key_type (std::string など範囲でもあるもの) はこちらで受け取らない
     */
    template <class C, std::enable_if_t<!std::is_same_v<std::decay_t<C>, Counter> && !std::is_convertible_v<C, key_type>, std::nullptr_t> = nullptr,
              class = decltype(std::begin(std::declval<C&>()), std::end(std::declval<C&>()))>
    explicit Counter(C&& v) {
        for (const key_type& a : v) {
            data[a]++;
        }
    }
    Counter(std::initializer_list<value_type> init) {
        for (const auto& p : init) {
            inc(p.first, p.second);
        }
    }
    Counter& operator+=(const Counter& o) {
        for (const auto& [i, c] : o.data) {
            data[i] += c;
        }
        return *this;
    }
    friend Counter operator+(const Counter& a, const Counter& b) {
        Counter res(a);
        return res += b;
    }
    Counter& operator-=(const Counter& o) {
        // 自分自身を引くと、走査中の o.data の要素を inc が消してしまう
        if (this == &o) {
            data.clear();
            return *this;
        }
        for (const auto& [i, c] : o.data) {
            inc(i, -c);
        }
        return *this;
    }
    friend Counter operator-(const Counter& a, const Counter& b) {
        Counter res(a);
        return res -= b;
    }
    auto begin() const { return data.begin(); }
    auto end() const { return data.end(); }
    std::size_t size() const {
        return data.size();
    }
    mapped_type get(const key_type& key) const {
        auto itr = data.find(key);
        if (itr == data.end()) return 0;
        return itr->second;
    }
    void set(const key_type& key, const mapped_type& t) {
        assert(t >= 0);
        if (t > 0) {
            data[key] = t;
        } else {
            auto itr = data.find(key);
            if (itr != data.end()) {
                data.erase(itr);
            }
        }
    }
    std::vector<value_type> most_common() const {
        std::vector<value_type> ret;
        ret.reserve(data.size());
        for (const auto& [i, c] : data) {
            ret.push_back({i, c});
        }
        std::sort(ret.begin(), ret.end(), [](const value_type& a, const value_type& b) { return a.second > b.second or (a.second == b.second and a.first < b.first); });
        return ret;
    }
    class CounterReference {
        Counter& base;
        key_type key;

       public:
        CounterReference(Counter& base, key_type key) : base(base), key(key) {}
        CounterReference& operator=(const mapped_type& x) {
            base.set(key, x);
            return *this;
        }
        CounterReference& operator+=(const mapped_type& x) {
            base.inc(key, x);
            return *this;
        }
        CounterReference& operator-=(const mapped_type& x) {
            base.inc(key, -x);
            return *this;
        }
        operator mapped_type() const {
            return base.get(key);
        }
    };
    mapped_type operator[](const key_type& key) const {
        return get(key);
    }
    CounterReference operator[](const key_type& key) {
        return CounterReference(*this, key);
    }
};

#line 2 "src/data_structures/counter.hpp"

/**
 * @file counter.hpp
 * @brief 値の個数を数える多重集合 (Counter)
 */

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <map>
#include <type_traits>
#include <utility>
#include <vector>

template <typename T>
struct Counter {
    using key_type = T;
    using mapped_type = long long;
    using value_type = std::pair<key_type, mapped_type>;
    std::map<key_type, mapped_type> data;

    void inc(const key_type& key, const mapped_type& t) {
        data[key] += t;
        auto itr = data.find(key);
        assert(itr->second >= 0);
        if (itr->second == 0) {
            data.erase(itr);
        }
    }
    Counter() = default;
    explicit Counter(const key_type& x) : data{{x, 1}} {}
    /**
     * @brief 範囲の要素を数える
     * Counter 自身と key_type (std::string など範囲でもあるもの) はこちらで受け取らない
     */
    template <class C, std::enable_if_t<!std::is_same_v<std::decay_t<C>, Counter> && !std::is_convertible_v<C, key_type>, std::nullptr_t> = nullptr,
              class = decltype(std::begin(std::declval<C&>()), std::end(std::declval<C&>()))>
    explicit Counter(C&& v) {
        for (const key_type& a : v) {
            data[a]++;
        }
    }
    Counter(std::initializer_list<value_type> init) {
        for (const auto& p : init) {
            inc(p.first, p.second);
        }
    }
    Counter& operator+=(const Counter& o) {
        for (const auto& [i, c] : o.data) {
            data[i] += c;
        }
        return *this;
    }
    friend Counter operator+(const Counter& a, const Counter& b) {
        Counter res(a);
        return res += b;
    }
    Counter& operator-=(const Counter& o) {
        // 自分自身を引くと、走査中の o.data の要素を inc が消してしまう
        if (this == &o) {
            data.clear();
            return *this;
        }
        for (const auto& [i, c] : o.data) {
            inc(i, -c);
        }
        return *this;
    }
    friend Counter operator-(const Counter& a, const Counter& b) {
        Counter res(a);
        return res -= b;
    }
    auto begin() const { return data.begin(); }
    auto end() const { return data.end(); }
    std::size_t size() const {
        return data.size();
    }
    mapped_type get(const key_type& key) const {
        auto itr = data.find(key);
        if (itr == data.end()) return 0;
        return itr->second;
    }
    void set(const key_type& key, const mapped_type& t) {
        assert(t >= 0);
        if (t > 0) {
            data[key] = t;
        } else {
            auto itr = data.find(key);
            if (itr != data.end()) {
                data.erase(itr);
            }
        }
    }
    std::vector<value_type> most_common() const {
        std::vector<value_type> ret;
        ret.reserve(data.size());
        for (const auto& [i, c] : data) {
            ret.push_back({i, c});
        }
        std::sort(ret.begin(), ret.end(), [](const value_type& a, const value_type& b) { return a.second > b.second or (a.second == b.second and a.first < b.first); });
        return ret;
    }
    class CounterReference {
        Counter& base;
        key_type key;

       public:
        CounterReference(Counter& base, key_type key) : base(base), key(key) {}
        CounterReference& operator=(const mapped_type& x) {
            base.set(key, x);
            return *this;
        }
        CounterReference& operator+=(const mapped_type& x) {
            base.inc(key, x);
            return *this;
        }
        CounterReference& operator-=(const mapped_type& x) {
            base.inc(key, -x);
            return *this;
        }
        operator mapped_type() const {
            return base.get(key);
        }
    };
    mapped_type operator[](const key_type& key) const {
        return get(key);
    }
    CounterReference operator[](const key_type& key) {
        return CounterReference(*this, key);
    }
};

Back to top page