The C++ Boost Library: Beyond the STL

Concept-Checking Classes

To overcome the problem of cryptic error messages from code not satisfying a concept the Boost Library has developed a C++ idiom for up-front enforcement of concept compliance, called concept checking. The supporting code for this idiom is available as the Boost Concept Checking Library (BCCL). For each concept, the BCCL provides a concept-checking class, such as the following concept-checking class for LessThanComparable. The required valid expressions for the concept are exercised in the constraints() member function.

template <var class='type'name T>
struct LessThanComparableConcept {
  void constraints() {
    (bool) (a < b);
  };
  T a, b;
};

The concept-checking class is instantiated with the user's template arguments at the beginning of the generic algorithm using the BCCL function_requires() function.

#include <boost/concept_check.hpp>
template <var class='type'name Iterator>
void safe_sort(Iterator first, Iterator last) {
  typedef typename std::iterator_traits<Iterator>::value_type T;
  function_requires< LessThanComparableConcept<T> >();
  // other requirements . . .
  std::sort(first, last);
};

Now when safe_sort() is misused the error message is much more comprehensible: the message is shorter, the point of error is indicated, the violated concept is listed, and the internal functions of the algorithm are not exposed.

The Boost Graph Library uses concept checks to provide better error messages to users. For each graph_concept there is a corresponding concept-checking class defined in the boost/graph/graph_concepts.hpp header file. At the beginning of each BGL algorithm there are concept checks for each of the parameters. Error messages originating from graph concepts.hpp are a likely indication that one of the argument types given to an algorithm does not meet the algorithm's requirements for a concept.

Concept Archetypes

The complementary problem to concept checking is verifying whether the documented requirements for a generic algorithm actually cover the algorithm's implementation, a problem we refer to as concept covering. Typically, library implementors check for covering by manual inspection, which of course is error prone. We have also developed a C++ idiom that exploits the C++ compiler's type checker to automate this task. The code for concept covering is also available as part of the Boost Concept Checking Library.

The BCCL provides an archetype class for each concept used in the Standard Library. An archetype class provides a minimal implementation of a concept. To check whether a concept covers an algorithm, the archetype class for the concept is instantiated and passed to the algorithm.

The following example program attempts to verify that the requirements of std::sort() are covered by an iterator that models RandomAccessIterator having a value type modeling LessThanComparable.

#include <algorithm>
#include <boost/concept_archetype.hpp>
int main() {
  using namespace boost;
  typedef less_than_comparable_archetype<> T;
  random access_iterator_archetype<T> ri;
  std::sort(ri, ri);
}

In fact, this program will not successfully compile because those concepts do not cover the requirements that std::sort() makes of its template parameters. The resulting error message indicates that the algorithm also requires that the value type be CopyConstructible.

null archetype(const null archetype<int> &) is private

Not only is the copy constructor needed, but the assignment operator is needed as well. These requirements are summarized in the Assignable concept. The following code shows the implementation of the archetype class for Assignable. The Base template parameter is provided so that archetypes can be combined. For checking std::sort(), we would need to combine the archetype classes for Assignable and LessThanComparable.

template <var class='type'name Base = null_archetype<> >
class assignable_archetype : public Base {
  typedef assignable_archetype self ;
public:
  assignable archetype(const self &) {}
  self & operator=(const self &) { return *this; }
};

The Boost Graph Library includes an archetype class for every graph concept in the header file boost/graph/graph_archetypes.hpp. Test programs to verify the specification of each BGL algorithm using the graph archetypes are located in the libs/graph/test/ directory.