c++ - 两个类型列表是否可以在恒定时间内拼接？

Question

我正在使用 Alexandrescu 的现代 C++ 设计中定义的类型列表。在他的书中，他谈到了 Appending a type to a typelist，但他没有谈到拼接两个类型列表......

我想可以使用 Append 功能拼接两个类型列表，但这不会导致线性时间拼接(而 std::list::splice 是 O(1) )。 ？

好吧，我知道这个计算时间可以被认为是“免费”的，因为它是编译时间，但我很好奇:)

谢谢!

Answer 1

类型列表的概念通常* 比 std::list 的(双向)链表更接近计算机科学中的列表概念。这两个想法同名，但有重要区别。

由于元程序是纯函数式的，因此您不能像 std::list::splice 那样就地修改输入类型列表:您必须“生成”输出类型列表，这将是线性的。 (然而，惰性可以用来推迟和减少该成本；支付的确切成本将取决于最终算法。)

*:我说通常是因为 Boost.MPL 支持迭代器和 View 之类的东西，这模糊了界限，至少从用户的角度来看是这样。

(为了论证，假设这里的“CS”列表是指 cons 单元格 + 空列表。)