Intro
I like writing libraries. In 2007 I refactored the heart of our library using types into a library using templates. This looked a bit like:
struct point { double x, y; };and then some functions using these types (there was also a polygon, etc).
When I was satisfied with the results I submitted this as a preview to Boost. The general reaction was: interesting, but it is not concept based, and therefore not generic enough.
So I had to make the types concept based, but I didn't know what it was. And I found out that concepts were not yet supported by the language - so how could I use them... That became all clear, with help of reviewers and joiners. The library was refactored again into a concept based library, it was accepted and it is now known as Boost.Geometry.
Now (14 years later) the C++ language has support for concepts.
This blog is targeted to the approach Boost.Geometry uses. It uses traits to adapt normal structs or classes to concepts. Functions in the library use those concepts.
The example in this blog
We start again with a point, and a function calculating the distance:
struct point { double x, y; };template <typename Point>
double distance_using_point(const Point& p1, const Point& p2)
{
auto sqr = [](const double v) -> double { return v * v; };
return std::sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
}
This function is template based but not generic. It only works for any point type having .x and .y member variables. But suppose it is not a member variable but a function .x(). Or you are using a std::array with two elements [0] and [1] (denoting x, y).
Traits as free functions
We will use traits for that. There are more ways to define and use traits. A first, concise way (not recommended! see below for a better version) is to just define free templated functions:
namespace point_traits
{
template <typename P> double get_x(const P& p);
template <typename P> double get_y(const P& p);
}
and these functions can then be specialized for the type:
namespace point_traits
{
template<> inline double get_x<point>(const point& p) { return p.x; }
template<> inline double get_y<point>(const point& p) { return p.y; }
}
And this works! Suppose you are to write a distance function, using these traits, it could look like this:
template <typename P1, typename P2>
double calculate_distance(const P1& p1, const P2& p2)
{
auto sqr = [](const double x) -> double { return x * x; };
return std::sqrt(sqr(point_traits::get_x<P1>(p1) - point_traits::get_x<P2>(p2))
+ sqr(point_traits::get_y<P1>(p1) - point_traits::get_y<P2>(p2)));
}
If you use a std::array, then you can specialize it too:
namespace point_traits
{
template<> inline double get_x<std::array<double, 2>>(const std::array<double, 2>& p) { return p[0]; }
template<> inline double get_y<std::array<double, 2>>(const std::array<double, 2>& p) { return p[1]; }
}
And you can calculate the distance of two different types, for example:
point mp{1, 1};
std::array<double, 2> sa{2, 2};
std::cout << calculate_distance(mp, sa) << std::endl;
It writes: 1.41421 as expected.
Evaluation of traits-as-free-functions
These traits give the example already a kind of concept based look. And it works, but there are some problems:
- functions cannot be specialized partially - this can be inconvenient
- suppose we want floats too, and long doubles, and we want to have that coordinate type defined in a meta-function. Where to define it?
- suppose we forget a traits adaptation: there is not appearing any compiler error message! Because it knows the generic templated function, and will not complain. It gives a linker error.
- it is (therefore) not suitable for C++20 concepts
The linker error, in case the specialization for point is forgotten or not right, will look like:
undefined reference to `double point_traits::get_x<point>(point const&)
undefined reference to `double point_traits::get_y<point>(point const&)
The linker just can't find these definitions. Compilation was fine. You can live with this, but there is a better alternative.
Concepts
Now we will try to make a C++ 20 concept using these traits:
template <typename P>
concept IsPoint = requires (P p)
{
point_traits::get_x<P>(p);
point_traits::get_y<P>(p);
};
template <typename P1, typename P2>
requires IsPoint<P1> && IsPoint<P2>
double calculate_distance(const P1& p1, const P2& p2)
{
// the same implementation
}
So we added, in bright magenta:
- a new concept IsPoint. That concept tries to use the functions in namespace point_traits. If they are not there, the type P does not fulfill the concept.
- a require clause decorating the distance function, stating that both point types should fulfill the IsPoint concept.
How cool is that!
However, even using this concept, there is the same linker error message. There is no neat compiler message about concepts, which we wished and maybe expected...
Traits as a struct
To fix this, the traits can be modeled as structures. So we adapt the code, we introduce a structure (here replacing the namespace - but that is only for the sake of the sample - these struct traits are often placed in an own namespace). And the structure is short!
template <typename P> struct point_traits {};So it is an empty structure. The magic happens in the specializations:
template<> struct point_traits<point>
{
static double get_x(const point& p) { return p.x; }
static double get_y(const point& p) { return p.y; }
};
template<> struct point_traits<std::array<double, 2>>
{
static double get_x(const std::array<double, 2>& p) { return p[0]; }
static double get_y(const std::array<double, 2>& p) { return p[1]; }
};
It looks nearly the same, just that now the struct is templatized with point or the std::array, instead of the free functions. And the free functions are now static member functions.
The concept is also similar, it's just the <P> part moving a bit left to the structure:
template <typename P>
concept IsPoint = requires (P p)
{
point_traits<P>::get_x(p);
point_traits<P>::get_y(p);
};
And so does the final generic concept-based distance function:
template <typename P1, typename P2>
requires IsPoint<P1> && IsPoint<P2>
double calculate_distance(const P1& p1, const P2& p2)
{
auto sqr = [](const double x) -> double { return x * x; };
return std::sqrt(sqr(point_traits<P1>::get_x(p1) - point_traits<P2>::get_x(p2))
+ sqr(point_traits<P1>::get_y(p1) - point_traits<P2>::get_y(p2)));
}
And if we now forget a specialization? We get a neat error message. In clang (13) it reads:
prog.cc:62:16: error: no matching function for call to 'calculate_distance'
std::cout << calculate_distance(mp, sa) << std::endl;
^~~~~~~~~~~~~~~~~~
prog.cc:45:8: note: candidate template ignored: constraints not satisfied [with P1 = point, P2 = std::array<double, 2>]
double calculate_distance(const P1& p1, const P2& p2)
^
prog.cc:43:10: note: because 'point' does not satisfy 'IsPoint'
requires IsPoint<P1> && IsPoint<P2>
^
prog.cc:35:20: note: because 'point_traits<P>::get_x(p)' would be invalid: no member named 'get_x' in 'point_traits<point>'
point_traits<P>::get_x(p);
^
1 error generated.
You can use C++20 and concepts, for example, in Wandbox.
Samples from libraries
Boost.Geometry uses this approach, also generalized for coordinate type and dimension. Here is the adaptation of the get function for std::array (in namespace boost::geometry::traits). It's partially specialized.
template <typename CoordinateType, std::size_t DimensionCount, std::size_t Dimension>
struct access<std::array<CoordinateType, DimensionCount>, Dimension>
{
static inline CoordinateType get(std::array<CoordinateType, DimensionCount> const& a)
{
return a[Dimension];
}
};
MapBox uses a similar approach, here is the adaptation for our point (in namespace mapbox::util):
template <> struct nth<0, point>
{
inline static auto get(const point &t) { return t.x; }
};
template <> struct nth<1, point>
{
inline static auto get(const point &t) { return t.y; }
};
Summary
The blog above shows, shortly, how to define traits, preferably as structs, and how to define a concept and use this concept in a free function distance.
