答疑小记: C++ 中模板实例化与 RTTI 的常见误区

这问题还挺好玩的

April 2, 2024

#C++

这是北京大学信科学院《软件设计实训》课程第五周的作业题。

描述：给出函数模板 sumIf 的定义。它的首个参数为 int 类型元素的范围 $r$，第二个参数为可单参数调用的判断条件 $f$。 sumIf 返回范围 $r$ 中，满足 $f$ 条件的所有元素的和。

#include <iostream>
#include <list>
#include <vector>
// 在此处补充你的代码
int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto x = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int a[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::list<int> l{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::cout << sumIf(v, [](int i) { return i % 3 == 1; }) << std::endl;
    std::cout << sumIf(x, [](int i) { return i % 3 == 0; }) << std::endl;
    std::cout << sumIf(a, [](int i) { return i % 2 == 0; }) << std::endl;
    std::cout << sumIf(l, [](int i) { return i % 2 == 1; }) << std::endl;
}

样例输出：

后面的 lambda 表达式很好说，当参数传进去就行。关键是怎么用统一的方法遍历 std::vector std::list std::initializer_list 和普通数组。很容易写出下面的代码：

template <typename T1, typename T2>
int sumIf(T1 cont, T2 cond)
{
    int ret = 0;
    for(auto & i : cont) if(cond(i)) ret += i;
    return ret;
}

hw_5_7_1.cpp:10:5: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
   10 |     for(auto & i : cont) if(cond(i)) ret += i;
      |     ^~~
      |     std::begin

爆！但是为啥呢？

观察在第一个参数为数组时，模板的实例化结果：

int sumIf<int *, lambda [](int i)->bool>(int *cont, lambda [](int i)->bool cond)

cont 的类型被推断为 int*。再看 C++ Reference 中对 range-based for loop 的叙述：

Syntax: attr (optional) for ( init-statement (optional) range-declaration : range-expression ) loop-statement

range-expression - any expression that represents a suitable sequence (either an array or an object for which begin and end member functions or free functions are defined, see below) or a braced-init-list.

也就是说，cont 必须是一个定义了 begin end 成员函数的对象，或者是一个数组。int 指针显然不是这两者之一。因此在实例化之后，会报编译错误。

那么怎么解决呢？其实也很简单。

template <typename T1, typename T2>
int sumIf(T1 & cont, T2 cond) // ...

把 cont 的类型改为左值引用即可。这样实例化的结果为：

int sumIf<int [10], lambda [](int i)->bool>(int (&cont)[10], lambda [](int i)->bool cond)

cont 推导出的类型为 int [10]。这样就可以编译了。

在遇到第一种编译错误的时候，也很容易想到依据不同的参数类型调用不同的代码，于是会狗急跳墙地写出类似这种的代码（这是问我问题的同学写的）：

#include <typeinfo>
using namespace std;
template <typename T1,typename T2>
int sumIf(T1 cont,T2 cond)
{
    int ret=0;
    if(typeid(T1)==typeid(int[10])){
        for(int i=0;i<10;i++){
            if(cond(cont[i])) ret+=cont[i];
        }
    }
	if(typeid(T1)==typeid(std::vector<int>)||typeid(T1)==typeid(std::list<int>)||typeid(T1)==typeid(std::initializer_list<int>)){
        for(auto i=cont.begin();i!=cont.end();i++){
            if(cond(*i)) ret+=*i;
        }
    }
	return ret;
}

这个思路很容易理解，利用 typeid 判断进入哪个分支，对数组（从上文了解到，其实是指向数组开头的指针）和 STL 容器采用不同的遍历方式。这对吗？

事实上是爆了的，并且报错跟之前完全一致。为啥呢？

你猜猜他为啥叫 RTTI？Run-Time Type Identification，运行时类型识别。也就是说，typeid 的判断是在运行时，而不是在编译期。而模板的实例化发生在编译期。从而，无论 typeid 的判定结果为何，编译器都会生成 if 语句的所有分支。所以这里依据类型选择不同分支的代码分别编译的想法是不可能的。

那或许可以利用模板偏特化来干这件事情吗？在实例化阶段，根据不同的模板参数编译不同的代码。

error: non-class, non-variable partial specialization 'f<T1, T2, true>' is not allowed

你说得对，但是模板偏特化不能对函数模板进行。这是为啥呢？

其实所谓的“函数模板偏特化”就是函数模板的重载。既然重载就可以完成需要的工作，就没有必要再定义一个偏特化的行为了。容易写出下面的代码：

template <typename T1, typename T2>
int sumIf(T1 cont, T2 cond)
{
    int ret = 0;
    for(auto & i : cont) if(cond(i)) ret += i;
    return ret;
}

template <typename T2>
int sumIf(int * cont, T2 cond)
{
    int ret = 0;
    for(int i = 0; i < 10; i++) if(cond(cont[i])) ret += cont[i];
    return ret;
}

过了。