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.
It's certainly the case that finding the correct specialization of N possibilities is not free. But finding the correct specialization and instantiating one template is *much* cheaper than instantiating N templates. At least, that's been my experience. -- Eric Niebler Boost Consulting www.boost-consulting.com