最近在看PyTorch源码时被C++模版给”恶心“到了，在死磕模版的路上，又遇到重载决议这个拦路虎。恰好在刷B站时看到这个视频CppCon 2021 Back To Basics: Overload Resolution，感觉讲的还不错，顺便记录下来。
一、前景知识（overload vs overide）
在讨论重载决议之前，我们需要先区分一些相似但完全不同的术语和概念。
1、多态的定义
overload和override大家讨论的非常多，为了理解它们之间的区别，我们需要回顾一下多态的概念，简单来说，多态是指某个事物具有多种形式，在计算机科学中，当我们处理一件事情具有多种可能性时，便需要用到多态。
2、编译期多态
在C++中，编译期多态出现在某个函数、方法或构造器的overloading过程，编译器在编译期间根据数据类型选择应该被执行的正确函数/方法。
3、运行期多态
当你override(重写)一个类方法，在运行期会根据对象类型（子类还是父类）选择执行正确的方法。
4、函数、方法和构造器重载
这几个概念非常相似，也经常容易被弄混，但它们的应用场景完全不同。在接下来的内容中，函数、方法或构造器重载都统一用函数重载表示，因为同一规则能普遍适用。
5、类方法重写
使用方法重写（method override）意味着在你的代码中存在继承关系，并且某个子类和基类有同名方法。这种编程方式更像是经典的面向对象技术，其中涉及到虚方法和方法覆盖，这与本次的主题——重载决议（overload reselution）毫不相关。
6、运算符重载
运算符重载是另一个容易混淆的概念，在给定数据类型的情况下，将为特定的运算符调用不同的运算符函数，比如你声明一个类方法叫做operator+，事实上这就是它的名称。运算符重载总是以单词operator开头，后面跟加号等符号。operator+方法可能是用于对两个数字求和，也可能用于拼接两个字符串，这完全取决于给定的数据类型。运算符重载的机制是使用重载决议取寻找合适的方法实现。因此，当我们对重载决议有更深的理解之后，也就有能力更高效的使用运算符重载并理解其背后的工作机制。
二、为什么需要重载决议
为什么我们需要重载决议呢？重载发生在当某个调用在可见域内有多个同名函数时，比如下面的例子doFunction，当只有参数类型不同时，不需要写多个函数以避免混乱，直接调用doFunction，让编译器决定哪个正确的重载应该被调用。
doFunction("mountain")
doFunction(17)
三、重载函数的声明
被重载的函数具有以下特点：
- 具有相同的名称
- 在作用域内可见
- 具有不同的参数类型集合
而且，重载函数声明的顺序没有意义，不影响重载决议的过程（在早期的C++标准中，重载函数声明顺序似乎有影响）。
四、什么是重载决议
重载决议是选择最合适重载函数的过程，编译器必须在编译期间决定调用哪个重载函数。在这个过程中只能考虑两条信息：被传入参数的数据类型和重载函数声明所定义的接收参数数据类型。即只能查看参数类型，不能考虑参数的值。如果在重载决议过程中编译器无法选择出某个特定的重载函数，将会抛出ambiguous错误。
重载决议过程中一个额外的复杂性就是：模版函数和模版方法也可以参与重载决议。如果两个重载函数是等价的，则非模版版本要优先于模版版本。
五、声明重载函数何时会失败
-
两个函数仅有返回值不同
事实上，仅有返回值不同的函数不会都参与编译，因为返回值的使用是可选的，不一定非得使用，编译器只会认为这个函数被多次定义。 -
两个函数仅有默认参数的值不同
同样不会都参与编译，默认值的不同不足以使函数签名不同。 -
两个类方法签名相同，一个被定义为static
也不属于重载，不会都编译
六、重载决议的过程概览
当你有重载函数时，编译器需要找到一种机制，用于确定要调用哪个函数。大多情况下，结果会和你预期的一样。但情况也可能变的非常复杂：
- 数据类型转换的复杂性
- 包含指针/引用类型时，结果可能与预期的不同
- 函数模版在参数推导时可能会出现奇怪的现象
- 如果编译器选择的重载函数与你预期的不同，调试也会很困难
虽然这些情况很复杂，但作为C++程序员，你真的需要做到这一点，因为在你职业生涯的某一时刻，一定会遇到这些复杂的情况，你需要弄清楚为什么编译器要如此决策。
七、重载或模板的使用选择
什么时候该用重载而不是模板？这是一个非常有趣的问题。
-
当函数实现随着数据类型的变化而变化时，应该使用重载
example：标准库std::string的构造函数 -
当函数实现不随着参数类型变化而变化时，应该使用模版
example：std::sort( data.begin(), data.end())
八、相关C++标准
在我们正真了解重载决议之前，我想要提一下C++标准。以下是重载决议内容分别在C++17和C++20标准的具体章节。
(1) C++ 17 defines overload resolution in clause 16 (32pages)
- name lokup, argument dependent lookup (44pages)
- fundamental types (33pages)
- value categories (31pages)
- declarations (45pages)
- standard conversions (15pages)
- user defined conversions (25pages)
- template argument deduction (80pages)
- SFINAE (35pages)
- special member functions (30pages)
(2) C++ 20 defines overload resolution in clause 12 (35pages)
你可能会问，为什么我需要知道user defined conversions或SFINAE这些C++标准？因为这是重载决议过程中的一部分，我们将会研究这些部分在重载决议中发挥怎样的作用。
九、进入重载决议之前的工作
在进入重载决议之前，编译器必须先进行name lookup（名称查找），这是一个找到当前可见域内所有函数声明的过程。听起来很简单，但它可能需要查找很多命名空间，还可能涉及依赖参数的查找（argument dependent lookup），因此名称查找将涵盖的名称空间列表可能是相当大的。如果在此过程中找到任何函数模版，编译器可能还要进行模版参数推导，以便完成整个过程后更好的进行模版实例化。
现在我们有一个可见函数声明的列表，称之为overload set（重载集合）。
十、重载决议的细节
重载决议的第一步是获取整个重载集合，并将它放到候选列表中（candidates），第二步编译器将会删除所有无效的候选函数，在标准中称作“not viable”（了解这个术语很有用，因为其经常出现在编译器给出的错误信息中）。
1、What Makes a Candidate Not Viable or Invalid
那么问题就来了，到底什么使候选函数可行（viable）或无效（not viable）呢？有两个原因可能导致候选函数在第一步被淘汰：
（1）传入的参数数量与候选函数的声明不匹配
当传入的参数数量多于候选函数的参数数量，该候选函数为不可选。当传入参数数量少于候选函数的参数数量时，只有当多传的参数均为候选函数的默认参数时，候选函数才可选。比如下面这个例子，只有candidate B是可选的。
doThing(38)
void doThing() // candidate A
void doThing(int, bool=True) // candidate B
（2）编译器无法转换传入数据的数据类型使其与函数声明相匹配，即使考虑隐式转换
doTing(38);
void doThing(); // too many arguments
void doThing(int); // valid
void doThing(std::string); // there is no conversion available to convert an int to std::string, so this candidate is invalid and not viable
2、寻找最佳重载的过程
继续我们重载决议的过程，现在我们已经找到了重载集合，并删除了其中无效的候选者。接下来我们要做的就是对剩余的候选者进行排名，而这正是编译器寻找最佳匹配的过程（最佳匹配也许是最不差的匹配）。在排名之后，如果仅有一个候选者排名最高，那它将获得重载决议的胜利，但是如果有多个候选者都排名最高，那将进入一个额外的过程即决胜局（tiebreaker），这个过程非常复杂，使用了大量的标准试图选择一个最合适的候选者。
3、类型转换（Type Conversions）
在查看编译器如何对候选者进行排序之前，我们需要先了解类型转换的基本思想，因为类型转换在排序过程中至关重要。
（1）类型转换是将值从一种数据类型转换到另一种数据类型的过程。标准中有许多可用的转换（根据您自己的代码库，还可以有更多的转换）
- int to float
- string literal to pointer
- enum to int
- timestamp to long
- int to string
- char* to void*
- type X to type Y (depending on your code base)
doThing(38) // passing an int
void doThing(float) // receving a float using an implicit conversion
上面这个例子，调用doThing的地方传入的是一个int值，但我们只有一个doThing的声明，其接收的参数类型是float，因此这里会执行一个隐式转换。
（2）隐式转换
我们经常会使用到隐式转换，比如下面的例子中，从字符数组中获取第一个字符将其赋值给一个int变量。
char str[] = "ABC";
int data = str[0]; // data will equal 65
（3）显示转换
与隐式转换对应的有显示转换，例如static_castm, dynamic_cast, reinterpret_cast 或 c style cast，除此之外还有一种称之为 functional cast 的显示转换。
4、标准转换的分类（从上到下ranking）
现在我们开始讨论排名，在排名中需要查看各种标准转换，总共有五类：
(1) exact match
- no conversion is required
(2) lvalue transformations
- lvalue to rvalue conversion (based on value categories)
- array to pointer conversion
- function to pointer conversion
(3) quanlification adjustments
- quanlification conversion (adding const or volatile)
- function pointer conversion (new in C++ 17)
(4) numeric promotions
- integral promotion
- floating-point promotion
(5) conversions
- integral conversion
- floating-point conversion
- float-integral conversion
- pointer conversion
- pointer-to-member conversion
- boolean conversion
虽然看起来有点怪，完全匹配理应是没有转换，但实际上它是类型转换的第一个标准。不需要记住这些转换，只需要记住它们之间也有排名。后面我们会介绍这些类型转换的排名具体发生在哪里。
Qualification Adjustments (categoriy 3)
下面主要介绍第三类quanlificastion adjutments。所谓quanlificastion adjutments是指编译器将const或volatile添加到指针数据类型时所调用的过程。在下面的试例中，编译器会为candidate A执行quanlificastion adjutments，因此candidates A也是有效候选者。但由于candidate B是完全匹配，因此candidates B将会被最终选择。
example 1:
std::string * myString = new std::string("text");
int value = lookUp(myString);
int lookUp(const std::string * key); // candidate A
int lookUp(std::string * key); // candidate B
// both viable, but the candidate B is exact match
在下面的example 2中，哪个候选者将会被调用呢？
example2:
void doThing2(char value) //overload A
{}
void doThing2(long value) //overload B
{}
int main() {
doThing2(42); //which overload is called ? ----> ambiguous (compile error)
}
Numeric Promotions(category 4)
上述的example2中，估计很多人会猜overload B将会被调用，但事实却是，编译器抛出了ambiguous错误。这确实是个令人惊讶的重载决议结果，为了了解其原因，我们需要深入研究下标准。
(1) integral promotion
- short to int
- unsigned short to unsigned int or int
- bool to int (0 or 1)
- char to int or unsigned int
- a few more however it must be defined in the standard
(2) floating point promotion
- float to double
回忆前面的conversion类型和顺序，integral promotion的顺序要比int conversion高，因此example2优先选择interal promotion，integral promotion有多种，它们在标准中有明确定义（上述列出来，floating promotion只有一个float to double）。从标准的定义中可以总结出一个基本原则：所有比int小的整数类型都可以提升为int，但不可以提升为long或long long。提升的定点停在了int。所以example2中int to long不是标准规定的promotion，而是conversion。
integral conversion (category 5)
- integral data types are defined by the C++ standard
- example: bool, char, short, int, long
- if the standard defines converting between integral type A and integral type B is a promotion, it is a conversion
example 3:
void count(long value); // int to long conversion, valid candidate
int main() {
count(42);
}
虽然不存在int到long的promotion，但并不表示参数为long的函数不能被调用。example3展示了这样的示例，虽然做不了promotion，但存在int到long的conversion。
5、排名顺序中类型转换的完整列表
在前面我们说过一共有五类标准的类型转换，其实还有另外两种发生在排名过程中，即下面将要介绍的用户定义类型转换，其出现的次数比你想象的要多，还有省略号转换，这个出现的次数可能比你想象的要少。
(1) no conversion(1-3)
- exact match, lvalue transformations, qualification adjustments
(2) numeric promotion (4)
- integral promotions, floating point promotions
(3) numeric conversion (5)
- integral, floating point, pointer , boolean
(4) user defined conversion
- convert a const char * to an std::string
(5) ellipsis conversion
- c style varargs function call
6、用户定义类型转换（User Defined Conversion）
在排名过程中，用户定义类型转换（User Defined Conversion）的排名要低于其他标准转换，令人惊讶的是，用户定义类型转换可以是转换成或转换自任何类数据类型，这就意味着这些类的声明可以位于任何标准库或第三方库中（即使在std库中，也被认为是用户定义类型转换）。因此，在下面这个调用中，我们将一个const字符指针传递给showMsg函数，showMsg被声明为接收一个std::string类型字符串，这是一个有效的候选对象，因为std::string的构造函数可以执行隐式转换以接收consd字符指针，但这是一个用户定义类型转换，如果我们再声明一个接收void参数的showMsg函数，则这个接收void参数的showMsg会赢得排名。听起来这很糟糕，可能违背了你的意愿，但这就是排名的标准规则。
example 4:
void showMsg(std::string value) {} // valid candidate。 But it is a user-defined conversion, it's worse than any other standard conversion if we were to add an overload that say took a void start that would win.
int main() {
const char * msg = "Text";
showMsg(msg);
}
7、选择一个候选函数
前面提到过，如果排名后有多个候选函数都排名最高，便会进入决胜局（tiebreaker），决胜局是重载决议的最后一步，用于选出最佳的匹配函数，虽然并不经常出现，但仍需了解它。
当决胜局中出现一个非模版候选者和模版候选者时，非模版候选者将会获胜。还有个重要的点便是，当决胜局中出现隐式转换时，那些花费更少步骤的隐式转换将会获胜（后面的example6会说明这一点）。最后，如果在决胜局中仍然选不出最佳匹配者，编译器将会抛出一个编译错误。
（在C++20增加了新的决胜局规则，主要和新功能concept相关，暂时跳过… …）
十一、重载决议如何debug
（1）当候选函数中找不到最佳匹配时
当函数调用出现ambiguous call 时该如何解决？下面有一些trics能帮到你：
- add or remove an overload
- mark a constructor explicit tp prevent an implicit conversion
- template functions can be eliminated through SFINAE (template functions which can not be instantiated will not be placed in the candidate set)
- convert arguments before the call, using an explicit conversion (static_cast<> a passed argument; explcitly construct an object; use std::string(“some text”) rather than pass a string literal )
example 5 :
void doThing5(char value) // not a viable candidate
{}
int main() {
doThing5('x', nullptr);
}
在example 5将会抛出编译错误信息“no matching function for call”。错误信息将会列出可能的候选函数，即使当中没有可选（viable）的。
（2）当最佳匹配不符合你的预期时
- overload resolution can be complicated to debugsince there is no clean way to ask the compiler why it chose particular overload
- it would be helpful if compilers provided a verbose mode
- by intentionally adding an ambiguous overload to the candidate list, the resulting error message may help in deciphering why
- try changing the data type of some passed argument
example 6:
// A
void doThing_A(double, int, int) { } // overload 1
void doThing_A(int, double, double) {} // overload 2
int main() {
doThing_A(4, 5, 6); // which verload is called ? ---> ambiguous (compile error)
}
// B
void doThing_B(int, int, double) {} // overload 3
void doThing_B(int, double, double) {} // overload 4
int main() {
doThing_B(4, 5, 6); // which overload is called ? ---> overload 3 wins
}
// The reasoning for this is a little bit subtle and it is because multiple arguments are considered one at a time in the overload resolution process, so if you look at example A we look at the first argument, overload 1 loses so it can't be the best match. Then if we look at the second argument, overload 2 loses so it can't be the best match. So there is no candidate in first place, so the call is ambiguous.
// On the other hand, on example B if we look at the first argument they're equivalent so they could both be the best match, when we look at the second argument, overload 3 wins, so it remains in consideration and then we look at the third arguments they are again tied, so overload 3 wins because it won at least one argument and was no worse on the others. This is very useful to know when you have multiple parameters.
（Notice：关于example6中doThing_A的重载结果，视频中的解释没太听懂，主要是多个参数进行排序的原则，我仔细查了一下标准Best_viable_function，当中有这样一条要求：若要判定F1函数比F2更好，F1所有参数的隐式转换都不能比F2所有参数的隐式转换更差。因此，当编译器检查到overload1和overload2的第二个参数时，这两个重载函数已经不可能满足这项要求，即不存在overload1比overload2差，也不存在overload2比overload1差，也就是两个都一样差，所以是ambiguous。）
example 7:
// C
void doThing_D(int &) { } // overload 1
void doThing_D(int) {} // overload 2
int main() {
int x = 42;
doThing_D(x); // which verload is called ? ---> ambiguous (compile error)
}
// D
void doThing_E(int &) {} // overload 3
void doThing_E(int) {} // overload 4
int main() {
doThing_E(42); // which overload is called ? ---> overload 4 wins
}
在example7中，doThing_D有两个重载函数，一个接收int一个接收int的引用，而传递的参数x是左值，由于将一个左值绑定到左值引用上不属于conversion，因此overload1和overload2都是exact match，因此调用结果是ambiguous。对于doThing_E的两个重载函数，传递的是右值42，由于不存在右值到非常量左值引用的隐式转换（即不能将一个右值绑定到非常量左值引用non-const lvalue refrence上），因此overload3是not viable的候选者，都走不到ranking阶段，因此overload4是唯一胜利着。
example 8:
// F
void doThing_F(int &) {} // overload 1
void doThing_F(int &&) {} // overload 2
int main() {
int x = 42;
doThing_F(x); // which overload is called ? --> overload 1 wins
}
// G
void doThing_G(int &) {} // overload 3
void doThing_G(int &&) {} // overload 4
int main() {
doThing_G(42); // which overload is called ? --> overload 4 wins
}
对于doThing_F的两个重载，传递的是左值x，由于不支持将左值绑定到右值引用上，因此overload 1 胜利，到不了ranking阶段。
对于doThing_G的两个重载，传递的是右值42，与doThing_F的情况相反，由于不支持将右值绑定到左值引用上，因此overload 4胜利，到不了ranking阶段。
example 9 (Bonus Round) :
void doThing_9(int &) {} // overload 1, lvaue ref to int
void doThing_9(...) {} // overload 2, c style varargs
struct MyStruct {
int m_data : 5; // bitfiled, 5 bits stored in an int
};
int main () {
MyStruct obj;
doThing_9(obj.m_data); // overload 1 wins
}
---> Hang on, compile error "non const refrence can not bind to bit filed"
---> adding an overload which takes a "const int &" does not change the result
十二、总结
- understand overload resolution requires knowing more of the C++ standard than amy other feature
- learn the difference between promotions and conversions
- try to avoid mixing overloaded functions with a tenplate of the same name
- debuging an ambiguous overload error can be frustrating and time consuming
