Dispatch based on arguments of a non-member function

I was under the (possibly incorrect) assumption that non-member functions in C++ do not dispatch based on the type of its arguments. But after reading about iterator_category it seems I can call a function depending on the category type of its argument and the call also handles inheritance. For instance if I write only the implementations for random access iterator and input iterator, all calls with a non-random access iterator will go to the function that accepts input iterator. This is a shortened example from the book

template <class T>
foo(T a) {
  foo(a, iterator_traits<T>::iterator_category());
}

template <class T>
foo(T a, random_access_iterator_tag) { \\body}

template <class T>
foo(T a, input_iterator_tag) { \\body}

// presumably this works even for
// ostream_iterator<int> i(cout);
// foo(i);

Is this kind of dispatch generally true or is this a special case ?

Is the compiler supposed to warn me if my implementations are not exhaustive, for example in the iterator category based example, if I gave an implementation for random access iterator and bidirectional iterator only, should the compiler complain that output iterator is not covered.

This is also the first time I encountered a function with an argument that is only a type, and not an object/instance. So can I define functions with built-in or user-defined types as one of its arguments without specifying the name of the instance/object of that type ?

The following seems to be an alternative to CRTP to achieve compile time polymorphism. Is that a correct interpretation

template<class T>
int foo(T a) {
  foo(a, a::type());
}

int foo(int a, base) { \\body }
int foo(int a, derived) { \\body }

Solution

You are indeed using compile-time polymorphism, which dispatches based on the static type of the object.

The iterator categories are chained by inheritance (not the iterator themselves), so that:

InputIterator <- ForwardIterator <- BidirectionalIterator <- RandomAccessIterator

(should be an OutputIterator too, but it does not matter here)

Using iterator_traits, you can retrieve the iterator category associated with the current iterator. You create a dummy value, and then the overload resolution process kicks in. Suppose for the sake of example that you have 3 overloads:

template <class T>
foo(T a, std::random_access_iterator_tag const&);
  // beware of slicing (in general)

template <class T>
foo(T a, std::forward_iterator_tag const&);

template <class T>
foo(T a, std::input_iterator_tag const&);

Now suppose that I use foo with a list iterator:

list<int> myList;
foo(myList.begin());

Then, the 4 foo are found in the scope (name resolution).

foo(T) is immediately discarded (wrong number of argument)
foo(T, std::random_access_iterator_tag const&) is discarded because there is no conversion from std::bidirectional_iterator_tag to std::random_access_iterator_tag.

This leaves 2 foo both being compatible (note: if we had used an OutputIterator, we would not have anything left, and a compilation error would be raised at this point).

We then finally get into the ranking part of the overload resolution process. Since std::forward_iterator_tag is a "closer" (more immediate) base than std::input_iterator_tag, it is therefore ranked higher.

foo(T, std::forward_iterator_tag const&) is selected.

Note the static portion of this though.

std::forward_iterator_tag const& tag = std::vector<int>::iterator_category;
foo(myVector.begin(), tag);

Here, even though the tag really is (dynamic) a std::random_access_iterator_tag, it is seen by the system as a std::forward_iterator_tag, and thus the same overload that above will be selected.