c++ - How can I use C++11 variadic templates to define a vector-of-tuples backed by a tuple-of-vectors?

Question

Suppose I have a bunch of vectors:

vector<int> v1;
vector<double> v2;
vector<int> v3;

all of the same length. Now, for every index i, I would like to be able to treat (v1[i], v2[i], v3[i]) as a tuple, and maybe pass it around. In fact, I want to have a a vector-of-tuples rather than a tuple-of-vectors, using which I can do the above. (In C terms, I might say an array-of-structs rather than a struct-of-arrays). I do not want to effect any data reordering (think: really long vectors), i.e. the new vector is backed by the individual vectors I pass in. Let's .

Now, I want the class I write (call it ToVBackedVoT for lack of a better name) to support any arbitrary choice of vectors to back it (not just 3, not int, double and int, not every just scalars). I want the vector-of-tuples to be mutable, and for no copies to be made on construction/assignments.

If I understand correctly, variadic templates and the new std::tuple type in C++11 are the means for doing this (assuming I don't want untyped void* arrays and such). However, I only barely know them and have never worked with them. Can you help me sketch out how such a class will look like? Or how, given

template <typename ... Ts>

I can express something like "the list of template arguments being the replacement of each typename in the original template arguments with a vector of elements of this type"?

Note: I think I might also want to later be able to adjoin additional vectors to the backing vectors, making an instance of ToVBackedVoT<int, double, int> into, say, an instance of ToVBackedVoT<int, double, int, unsigned int>. So, bear that in mind when answering. This is not critically important though.

Answer 1

One idea is to keep the storage in the "struct of array" style in form of vectors for good performance if only a subset of the fields are used for a particular task. Then, for each kind of task requiring a different set of fields, you can write a lightweight wrapper around some of those vectors, giving you a nice random access iterator interface similar to what std::vector supports.

Concerning the syntax of variadic templates, this is how a wrapper class (without any iterators yet) could look like:

template<class ...Ts> // Element types
class WrapMultiVector
{
    // references to vectors in a TUPLE
    std::tuple<std::vector<Ts>&...> m_vectors;

public:
    // references to vectors in multiple arguments
    WrapMultiVector(std::vector<Ts> & ...vectors)
        : m_vectors(vectors...)    // construct tuple from multiple args.
    {}
};

To construct such a templated class, it's often preferred to have a template type deducting helper function available (similar to those make_{pair|tuple|...} functions in std):

template<class ...Ts> // Element types
WrapMultiVector<Ts...> makeWrapper(std::vector<Ts> & ...vectors) {
    return WrapMultiVector<Ts...>(vectors...);
}

You already see different types of "unpacking" the type list.

Adding iterators suitable to your application (you requested in particular random access iterators) is not so easy. A start could be forward only iterators, which you might extend to random access iterators.

The following iterator class is capable of being constructed using a tuple of element iterators, being incremented and being dereferenced to obtain a tuple of element references (important for read-write access).

class iterator {
    std::tuple<typename std::vector<Ts>::iterator...> m_elemIterators;

public:
    iterator(std::tuple<typename std::vector<Ts>::iterator...> elemIterators) 
        : m_elemIterators(elemIterators)
    {}

    bool operator==(const iterator &o) const {
        return std::get<0>(m_elemIterators) == std::get<0>(o.m_elemIterators);
    }
    bool operator!=(const iterator &o) const {
        return std::get<0>(m_elemIterators) != std::get<0>(o.m_elemIterators);
    }

    iterator& operator ++() {
        tupleIncrement(m_elemIterators);
        return *this;
    }
    iterator operator ++(int) {
        iterator old = *this;
        tupleIncrement(m_elemIterators);
        return old;
    }

    std::tuple<Ts&...> operator*() {
        return getElements(IndexList());
    }

private:
    template<size_t ...Is>
    std::tuple<Ts&...> getElements(index_list<Is...>) {
        return std::tie(*std::get<Is>(m_elemIterators)...);
    }
};

For demonstration purposes, two different patterns are in this code which "iterate" over a tuple in order to apply some operation or construct a new tuple with some epxression to be called per element. I used both in order to demonstrate alternatives; you can also use the second method only.

1. tupleIncrement: You can use a helper function which uses meta programming to index a single entry and advance the index by one, then calling a recursive function, until the index is at the end of the tuple (then there is a special case implementation which is triggered using SFINAE). The function is defined outside of the class and not above; here is its code:

   template<std::size_t I = 0, typename ...Ts>
   inline typename std::enable_if<I == sizeof...(Ts), void>::type
   tupleIncrement(std::tuple<Ts...> &tup)
   { }
   template<std::size_t I = 0, typename ...Ts>
   inline typename std::enable_if<I < sizeof...(Ts), void>::type
   tupleIncrement(std::tuple<Ts...> &tup)
   {
       ++std::get<I>(tup); 
       tupleIncrement<I + 1, Ts...>(tup);
   }
   

   This method can't be used to assign a tuple of references in the case of operator* because such a tuple has to be initialized with references immediately, which is not possible with this method. So we need something else for operator*:

2. getElements: This version uses an index list (https://stackoverflow.com/a/15036110/592323) which gets expanded too and then you can use std::get with the index list to expand full expressions. The IndexList when calling the function instantiates an appropriate index list which is only required for template type deduction in order to get those Is.... The type can be defined in the wrapper class:

   // list of indices
   typedef decltype(index_range<0, sizeof...(Ts)>()) IndexList;
   

More complete code with a little example can be found here: http://ideone.com/O3CPTq

Open problems are:

• If the vectors have different sizes, the code fails. Better would be to check all "end" iterators for equality; if one iterator is "at end", we're also "at end"; but this would require some logic more than operator== and operator!= unless it's ok to "fake" it in; meaning that operator!= could return false as soon as any operator is unequal.

• The solution is not const-correct, e.g. there is no const_iterator.

• Appending, inserting etc. is not possible. The wrapper class could add some insert or and / or push_back function in order to make it work similar to std::vector. If your goal is that it's syntactically compatible to a vector of tuples, reimplement all those relevant functions from std::vector.

• Not enough tests ;)