c++ - 以 C++ 元编程风格实现 RLE 算法

Question

我已经为 RLE(运行长度编码)实现了一个简单的递归算法。

代码:

#include <iostream>
using namespace std;

template <size_t N>
struct RLE {
    static size_t cnt;

    static void Compress(char const p[]) {                
        // Check current char with next char. If they are not same then print the current character and its count. Then reset the counter to 0 for next itetation.
        if (!(*p == *(p + 1))) {
            cout << cnt << *p;
            cnt = 0;
        }
        // Call the function again with new character
        RLE<N - 1>::Compress(p + 1);
    }
};

template <size_t N>
size_t RLE<N>::cnt = 1 + RLE<N - 1>::cnt;

template <>
struct RLE<0> {
    static size_t cnt;
    static void Compress(char const[]) {
    }
};;

//template<>  // On uncomenting this like why do I get a error "extraneous template<>, in declaration of variable cnt."
size_t RLE<0>::cnt = 0;

int main(void) {
    char const str[]{"mmatsss"};

    // -1 since sizeof includes terminating null char.
    RLE<sizeof(str) - 1>::Compress(str);
}

对于像“mmatsss”这样的输入，预期输出是“2m1a1t3s”，但我得到的是“1m1a1t1s”，即代码只打印组的第一个字符。我无法找出代码中的错误。有人可以看一下它，并帮助我了解我在这里做错了什么。

Answer 1

I am unable to figure out the bug in the code, can someone please take a look at it, and help me to understand what am i doing wrong here.

问题是你初始化静态成员cnt如下

template <size_t N>
size_t RLE<N>::cnt = 1 + RLE<N - 1>::cnt;

size_t RLE<0>::cnt = 0;

所以你得到cnt == N , 当编译器使用 RLE<N - 1>::cnt值已初始化(g++ 案例)，cnt == 1什么时候N > 0 ，当编译器对 RLE<N - 1>::cnt 使用零时(clang++ 案例)。

我不知道谁是对的，但关键是当你写的时候

        cout << cnt << *p;
        cnt = 0;

你打印cnt在 RLE<N> -- 所以 N或 1 ，根据情况——你将 cnt 设置为零在 RLE<N> .

但是当您将 cnt 设置为零时在 RLE<N> , cnt在 RLE<N-1>保持不变(因此 N-1 或 1 ，视情况而定)。

我在您的代码中没有看到太多的元编程，但在我看来，可能的更正设置为所有 cnt到 1

template <size_t N>
size_t RLE<N>::cnt = 1;

size_t RLE<0>::cnt = 1;

并设置RNE<N-1>::cnt作为cnt + 1在 Compress()

static void Compress(char const p[])
{                
    if (!(*p == *(p + 1)))
    {
        cout << cnt << *p;
        cnt = 0u;
    }

    RLE<N - 1>::cnt = cnt+1u;  <---  add this line

    RLE<N - 1>::Compress(p + 1);
}

但是，坦率地说，我更喜欢您的原始(不是元编程)代码。