Vadim Androsov

Boost Concepts

C++

Boost I was always scared to use C++ templates due to the absence of standard mechanisms for setting parameter limits. In other words, when a developer writes the following function:

template 
bool someFunc(T t)
{
    if (t.someCheck()) {
        t.someAction(0);
    }
}

it makes different assumptions as for the functionality of T type objects, but doesn’t have a standard facility to inform the user about them. Thus, the provided example can suppose at least the following things:

  1. T type objects are passed by value. So they should have on open copy constructor.
  2. There’s an open T::someCheck method with no parameters. It returns the value that is cast to bool type.
  3. There’s an open T::someAction method that can accept one parameter that is cast to numeric data type.

The Problem

Suppose the programmer has decided to distribute someFunc in the form of a library. How can the library user find out about the current limits?

  • Reading library’s documentation. If it’s there and is written properly. But even in this case no one will read the documentation of all libraries being used before every code change. Not all of us can keep in mind all conditions.
  • Learning the library source code isn’t to everyone’s liking either. There are also few fans of learning the code of big libraries and complex projects.

We could also start from compilation errors. So we make a change. If it doesn’t build, look for the reason why. But those having used C++ templates know what error messages can look like. They can look like anything but fix-here-and-it-will-work hint. Sometimes the message is quite understandable, but sometimes we’re lost in depths of someone’s library… The compiler notifies us of an error at the place it occurred. It doesn’t care that we can’t reconstruct the primary use context there.

Let’s take a look at the following example (we’ll get back to it later): Sorting a list (a standard container).

std::listtheList;
std::sort(theList.begin(), theList.end());

Won’t compile. An error looks like the following in VS2013:

error C2784: 'unknown-type std::operator -(std::move_iterator<_ranit> &,const std::move_iterator<_ranit2> &)': could not deduce template argument for 'std::move_iterator<_ranit> &' from 'std::_List_iterator<:_list_val>>>' c:\program files (x86)\microsoft visual studio 12.0\vc\include\algorithm 3157 1 MyApp

But it’s half the trouble. When clicking on the error we get into the depths of algorithm standard library, right here:

template inline
    void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)
    {   // order [_First, _Last), using _Pred
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER(_Pred);
    _Sort(_Unchecked(_First), _Unchecked(_Last), _Last - _First, _Pred);
    }

Our first reaction is: “What? Why has the vector sorted out, but not the list? Both containers have iterators, both of them know about the element order…” It’s okay if the library is standard, but what if we’re in an unfamiliar one…

Solution

It turns out that there’s a solution. There is an initiative of changing the language in this direction, but it’s not in the standard yet. While boost library supports the notion of concepts, by utilizing them we can create user limits for template parameters.

There’s an algorithm of concepts use. A developer with his libraries provides description of the necessary concepts required for their proper operation. A user can automatically test all entities on the matter of fitting the suggested rules. The errors will be much clearer: The class doesn’t support the following concept: “There should be a constructor by default”.

Using boost the developer doesn’t have to construct new concepts from scratch every time as the library contains drafts of basic limits.

Let’s review an example for someFunc function provided at the beginning of the article. The first rule is that we substitute the copy constructor by boost::CopyConstructible concept. We’ll have to write tests manually for others.

#include 

template 
struct SomeFuncAppropriate {
public:
    BOOST_CONCEPT_ASSERT((boost::CopyConstructible));
    BOOST_CONCEPT_USAGE(SomeFuncAppropriate)
    {
        bool b = t.someCheck();//someCheck method, with the returned value, cast to bool
        t.someAction(0);// someAction method with the parameter that we cast to a number
    }
private:
    T t; // must be data members
};

Therefore, the boost concept is a template structure with a tested type as a parameter. We carry out the checkup on the matter of fitting the ready concepts via BOOST_CONCEPT_ASSERT macro. Note that as a parameter we pass a concept in brackets to it. Therefore double brackets are necessary though they offend the eye.

