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,
{ ... };

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()),

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>
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;
for(typename HeadContainer::const_iterator iter = head_container_.begin();
iter != head_container_.end();
ValueTypeTuple vtuple;
return tran;


void populate_tuple(ValueTypeTuple & vtuple)
if(head_iter_ == head_container_.end())
throw std::runtime_error("Container bound exceeded.");
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.


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.
Paul Graphov said…
gcc-4.4 supports it too with -std=c++0x
cornedbee 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
Cpp Programs said…
i like c++ programming so much.............visit my blog 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...
xander345 said…
if you like c++ you can compile it online here:

32, 64 - windows & Linux - and more programming languages
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 Tambe said…
I use SyntaxHighlighter 3.0.83 ( There is ample information on how to use it for blogspot or other blog hosting websites. You may also like to use to host your own javascript sources. You can do "View page source" to get a better idea how I'm doing it. Cheers!

Popular posts from this blog

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 two r…

Understanding Fold Expressions

C++17 has an interesting new feature called fold expressions. Fold expressions offer a compact syntax to apply a binary operation to the elements of a parameter pack. Here’s an example. template <typename... Args> auto addall(Args... args) { return (... + args); } addall(1,2,3,4,5); // returns 15. This particular example is a unary left fold. It's equivalent to ((((1+2)+3)+4)+5). It reduces/folds the parameter pack of integers into a single integer by applying the binary operator successively. It's unary because it does not explicitly specify an init (a.k.a. identity) argument. So, let add it. template <typename... Args> auto addall(Args... args) { return (0 + ... + args); } addall(1,2,3,4,5); // returns 15. This version of addall is a binary left fold. The init argument is 0 and it's redundant (in this case). That's because this fold expression is equivalent to (((((0+1)+2)+3)+4)+5). Explicit identity elements will come in handy a little la…

Folding Monadic Functions

In the previous two blog posts (Understanding Fold Expressions and Folding Functions) we looked at the basic usage of C++17 fold expressions and how simple functions can be folded to create a composite one. We’ll continue our stride and see how "embellished" functions may be composed in fold expressions.

First, let me define what I mean by embellished functions. Instead of just returning a simple value, these functions are going to return a generic container of the desired value. The choice of container is very broad but not arbitrary. There are some constraints on the container and once you select a generic container, all functions must return values of the same container. Let's begin with std::vector.
// Hide the allocator template argument of std::vector. // It causes problems and is irrelevant here. template <class T> struct Vector : std::vector<T> {}; struct Continent { }; struct Country { }; struct State { }; struct City { }; auto get_countries…