やりたいこと
この記事ではstd::tupleの直積を作る関数テンプレートtuple_product(tuples...)を作ります．
何故そんなことをするのかって？
やりたいからです．
C++20以降の環境を前提にしています．
やってみよう
簡単のため，a0, a1, ...を要素に持つstd::tupleを(a0, a1, ...)と書きます．
(a0, a1, ...),
(b0, b1, ...),
(c0, c1, ...),
...
が与えられたとき，
(a0, b0, c0, ...), ...
(a0, b0, c1, ...), ...
(a0, b1, c0, ...), ...
(a0, b1, c1, ...), ...
...
を作って，最後に1つのtupleにまとめる方針です．
直積の大きさを求めるメタ関数product_size<Tuples...>と，直積のN番目のtupleを求める関数テンプレートproduct_leaf<N>(tuples...)を作って組み合わせればよさそうですね．
product_sizeはサッと作ってしまいましょう．
空の直積の大きさは1だということに気を付けます．
template <typename... Tuples>
struct product_size {
static constexpr std::size_t value = (std::tuple_size_v<Tuples> * ... * 1);
};
さて，つぎはproduct_leafですね．
ところで，product_leafの結果にしたいtupleを並べたときの，
(a0, b0, c0, ...), ...
(a0, b0, c1, ...), ...
(a0, b1, c0, ...), ...
(a0, b1, c1, ...), ...
という添え字の並び，なんか$n$進数みたいですね．
実際そんな感じに添え字の列は変化していくのですが，どの桁でも最大の数が$n - 1$である$n$進数とは違って，それぞれの「桁」がとる値の個数が異なります．
具体的な例，
(a0, a1, a2),
(b0, b1),
(c0, c1, c2, c3)
で試してみましょう．
この例では，
(a0, b0, c0),
(a0, b0, c1),
(a0, b0, c2),
(a0, b0, c3),
(a0, b1, c0),
(a0, b1, c1),
(a0, b1, c2),
(a0, b1, c3),
(a1, b0, c0),
(a1, b0, c1),
(a1, b0, c2),
(a1, b0, c3),
(a1, b1, c0),
(a1, b1, c1),
(a1, b1, c2),
(a1, b1, c3)
となります．
product_leaf<N>(tuples...)は，これを逆向きに計算する，つまりNからこの添え字の列を計算することになります．
そのためにメタ関数product_leaf_index_sequence<N, Ns...>を作ります．
なお，Ns...はtuples...の対応する要素のtupleの大きさ，つまり各「桁」が取り得る値の個数の列になります．
たとえば先ほどの例では，Ns...は3, 2, 4です．
ここから複雑になるので，C++の前にちょっと数学の時間にしましょう．
product_leaf_index_sequence<N, Ns...>は，Ns...を有限数列$n_i$とし，その長さを$k$としたとき，
$$
N = (n_1 n_2 \cdots n_{k-1})x_0 + (n_2 n_3 \cdots n_{k-1})x_1 + \cdots + n_{k-1}x_{k-2} + x_{k-1}
$$をみたす数列$x_i$（ただし$0 \le x_i < n_i$）を求める関数です．
この式を各$x_i$について解きましょう．
最後の項$x_{k-1}$以外には$n_{k-1}$が掛かっているので，割り算の余りについて
$$
N \equiv x_{k-1} \mod{n_{k-1}}
$$が成り立ちます．そして$x_{k-1}$は$n_{k-1}$より小さいので$x_{k-1} = N \bmod n_{k-1}$となります．
次に$N$を$n_{k-1}$で割ると，
$$
\frac{N}{n_{k-1}} = (n_1 n_2 \cdots n_{k-2})x_0 + (n_2 n_3 \cdots n_{k-2})x_1 + \cdots + x_{k-2} + \frac{x_{k-1}}{n_{k-1}}
$$となります．
両辺の小数部分を切り捨てて，
$$
\mathrm{floor}\left(\frac{N}{n_{k-1}}\right) = (n_1 n_2 \cdots n_{k-2})x_0 + (n_2 n_3 \cdots n_{k-2})x_1 + \cdots + x_{k-2}
$$となるので，同様にして$x_{k-2} = \mathrm{floor}\left(\frac{N}{n_{k-1}}\right) \bmod n_{k-2}$が求められます．
これを繰り返すと，
$$
x_i = \mathrm{floor}\left(\frac{N}{n_{i+1} \cdots n_{k-1}}\right) \bmod n_i
$$となります．
さて，これで求めるものが分かったので，C++の時間です．
$\mathrm{floor}\left(\frac{N}{n_{i+1} \cdots n_{k-1}}\right) \bmod n_i$を求めるメタ関数product_leaf_index<I, N, Ns...>を作って組み合わせます．
template <std::size_t I, std::size_t N, std::size_t... Ns>
struct product_leaf_index;
template <std::size_t N, std::size_t N0, std::size_t... Ns>
struct product_leaf_index<0, N, N0, Ns...> {
static constexpr std::size_t value = (N / (Ns * ... * 1)) % N0;
};
template <std::size_t I, std::size_t N, std::size_t N0, std::size_t... Ns>
struct product_leaf_index<I, N, N0, Ns...> {
static constexpr std::size_t value = product_leaf_index<I - 1, N, Ns...>::value;
};
これを使ってproduct_leaf_index_sequence<N, Ns...>を作ります．
template <typename Indices, std::size_t N, std::size_t... Ns>
struct product_leaf_index_sequence_impl;
template <std::size_t... Index, std::size_t N, std::size_t... Ns>
struct product_leaf_index_sequence_impl<std::index_sequence<Index...>, N, Ns...> {
using type = std::index_sequence<product_leaf_index<Index, N, Ns...>::value...>;
};
template <std::size_t N, std::size_t... Ns>
struct product_leaf_index_sequence {
using type = product_leaf_index_sequence_impl<std::make_index_sequence<sizeof...(Ns)>, N, Ns...>::type;
};
……何のためにこれを作っていたのでしょう？
そうそう，直積のN番目のtupleを求めるproduct_leafを作るのでしたね．
あとはインデックス展開を繰り返すだけです．作っちゃいましょう．
template <typename... Tuples, std::size_t... Index>
auto product_leaf_impl(std::index_sequence<Index...>, const Tuples&... tuples) {
return std::make_tuple(std::get<Index>(tuples)...);
}
template <std::size_t N, typename... Tuples>
auto product_leaf(const Tuples&... tuples) {
using indices = product_leaf_index_sequence<N, std::tuple_size_v<std::remove_cvref_t<Tuples>>...>::type;
return product_leaf_impl(indices{}, tuples...);
}
さて，これでようやくtuple_productを作れます．ここまで長い旅路でした．
template <std::size_t... Ns, typename... Tuples>
auto tuple_product_impl(std::index_sequence<Ns...>, const Tuples&... tuples) {
return std::make_tuple(product_leaf<Ns>(tuples...)...);
}
template <typename... Tuples>
auto tuple_product(const Tuples&... tuples) {
constexpr std::size_t size = product_size<std::remove_cvref_t<Tuples>...>::value;
return tuple_product_impl(std::make_index_sequence<size>{}, tuples...);
}
せっかくなので試してみましょう．
int main() {
using namespace std::string_literals;
auto a = std::tuple{1, 2, 3};
auto b = std::tuple{'A', 'B'};
auto c = std::tuple{"first"s, "second"s, "third"s, "fourth"s};
auto product = tuple_product(a, b, c);
std::apply([](const auto&... tuples) { (std::cout << ... << std::format("{}\n", tuples)); }, product);
}
出力は
(1, 'A', "first")
(1, 'A', "second")
(1, 'A', "third")
(1, 'A', "fourth")
(1, 'B', "first")
(1, 'B', "second")
(1, 'B', "third")
(1, 'B', "fourth")
(2, 'A', "first")
(2, 'A', "second")
(2, 'A', "third")
(2, 'A', "fourth")
(2, 'B', "first")
(2, 'B', "second")
(2, 'B', "third")
(2, 'B', "fourth")
(3, 'A', "first")
(3, 'A', "second")
(3, 'A', "third")
(3, 'A', "fourth")
(3, 'B', "first")
(3, 'B', "second")
(3, 'B', "third")
(3, 'B', "fourth")
となりました．合っていそうですね．よかったです．
ちなみに
ちなみにC++23なら，std::ranges::cartesian_product_viewとコンパイル時計算の暴力によって，product_leaf_index_sequenceを作らずに書けてしまいます．
template <typename... Tuples>
consteval auto make_indices_table() {
auto indices_table_view
= std::views::cartesian_product(std::views::iota(std::size_t{0}, std::tuple_size_v<Tuples>)...);
using indices_t = std::array<std::size_t, sizeof...(Tuples)>;
constexpr std::size_t size = (std::tuple_size_v<Tuples> * ... * 1);
std::array<indices_t, size> indices_table;
std::ranges::transform(indices_table_view, indices_table.begin(), [](auto tuple) {
return std::apply([](auto... index) { return indices_t{index...}; }, tuple);
});
return indices_table;
}
これでtupleの列から直積の添え字の列を直接作れるので，
template <auto Table, typename... Tuples, std::size_t... Index>
auto product_leaf_impl(std::index_sequence<Index...>, const Tuples&... tuples) {
return std::make_tuple(std::get<Table[Index]>(tuples)...);
}
template <std::size_t N, auto Table, typename... Tuples>
auto product_leaf(const Tuples&... tuples) {
return product_leaf_impl<Table[N]>(std::make_index_sequence<Table[N].size()>{}, tuples...);
}
template <auto Table, std::size_t... Ns, typename... Tuples>
auto tuple_product_impl(std::index_sequence<Ns...>, const Tuples&... tuples) {
return std::make_tuple(product_leaf<Ns, Table>(tuples...)...);
}
template <typename... Tuples>
auto tuple_product(const Tuples&... tuples) {
constexpr auto indices_table = make_indices_table<std::remove_cvref_t<Tuples>...>();
return tuple_product_impl<indices_table>(std::make_index_sequence<indices_table.size()>{}, tuples...);
}
とするだけでできてしまいます．
あとがき
何の役に立つかわからないようなユーティリティを作るのは楽しいですね．
こんな感じのものをいっぱい集めたライブラリYu Librariesをまだまだ作りかけですが作ってるのでよければ見ていってください（宣伝）．