Skip to main content

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.

Comments

lefticus said…
You would be able to collapse your hand rolled GetTransposeTuple using the boost preprocessor metaprogramming library.

A second option would be to use variadic templates which are supported by most modern compilers right now.
Sumant said…
@lefticus: I don't think variadic templates are well-supported today. VS2010, IBM C++ compiler 10.1, Comeau 4.3.10, C++ Builder 2009 don't support them. g++ 4.5 is the only one I know that does. But you are right that variadic templates will make it more elegant.
Unknown said…
gcc-4.4 supports it too with -std=c++0x
Anonymous said…
VS 2010 has some support for variadic macros as well.

On a side note, I would call this function zip, not transpose. Transpose's classical meaning is to swap the dimensions in a 2-dimensional structure, like a vector of vectors.
Anonymous said…
check out for more details cpp http://learnsthgeveryday.blogspot.com/
Cpp Programs said…
i like c++ programming so much.............visit my blog http://cpp-programs.blogspot.com/ for almost all c++ programs.............
Mathias Gaunard said…
boost::zip_iterator and related utilities already solve that problem, and without even having to copy the data.
Tutorials Mad said…
thanks for the nice tutorial... it helped me...
CrazyBugger said…
I would like to know how you post ur c++ codes in a nice manner...
Send any useful link... Through the mail or else post it on this comment area
Please Please Please
Sumant said…
I use SyntaxHighlighter 3.0.83 (http://alexgorbatchev.com/SyntaxHighlighter/) There is ample information on how to use it for blogspot or other blog hosting websites. You may also like to use http://sites.google.com to host your own javascript sources. You can do "View page source" to get a better idea how I'm doing it. Cheers!

Popular Content

Unit Testing C++ Templates and Mock Injection Using Traits

Unit testing your template code comes up from time to time. (You test your templates, right?) Some templates are easy to test. No others. Sometimes it's not clear how to about injecting mock code into the template code that's under test. I've seen several reasons why code injection becomes challenging. Here I've outlined some examples below with roughly increasing code injection difficulty. Template accepts a type argument and an object of the same type by reference in constructor Template accepts a type argument. Makes a copy of the constructor argument or simply does not take one Template accepts a type argument and instantiates multiple interrelated templates without virtual functions Lets start with the easy ones. Template accepts a type argument and an object of the same type by reference in constructor This one appears straight-forward because the unit test simply instantiates the template under test with a mock type. Some assertion might be tested in

Multi-dimensional arrays in C++11

What new can be said about multi-dimensional arrays in C++? As it turns out, quite a bit! With the advent of C++11, we get new standard library class std::array. We also get new language features, such as template aliases and variadic templates. So I'll talk about interesting ways in which they come together. It all started with a simple question of how to define a multi-dimensional std::array. It is a great example of deceptively simple things. Are the following the two arrays identical except that one is native and the other one is std::array? int native[3][4]; std::array<std::array<int, 3>, 4> arr; No! They are not. In fact, arr is more like an int[4][3]. Note the difference in the array subscripts. The native array is an array of 3 elements where every element is itself an array of 4 integers. 3 rows and 4 columns. If you want a std::array with the same layout, what you really need is: std::array<std::array<int, 4>, 3> arr; That's quite annoying for

Covariance and Contravariance in C++ Standard Library

Covariance and Contravariance are concepts that come up often as you go deeper into generic programming. While designing a language that supports parametric polymorphism (e.g., templates in C++, generics in Java, C#), the language designer has a choice between Invariance, Covariance, and Contravariance when dealing with generic types. C++'s choice is "invariance". Let's look at an example. struct Vehicle {}; struct Car : Vehicle {}; std::vector<Vehicle *> vehicles; std::vector<Car *> cars; vehicles = cars; // Does not compile The above program does not compile because C++ templates are invariant. Of course, each time a C++ template is instantiated, the compiler creates a brand new type that uniquely represents that instantiation. Any other type to the same template creates another unique type that has nothing to do with the earlier one. Any two unrelated user-defined types in C++ can't be assigned to each-other by default. You have to provide a