(cache)多次元vectorを再帰的に作成する

generate multi-dimensional vector recursively

多重ループを書かず、パラメータの長さによって次元数が違うvectorが欲しい。

各要素数

最初は各要素数をvariadic templateにする方針。

#include <iostream>
#include <vector>

template<typename T, size_t N> std::vector<T> rec(){
    std::vector<T> r(N);
    return r;
}
template<typename T, size_t N, size_t M, size_t... Tail> auto rec(){
    typedef decltype(rec<T,M,Tail...>()) X;
    std::vector<X> r(N);
    for (int i = 0; i < N; i++)
        r[i] = rec<T,M,Tail...>();
    return r;
}

int main(){
    auto v = rec<int,3,4,5,6,7,8>();
    std::cout << v.size() << std::endl;
    std::cout << v[0].size() << std::endl;
    std::cout << v[0][0].size() << std::endl;
    std::cout << v[0][0][0].size() << std::endl;
    std::cout << v[0][0][0][0].size() << std::endl;
    std::cout << v[0][0][0][0][0].size() << std::endl;
}

次元数

動く事は動くが、要素数を動的に変更できないことに気がついた。次元数をテンプレートパラメータにするように変更。

#include <vector>
template<typename T,int n>
auto rec(const std::vector<int> &b) noexcept {
    typedef decltype(rec<T,n-1>(b)) X;
    int N = b[b.size()-n];
    std::vector<X> r(N);
    for (int i = 0; i < N; i++)
        r[i] = rec<T,n-1>(b);
    return r;
}
template<typename T>
std::vector<T> rec<T,1>(const std::vector<int> &b) noexcept {
    int N = b[b.size()-1];
    std::vector<T> r(N);
    return r;
}

しかし、これはコンパイルできない。関数テンプレートの部分特殊化はできないとのことである。
結局はクラステンプレートを作るしかなかったっぽい。関数をstaticにしておくとパフォーマンス的に少しお得な気がする。

#include <iostream>
#include <vector>

template<typename T,int n>
struct ArrayBuilder{
    static auto rec(const std::vector<int> &b) noexcept {
        typedef decltype(ArrayBuilder<T,n-1>::rec(b)) X;
        int N = b[b.size()-n];
        std::vector<X> r(N);
        for (int i = 0; i < N; i++)
            r[i] = ArrayBuilder<T,n-1>::rec(b);
        return r;
    }
};
template<typename T>
struct ArrayBuilder<T,1>{
    static std::vector<T> rec(const std::vector<int> &b) noexcept {
        int N = b[b.size()-1];
        std::vector<T> r(N);
        return r;
    }
};

int main(){
    auto v = ArrayBuilder<int,6>::rec({3,4,5,6,7,8});
    std::cout << v.size() << std::endl;
    std::cout << v[0].size() << std::endl;
    std::cout << v[0][0].size() << std::endl;
    std::cout << v[0][0][0].size() << std::endl;
    std::cout << v[0][0][0][0].size() << std::endl;
    std::cout << v[0][0][0][0][0].size() << std::endl;
}

vector等について標準的な方法

このように書くほうがvector等については標準的だが、上の方がどういったクラスにも使えて汎用性が高いと思う。というかこちらはコードが長くなりそうだったので4次元以降は省略。

#include <iostream>
#include <vector>

int main(){
    auto v = std::vector<std::vector<std::vector<int>>>(3,std::vector<std::vector<int>>(4,std::vector<int>(5)));
    std::cout << v.size() << std::endl;
    std::cout << v[0].size() << std::endl;
    std::cout << v[0][0].size() << std::endl;
}

実際の動機

KuinInKuin C++バックエンドの配列はこのようなArray_クラスによって表現されている。これの多次元配列が欲しかったのである。
元はshared_ptrを使わずに生ポインタを返し、これを内部的にキャストして内側の配列を得ていたようだ。
ただし、newされたポインタを自動的に解放するにはshared_ptrが必要になるという話なのであった。

#include <iostream>
#include <memory>
template<typename T> struct Array_ {
    Array_() noexcept : L(), B() {}
    explicit Array_(int64_t n, ...) noexcept {
        L = n;
        B = new T[static_cast<size_t>(n)];
        va_list l;
        va_start(l, n);
        for (int64_t i = 0; i < n; i++)
            B[i] = va_arg(l, T);
        va_end(l);
    }
    ~Array_() {
        delete[] B;
    }
    int64_t L;
    T* B;
};

template<typename T,size_t n>
struct ArrayBuilder{
    static auto newArrayRec_(int64_t n_,const int64_t* b) noexcept {
        typedef decltype(ArrayBuilder<T,n-1>::newArrayRec_(n_,b)) X;
        std::shared_ptr<Array_<X>> r(new Array_<X>());
        int64_t N = b[n_-n];
        r->L = N;
        size_t s = static_cast<size_t>(N + 0);
        r->B = new X[s];
        for (int64_t i = 0; i < N; i++)
            r->B[i] = ArrayBuilder<T,n-1>::newArrayRec_(n_,b);
        return r;
    }
};
template<typename T>
struct ArrayBuilder<T,1>{
    static std::shared_ptr<Array_<T>> newArrayRec_(int64_t n_,const int64_t* b) noexcept {
        std::shared_ptr<Array_<T>> r(new Array_<T>());
        int64_t N = b[n_-1];
        r->L = N;
        size_t s = static_cast<size_t>(N);
        r->B = new T[s];
        std::fill(r->B, r->B + s, 0);
        return r;
    }
};

int main(){
    int64_t b[]={3,4,5,6,7,8};
    auto v = ArrayBuilder<int,6>::newArrayRec_(6,b);
    std::cout << v->L << std::endl;
    std::cout << v->B[0]->L << std::endl;
    std::cout << v->B[0]->B[0]->L << std::endl;
    std::cout << v->B[0]->B[0]->B[0]->L << std::endl;
    std::cout << v->B[0]->B[0]->B[0]->B[0]->L << std::endl;
    std::cout << v->B[0]->B[0]->B[0]->B[0]->B[0]->L << std::endl;
}

そういえば

次元数を変数にすることはできるんだろうか。