Можно ли соединить два списка типов за постоянное время?

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

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

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

Спасибо !


c++ metaprogramming splice typelist
person Ragnar    schedule 16.07.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

person Luc Danton    schedule 16.07.2011
comment
std::list — вполне допустимый пример списка по компьютерным наукам. CS также имеет дело с изменяемыми структурами данных, и std::list — совершенно обычный пример двусвязного списка. Возможно, вы имели в виду, что это ближе к концепции функционального программирования списка (который является односвязным и неизменяемым)? - person jalf; 16.07.2011
comment
@jalf Я не хотел давать ссылку на определение списка CS, я не думаю, что это имеет отношение к тому, что есть под рукой. Первый абзац предназначен только как предупреждение не предполагать, что операции, доступные в списке типов, аналогичны операциям, доступным в std::list только на основе имени. Второй абзац находится там, где он находится (и суть здесь в чистом FP). - person Luc Danton; 16.07.2011