Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at