Why std::sort doesn't accept Compare classes declared within a function

Question

I was at work, writing the Comparators in a function (to move later, when I decided where was best), and noticed this peculiarity. I thought about it for a while, and realized I do not understand exactly why the code will not compile if I use the inner comparators, but the outer one is fine.

Any explanations?

Quick Test harness:

#include <iostream>
#include <vector>
#include <algorithm>

class CompareMe
{
 public:
    CompareMe(int in) : toCompare(in){}
    int toCompare;
};

class Comparators
{
public:
    bool operator()(CompareMe * first, CompareMe * second)
    {
        return first->toCompare < second->toCompare;
    }
};

class ComparatorsOuter : public Comparators{};

int main()
{
    class ComparatorsInner : public Comparators{};

    std::vector<CompareMe *> compares;
    compares.push_back(new CompareMe(0));
    compares.push_back(new CompareMe(1234));
    compares.push_back(new CompareMe(163));
    compares.push_back(new CompareMe(6));
    compares.push_back(new CompareMe(12));

    //This works, and properly sorts the array
    ComparatorsOuter comparator;
    std::sort(compares.begin(), compares.end(), comparator);

    //Uncomment out the sort below and it will not compile.
    ComparatorsInner comparatorInner;
    //std::sort(compares.begin(), compares.end(), comparatorInner);

    std::vector<CompareMe *>::iterator it;
    for(it = compares.begin(); it != compares.end(); ++it)
    {
        std::cout << (*it)->toCompare << std::endl;
    }
}

error: no matching function for call to 'sort(__gnu_cxx::__normal_iterator<CompareMe**, std::vector<CompareMe*, std::allocator<CompareMe*> > >, __gnu_cxx::__normal_iterator<CompareMe**, std::vector<CompareMe*, std::allocator<CompareMe*> > >, main()::ComparitorInner&)'

Answer 1

In C++03, template arguments could not have internal linkage:

[C++03: 14.6.4.2/1]: For a function call that depends on a template parameter, if the function name is an unqualified-id but not a template-id, the candidate functions are found using the usual lookup rules (3.4.1, 3.4.2) except that:

• For the part of the lookup using unqualified name lookup (3.4.1), only function declarations with external linkage from the template definition context are found.
• For the part of the lookup using associated namespaces (3.4.2), only function declarations with external linkage found in either the template definition context or the template instantiation context are found.

[..]

This was changed (issue #561: "Internal linkage functions in dependent name lookup") in C++11:

[C++11: C.2.6]: 14.6.4.2
Change: Allow dependent calls of functions with internal linkage
Rationale: Overly constrained, simplify overload resolution rules.

resulting in:

[C++11: 14.6.4.2/1]: For a function call that depends on a template parameter, the candidate functions are found using the usual lookup rules (3.4.1, 3.4.2, 3.4.3) except that:

• For the part of the lookup using unqualified name lookup (3.4.1) or qualified name lookup (3.4.3), only function declarations from the template definition context are found.
• For the part of the lookup using associated namespaces (3.4.2), only function declarations found in either the template definition context or the template instantiation context are found.

[..]

(Spot the missing "with external linkage" qualification.)

Since your main()::ComparitorInner& has internal linkage, and the instantiation of std::sort requires this type to be a template parameter (albeit deduced), your code is only valid in C++11.

Answer 2

Your code is fine in C++11; there was a restriction about using local types as template arguments in C++03.