Constructor/Function 重载签名查找时间复杂度？

Question

我正在阅读 C++ 中的 std::string class 并注意到有很多不同的构造函数可用，为我们提供了广泛的初始化功能。这让我想知道编译器如何在给定参数时选择要选择的构造函数，或者在重载的情况下，编译器如何将函数签名与给定的参数集匹配。

如果我们在伪代码中声明了以下函数：

function f1(int numberHere) {
    //....do something
}

function f1(int numberHere, string stringHere) {
    //....do something
}

而我决定调用f1(4)，显然有两个选项可供选择，但是如果有10000个options/signatures呢？会按比例花费更长的时间吗？如果是这样，什么需要更长的时间？编译器是否有一些偷偷摸摸的 O(n) 索引重载的方法，以便它可以在 O(1) 时间内调用正确的程序，一旦程序运行ning 或者它会在 O(1) 中编译无论存在多少重载，但由于实时签名匹配需要更长的时间运行完成结果？

这个问题还能有效回答吗？

谢谢！

Answer 1

匹配函数签名实际上与任何其他搜索或查找问题没有什么不同。根据您存储可用函数签名的数据结构，可以采用三种基本方法：

使用未排序的列表或数组并获得 O(n) 时间复杂度。
使用排序数组或树状结构并获得 O(log(n))。（您可以按第一个参数的类型排序，然后是第二个，依此类推，假设每个类型都分配了一个整数 ID。）
使用哈希映射并获得 O(1)。

但我怀疑时间复杂度在这种情况下有任何实际意义。它描述了算法对大 n 值的渐近行为。即使对于 n=100，未排序的数组搜索也可能比哈希映射查找更快，因为它的开销更少。

从可用性的角度来看，设计一个 API 具有 10 甚至 100 个重载的函数是一个非常糟糕的主意。

Constructor/Function 重载签名查找时间复杂度？

Constructor/Function overload signature lookup time complexity?

language-agnostic

constructor

overloading

compilation

initialization