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 overloads. According to whom? The C++ standard has a footnote that outlines a linear algorithm for overload resolution. 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.
Sebastian