There are some nice-to-know use cases for classes that have no members. One of them is tag dispatch. It can even be found in your standard library implementation.

When I write empty classes, I really mean empty. Classes without data can be found everywhere. Abstract base classes of class hierarchies often carry only declarations of virtual functions. Classes used in template metaprogramming may contain only typedefs or static members that are used at compile time.

That’s not what I write about today. I mean really empty, no data, no functions, no typedefs.

class Empty {};

Tag dispatch

Empty classes can be useful in C++ because it is a strongly typed language. If there are two empty classes, they are different types. They don’t have anything to do with each other. Objects of those types can not be converted to each other. There is nothing we can do with them but construct them and let them get destroyed.

Except we can pass them to functions. That is where tag dispatch comes in. It usually is used in generic programming, i.e. in templates. Imagine two or more alternatives of a function that take the same list of parameters. They need to have the same name but different implementations. How do we distinguish between the two?

A function signature is defined by its name and the types of its parameters. That information is what the compiler uses to look up the right function to call. So, to have more than one function identical in this regard, we have to add something that helps the compiler telling them apart. This can be achieved by adding a sentinel parameter type that is not used.

struct Variant1Tag {};
struct Variant2Tag {};

void functionWithVariants(int i, double d, std::string str, Variant1Tag) {
  // ...
}

void functionWithVariants(int i, double d, std::string str, Variant2Tag) {
  // ...
}

You see here that the tag type makes the two functions have different parameter lists. That way we can tell the compiler which one to use.

functionWithVariants(42, 3.14, "less obvious values next time", Variant1Tag{});</pre>

Use case example

A prominent case where this technique usually is used is the constructor of std::vector. vector has many constructors. One of them takes a pair of iterators to a range of values that shall be copied into the newly constructed vector. Another takes a size_type N and a value. It constructs the vector with N copies of that value.

So far that doesn’t sound too bad. We can write the signatures pretty fast:

template <class T>
class vector {
public:
  vector(size_type N, T const& value = T());
  template <class It>
  vector(It first, It last);
};

(I left out the optional allocator parameters for simplicity)

Now imagine a vector<int>. We want to construct it containing four elements with the value 32:
vector<int> v(4, 32);
size_type is an unsigned integral type. Therefore to call the constructor we want to be called, the compiler would have to convert the int 4 into a size_type. But there is an overload of the constructor taking two arguments of the same type! The constructor we meant to be used for iterators is the better match! We can not do anything against that, except explicitly casting the 4 to vector<int>::size_type, which is quite ugly to type and read.

For that reason, until C++11, the templated constructor had the same effect as the other constructor, if It turned out to be not really an input iterator type. (Today the iterator version does not take part in overload resolution if It is not an iterator)

Tag dispatch can be used to distinguish between the iterator version and the integral type version of the constructor, using the iterator tags of the standard library.

template <class It>
vector<T>::vector(It first, It last) {
  typedef get_iterator_tag_for<It>::type tag_type;
  construct(first, last, tag_type{});
}

template <class It>;
vector<T>::construct(It first, It last, std::input_iterator_tag) {
  // construct iterator style
}

template <class Int>
vector<T>::construct(Int N, Int const& value, SomeOtherTag) {
  // construct with N copies of value
}

Templated tags

What if we want to store a bit more information in our tags than just a type name to distinguish things? We can do that with templates. Tags are used to distinguish functions at compile time, so the compile-time information encoded in templates can come in handy.

The above example of the iterators basically contained a boolean information: Is the parameter type an iterator or not? So, instead of having different named types we could also have used a template. Be careful to not use std::true_type and std::false_type in a boolean situation like that, because only seeing the call contruct(first, last, std::true_type{}) would not be very informative (what is true?).

Instead, a well-named tag template will make very clear what is going on:

template <bool> 
struct UseIteratorSemantics
{};

//...

construct(first, last, UseIteratorSemantics<true>{});

A note on performance

Although performance should not be our first concern, it clearly matters if we are talking about general utilities like std::vector that can be used everywhere. So what is the performance and memory overhead of constructing and passing around tags like this?

The answer is zero. Nothing. Since we are usually talking about templates here, the compiler can see the function definition and that the tag is never used. Therefore, it can optimize away the extra parameter, its construction and everything related easily.