C++ Blog

C++0x "Concepts"

Posted in c++0x by Umesh Sirsiwal on January 17, 2009

It is generally agreed that “Concept” is the biggest addition to C++ during C++0x (e.g. look @ Herb Shutter’s blog). The subject is large and I possibly cannot explain it in a single post. This post provides high level concept behind C++0x Concept.

Any person who has ever used C++ templates knows that compiler error messages when using templates are pain to understand. The problem stands from the fact that there is no easy way for template developers to define constraints on template parameters. For example let us consider the following example:

#include <vector>
#include <complex>
#include <algorithm>

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

On my machine running GCC 4.2.1 it produces the following error:

/usr/include/c++/4.2.1/bits/stl_algo.h: In function âvoid std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â:

/usr/include/c++/4.2.1/bits/stl_algo.h:3176:   instantiated from âvoid std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3892:   instantiated from âvoid std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:11:   instantiated from here

/usr/include/c++/4.2.1/bits/stl_algo.h:2356: error: no match for âoperator<â in â__val < __first. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = std::complex<float>*, _Container = std::vector<std::complex<float>, std::allocator<std::complex<float> > >]()â

/usr/include/c++/4.2.1/bits/stl_algo.h: In function âvoid std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >, _Distance = int]â:

/usr/include/c++/4.2.1/bits/stl_algo.h:3182:   instantiated from âvoid std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3892:   instantiated from âvoid std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:11:   instantiated from here

/usr/include/c++/4.2.1/bits/stl_algo.h:3082: error: no match for âoperator<â in â__middle. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = std::complex<float>*, _Container = std::vector<std::complex<float>, std::allocator<std::complex<float> > >]() < __first. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = std::complex<float>*, _Container = std::vector<std::complex<float>, std::allocator<std::complex<float> > >]()â

/usr/include/c++/4.2.1/bits/stl_algo.h: In function âvoid std::__unguarded_linear_insert(_RandomAccessIterator, _Tp) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >, _Tp = std::complex<float>]â:

/usr/include/c++/4.2.1/bits/stl_algo.h:2362:   instantiated from âvoid std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3176:   instantiated from âvoid std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3892:   instantiated from âvoid std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:11:   instantiated from here

/usr/include/c++/4.2.1/bits/stl_algo.h:2309: error: no match for âoperator<â in â__val < __next. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = std::complex<float>*, _Container = std::vector<std::complex<float>, std::allocator<std::complex<float> > >]()â

/usr/include/c++/4.2.1/bits/stl_algo.h: In function â_ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >, _Tp = std::complex<float>]â:

/usr/include/c++/4.2.1/bits/stl_algo.h:3094:   instantiated from âvoid std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >, _Distance = int]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3182:   instantiated from âvoid std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3892:   instantiated from âvoid std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:11:   instantiated from here

/usr/include/c++/4.2.1/bits/stl_algo.h:3252: error: no match for âoperator<â in â* __first2 < * __first1â

Experienced C++ programmers may be able to figure out this error message however for most users it is extremely difficult. The error message is long and does not provide any insight in to cause of the error. The basic error is that  std:complex<float> does not model LessThanComparable which is required by std:sort.  In C++ there is no easy way for template developers to provide requirements on their parameters. Hence, compilers are not capable of testing the parameter errors early and provide meaningful error message. This C++ deficiency has significantly affected wider adaptation of templates and has resulted in development various methods of providing template parameter checks. These alternatives include both Language based and library based. C++0x Concepts will provide language level facility for error early error detection and meaningful error generation for template parameters.

It will probably take some time before MSVC and G++ support Concepts in their mainline languages. Till such time, existing alternatives may provide you with short term solutions.

Boost Concept Check Library

The Boost Concept Checking Library provides a library level concepts check facility without any language changes. Also the mechanism does not incur any run-time overhead. The checks are completely implemented at compile time. According to BCCL, it provides:

  • A mechanism for inserting compile-time checks on template parameters at their point of use.
  • A framework for specifying concept requirements though concept checking classes.
  • A mechanism for verifying that concept requirements cover the template.
  • A suite of concept checking classes and archetype classes that match the concept requirements in the C++ Standard Library.
  • An alternative to the use of traits classes for accessing associated types that mirrors the syntax proposed for the next C++ standard.

With BCCL the std::stable_sort can be written as:

template<typename T>
void sort(T b, T e)
{
  function_requires< LessThanComparableConcept<T> >();
  typedef typename
     std::iterator_traits<T>::value_type value_type;
  function_requires
     <LessThanComparableConcept<value_type> >();
  ....
}

With this change the error message changes to:

/usr/include/boost/concept_check.hpp: In member function âvoid boost::LessThanComparableConcept<TT>::constraints() [with TT = std::complex<float>]â:

/usr/include/boost/concept_check.hpp:48:   instantiated from âvoid boost::function_requires(boost::mpl::identity<T>*) [with Concept = boost::LessThanComparableConcept<std::complex<float> >]â

t.cc:13:   instantiated from âvoid mysort(T, T) [with T = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:21:   instantiated from here

/usr/include/boost/concept_check.hpp:314: error: no match for âoperator<â in â((boost::LessThanComparableConcept<std::complex<float> >*)this)->boost::LessThanComparableConcept<std::complex<float> >::a < ((boost::LessThanComparableConcept<std::complex<float> >*)this)->boost::LessThanComparableConcept<std::complex<float> >::bâ

/usr/include/c++/4.2.1/bits/stl_algo.h: In function âvoid std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â:

/usr/include/c++/4.2.1/bits/stl_algo.h:3176:   instantiated from âvoid std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3892:   instantiated from âvoid std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:15:   instantiated from âvoid mysort(T, T) [with T = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:21:   instantiated from here

/usr/include/c++/4.2.1/bits/stl_algo.h:2356: error: no match for âoperator<â in â__val < __first. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = std::complex<float>*, _Container = std::vector<std::complex<float>, std::allocator<std::complex<float> > >]()â

/usr/include/c++/4.2.1/bits/stl_algo.h: In function âvoid std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >, _Distance = int]â:

/usr/include/c++/4.2.1/bits/stl_algo.h:3182:   instantiated from âvoid std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3892:   instantiated from âvoid std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:15:   instantiated from âvoid mysort(T, T) [with T = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:21:   instantiated from here

/usr/include/c++/4.2.1/bits/stl_algo.h:3082: error: no match for âoperator<â in â__middle. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = std::complex<float>*, _Container = std::vector<std::complex<float>, std::allocator<std::complex<float> > >]() < __first. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = std::complex<float>*, _Container = std::vector<std::complex<float>, std::allocator<std::complex<float> > >]()â

/usr/include/c++/4.2.1/bits/stl_algo.h: In function âvoid std::__unguarded_linear_insert(_RandomAccessIterator, _Tp) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >, _Tp = std::complex<float>]â:

/usr/include/c++/4.2.1/bits/stl_algo.h:2362:   instantiated from âvoid std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3176:   instantiated from âvoid std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3892:   instantiated from âvoid std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:15:   instantiated from âvoid mysort(T, T) [with T = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:21:   instantiated from here

/usr/include/c++/4.2.1/bits/stl_algo.h:2309: error: no match for âoperator<â in â__val < __next. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = std::complex<float>*, _Container = std::vector<std::complex<float>, std::allocator<std::complex<float> > >]()â

/usr/include/c++/4.2.1/bits/stl_algo.h: In function â_ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >, _Tp = std::complex<float>]â:

/usr/include/c++/4.2.1/bits/stl_algo.h:3094:   instantiated from âvoid std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >, _Distance = int]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3182:   instantiated from âvoid std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

/usr/include/c++/4.2.1/bits/stl_algo.h:3892:   instantiated from âvoid std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:15:   instantiated from âvoid mysort(T, T) [with T = __gnu_cxx::__normal_iterator<std::complex<float>*, std::vector<std::complex<float>, std::allocator<std::complex<float> > > >]â

t.cc:21:   instantiated from here

….
….

/usr/include/c++/4.2.1/bits/stl_algo.h:3252: error: no match for âoperator<â in â* __first2 < * __first1â

Clearly a better error message (still a little longer than what we want it to be).

Although, BCCL provides better error message. The biggest drawback of the BCCL is that the restriction on the template parameter is not part of template prototype and hence not easily discoverable by algorithm user.  Language level support is needed to support that. The ConceptC++ was an experimental implementation of language level support. Significant parts of C++0x is derived from ConceptC++ and boost experimantation. I will discuss these changes in future posts.

Advertisements

Template or not to Template

Posted in templates by Umesh Sirsiwal on January 10, 2009

As I was learning C++ over an year ago,  I bought Modern C++ Design by Andrei Alexandrescu. As I read through the book, I was simply amazed by power offered by templates. Experience with the book was followed by Boost libraries. Specifically boost lambda and what it could provide to programmer. These went way beyond traditional STL use of templates. This excitement with C++ templates was followed by my experimentation with using templates in my own projects.  This post summarizes  experiences with templates.

  • Templates provide power with efficiency: Templates provide a lot of power without compromising efficiency. The Andrei’s book is full of examples of such power. A quick look inside the boost library provides examples of such power. Look at simple construct like boost::any which allows you to hold any type of data in it so that you can create a container/array which can hold boolean, integers, your various classes, etc. all at the same time. You can also look at a lot more complex construct like boost::lambda library which brings lambda programming to C++. Recently the boost has added boost::proto discussed in a seperate post on this site. The power really exists. Using these libraries can make your programming life a lot simpler. It is natural tendency to write your own templates on the same line. Should you or shouldn’t you?
  • Templates are not well understood: The templates are not well understood yet. Most experienced C++ programmers find it hard to understand how to program templates. At present templates are a the stage as Object Oriented Programming was several years ago. The compilers have progressed to state where they can correctly compile templates. However, the power of templates is yet to be distilled in to developer community at large. So if you decide to use templates, please be patient and give plenty of time for developers to learn and get up to speed.
  • Template debugging is horrifying experience for first time users: Error messages produced by compiler are horrifying large and complex. For simplest of errors, one gets 3 pages long error message with actual error who knows where. Once you get used to of debugging compilation issues you can generally figure out the error but it takes time to get used to of those errors. Template adaption will go a long way if the compilers start producing better error messages. But if you think compiler was the only issue just wait till you get to debuggers. The debuggers have not yet found a good way to deal with templates. Last but not least is compile time with templates. With most compilers, templates have to be included in header files. A simple change in the template requires compilation of all of your code which uses templates. This is like going backward on libraries.

In my experience, templates offer a lot of power and flexibility without compromising efficiency. The compilers can mostly deal with templates correctly. However debugger, compiler errors, and ways to reduce compile time can go a very long way in helping wider adaptation of templates. But if you are one of those early adapters and technology enthusiast, go ahead experiment and adapt templates and it will go a long way in helping your projects.

If you are going to use templates, you should start off by reading C++ FAQ Lite on template.