Dispatch based on arguments of a non-member function

Question

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 }

Answer 1

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.

Answer 2

Yes, this is a way to achieve compile-time polymorphism. All the types are known to the compiler and that's how it selects the overload.

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. Is this kind of dispatch generally true or is this a special case ?

As long as the iterator tag classes are related (e.g bidirectional_iterator_tag is inherited from input_iterator_tag).

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.

The compiler doesn't know if your code does what you want or not. However, you will get an error if you try to instantiate the function with an unsupported iterator type.

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 ? Does this have to be last argument ?

I think your syntax is just incorrect. Objects are generally used (the tag classes don't have any members, though, so they are only created for their type). I suppose, template specializations could also be used, but then those wouldn't be able to take advantage of the relationships between iterator categories (bidirectional iterator is an input iterator etc).

A sample how the syntax normally looks.

#include <cstdio>
#include <iterator>
#include <iostream>
#include <vector>
#include <list>

template <class Iter>
void foo_impl(Iter, std::random_access_iterator_tag)
{
    puts("Iter is random access");
}

//for other iterator categories
template <class Iter, class IterCategory>
void foo_impl(Iter, IterCategory)
{
   puts("Iter is other kind of iterator");
}

template <class Iter>
void foo(Iter it)
{
    //use iterator_traits, which will recognize pointers as random access iterators
    foo_impl(it, typename std::iterator_traits<Iter>::iterator_category()); 
}

int main()
{
    int* p = 0;
    std::vector<int>::iterator vec_it;
    std::list<int>::iterator list_it;
    std::ostream_iterator<int> os_it(std::cout);
    foo(p);
    foo(vec_it);
    foo(list_it);
    foo(os_it); 
}

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

If I'm not mistaken, even the most trivial use of templates can be thought of as compile-time polymorphism. I also guess this technique is older than CRTP (which AFAIK is not used in the standard library).

Answer 3

Overloaded function calls are resolved via the static types of the arguments (this is true both for member and non-member functions).

So:

class Base {};
class Derived : public Base {};

void foo(Base &b) {}
void foo(Derived &d) {}

Base b;
Derived d;
Base &r = d;

foo(b);  // Calls first overload
foo(d);  // Calls second overload
foo(r);  // Calls first overload

UPDATE

So in your new code snippet, the arguments are not types, they're just "anonymous"; they don't have a variable name associated with them.

This is all resolved at compile-time. iterator_traits<T>::iterator_category is a typedef (which will depend on T via the iterator_traits<T> template). iterator_traits<T>::iterator_category() is calling the constructor, to create a new temporary object of that type, which is being used as a "dummy" argument. The compiler then resolves that call to the correct overload. Given that this argument is a dummy, there's no need for a variable name inside the function.