How to declare high order vectors vector<vector<vector<.....<vector<double>>>>>...>

Hello,

I suspect that C++11 would make it possible to declare high rank vectors such as

Code:

---

int N = 15; // chosen arbitrary rank
vector<vector<vector<...<vector<double>>>>..> vec; // N layers of nested vectors

---

Is there a way to declare such a vector of rank N (given a fixed integer rank N)?

Heuristically I would like to write the declaration like this:

Code:

---


vector<double> A;
vector<A> vec[0];
for(int i=1; i<N; i++)
{
  vector<vec[i-1]> vec[i];
}

---

Is there a way to use the new variadic templates to make this work?




Many thanks.

> int N = 15; // chosen arbitrary rank
> vector<vector<vector<...<vector<double>>>>..> vec; // N layers of nested vectors
And how many elements do you plan to store in each dimension?

With just the equivalent of
double vec[4][4][4][4][4][4][4][4][4][4][4][4][4][4][4];
you're looking at 8GB just to store the data, and who knows how overhead of storing all the vector information.

Replace 4 with 5, and it jumps to 256GB!

Declaring it seems much less of a problem than finding a machine with enough memory to deal with the result.

Perhaps you should describe the problem you're trying to solve, rather than how to implement your current approach.

Quote:

---

Originally Posted by Salem

> int N = 15; // chosen arbitrary rank
> vector<vector<vector<...<vector<double>>>>..> vec; // N layers of nested vectors
And how many elements do you plan to store in each dimension?

With just the equivalent of
double vec[4][4][4][4][4][4][4][4][4][4][4][4][4][4][4];
you're looking at 8GB just to store the data, and who knows how overhead of storing all the vector information.

Replace 4 with 5, and it jumps to 256GB!

Declaring it seems much less of a problem than finding a machine with enough memory to deal with the result.

Perhaps you should describe the problem you're trying to solve, rather than how to implement your current approach.

---

Thanks a lot for the comments.

The above choice N=15 was only for illustration purposes. So far I have not yet used more than 4 layers of vectors, and probably the N will never exceed 7.

But I would like to make this rank N variable, to add flexibility.

Code:

---

template <typename T, int N>
class NestedVectorType
{
public:
        typedef std::vector<typename NestedVectorType<T, N-1>::type> type;
};

template <typename T>
class NestedVectorType<T, 1>
{
public:
        typedef std::vector<T> type;
};

// Declare a 15-dimensional vector of integers
NestedVectorType<int, 15>::type vec;

---

EDIT: More would be required than just this basic level to be useful. For instance, functions to set the size of the vector's various dimensions.

You can do it in any standard version of C++

Code:

---

#include <vector>

template<std::size_t n> struct Vec
{
    typedef std::vector<typename Vec<n-1>::type>  type;
};

template<> struct Vec<0>
{
    typedef double type;
};

int main()
{
      Vec<15>::type  a_vector;
}

---

You'll get an unpleasant surprise with how long it takes to compile though.

The technique is recursive at compile time, and most modern compilers enforce a limit on the depth of that recursion.

Note also that, as shown, the vectors are not sized. All you get from this is a multidimensional array .... with each dimension being of zero length. I'll leave sorting that out as an exercise (not least of which because I haven't thought through how to do that).


The real world need for more than 5 dimensions in a matrix is pretty rare (except in cases of poor design).

Thanks a lot!

It's worth noting that although Salem mentioned a 15-dimensional array with each dimension of length 4 would be 8 GB, that with vectors it would be even worse. A vector typically consists of 3 pointers, likely 4 or 8 bytes each depending on platform, plus the rest on the heap. These pointers themselves exceed the size of the data by my estimates, and that's not including the fact that heap allocations are typically rounded up to the nearest 8 bytes in size or so either.
Every item in a 15-dimensional matrix requires traversing 14 levels of vectors to get to it too. That's following 15 pointers to get there!
Performance would be, in a word... "laughable".

