c++ - 使用新模板参数递归调用模板化函数

Question

我正在尝试用 C++ 实现一些功能结构。想要实现将列表的列表扁平化到任意数量级别的功能。

template<typename T, typename R>
struct Fold{
    typedef R(*func)(T, R);
};


template<typename T>
T head(std::list<T> const& list) {
    return list.front();
}

template<typename T>
std::list<T> tail(std::list<T> list) {
    list.pop_front();
    return list;
}

template<typename T>
std::list<T> cons(T head, std::list<T> tail){
    tail.push_front(head);
    return tail;
}

template<typename T, typename ACCUM>
ACCUM foldl(typename Fold<T, ACCUM>::func function, ACCUM accum, std::list<T> list) {
    if(list.empty())
        return accum;

    return foldl(function, (*function)(head(list), accum), tail(list));
}

template<typename T, typename ACCUM>
ACCUM foldr(typename Fold<T, ACCUM>::func function, ACCUM accum, std::list<T> list) {
    if(list.empty())
        return accum;

    return (*function)(head(list), foldr(function, accum, tail(list)));
}

template<typename T>
std::list<T> reverse(std::list<T> list){

    struct LAMBDA{
        static std::list<T> reverse(T t, std::list<T> tList){
            return cons(t, tList);
        }
    };

    std::list<T> revTList;
    return foldl( static_cast<typename Fold<T, std::list<T>>::func>(&LAMBDA::reverse), revTList, list); 
}

template<typename T>
std::list<T> append(std::list<T> list1, std::list<T> list2) {
    struct LAMBDA{
        static std::list<T> append_lambda(T t, std::list<T> list){
            return cons(t, list);;
        }
    };

    return foldl( static_cast<typename Fold<T, std::list<T>>::func>(&LAMBDA::append_lambda), list2, reverse(list1));
}

template<typename T, typename Ty>
struct Flattener{
    static std::list<T> flatten(typename std::list<Ty> deepList){
        struct LAMBDA{
            static Ty flatten_lambda(Ty ty, Ty accum){
                return append(ty, accum);
            }
        };
        Ty ty;
        Ty flat = foldr( static_cast<typename Fold<Ty, Ty>::func>(&LAMBDA::flatten_lambda), ty, deepList);
        return Flattener::flatten(flat);
    }
};

template<typename T>
struct Flattener<T, T>{
    static std::list<T> flatten(std::list<T> list){
        return list;
    }
};

上面的代码编译正常，但是当我尝试用

调用函数时

std::list<int> emptyList;
std::list<int> list1 = cons(1, cons(2, cons(3, cons(4, emptyList))));
std::list<int> list2 = cons(5, cons(6, cons(7, cons(8, emptyList))));

std::list<std::list<int>> emptyDeepList;
std::list<std::list<int>> deepList = cons(list1, cons(list2, emptyDeepList));
Flattener<int, std::list<int>>::flatten(deepList);

我在编译代码时遇到了这个巨大的错误:

error C2664: 'Flattener<T,Ty>::flatten' : cannot convert parameter 1 from 'std::list<T>' to 'std::list<T>'
    with
    [
        T=int,
        Ty=std::list<int>
    ]
    and
    [
        T=int
    ]
    and
    [
        T=std::list<int>
    ]
    No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
    list.h(212) : while compiling class template member function 'std::list<T> Flattener<T,Ty>::flatten(std::list<std::list<T>>)'
    with
    [
        T=int,
        Ty=std::list<int>
    ]
    main.cpp(67) : see reference to class template instantiation 'Flattener<T,Ty>' being compiled
    with
    [
        T=int,
        Ty=std::list<int>
    ]

如果我删除对 Flattener::flatten 的调用，代码将编译。

我做错了什么？ (因为我是 c++ 和模板编程的新手，所以一些解释也会很有帮助)。

编辑:

试过了。同样的错误。我想我正在做某事。

template<typename T, typename L>
struct Flattener{
    static std::list<T> flatten(L list){
        struct LAMBDA{
            static std::list<T> flatten_lambda(typename L1 l1, std::list<T> tList){
                return append(Flattener<T, L1>::flatten(l1), tList);
            }
        };

        std::list<T> tList;
        return foldl(&LAMBDA::flatten_lambda, tList, list);
    }
};

template<typename T>
struct Flattener<T, typename std::list<T>>{
    static std::list<T> flatten(std::list<T> list){
        return list;
    }
};

这是这个编译器的错误:

error C2664: 'Flattener<T,L>::flatten' : cannot convert parameter 1 from 'std::list<T>' to 'std::list<T>'
    with
    [
        T=int,
        L=std::list<std::list<int>>
    ]
    and
    [
        T=std::list<std::list<int>>
    ]
    and
    [
        T=std::list<int>
    ]
    No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called

Answer 1

AS @tMJ 指出，写作 Flattener<T, T>将使编译错误消失，但是Flattener::flatten方法将能够两个展平只有两层深的列表(实际上，当您尝试展平 m 嵌套列表时会返回错误 m >= 3 因为我们将再次遇到类型不匹配)。

为了使此列表适用于 m 级 std::list<std::list<...<std::list<int>...>>我们必须有办法找出当前 Ty 容器的元素类型。例如，如果 Ty = std::list<std::list<std::list<int>>>那么 Ty 的当前元素类型实际上是 std::list<std::list<int>> .这就是下一步递归必须设置的 Ty 类型。

幸运的是，C++ 容器如 std::list 有静态 value_type property 是模板参数的同义词 Type容器的类型(简单来说，它将返回此容器的元素类型)。了解这一点，我们可以通过以下方式解决您的问题:

template<typename T, typename Ty>
struct Flattener {
    static std::list<T> flatten(typename std::list<Ty> deepList) {
        struct LAMBDA {
            static Ty flatten_lambda(Ty ty, Ty accum) {
                return append(ty, accum);
            }
        };
        Ty ty;
        Ty flat = foldr(static_cast<typename Fold<Ty, Ty>::func>(&LAMBDA::flatten_lambda), ty, deepList);
        return Flattener<T, Ty::value_type>::flatten(flat);
    }
};

template<typename T>
struct Flattener<T, T> {
    static std::list<T> flatten(std::list<T> list) {
        return list;
    }
};

递归会停止一次T变得等于 Ty::value_type ，这将在 Ty 时发生变成 std::list<int> .此时Flattener<T, T>::flatten()将被执行并产生最终结果。

我用三重嵌套 std::list 测试了解决方案:

std::list<std::list<std::list<int>>> triple_empty_list;
std::list<std::list<std::list<int>>> triple_list = cons(deepList, cons(deepList, triple_empty_list));
std::list<int> result = Flattener<int, std::list<std::list<int>>>::flatten(triple_list);

P.S. 澄清一下，这里没有发生递归。每次调用Flattener<T,Ty>::flatten()调用 Flattener 的不同特化的静态方法类模板。