ランレングス圧縮 (lib/algorithm/rle.hpp)

View this file on GitHub
Last update: 2025-05-21 13:00:40+09:00
Include: #include "lib/algorithm/rle.hpp"

Verified with

test/aoj/joi/rle.test.cpp

Code

#pragma once
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

/// @brief ランレングス圧縮
template <class Container>
auto run_length_encoding(const Container &v) {
    std::vector<std::pair<std::decay_t<decltype(*std::begin(v))>, int>> res;
    for (auto &&e : v) {
        if (res.empty() || res.back().first != e) res.emplace_back(e, 1);
        else ++res.back().second;
    }
    return res;
}

#line 2 "lib/algorithm/rle.hpp"
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

/// @brief ランレングス圧縮
template <class Container>
auto run_length_encoding(const Container &v) {
    std::vector<std::pair<std::decay_t<decltype(*std::begin(v))>, int>> res;
    for (auto &&e : v) {
        if (res.empty() || res.back().first != e) res.emplace_back(e, 1);
        else ++res.back().second;
    }
    return res;
}