Lorenzo Caminiti wrote:
Hello all:
Is there a computational complexity analysis of Boost.Preprocessor data structures? This would be in terms of preprocessing time.
For example: Does BOOST_PP_SEQ_ELEM() run* in O(n)? Do BOOST_PP_TUPLE_ELEM() and BOOST_PP_ARRAY_ELEM() run* in O(1)? (*) "Run" within the preprocessor so maybe "expand" is a better term...
Thank you. Lorenzo
I've used the Boost.Preprocessor library quite a bit, so I'm only responding in light of that. "Number of macro invocations" (as it depends on an argument) should be immediately inferred from a quick glance through the code. E.g., BOOST_PP_SEQ_ELEM( n, seq ) requires O(n) macro invocations, and BOOST_PP_TUPLE_ELEM( n, k, tuple ) (in terms of which BOOST_PP_ARRAY_ELEM is implemented) requires O(1) macro invocations. Of course, Boost.PP tuple/array sizes is capped at a smaller limit than Boost.PP seq sizes (25 vs. 255, I believe). I'm guessing "preprocessing time" could have a more elusive relationship that depends on the implementation of the preprocessor. E.g., is the time for a single macro invocation independent of the number of arguments, or the size of the arguments? If not, how does it scale? Seems to me you're now asking a preprocessor implementation question... - Jeff