经常引用 C++s std::variant性能比其他语言的变体差。参见例如https://pbackus.github.io/blog/beating-stdvisit-without-really-trying.html
原因之一是 exception状态，另一个据说是标准的要求std::visit复杂性 does not depend on the number of types这迫使实现者使用函数指针的调度表，这会抑制某些优化，如内联。
问题:
- 实现
std::visit是否合法？作为if-elseif的链条每张支票都像if(v.index() == I) return visitor(get<I>(v));？似乎不是，因为调度到更高的索引需要对索引进行更多检查。 - 用
switch(v.index()) case I: return visitor(get<I>(v));这样的开关实现它合法吗？ ？这看起来像“独立于类型的数量”，因为控制流直接跳转到案例，例如Microsoft 为少于 64 种(或更多)类型实现了它。 - 如果开关是合法的，那么优化器将小开关转换为 if-elseif 阶梯是否合法？ MSVC 编译器再次执行此操作:https://godbolt.org/z/D2Q5ED .但是 IMO 这违反了标准规定的“独立于类型数量”的复杂性，尽管它在实践中会更快。
我问的是基于 reddit 上有人声称 "Constant time" again refers to the behavior in the limit. 的讨论我真的不同意。 IMO“恒定时间”意味着无论输入哪个if-elseif，时间都是恒定的-链不是这样的。
但我不确定这在此处如何适用。似乎 1. 是非法的，2. 是合法的，但优化器(可能)将其转换为 1. 这意味着 2. 也是非法的。至少如果严格遵守标准。
最佳答案
您混淆了时间复杂度和运行时间。参见示例 here .
话虽这么说，但在谈论复杂性时，重要的是要了解“恒定时间”和“不依赖于”等语句的含义:在这种情况下，它们都是 O(1)< 的同义词/em>。因此，reddit 评论中的说法确实是正确的。
在 visit 的情况下，这意味着存在一些常量 C，使得 visit 永远不会超过 C cpu 周期，即使对于疯狂数量的类型变体。特别是，当然允许保持在这个数字 C 以下。
因此，实际回答您的问题:使用 if-else if 链 exclusively 通常具有线性(即 O(n) ) 复杂性，正如您正确陈述的那样。因此，除非实现者知道编译器会将其优化为常量，否则这是非法的。
switch 很可能会被编译成一个跳转表，其运行时间复杂度为 O(1)。如果 case 是后续数量的整数，这尤其可能发生，就像这里的情况一样。因此，使用 switch 的实现应该是合法的。但是请注意，对于困难的 case 分布，switch 将被编译为 O(log n) 的二进制搜索。参见例如 here .
最后，考虑到我之前所说的，当然允许应用任何类型的优化，只要这不会将算法移至更差的复杂性类别。即使这意味着实际运行时间确实取决于类型的数量，时间复杂度也不会。
更新:
根据您的意见，让我给您一个函数示例，该函数复杂性，独立于 n(也称为“常量”或 O(1 )) 而实际运行时间当然取决于n:
int get_max_of_first_50(std::vector<int> const& v)
{
int max = std::numeric_limits<int>::min();
for (int i = 0; i < 50; ++i)
if (v[i] > max)
max = v[i];
return max;
}
无论 v.size() 有多大，此函数将始终进行 50 次或更少的迭代。因此，在复杂性方面，它被归类为常量 算法，独立于 n 或 O(1)；所有三个语句都是等价的。
这可能看起来像作弊，在某种程度上我可以理解这个推理，但重要的是要理解这就是为什么首先以这种方式引入复杂性的原因:
- 允许在算法分析中进行某些简化。否则很容易变得非常困难
- 只关心巨大的投入。通常，没有人关心某件事是在 5 毫秒还是 10 毫秒内完成。但 5 天与 10 天确实很重要。
顺便说一句，这种“作弊”方式很常见。另一个著名的例子是 std::sort 的实现。基本上，我听说过的大多数库实现都使用 Quicksort(有一些技巧，所以即使在最坏的情况下也是 O(n log(n)))。但是对于小序列，他们通常会切换到插入排序，这在非常小的范围内被证明更快，即使它本身是一种复杂度为 O(n^2) 的算法。但是正如已经解释的那样，从复杂性的角度来看，只要它的用法受常数约束就可以了。而从实际运行时间来看，当然也好，速度更快。
关于c++ - 哪些实现符合 std::visit 的恒定时间调度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58625565/