多次元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;
}

そういえば

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