向量 n 维的通用向量

Question

我尝试了一些东西（可能以错误的方式），但语言和标准不允许我做我想做的事。我有一个 void* 可以包含：std::vector<int> 或 std::vector<std::vector<int>> 或 std::vector<std::vector<std::vector<int>>> 或 ... 等等。我有一个 dpeth 变量来知道有多少向量级别。

所以我“只是”想编写一个方法来遍历我的向量，并为每个元素给我一个新的 void* 到 subVector 或 int。但是如果不给出真实类型（可能非常非常长），我通常无法从我的向量中获取子元素我正在尝试宏一些 typedef :

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

但我无法将 void* 转换为 DIMX*（没有疯狂的 switch case 语句）

任何想法，（或解决问题的其他方法）

Answer 1

您可能有更好的方法来实现您的目标，但您可以使用以下模板：

#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;
}

这将递归地构造你想要的类型。也可以忽略cast_to_vector函数，使用helper类.

如果这些不是编译时常量，那么这可能会有更多问题。一种简单但可能非常混乱的处理方法是使用自定义数据类型，例如：

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;
};

此实现确实遗漏了很多您想要的东西，但它确实适用于演示。然后您可以像 a[0][2][3] = 10; 一样迭代访问它另一种选择（如果数据大小不变，则特别有用）是实现一个新对象，例如：

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;
};

如前所述，但是如果数据的大小被修改，这将不起作用，而且它可能有点复杂。

Answer 2

首先，更喜欢 std::any（而不是 void*）以允许变量采用任何类型的值。

这是一种描述 strongly-typed N-dimensional 锯齿状矢量的方法。

#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);
}

(以上示例需要 C++17。)

但是你仍然需要在编译时知道维度。这不会为您提供 run-time-variable 个维度（可变深度）。

如果您需要 run-time 的可变深度，则寻找 tree 数据结构。

Answer 3

你应该使用平面向量。

std::vector 的一大优点是它的元素存储在连续的内存中。嵌套的一大缺点std::vector是最里面的元素没有存储在连续的内存中。

考虑一下 std::vector<int> 大致的样子：

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

在内部它有一个指向堆分配元素的指针：

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

A std::vector<std::vector<int>> 但是看起来像这样

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

内部向量是连续存储的，但最低层的元素分散在内存中。

使用平面向量代替 N-dimensional 数组只是索引转换的问题。以下不是最好的方法，但我希望它足以说明这个想法：

#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

向量 n 维的通用向量

Generic vector of vector n dimensionnal

c++

vector