Use Concepts and Concept Checking Classes


Use "Concepts" to constain template parameters. This will make your library

  • easier to use.

  • easier to learn to use.

  • harder to misuse.

  • more logically coherent.

  • faster to develop.

  • easier and faster to write correct documentation.

What is a Concept?

For our purposes, we will define "C++ concept" as:

A C++ Template will have one or more type arguments. The template may require that each argument fullfill more or more requirements in order for the template to compile without error. These requirements are called Concepts. In this context, the word concept is equivalent to type requirements or type contraints.

So, for our purposes, the word concepts can be substituted with type requirements or type constraints without losing meaning. In fact, the meaning word concept in this context is one of the reasons that the subject has been so confusing. Another reason is that it is really only necessary to understand concepts when writting a templated library. Since very few programmers actually write such code, very few people actually use this idea and hence are unfamilar with it.

Concept Checking for Function Templates

Our discussion below is largely based on and example from the documentation of Boost Concept Checking Library As an illustration consider the standard C library function qsort. The prototype for this function is

void qsort(
    void *base, 
    size_t nitems, 
    size_t size, 
    int (*compar)(const void *, const void*)
);

The prototype lists the specific types of the function arguments. In other words, the function arguments are constrained to specific types. Any attempt to compile a call of this function with arguments which don't fit this type signature will result in a compile time error message. This generally works very well and is helpful to the user.

But for a general use library function this declaration has some problems. It's defined in terms of void * which require passing data without the type information. Then we need to add a "size" parameter. Then we need to start type casting the arguments. All this introduces it's own set off possibilities for errors which are a pain to track down. This is one of the main motivations for the invention of templates.

This function is defined in terms of any type T to permit it to be instantiated for any type.

template<typename T>
void bubble_sort(T begin, T end);

That is, we're saying that bubble_sort can be invoked with ANY type of arguments. The compiler won't detect any error where the function is invoked regardless of which arguments we pass to the function! So the following will compile without errors:

#include <vector>
#include <complex>

template<typename T>
void bubble_sort(T begin, T end);

void main(){
    std::vector<std::complex<float> > v;
    bubble_sort(v.begin(), v.end());
}

Hmmm, surely we can't pass any type to bubble sort. Indeed, when we include the implementation:

#include <vector>
#include <complex>
#include <utility> // swap

template<typename T>
void bubble_sort(T begin, T end){
    for(T i = begin; i < end; ++i)
        for(T j = i + 1; j < end; ++j)
            if(*j < *i)               // error!
                std::swap(*i, *j);
}

void main(){
    std::vector<std::complex<float> > v;
    bubble_sort(v.begin(), v.end());
}

We get an error message on the line including the comparison. Looking the implementation, considering that in this case T is defined as complex<float>, and recalling that complex is not a type which supports comparison we see the source of our error. It is obvious when we trace into to the implementation of the algorithm. But doing so can consume a huge amount of time when one must trace through several layers of templated code. One of the main reasons for using a library is to hide the implementation of some possible complicated procedure behind a simple declaration of what the function does. Expecting a user to delve deep into the implementation of the procedure defeats the reason for using the library in the first place!

So we need some way to add information about what types are permeated (type requirements or concepts) and a mechanism to automatically trap instances where these requirements are not satisfied. As I write this, I recommend usage of the Boost Concept Checking Library for this purpose. Here is how to use it for our example function.

DocumentationCode
template<typename T>
void bubble_sort(T begin, T end)

Type T must be an instance of a Forward
Iterator type.

For variables t1 and t2 of type T:

*t1 < *t2 must be valid and return value
convertible to bool

swap(*t1, *t2) must be valid.
#include "boost/concept/requires.hpp"
#include "boost/concept_check.hpp"
#include <iterator> // iterator_traits

template <typename T>
BOOST_CONCEPT_REQUIRES(
  ((boost::ForwardAccessIterator<T>))
  ((boost::LessThanComparable<
     typename std::iterator_traits<T>::value_type
   >))
  ((boost::Swappable<
     typename std::iterator_traits<T>::value_type
  )),
  (void)
)
bubble_sort(T begin, T end);