We can implement checking with the help of BOOST_CONCEPT_USAGE macro. But we should keep in mind that it is necessary to declare all exemplars participating in the test as class members, not as local variables.

After declaring the concept we can perform a checkup on the matter of fitting with the use of BOOST_CONCEPT_ASSERT macro. Suppose we have the following class:

class SomeClass
{
public:
    SomeClass();
    void someCheck();
    int someAction(int);

private:
    SomeClass(const SomeClass& other);
};

We can test it the following way: BOOST_CONCEPT_ASSERT((SomeFuncAppropriate));

Let’s try to run it. Immediately get an error: error C2440: 'initializing': cannot convert from 'void' to 'bool'

When clicking on it we get to the broken line in the definition of SomeFuncAppropriate (в BOOST_CONCEPT_USAGE) concept. That’s where we can easily understand the reason of the problem. someCheck returns void instead of bool. Fix it and try again. error C2248: 'SomeClass::SomeClass': cannot access private member declared in class 'SomeClass' boost\concept_check.hpp

Clicking the error we get to the concept source code

BOOST_concept(CopyConstructible,(TT))
  {
    BOOST_CONCEPT_USAGE(CopyConstructible) {
      TT a(b);            // require copy constructor
      TT* ptr = &a;       // require address of operator
      const_constraints(a);
      ignore_unused_variable_warning(ptr);
    }
...

The cursor points to the following line: TT a(b); // require copy constructor

The copy constructor is hidden. Let’s fix it. Now the test is passed (compiling the file with BOOST_CONCEPT_ASSERT). Thus, SomeClass class completely meets the developer’s expectations as for someFunc function. If we add some changes breaking the compatibility the concept checkup will immediately notify us about the exact problem.

Now let’s get back to the example with std::list sorting with the help of std::sort. Let’s express requirements to the sorted container in a form of a concept. First of all, std::sort can work only with containers supporting random access. There’s a corresponding concept in boost (boost::RandomAccessContainer), but it’s not enough. There’s also a requirement to the container content. Its elements should support “less than” comparison operator. And again boost helps us with its ready boost::LessThanComparable concept. Combine the concepts into one

template 
struct Sortable 
{
    public:
        typedef typename std::iterator_traits::value_type content_type;

        BOOST_CONCEPT_ASSERT((boost::RandomAccessContainer));
        BOOST_CONCEPT_ASSERT((boost::LessThanComparable));
};

Start the checkup BOOST_CONCEPT_ASSERT((Sortable<:list> >));

We can see error C2676: binary '[': 'const std::list>' does not define this operator or a conversion to a type acceptable to the predefined operator boost\concept_check.hpp

A click on the error will send us to RandomAccessContainer concept source code giving to understand that it’s the one broken. If we replace std::list by std::vector the concept checkup will be successful. Now let’s try to check SomeClass exemplar vector on the matter of sorting. BOOST_CONCEPT_ASSERT((Sortable<:vector> >));

The container is really suitable but we can’t sort it out anyway whereas SomeClass doesn’t define “less than” operator. We’ll know about it at once: error C2676: binary '

Clicking the error we’ll get into LessThanComparable source code and understand what we’ve broken.

Thus, these concepts make generic programming in C++ a bit less extreme. And it’s great!

  1. Boost Concepts
  2. Masking a Class in Boost Graph. Part 1: Let the Interface Be
  3. Masking a Class in Boost Graph. Part 2: Completing the Implementation of Concept Support
  4. Masking a Class in Boost Graph. Part 3: Finding the Path

Comments

    Flux 3,751

    Ropes — Fast Strings

    Most of us work with strings one way or another. There’s no way to avoid them — when writing code, you’re doomed to concatinate strings every day, split them into parts and access certain characters by index. We are used to the fact that strings are fixed-length arrays of characters, which leads to certain limitations when working with them. For instance, we cannot quickly concatenate two strings. To do this, we will at first need to allocate the required amount of memory, and then copy there the data from the concatenated strings.