Home > Articles > Programming > C/C++

C++ Reference Guide

Hosted by

Toggle Open Guide Table of ContentsGuide Contents

Close Table of ContentsGuide Contents

Close Table of Contents

Concepts, Part I

Last updated Jan 1, 2003.

In many of his interviews and books, Bjarne Stroustrup emphasized the importance of adding a mechanism for specifying and enforcing template constraints. Such a mechanism is about to become a reality soon. The Evolution Group is now working on a new feature called concepts. Concepts introduce a type system for templates, enabling you to specify template constraints clearly and intuitively, while improving the compiler’s capability to detect and diagnose violations of these constraints.

The Problem with Templates Constraints

The following program demonstrates a common template-related problem:

#include <vector>
#include <algorithm>
using namespace std;
struct B
 void f() const;
int main()
 vector <B> vb;

//..code continues below

The code thus far is fine and should compile successfully. However, once the following line is added to the program, you get a compilation error:

 sort(vb.begin(), vb.end());//compilation error here

One of my reference compilers issues the following error message:

[C++ Error] algorith.h(644): E2093 ’operator<’ not implemented in type ’B’ for arguments of the same type.

If you’ve used std::sort() before, you probably know that it uses under the hood some helper algorithms that ultimately call operator<. If the template argument of vector has an associated operator<, the sort() call will compile and execute successfully. Alas, since there’s no operator< associated with B, the code fails to compile.

Many programmers get bitten by this error when using sort() for the first time. You can’t blame them, though. The requirement that T shall be a type that has a less-than operator taking references to two objects of type T and returning some value that is convertible to bool isn’t expressed in the signature of std::sort(). Only when you examine the definition of sort() do you see that it uses operator<. In C++98, this is the best you can hope for with respect to template constraints -- the constraint itself isn’t clearly documented in the template function’s declaration but at least the compilation tells you more or less what’s wrong.

In many other cases, the constraints are more complex, which necessitates contrived code, or there is no direct way of expressing and enforcing them. Take the infamous example of auto_ptr and Standard Library containers. Standard Library containers must store only objects that are copy-constructible and assignable. auto_ptr , as you may recall, is neither copy-constructible nor assignable. However, the instantiation of a vector or deque of auto_ptr objects compiles successfully:

 vector <auto_ptr<int> > vb; //undefined behavior
 deque <auto_ptr<int> > vb;//undefined behavior

To the surprise of the poor programmer, this code could lead to unpredictable results. The requirement that T shall be copy-constructible and assignable isn’t enforced at compile time nor is it discernible from the declarations of vector and deque. We can conclude that C++ doesn’t have a mechanism for expressing template constraints consistently and clearly.

Introducing Concepts

Concepts rely on the notion of separate type checking for templates. Template declarations are augmented with a set of constraints. When a template is instantiated, the compiler checks that the instantiation meets all of the constraints, or requirements, of the said template. If all is well, the template is instantiated successfully. Otherwise, a compilation error stating which constraints(s) were violated is issued. Let’s look at a concrete example. The std::min() algorithm is defined as follows:

template<typename T>

const T& min(const T& x, const T& y) 
 return x < y? x : y;

As with std::sort(), you need to examine the body of min() to know what the constraints on T are: T must be a type that has a less-than operator taking references to two objects of type T and returning some value that is convertible to bool. Using concepts, these requirements can be expressed directly in the definition min():

template<LessThanComparable T> //using a concept 
const T& min(const T& x, const T& y) 
 return x < y? x : y;

The difference here is subtle yet crucial. Instead of stating that T is an arbitrary type (as implied by the typename keyword), this version states that T is a LessThanComparable type, whatever this may be. Therefore, min() will only accept arguments whose types meet the requirements of the LessThanComparable concept. If min() is instantiated with an argument that is not LessThanComparable, the compiler will detect the error early, i.e., not when the operator< is used but when the call to min() is made. Thus, instead of pointing to a random line is some obscure header file that contains the implementation of min(), the error will refer to the source file that actually contains the call to min(). More importantly, the error message will be descriptive, stating that the argument of min() doesn’t satisfy the LessThanComparable requirement. Early detection of errors and clear error messages are a rare commodity these days in the template market!

This is all well and good, but the big question still remains: how do you define the LessThanComparable concept?

Defining Concepts

A concept definition uses the new keyword concept followed by the name of the concept and a template parameter list (I will discuss the role of the keyword auto shortly):

auto concept LessThanComparable<typename T> {/*...*/} //definition of a concept

The body of the concept contains the list the declarations that express the requirements from the template parameter(s). Here’s the complete definition of the LessThanComparable concept:

auto concept LessThanComparable<typename T> 
 bool operator<(T, T);

We have just defined a concept called LessThanComparable which states that the parameter T of a given template must be a type that has a less-than operator taking references to two objects of type T and returning some value that is convertible to bool. The auto keyword specifies that any type which has a suitable operator< will qualify as LessThanComparable. If auto isn’t used in the concept definition, clients will have to explicitly state that their types meet the requirements of this concept using a concept map.

In the second part of this series I will explain what a concept map is and show other examples of concepts.