Note that:

  • The macro BOOST_CONCEPT_REQUIRES takes two arguments: a list of requirements, and the return type of the function. In particular, note that each requirement is placed in it's own set of parenthesis and that requirements are NOT separated by commas. This C++ unfriendly syntax is a necessary artifact of the way that the macro is implemented.

  • There is a one to one correspondence between the clauses in the documentation for the function and the lines in the code which implement the concept checking.

  • Our example includes type requirements (ForwardAccessIterator, LessThanComparable and Swappable) which are already defined in the C++ Standard Library. Since the Boost Concept Checking Library already includes the code for checking these requirements, we didn't have to write any code ourselves. All we had to do was to indicate which of the standard defined requirements should be checked. As it turns out this is quite common and many times we don't need to create any new type requirements

Assuming we've put the code including the type requirements in a header named bubble_sort.hpp we can now write a small program like this:

#include <list>
#include <complex>

#include "bubble_sort.hpp"

void main(){
    std::list<std::complex<float> > l;
    bubble_sort(l.begin(), l.end());
}

Attempting to compile this program will result in an error listing which refers to the source line were boost::LessThanComparable is instantiated with a type std::complex. Hopefully, this should remind the user to the fact that the < operator cannot be applied to the complex data type. Note that the user is not required to trace through the implementation of bubble sort to discover this fact. In fact, the bubble sort implementation is not even required to be present for the error to be detected and flagged with a compile time error. This will save your users hours of time and frustration and make it more likely that your library is successful.

Creating Concept Checking Classes

The meticulous reader who is compiling the above code examples as he reads will have discovered that one thing is not true. The concept checking class Swappable is not currently defined in the Boost Concept Checking Library. The following is based on Creating Concept Checking Classes From the documentation for Boost Concept Checking Library . The following code defines Swappable.

#include "boost/concept/usage.hpp"
#include "boost/concept/assert.hpp"

template <class T>
struct Swappable {
private:
    T t1, t2; // must be data members
public:
    BOOST_CONCEPT_ASSERT((boost::Assignable<T>));
    BOOST_CONCEPT_USAGE(Swappable)
    {
        swap(t1, t2);
    }
};

BOOST_CONCEPT_ASSERT can be used just about anywhere to verify that a given type fulfills the type requirements for any defined concept. Here it's use to register the fact that any Swappable type must be Assignable as well. That is, Swappable is a refinement of Assignable. Given that we've chosen to use BOOST_CONCEPT_REQUIRES for function template arguments, the most common usage BOOST_CONCEPT_ASSERT would be in class templates.

Future Compatibility

Inclusion of concepts in C++ has generated a huge amount of discussion, activity, experiments, and effort over the last decade. Googling "C++ Concepts" will result in many, many hits. This paper is one of those and gives a summary of the current state of the discussion. The latest effort, Concepts Lite, seems to be well received and perhaps destined for approval. Still, inclusion in the language and support by compilers is still years way. Boost Concept Checking Library on the other hand, can be used today. The following table contrasts Boost Concept Boost Concept Checking LibraryChecking Library with Concepts Lite:

Boost Concept CheckingConcepts Lite
#include "boost/concept/requires.hpp"
#include "boost/concept_check.hpp"
#include <iterator> // iterator_traits

template <typename T>
BOOST_CONCEPT_REQUIRES(
  ((boost::ForwardAccessIterator<T>))
  ((boost::LessThanComparable<
     typename std::iterator_traits<T>::value_type
   >))
  ((boost::Swappable<
     typename std::iterator_traits<T>::value_type
  )),
  (void)
)
bubble_sort(T begin, T end);
template<typename T>
requires 
    ForwardAccessIterator<T>() &&
    LessThanComparable<
        typename std::iterator_traits<T>::value_type
    >() &&
    Swappable<
        typename std::iterator_traits<T>::value_type
    >()
void bubble_sort(T begin, T end);
BOOST_CONCEPT_ASSERT(
    boost::ForwardAccessIterator<T>
)
static_assert(std::ForwardAccessIterator<T>())
BOOST_CONCEPT_USAGE
Unclear on how to specify this at this time

It turns out that there is almost a one to one relationship between lines of code used to specify concepts in between the two systems. So if one uses Boost Concept Checking Library. So transition to any future standard system when and if that occurs should be almost trivial. Also note that users code will not be effected in any way since any required changes are confined to the library code modules

.

References

More good information regarding practical aspects of C++ concepts and be found by checking the following links

p5rn7vb

Comment on This Page

There are 0 comments