As you've noted, there's nothing in the usage of sort_ints that hints at its requirements of the comparison functor:

compare_class functor;
sort_ints(items, sizeof(items)/sizeof(items[0]), functor);

There's nothing in sort_ints itself either:

template <class ComparisonFunctor>
void sort_ints(int* begin_items, int num_items, ComparisonFunctor c);

And in class_compare, we can only deduce the functionality that will be used by observing it offers no other functionality:

class compare_class
{
  public:
     bool operator()(int A, int B) const { return A < B; }
};

The compiler does indeed leave it until it tries to compile the implementation of sort_ints, using the types with which its instantiated, before it works out whether this all hangs together. sort_ints will have to have exactly the kind of statement you mention:

c(*begin_items, *(begin_items+1));    // note: functor argument is "c"

So, your understanding is correct on all counts. BUT, it's worth noting that the proposed C++0x feature called Concepts was intended to make the requirements of sort_int more explicit without looking at its implementation. Unfortunately, C++0x had to abandon this feature as there's been insufficient time and experience to ensure it's optimal. Hopefully a future version of C++ will incorporate such a feature. You can find lots of discussions of Concepts on the 'net, and they should help you understand the overall issue better.

As you've noted, there's nothing in the usage of sort_ints that hints at its requirements of the comparison functor:

compare_class functor;
sort_ints(items, sizeof(items)/sizeof(items[0]), functor);

There's nothing in sort_ints itself either:

template <class ComparisonFunctor>
void sort_ints(int* begin_items, int num_items, ComparisonFunctor c);

And in class_compare, we can only deduce the functionality that will be used by observing it offers no other functionality:

class compare_class
{
  public:
     bool operator()(int A, int B) const { return A < B; }
};

The compiler does indeed leave it until it tries to compile the implementation of sort_ints, using the types with which it's instantiated, before it works out whether this all hangs together. sort_ints will have to have exactly the kind of statement you mention:

c(*begin_items, *(begin_items+1));    // note: functor argument is "c"

So, your understanding is correct on all counts. BUT, it's worth noting that the proposed C++0x feature called Concepts was intended to make the requirements of sort_int more explicit without looking at its implementation. Unfortunately, C++0x had to abandon this feature as there's been insufficient time and experience to ensure it's optimal. Hopefully a future version of C++ will incorporate such a feature. You can find lots of discussions of Concepts on the 'net, and they should help you understand the overall issue better.

It's an important issue because when you've only pieces of the puzzle - such as a sort_ints function you want to use but no example ComparisonFunctor, then you have to study the implementation of sort_ints to know how to create that Functor (unless you're super lucky and there's good, current documentation). You may accidentally make your code too dependent on the existing implementation, so that your code breaks or slows down unacceptably when the implementation of sort_int is changed slightly later - even if it is subtly enough not to break the test cases or other users' code or expectations. It's also likely that a small mistake in the provided ComparisonFunctor will produce a very convoluted and confusing compiler error message from somewhere in the guts of sort_int - that's not a nice way to provide a user with an abstracted service. Let's hope Concepts makes it in one day...!