Generic vector of vector n dimensionnal

Question

I try something (probably in the wrong way) but the langage and std doesn't let me do what I want. I have a void* that can contain : std::vector<int> or std::vector<std::vector<int>> or std::vector<std::vector<std::vector<int>>> or ... and so on. I have a dpeth variable to know how much vector level.

So I "just" want to write a method that iterate through my vector and for each element give to me a new void* to a subVector or int. But I can't get generically a sub element from my vector if don't give the real type (which can be very very very long) I'm trying to macro some typedef :

using DIM1 = std::vector<int>;
using DIM2 = std::vector<std::vector<int>>;

But I can't convert my void* to a DIMX* (without an insane switch case statement)

Any ideas, (or other ways to approach the problem)

Answer 1

Probably there is a better way for you to achieve what you want to do, but you can use templates like:

#include <vector>
#include <cstddef>

template <size_t DEPTH>
struct helper;

template <>
struct helper<1>{
    using type = std::vector<int>;
};

template <size_t DEPTH>
struct helper {
    using type = std::vector<typename helper<DEPTH-1>::type>;
};

template <size_t DEPTH>
typename helper<DEPTH>::type* cast_to_vector(void* data){
    return static_cast<typename helper<DEPTH>::type*>(data);
}


int main() {

    std::vector<std::vector<std::vector<int>>> vec{};
    void * example = &vec;
    std::vector<std::vector<std::vector<int>>>* vec_prt = cast_to_vector<3>(example);
    return 0;
}

This will recursively construct the type you want. You can also ignore the cast_to_vector function and use the helper classes.

If these are not compile time constants then this might be more problematic. One easy, but potentially very messy method of working with this is by using a custom datatype, like:

template <typename T>
class Tree : public std::vector<Tree<T>>{
    public:
        operator T&() { return val; }
        Tree& operator =(const T& new_val) {
            this->val = new_val;
            return *this;
        }
    private:
        T val;
};

This implementation does miss a lot of things you'd want, but it does work for demonstration. You can then access this iteratively like a[0][2][3] = 10; An other option (especially useful if the data's size is constant), would be to implement a new object, something like:

template <typename T, bool ret_self = true>
class Tree {
    public:
        Tree(const std::vector<size_t>& arr_sizes)
            : data_size{arr_sizes}
            , data{std::make_shared<T[]>(prod(arr_sizes))}
            , array{data.get()} {}

         Tree<T>& operator[] (size_t index) {
             std::vector<size_t> new_sizes = data_size;
             new_sizes.erase(new_sizes.begin());
             if (new_sizes.empty())
                return Tree<T>(new_sizes, this->data, array + prod(new_sizes)*index);
            return Tree<T,false>(new_sizes, this->data, array + prod(new_sizes)*index);
        }
    private:
        Tree(std::vector<size_t>&& arr_sizes, const std::shared_ptr<T>& d, T* arr)
            : data_size{arr_sizes}
            , data_size{d}
            , array{arr} {}
        std::vector<size_t> data_size;
        std::shared_ptr<T> data;
        T* array;
};

template <typename T>
class Tree<T,false> {
    public:
        Tree(const std::vector<size_t>& arr_sizes)
            : data_size{arr_sizes}
            , data{std::make_shared<T[]>(prod(arr_sizes))}
            , array{data.get()} {}

         T& operator[] (size_t index) {
             return this->array[index];
        }
    private:
        Tree(std::vector<size_t>&& arr_sizes, const std::shared_ptr<T>& d, T* arr)
            : data_size{arr_sizes}
            , data_size{d}
            , array{arr} {}
        std::vector<size_t> data_size;
        std::shared_ptr<T> data;
        T* array;
};

As stated however this does not work if the data's size is ever modified, and also it might be a bit convoluted.

Answer 2

First of all, prefer a std::any (rather than void*) to allow a variable to take on values of any type.

Here is a way to describe your strongly-typed N-dimensional jagged vector.

#include <vector>
#include <any>

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

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

int main()
{
    // Let's populate a minimal 4-D example object.
    DIM<4, int> foo;
    foo.push_back(DIM<3,int>());
    foo[0].push_back(DIM<2,int>());
    foo[0][0].push_back(DIM<1, int>());
    foo[0][0][0].push_back(1);

    // example of stashing it in a std::any
    std::any idk = foo;
    
    // example of extracting the contents of idk
    DIM<4, int> bar;
    bar = std::any_cast<DIM<4, int>>(idk);
}

(Above example requires C++17.)

But you still are required to know the dimension at compile time. This doesn't get you a run-time-variable number of dimensions (variable depth).

If you require variable depth at run-time then look for a tree data structure.

Answer 3

You should use a flat vector.

The big advantage of std::vector is that its elements are stored in contiguous memory. The big disadvantage of nested std::vector is that the innermost elements are not stored in contiguous memory.

Consider how a std::vector<int> looks like roughly:

struct fake_vector {
     int* data;
     size_t size;
};

Internally it has a pointer to heap allocated elements:

|---------|            elements
| vector  | --->   [0][1][2][3]...........
|---------|

A std::vector<std::vector<int>> however looks like this

|--------------|       |--------------|            some elements
| outer vector | --->  | inner vector | ---->      [0][1][2].....
|--------------|       |--------------|        
                       |--------------|            some elements
                       | inner vector | ---->      [0][1][2]....
                       |--------------|
                       | ....         |
                       |--------------|

The inner vectors are stored contiguously, but the elements on the lowest level are scattered around in memory.

Using a flat vector in place of a N-dimensional array is just a matter of index transformations. The following isnt the nicest way to do it, but I hope it suffices to illustrate the idea:

#include <iostream>
#include <vector>

struct N_dims {
    N_dims(std::initializer_list<size_t> d) : dims(d) {
        sizes.resize(dims.size());
        auto it = dims.rbegin();
        auto its = sizes.rbegin();
        *its = *it;
        for (++it; it != dims.rend(); ++it) { 
            auto prev = *its;
            ++its;
            *its = *it * prev;                        
        }
        data.resize(sizes[0]);
    }
    int& operator()(std::vector<size_t> index) {
        auto it = index.rbegin();
        size_t flat_index = *it;
        auto its = sizes.rbegin();
        for (++it; it != index.rend(); ++it) {
            flat_index += *it * *its;
            ++its;
        }
        return data[flat_index];
    }

    std::vector<size_t> dims;
    std::vector<int> data;
    std::vector<size_t> sizes;
};


int main()
{
    N_dims nd{2,3,4};
    nd({0,0,0}) = 1;
    nd({0,0,3}) = 2;
    nd({0,1,0}) = 3;
    nd({0,1,3}) = 4;
    nd({0,2,3}) = 5;
    nd({1,0,0}) = 6;  // first element of second 3x4 submatrix. 
                      // Its "flat index" is 1*3*4 + 0*4 + 0 = 12
    nd({1,0,3}) = 7;
    nd({1,2,3}) = 8;
    for (const auto& e : nd.data) {
        std::cout << e << " ";
    }
}

Output:

1 0 0 2 3 0 0 4 0 0 0 5 6 0 0 7 0 0 0 0 0 0 0 8