Posts Tagged ‘generics’

Template concept feature (C++0x)

Friday, October 31st, 2008

So I was kind of bored and went on to read parts of C++0x committee draft that were published recently (was it just last month?). A copy is available at the C++ standards committee website. I have heard of some new interesting stuffs that’s coming with C++0x, but wasn’t really paying attention to their specifics. So when I read them in the standard paper, the specifics started to blow me out! The one thing that interest me a lot (other than all those functional programming’s lambdas) is template concept (ยง14.9.2).

As you may already know, C++ has long supported generic programming through template. Simple example:

template <typename T, typename U>
class pair {
  pair(T t, U u) : first(t), second(u) {}
  T first;
  U second;

That defines a pair container that can contain a pair of anything! Straightforward, isn’t it? It is, up to a point. Note that this is also a valid template:

template <typename Runnable>
void schedule(Runnable* task) {
  // Let's delegate to a scheduler
  // to schedule the task.

class scheduler {
  template <typename Runnable>
  void run(Runnable* task) {
    // Do something and then run the task.

// somewhere in main:

What does this template requires? Yes, it needs Runnable to actually implement run method. Now remember that while we name the typename Runnable, there is nothing stopping us from using typename T for it. Runnable is not an interface! Let’s say some_task actually does not implement run method. However, when the compiler encountered schedule(some_task); in main, it has no way to determine what some_task needs to implement (it does not know that some_task needs to have run method). Similarly when scheduler_->run(task); is called, the compiler still has no reason to reject it. It only rejects the program when it encounters task->run();. At that point the compiler will throw several cryptic line that basically says, hey task does not implements run in scheduler#run, which is instantiated in schedule function, which is instantiated in main. In reality, that is 3 lines of compiler error for 1 error. If you use standard library that relies on templates heavily, it is not uncommon to have 10+ lines of compiler errors, each lines averaging at about 200 characters, just for 1 template error. I have had my share of “debugging” compiler error message.

Template concept

This is where concept comes in. Concept allows you to provide requirements for a typename. For the above example, using concept, we can transform it into:

auto concept Runnable<typename T> {
  void T::run();

template <Runnable T>
  void schedule(T task) {

Now Runnable becomes a kind of interface (well, the committee calls it concept). Now the compiler could easily tells, the moment schedule is called, whether task satisfies the requirement of needing run method, instead of analyzing further until it encounters the requirement implicitly in scheduler#run. It can then inform the developer the moment he tries to use template with conceptually incompatible type. Neat huh?

It’s very powerful too. It allows several different type of requirement:

  • Availability of a non-member operator exists;
  • Availability static/non-static c-tor/d-tor/method (may specify different overloaded methods as well) exists;
  • Availability of a operator new and delete (these are necessarily member operator, hence the special case);
  • Axioms; etc.

There are more interesting concept-related stuffs. Concept refinement is of course possible (similar to class inheritance; heck, even the syntax is similar). You can also specify a default if the requirement is not satisfied. The draft gave one example of this:

concept EqualityComparable<typename T> {
  bool operator==(T, T);
  bool operator!=(T x, T y) { return !(x == y); }

That’s freakin’ awesome! While T may not have operator!= defined, you can provide a default implementation that will work as long as T have operator== defined.

Effect on compilation speed

At first I was excited to think that this will probably speed up compilation of bigger codebase, only to realize a minute later that I was wrong, so completely wrong. Concept provides a set of requirements that a typename must satisfy, but the template itself may use other methods/operators not specified by the concept! That means that the usual static type-checking must still be done, in addition to checking that the typename satisfies the concept! So compilation speed definitely goes down. That’s a definite blah, but the benefits seem to far outweigh the additional burden placed at the compiler.