Subject: Re: [boost] Overload resolution speed
From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2011-09-23 07:51:20
On 22.09.2011 17:57, Dave Abrahams wrote:
> on Thu Sep 22 2011, Sebastian Redl<sebastian.redl-AT-getdesigned.at> wrote:
>> Overload resolution is supposed to be linear in the number of
> According to whom?
The C++ standard has a footnote that outlines a linear algorithm for
Clang follows this algorithm, and I suspect pretty much every other
compiler does as well.
Therefore, if resolution is superlinear, it's a bug.
>> In general, all algorithms in a compiler should be linear, or worst
>> case n*log(n). Any quadratic or worse algorithm is pretty much a bug.
> I'd like to think so, too, but I'm not sure all implementors would agree
> with you.
I can't speak for any other compilers, but I'm pretty sure Ted and Doug
would agree with me about the main compilation pass of Clang.
We make exceptions for emitting errors, and of course for the static
analyzer, whose pass-sensitive checks are inherently exponential.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk