Bubble sort with CPP template metaprogramming — part 3

4 min readJan 19, 2024

So last time we had this

template <int current_index, int max_index, class current_state, class Iteration>
struct ForLoop
{
 typedef typename Iteration<current_index, current_state>::state next_state;
 typedef typename ForLoop<current_index+1, max_index, next_state, Iteration>::state state;
};

template <int max_index, class current_state, class Iteration>
struct ForLoop<max_index, max_index, current_state, Iteration>
{
 typedef typename current_state state;
};

that is a “for loop” that is running from a current_index to max_index (minus one, per convention), executing state = Iteration(current_state). This is a known flow control, but for a small problem — it won’t compile.

What’s wrong?

The sensitive ones may have noticed this part

typedef typename Iteration<current_index, current_state>::state next_state;

and to focus on the issue the Iteration<…. As far as the compiler is concerned, Iteration is a type. This is what was declared in the template argument list. So seeing this piece, is just like compiling the code int<…! As a compiler, you don’t really have to look further there is no way this is going to issue a legal C++ code. Giving it another thought we notice that this is a good example that C++ templates are not macros, a fact easily missed when you move from C and see templates for the first time.

What’s right?

To fix this issue, the C++ god in their infinite wisdom granted us a solution — a means to inform the compiler that this is actually another templated class — the template template parameter. Indeed, this is not a typo! We will declare Iteration to be template<int,class> class Iteration — a template class, receiving two (normal) template parameters, an int and a class. Since the actual parameters are specified in the ForLoop body, the actual names of the int and the class are unimportant. This is analogous to declaring a parameter of function-pointer type, say int(*func)(int, float).

So the correct version of the ForLoop would be

template <int current_index, int max_index, class current_state, template<int,class> class Iteration>
struct ForLoop
{
 typedef typename Iteration<current_index, current_state>::state next_state;
 typedef typename ForLoop<current_index+1, max_index, next_state, Iteration>::state state;
};

template <int max_index, class current_state, template<int, class> class Iteration>
struct ForLoop<max_index, max_index, current_state, Iteration>
{
 typedef typename current_state state;
};

Implementation

A first step would be to rework the BubbleInnerLoop. Let’s identify the state and the iteration (see the Some loop analysis section in the previous post).

template <int max_index, int index, class T>
struct BubbleInnerLoop
{
 typedef typename BubbleIter<index, T>::type BubbleStepType;
 typedef typename BubbleInnerLoop<max_index, index+1, BubbleStepType>::type type;
};
template <int max_index, class T>
struct BubbleInnerLoop<max_index, max_index, T>
{
 typedef typename T type;
};

template <int max_index, int index, class T>
struct BubbleOuterLoop
{
 typedef typename BubbleInnerLoop<max_index, 0, T>::type BubbleStepType;
 typedef typename BubbleOuterLoop<max_index, index + 1, BubbleStepType>::type type;
};
template <int max_index, class T>
struct BubbleOuterLoop<max_index, max_index, T>
{
 typedef typename T type;
};

The state is our type T that holds the integer list, and the iteration is the BubbleIter. We can see here that the inner loop produces the type based on the BubbleIter and that T is the type passing as input and output template parameter. But let’s push even further — this is true for the BubbleOuterLoop as well! So we get two in the price of one, like this

template <class T>
struct BubbleSort
{
 template <int index, class T>
 struct InternalIter
 {
  typedef typename ForLoop<0, IntVec_Size<T>::value - 1, T, BubbleIter>::state state;
 };

 typedef typename ForLoop<0, IntVec_Size<T>::value - 1, T, InternalIter>::state type;
};

This is some clean looking template meta-programmed double loop!

A more complicated implementation

There was another loop in the original post. That was the “Debugging” loop, that checks to see that the resulting IntVec is indeed sorted. This is a bit more complicated, because now the state includes other than the list itself (T) a Boolean (value) that indicates if the IntVec is sorted or not.

template <int max_index, int index, class T>
struct CheckSortedLoop
{
 typedef typename IntVec_Get<index, T>::type I1type;
 typedef typename IntVec_Get<index + 1, T>::type I2type;

 static constexpr bool value = (I1type::value <= I2type::value) && CheckSortedLoop<max_index, index+1, T>::value;
};

template <int max_index, class T>
struct CheckSortedLoop<max_index, max_index, T>
{
 static constexpr bool value = true;
};

template <class T>
struct CheckSorted
{
 static constexpr bool value = CheckSortedLoop<IntVec_Size<T>::value - 1, 0, T>::value;
};

So, the state is a Boolean value and T the list, and the iteration is the part that is doing

value = (I1type::value <= I2type::value) && value;

So here we need to define a new state type to hold both these values, and write an iteration that performs the above line. In the code I used CheckSortedState and CheckSortedIter respectively

template <class T>
struct CheckSorted
{
 template<bool b, class T>
 struct CheckSortedState
 {
  typedef Bool<b> _bool;
  typedef T       _T;
 };

 template<int index, class State>
 struct CheckSortedIter
 {
  typedef typename State::_T T;
  typedef typename State::_bool B;

  typedef typename IntVec_Get<index, T>::type I1type;
  typedef typename IntVec_Get<index + 1, T>::type I2type;

  // the output of the iteration 'value' is '(I1type::value <= I2type::value) && value'
  typedef CheckSortedState<(I1type::value <= I2type::value) && B::value, T> state;
 };

 // run the loop from 0 to the size-1 of the IntVec T, using CheckSortedIter to update the CheckSertedState
 typedef typename ForLoop<0, IntVec_Size<T>::value - 1, CheckSortedState<true, T>, CheckSortedIter>::state final_state;

 // produce the value computed by the previous line
 static constexpr bool value = final_state::_bool::value;
};

Appologies

Due to lack of proper convention, the code seems a bit confusing, even for a template code. The next chapter will introduce the complete reworked solution explained with more details. In the meantime — what do you think is the next obvious flow control statement in the code that can be reworked? See the The problem section of the first post.