Use Type Constraints (Concepts) for Template Parameters


Use Type Constraints (Concepts) for 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 Type Constraint?

For our purposes, we will define "C++ Type Constraint" in the following way:

A C++ Template will have one or more type arguments. The template may require that each argument fullfill more or more conditions in order for the template to compile without error. These requirements are called Type Constraints or Type Requirements.

C++ literature and documentation use the word Concept for this purpose. In fact, this usage of the word Concept 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 writing a templated library. Since very few programmers actually write such code, very few people actually use this idea and hence are unfamilar with it. Our term Type Constraint is exactly equivalent to the C++ term Concept. Either one can be substituted for the other without loss of meaning.

Type Constraints 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 (*compare)(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 requires 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);

This declares an implementation the function bubble_sort in terms of some type T. So there is no runtime casting required and the compiler can optimize implentations in terms of type T. But this declaration leaves as wondering which types we can use for T. Surely we can't pass any type to bubble sort. We can guess from the function signature that T must be some iterator type. But which one? RandomAccess, ForwardAccess, InputIterator? And what types is the iterator allowed to point to? And what other requirements might T have to fulfill.

It turns out that this example will fail to compile.

#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());
}

But the point of failure will be several levels deep in the call chain. The error message will only be found at a very deep level in the template instantiation stack. It will be extremely difficult to relate the error to any specific attibute of type T. In order to do this, we'll have to look at 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 which invokes the comparison. Looking the implementation, considering that in this case T is defined as type std::vector<std::complex<float>::iterator, the dereferencing operator * will yield an instance of std::complex<float> and std::complex is not a type which supports comparison. We can now see the source of our error. It becomes 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 possibly complicated procedure behind a simple declaration of what the function does. Expecting a user to delve deep into the implementation of the procedure to understand how to invoke it defeats the whole purpose of using the library in the first place!

Note that with C++11 the problem is even worse! Consider

#include <vector>
#include <complex>

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

void main(){
    auto r = some_function();
    bubble_sort(r.begin(), r.end());
}

In this case the actual type of r will be hidden behind the auto keyword. So tracing into the implementation will be even more difficult!

So we need some way to add information about which types are permitted (type requirements or constraints) and a mechanism to automatically trap instances where these constraints are violated. 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 model Forward Iterator type constraints.

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. It's trivial to verify that one's documentation is consistent with the code.

  • 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 a compile time 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.

Note that our bubble_sort above will compile and run properly in some cases where std::sort will fail.

#include <list>
#include <algorithm> // std::sort

#include "bubble_sort.hpp"

void main(){
    std::list<int> l;
    std::sort(l.begin(), l.end()); // fails to compile
    bubble_sort(l.begin(), l.end()); // compiles and runs
}

The std::sort requires that the arguments meet type requirements of a RandomAccessIterator. But our bubble_sort requires that the arguments meet the weaker type requirements of a ForwardAccessIterator.

Without explicit type requirements, this will be an extremely confusing result which will require browsing the standard library implementation of std::sort to sort out. With explicit type requirements, the error message will directly reveal the source of the problem.

Creating Type Constraint 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"

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

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. 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 Checking Library with Concepts Lite:

Boost Concept Checking LibraryConcepts Lite
#include "boost/concept/assert.hpp"
#include "boost/concept/usage.hpp"

BOOST_CONCEPT_USAGE(Swappable){
    BOOST_CONCEPT_ASSERT((boost::Assignable<T>));
    boost::swap(t1, t2);
}
template <typename T>
concept bool Swappable(){
    return requires(){
        requires Assignable<T>;
        requires requires(T t1, T t2){
            boost::swap(t1, t2);
        }
    }
}
#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 
    std::ForwardIterator<T>()
    && std::LessThanComparable<
        typename std::iterator_traits<T>::value_type
    >()
    && std::ValueSwappable<T>()
void bubble_sort(T begin, T end);
#include "boost/concept/assert.hpp"

BOOST_CONCEPT_ASSERT(
    boost::ForwardAccessIterator<T>
)
static_assert(std::ForwardIterator<T>())

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