Generic Transpose using boost tuples
Recently, while working on LEESA I faced an interesting problem of creating a transpose using generic programming. The problem is pretty straight forward. Suppose you are given a tuple of 2 vectors i.e. tuple<vector<int>, vector<long> >. Assuming both the vectors are of the same size, how would create a vector <tuple<int, long> > containing the data from the earlier two vectors? Of course, the size of the tuple may vary.Lets call the function transpose. A brute force solution would be to overload transpose function N times such that each one takes different size of tuple. Here's one that takes a three parameter tuple.
template <class C1, class C2, class C3> // Assuming all Cs are STL containers
std::vector<tuple<C1::value_type, C2::value_type, C3::value_type> >
transpose (tuple<C1, C2, C3> const &) { ... }
}
The implementation is fairly straight forward for those who have seen tuples in the past. We basically need a loop with three forward iterators that iterate over the source containers and populate a resultant tuple in each iteration. The resultant tuple is pushed into the vector that is returned at the end.
However, implementing this in a more generic fashion is quite a lot of fun! A bit of metaprogramming and a byte of compile-time hierarchy generation gets the job done. Lets begin!
First we need to extract out the value_types from the containers and create the type of the resultant tuple. Here is a small metaprogram that does half the job.
template <>
struct GetTransposeCons<tuples::null_type>
{
typedef tuples::null_type type;
};
template <class TupleOfVectors>
struct GetTransposeCons
{
typedef typename TupleOfVectors::head_type Head;
typedef typename TupleOfVectors::tail_type Tail;
typedef typename
tuples::cons<typename remove_reference<Head>::type::value_type,
typename GetTransposeCons<Tail>::type> type;
};
Given a TupleOfVectors, it produces a cons-list, which is the underlying representation of boost tuples. remove_reference is not strictly needed here, but we'll see its use at the end. This metaprogram produces type cons<int, cons<float, cons<double, tuples::null_type> > > if we give tuple<vector<int>, vector<float>, vector<double> > as the input. The cons-list is practically as useful as the tuple itself. You can print it using tuple's I/O functionality, convert it into a regular tuple and so on so forth.
But promise is a promise, we have to create a tuple! Lets write simple mapping from cons list to tuples. We create many(!) specializations of cons-list to do the mapping.
template <class T>
struct GetTransposeTuple;
template <class T0>
struct GetTransposeTuple<cons<T0, null_type> >
{
typedef tuples::tuple<T0> type;
};
template <class T0, class T1>
struct GetTransposeTuple<cons<T0, cons<T1, null_type> > >
{
typedef tuples::tuple<T0, T1> type;
};
template <class T0, class T1, class T2>
struct GetTransposeTuple<cons<T0, cons<T1, cons<T2, null_type> > > >
{
typedef tuples::tuple<T0, T1, T2> type;
};
I've not found a better way to do it. May be boost tuples have a simpler way to create an equivalent tuple type from cons-list like it does the other way round. tuple::inherited returns the underlying cons-list. Reverse mapping would be nice to have.
With that now we can write a slightly complicated metafunction that converts a TupleOfVectors to a tuple of value_types. Here is how it looks.
typedef typename GetTransposeTuple<
typename GetTransposeCons<TupleOfVectors>::type
>::type ValueTypeTuple;
Lets proceed with the hierarchy generation part. Hierarchy generation is quite idiomatic in C++ template metaprogramming while working on list of types as in tuples. Whenever there is a need to generate code that does something useful at run-time (not just compile-time) hierarchy generation comes quite handy. It is applicable when a single class can encapsulate the necessary run-time code for a single type in the cons-list (actually any other type-list for that matter). Rest is just the coordination of the generated classes. It's that simple!
In the case of generic transpose, there needs to be a class for each type in the tuple. Each class does the following things.
1. Hold a reference to the source vector.
2. Hold an iterator to that vector.
3. Extract the value iterator is pointing to and advance the iterator.
4. Copy the value into the <span style="font-weight:bold;">right</span> position in the resultant tuple.
Finally, the resultant tuple is pushed in the resultant vector, which is returned when all the iterators reach the end.
The gist of hierarchy generation is in its inheritance expression.
template <class TupleOfVectors,
class ValueTypeTuple = /* we saw earlier */,
unsigned int TUPLE_INDEX = 0>
struct Transposer
: Transposer <typename TupleOfVectors::tail_type,
ValueTypeTuple,
TUPLE_INDEX + 1>
{ ... };
template <class ValueTypeTuple,
unsigned int INDEX>
struct Transposer <tuples::null_type, ValueTypeTuple, INDEX>
{ ... };
Transposer inherits from another instantiation of itself. The first and the third template parameters change progressively. The recursion ends only when the TupleOfVectors is exhausted and that's when the null_type specialization of the Transposer comes into picture. Note that the ValueTypeTuple remains unchanged throughout the hierarchy but the INDEX into that ValueTypeTuple increases. That is, if the derived Transposer copies the value in slot #i then its immediate base Transposer copies the value in slot #i+1. We don't care what the slot number is for the Transposer of null_type specialization.
Lets now write the body of the Transposer. Here are some typedef that come handy in the implementation of the Transposer template.
typedef typename TupleOfVectors::head_type Head; typedef typename TupleOfVectors::tail_type Tail; typedef typename remove_reference<Head>::type HeadContainer; typedef Transposer<Tail, ValueTypeTuple, TUPLE_INDEX + 1> super; typedef ValueTypeTuple TransposeTuple; typedef std::vector<ValueTypeTuple> Transpose;
The class template has two private members.
HeadContainer const & head_container_; typename HeadContainer::const_iterator head_iter_;
Note that the HeadContainer is gonna be different in every instantiation of the Transposer. The constructor looks like this
Transposer(TupleOfVectors const & tuple)
: super(tuple.get_tail()),
head_container_(tuple.get_head()),
head_iter_(head_container_.begin())
{}
Each constructor takes what it needs from the TupleOfVectors and passes the rest of it to its base class. Tuple expects such use and provides the right API (get_head, get_tail) to achieve that. The reference to the container is assigned to the head_container_ member and the iterator is also initialized. The same happens in all the constructors except the last one that is a specialization of null_type. Its constructor is no-op.
template <class ValueTypeTuple,
unsigned int INDEX>
struct Transposer <tuples::null_type, ValueTypeTuple, INDEX>
{
protected:
void populate_tuple(ValueTypeTuple &) {}
Transposer (tuples::null_type const &) {}
};
With this much setup, everything that is needed to begin transpose procedure is arranged neat and tidy. Now we write the final get_transpose method that creates the transpose.
Transpose get_transpose ()
{
Transpose tran;
tran.reserve(head_container_.size());
for(typename HeadContainer::const_iterator iter = head_container_.begin();
iter != head_container_.end();
++iter)
{
ValueTypeTuple vtuple;
this->populate_tuple(vtuple);
tran.push_back(vtuple);
}
return tran;
}
protected:
void populate_tuple(ValueTypeTuple & vtuple)
{
if(head_iter_ == head_container_.end())
throw std::runtime_error("Container bound exceeded.");
else
{
vtuple.get<TUPLE_INDEX>() = *head_iter_++;
super::populate_tuple (vtuple);
}
}
get_transpose method has a loop that iterates over all the elements of the head_container. For each iteration, it creates a default initialized ValueTypeTuple, which needs to be populated with one sample from each of the source containers. We do that in the populate_tuple method, which receives the tuple as a non-const reference. It does #3 and #4 bullets mentioned earlier. It extracts one data sample from the container using the iterator, advances the iterator, and then copies that data sample into the "right place" in the tuple. The "right place" is nothing but the INDEX parameter that was passed while creating the hierarchy. Once again, tuple provided the right API to assign the Nth entry in a tuple provided N is known at compile-time. Finally, the same procedure has to happen in every class in the hierarchy. We simply call the base class's populate_tuple function and pass the partially populated ValueTypeTuple by reference. Note that populate_tuple throws runtime_error exception if some iterator hits end of the container in the middle of transpose procedure.
Finally, we implement the transpose function in terms of Transposer template.
template <class TupleOfVectors>
typename Transposer<TupleOfVectors>::Transpose
transpose (TupleOfVectors const & tupleofv)
{
return Transposer<TupleOfVectors>(tupleofv).get_transpose();
}
Here is how we use it.
int arr[5] = {10, 20, 30, 40, 50};
std::vector<int> vint(arr, arr+5);
std::list<float> lfloat(arr, arr+5);
std::vector<long> vlong(arr, arr+5);
Transposer<TupleOfV>::Transpose tran
= transpose(make_tuple(cref(vint), cref(lfloat), cref(vlong)));
To avoid unnecessary copies of the source vectors, we make use of cref reference_wrapper. In such cases, each entry is a const-reference to the original container, which causes problems in the GetTransposeCons metafunction if we don't use remove_reference.
The complete source code is available here.
