Introduction

If you only have two vectors, a Cartesian product is easy to write with two nested loops. The real problem is making the same idea work for an arbitrary number of vectors without hardcoding loop depth.

In modern C++, the clean approach is to use variadic templates for type generality and a recursive helper for runtime enumeration. That gives you one function that works for any number of input vectors and returns tuples containing one choice from each vector.

What Needs To Be Generalized

For vectors A, B, and C, the Cartesian product contains every tuple:

• one element from A
• one element from B
• one element from C

The number of outputs is the product of the input sizes, so the challenge is not asymptotic magic. The challenge is expressing "nested loops of arbitrary depth" in reusable code.

A Variadic Template Solution

The example below stores the current partial tuple and recursively fills one position at a time.

1#include <iostream>
2#include <tuple>
3#include <vector>
4
5template <typename Tuple, typename VectorTuple, std::size_t I = 0>
6void cartesian_product_impl(
7    const VectorTuple& vectors,
8    Tuple& current,
9    std::vector<Tuple>& output)
10{
11    if constexpr (I == std::tuple_size_v<Tuple>) {
12        output.push_back(current);
13    } else {
14        const auto& vec = std::get<I>(vectors);
15        for (const auto& value : vec) {
16            std::get<I>(current) = value;
17            cartesian_product_impl<Tuple, VectorTuple, I + 1>(vectors, current, output);
18        }
19    }
20}
21
22template <typename... Ts>
23auto cartesian_product(const std::vector<Ts>&... vectors)
24{
25    using Tuple = std::tuple<Ts...>;
26    std::tuple<const std::vector<Ts>&...> packed(vectors...);
27    std::vector<Tuple> output;
28    Tuple current{};
29
30    cartesian_product_impl(packed, current, output);
31    return output;
32}
33
34int main()
35{
36    std::vector<int> a{1, 2};
37    std::vector<char> b{'x', 'y'};
38    std::vector<double> c{0.5, 1.5};
39
40    auto result = cartesian_product(a, b, c);
41
42    for (const auto& [i, ch, d] : result) {
43        std::cout << '(' << i << ", " << ch << ", " << d << ")\n";
44    }
45}

This is generic across element types and across vector count. The recursion happens over tuple indices rather than over handwritten loops.

Why TMP Helps Here

Template metaprogramming is useful because the number and types of vectors are known at compile time. That lets the compiler build:

• the tuple type for one output row
• the tuple of input vector references
• the recursive instantiations for each position

The values themselves are still runtime data. TMP is not being used to compute the entire Cartesian product at compile time. It is being used to generate a type-safe generalized algorithm.

Design Tradeoffs

This approach is clean, but the cost is still real:

• output size grows multiplicatively
• memory usage can explode if you materialize all tuples
• compile errors can be harder to read than in a handwritten two-vector version

If you only need to visit combinations one at a time, a callback-based generator can be better than building a giant std::vector<Tuple>.

When a Callback Is Better

For large products, replace output.push_back(current) with a function call such as visitor(current). That lets you process each tuple immediately instead of storing the full product in memory.

This is often the right design for search, filtering, or streaming pipelines where most combinations are discarded quickly.

Common Pitfalls

• Confusing compile-time type generalization with compile-time generation of all values.
• Materializing the full Cartesian product when the result set is enormous.
• Hardcoding homogeneous element types when the problem really needs tuples of mixed types.
• Writing nested loops manually and losing scalability beyond two or three vectors.
• Ignoring the multiplicative output size and blaming templates for performance problems caused by the problem itself.

Summary

• The generalized Cartesian product problem is really "nested loops of arbitrary depth."
• Variadic templates and tuple recursion provide a clean C++ solution.
• TMP helps build a type-safe generic algorithm, even though the values are produced at runtime.
• Returning all tuples is convenient but can consume a lot of memory.
• For large products, a visitor or generator style is often the better design.