It probably doesn't make sense to use vectors in this case. Unless any of the dimensions must be adjustable or it must be a ragged matrix (e.g. rows with different length), then the better option is to use a nested std::array.

If you need such a high rank, sparse matrix is the way to go. However, this requires you to write your own variadic class template which must consider the rank. As a really simple, reference implementation, std::unordered_map of tuples as keys can do the job. I've written a simplified implementation with operator() which takes a variable number of parameters and forwards them as tuple to the map (operator() acts here the same way as operator[], but can take a variable number of operands and hides implementation detail which is using a tuple).

Code:

---

#include <iostream>
#include <string>
#include <tuple>
#include <unordered_map>

// http://stackoverflow.com/questions/7110301/generic-hash-for-tuples-in-unordered-map-unordered-set

size_t hash_combiner(size_t left, size_t right) //replacable
{ return left^right;}

template<int index, class...types>
struct hash_impl {
    size_t operator()(size_t a, const std::tuple<types...>& t) const {
        typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype;
        hash_impl<index-1, types...> next;
        size_t b = std::hash<nexttype>()(std::get<index>(t));
        return next(hash_combiner(a, b), t);
    }
};
template<class...types>
struct hash_impl<0, types...> {
    size_t operator()(size_t a, const std::tuple<types...>& t) const {
        typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype;
        size_t b = std::hash<nexttype>()(std::get<0>(t));
        return hash_combiner(a, b);
    }
};

namespace std {
    template<class...types>
    struct hash<std::tuple<types...>> {
        size_t operator()(const std::tuple<types...>& t) const {
            const size_t begin = std::tuple_size<std::tuple<types...>>::value-1;
            return hash_impl<begin, types...>()(1, t); //1 should be some largervalue
        }
    };
}

// END of stack overflow code

template <typename TupleT, typename T>
struct AppendTupleElement;

template <typename... Types, typename T>
struct AppendTupleElement<std::tuple<Types...>, T>
{
    typedef std::tuple<Types..., T> type;
};

template <unsigned int N>
struct GenerateSparseMatrixKey
{
    typedef typename AppendTupleElement
        <
            typename GenerateSparseMatrixKey<N - 1>::type,
            unsigned int
        >::type type;
};

template <>
struct GenerateSparseMatrixKey<0>
{
    typedef std::tuple<> type;
};

template <typename T, unsigned int N>
class SparseMatrix
{
public:

    typedef T MappedType;

    static constexpr unsigned int Rank = N;

    // This is the actual indexing operator.
    // Passing arguments of wrong types, or passing their wrong number,
    // will result in compile-time error.
    template <typename... Dimensions>
    MappedType& operator()(Dimensions... dimensions)
    {
        return map[std::forward_as_tuple(dimensions...)];
    }

private:

    typedef typename GenerateSparseMatrixKey<N>::type KeyType;

    // std::unordered_map has tuple as its key. I took tuple hashing
    // from stack overflow which specializes std::hash, but I would
    // personally do it by defining a separate hashing class which then
    // I would explicitly pass as a third template argument.
    std::unordered_map<KeyType, MappedType> map;
};

int main()
{
    SparseMatrix<std::string, 4> matrix;
    matrix(0, 0, 1, 2) = "AA";
    matrix(0, 0, 1, 3) = "BB";
    matrix(0, 0, 4, 4) = "CC";

    std::cout << matrix(0, 0, 1, 2) << std::endl;
    std::cout << matrix(0, 0, 1, 3) << std::endl;
    std::cout << matrix(0, 0, 1, 4) << std::endl; // doesn't exist
    std::cout << matrix(0, 0, 4, 4) << std::endl;
}

---

Compiles with GCC 4.8.1.

Many thanks for the Sparse Matrix formulation. This is very interesting. And the code compiles without any problems.

From your username, I infer you know a bit of Fortran. If that's the case, I'm surprised you haven't come across sparse matrices before. It is a rare Fortran programmer who tries to build high-dimensional arrays without knowing about sparse matrices.