Re: [boost] A C++ puzzler

From: Eric Niebler (eric_at_[hidden])
Date: 2008-04-12 17:08:06

Marco wrote:
> On Sat, 12 Apr 2008 22:24:53 +0200, Sohail Somani <sohail_at_[hidden]>  
> 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