Являются ли два списка типов сращиваемыми в постоянное время?

Question

Я немного работаю со списками типов, определенными в Modern C ++ Design Александреску.В своих книгах он говорит о добавлении типа в список типов, но он не говорит о соединении двух списков типов ...

Я думаю, что возможно объединить два списка типов, используя функцию Append, но неЭто приводит к линейному сплайсингу (тогда как std :: list :: splice равно O (1)).?

Ну, я знаю, что это время вычислений можно считать «свободным», так как это время компиляции, но мне любопытно:)

Спасибо!

Answer 1

Концепция списка типов обычно * ближе к понятию информатики списка, чем (вдвойне) связанный список, которым является std::list.Эти две идеи имеют общее имя, но имеют принципиальные различия.

Поскольку метапрограммы являются чисто функциональными, вы не можете изменять на месте входной список типов, как это делает std::list::splice: вы должны «сгенерировать» выходной список типов (s), который был бы линейным.(Однако лень можно использовать для отсрочки и снижения этой стоимости; точная стоимость будет зависеть от окончательного алгоритма.)

*: Я обычно говорил, потому что Boost.MPL поддерживает такие вещи, как итераторы и представления, которые размываетсястрока, по крайней мере, с точки зрения пользователя.

(Ради аргумента предположим, что под списком "CS" здесь я имел в виду ячейку cons + пустой список.)