std::tuple中使用std::get的效率问题

Question

我很好奇调用 std::tuple<> 上的 std::get<> 方法所需的查找时间。简短的谷歌搜索（包括通常有此信息的参考页面）没有得到结果。

我的初步直觉（和担忧）是，如果元组被实现为可变参数模板，则元组的递归结构将导致 get 需要 N 次查找（调用 get<3>(t) 看起来像 t.rest().rest().first()）。但愿我这里完全错了...

另一方面，我希望编译器能够优化此过程，直接返回正确的偏移量，而不需要 N 次调用的开销。

基本上我想知道：是否有规定的运行时保证？这会限制如何实现 std::tuple 吗？

- anthony sottile

Answer 1

效率将与访问结构体成员类似。get<> 在编译时解析。

- David Rodríguez - dribeas

---

可以给我指一下规范吗？你能详细解释一下吗？是什么使这成为可能？内联吗？ - anthony sottile

我没有看到标准中有任何要求高效实现std::get<>的内容，我可以想象出合理的原因来解释为什么它可能不是高效的（例如调试）。 - user743382

标准中并没有要求任何东西必须被“高效地”实现（即使O(1)操作也可能被低效实现）。如果你花费大量时间来反复推测编译器或标准库的实现，你将无法真正完成太多工作。在经过优化的构建中，可以合理地期待内联和RVO使调用只是一个结构体访问。 - Nicol Bolas

@NicolBolas 考虑到问题明确要求“是否有运行时保证”，如果规范没有保证这个答案所声称的内容，那么这不是一个答案，但出于你提供的原因，它将成为另一个问题的有用答案。 - user743382

哦，我明白你现在所说的需要运行时转换了...不过我仍然认为这是纯粹的编译时操作。 - Jonathan Wakely

Answer 2

C++规范并未保证任何函数的运行时性能。即使它给出了渐近需求，这也只保证操作的相对数量，而不是这些操作的性能。O(1)并不意味着快速，O(n)也不意味着缓慢。

你可以选择相信编译器/优化器/标准库实现，或者自己重写代码以达到所需性能。在大多数合理的编译器（开启优化）下，std::get 的性能应该与直接从结构体访问值的性能基本相同。但是规范从未要求过这一点。

- Nicol Bolas

---

这里的标准相关部分是 **1.9 程序执行 [intro.execution]**。“1 本国际标准中的语义描述定义了一个参数化的非确定性抽象机。本国际标准对符合要求的实现结构没有任何要求。特别地，它们不需要复制或模拟抽象机的结构。相反，符合要求的实现需要模拟（仅）下面解释的抽象机的可观察行为。” - TemplateRex

Answer 3

第一个问题的答案（std::get需要多长时间）取决于您的库如何选择实现std::tuple和std::get。但通常，库将选择使用非递归方法，类似于此处概述的方法：http://mitchnull.blogspot.com/2012/06/c11-tuple-implementation-details-part-1.html。使用这种方法，访问std::get的时间将保持恒定，并且大致相当于访问结构体成员所需的时间。

至于标准是否提供任何保证：正如其他人所说，标准在这里没有提供任何保证。一个邪恶的库编写者可以选择使std::get呈N的指数增长，他们仍然符合标准。

- Edward Loper