Marco wrote:
On Sat, 12 Apr 2008 22:24:53 +0200, Sohail Somani <sohail@taggedtype.net> wrote:
Correct me if my thinking is incorrect but I think a solution using a variable number of template specialization has an implicit O(f(N)) complexity where f(N) is some non-constant function of N. The compiler needs to iterate through all the specializations in order to find the match, which is the same as you explicitly iterating through some sort of fusion data structure. It may optimize this somehow but it still isn't O(1).
Interesting puzzle. Can't wait to see all the answers.
Your concern is sensible, and someone with a more insight than me on how a compiler works should give an answer, here. Anyway this is my point of view: the compiler has to do O(N) comparisons to find the right match but only the matching template specialization will be instantiated, so actually we need O(1) template instantiation only.
Clearly, I misread the O(1) template instantiations requirement. Thanks for clarifying for me. And to reply to Eric, it is also my experience that O(N) comparisons (would probably actually be O(N*MAX_TYPES) comparisons) are better than O(N) instantiations, but I'm sure the "Proto"-typical C++ guru (Eric) knows about that ;-) -- Sohail Somani http://uint32t.blogspot.com