Run Length Encoding
(algo/sequence/run_length_encoding.hpp)

• View this file on GitHub
• Last update: 2026-07-07 21:49:48+09:00
• Include: #include "algo/sequence/run_length_encoding.hpp"

Overview

Compresses consecutive equal values into (value, count) pairs. It works with containers such as std::vector and std::string.

Functions

Function	Description	Complexity
run_length_encoding(container)	Returns vector<pair<T, long long>> for consecutive runs.	$O(N)$

Example

#include "algo/sequence/run_length_encoding.hpp"
#include <string>

int main() {
    std::string s = "aaabbc";
    auto runs = m1une::algo::run_length_encoding(s);
    // ('a', 3), ('b', 2), ('c', 1)
}

Required by

• Algorithms All (algo/all.hpp)
• Sequence Algorithms All (algo/sequence/all.hpp)

Verified with

• verify/algo/sequence/sequence_algorithms.test.cpp

Code

#ifndef M1UNE_ALGO_SEQUENCE_RUN_LENGTH_ENCODING_HPP
#define M1UNE_ALGO_SEQUENCE_RUN_LENGTH_ENCODING_HPP 1

#include <iterator>
#include <utility>
#include <vector>

namespace m1une {
namespace algo {

template <typename Container>
auto run_length_encoding(const Container& values) {
    using T = typename Container::value_type;
    std::vector<std::pair<T, long long>> result;

    auto it = std::begin(values);
    auto last = std::end(values);
    if (it == last) {
        return result;
    }

    T current = *it;
    long long count = 0;
    for (; it != last; ++it) {
        if (*it == current) {
            ++count;
        } else {
            result.emplace_back(current, count);
            current = *it;
            count = 1;
        }
    }
    result.emplace_back(current, count);
    return result;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEQUENCE_RUN_LENGTH_ENCODING_HPP

#line 1 "algo/sequence/run_length_encoding.hpp"



#include <iterator>
#include <utility>
#include <vector>

namespace m1une {
namespace algo {

template <typename Container>
auto run_length_encoding(const Container& values) {
    using T = typename Container::value_type;
    std::vector<std::pair<T, long long>> result;

    auto it = std::begin(values);
    auto last = std::end(values);
    if (it == last) {
        return result;
    }

    T current = *it;
    long long count = 0;
    for (; it != last; ++it) {
        if (*it == current) {
            ++count;
        } else {
            result.emplace_back(current, count);
            current = *it;
            count = 1;
        }
    }
    result.emplace_back(current, count);
    return result;
}

}  // namespace algo
}  // namespace m1une

Back to top page