ランレングス圧縮 (groupby)
(util/groupby.hpp)

• View this file on GitHub
• Last update: 2020-08-24 19:38:59+09:00
• Include: #include "util/groupby.hpp"

概要

ランレングス圧縮. 命名はPythonに準拠.

注意

• C++14以降で動く.
• vector<bool>だと内部の参照を外さないと動かない？

使用例

• groupby(v) : コンテナvをランレングス圧縮.
  • 返り値の型 : vector<pair<T, int>>
    • T : vの要素.
    • int : その要素が何個続いているか.

Verified with

• test/yukicoder/1183.test.cpp
• test/yukicoder/203.test.cpp

Code

/**
* @brief ランレングス圧縮 (groupby)
* @docs docs/util/groupby.md
*/

template <typename Container>
auto groupby(const Container &vec) {
    assert(vec.size() != 0);
    vector<pair<remove_const_t<remove_reference_t<decltype(vec.front())>>, int>> ret;
    int piv = -1;
    for (auto &e : vec) {
        if (piv == -1 or ret[piv].first != e)
            ++piv, ret.emplace_back(make_pair(e, 1));
        else
            ++(ret[piv].second);
    }
    return ret;
}

#line 1 "util/groupby.hpp"
/**
* @brief ランレングス圧縮 (groupby)
* @docs docs/util/groupby.md
*/

template <typename Container>
auto groupby(const Container &vec) {
    assert(vec.size() != 0);
    vector<pair<remove_const_t<remove_reference_t<decltype(vec.front())>>, int>> ret;
    int piv = -1;
    for (auto &e : vec) {
        if (piv == -1 or ret[piv].first != e)
            ++piv, ret.emplace_back(make_pair(e, 1));
        else
            ++(ret[piv].second);
    }
    return ret;
}

Back to top page