Re: [Boost-users] [mpl] Implementing includes_if

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2007-03-18 17:04:08

Hi Ovanes,

Ovanes Markarian wrote:
> Tobias,
> 
> I looked in your code and have an additional question. Compiletime
> complexity of the algorithm is exponential as I see it. 

Not quite - it's just quadratic in the worst case (I believe it's just 
about the wording: Although there's a constant exponent in O(N^2), 
"exponential complexity" is something with N being a factor of the 
exponent e.g. O(2^N)).

> Isn't it probably
> better to convert the first vector into a set and make set lookups with
> amortized constant time?

Seems it's only possible to implement the "Pred = is_same<_1,_2> case", 
this way - not the "Pred = is_base_of<_1,_2> case" asked for by the OP.

That issue aside, it seems an interesting idea. If you decide to give it 
a try I'd be interested to see your benchmarks!

Regards,
Tobias