Simple generic cartesian product in C++

Question

The idea is to take a sequence of sequences (of the same type) and use tuples of [iterator, current index, sequence size] to keep track of the current state, such that the cartesian_product object can return one sequence at a time.

General questions:

• bugs? (would hope not!)
• code quality ok? anything i've missed?
• is there a simpler way to keep track of the object state (iterators, counts, etc)
• would it make sense to make this into an iterator (it could probably be bidirectional?)

Improvement ideas:

• when the number of sequences is known at compile time, maybe it would be better for next() to return a tuple/static array instead of a std::vector<T>?
• use a simple aggregate type instead of a tuple to avoid all the std::get ugliness?

Thanks a lot!

#include <iostream>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

template <typename T>
class cartesian_product {
public:
    template <typename... Args, typename = typename std::enable_if<(sizeof...(Args) > 1)>::type>
    cartesian_product(Args&&... args)
        : count(1)
    {
        std::cout << "constructor 1\n";
        static_assert(std::is_arithmetic<T>::value, "T must be an arithmetic type.");
        append(args...);
    }

    cartesian_product(std::vector<std::vector<T>> const& sequences) 
        : count(1)
    {
        std::cout << "constructor 2\n";
        tuples.reserve(sequences.size());
        for(auto&& s : sequences) {
            tuples.emplace_back(s.cbegin(), 0ul, s.size());
            count *= s.size();
        }
    }

    cartesian_product(std::vector<std::vector<T>>&& sequences)
        : cartesian_product(sequences)
    {
        std::cout << "constructor 3\n";
    }


    bool has_next() { return count > 0; }

    // next combination
    std::vector<T> next()
    {
        std::vector<T> res(tuples.size());
        auto s = res.rbegin();

        for (auto p = tuples.rbegin(); p < tuples.rend(); ++p, ++s) {
            *s = *std::get<0>(*p);

            if (p > tuples.rbegin()) {
                auto q = p - 1;
                if (std::get<1>(*q) == std::get<2>(*q)) {
                    std::get<0>(*q) -= std::get<2>(*q);
                    std::get<1>(*q) = 0;

                    ++std::get<0>(*p);
                    ++std::get<1>(*p);
                }
            } else {
                ++std::get<0>(*p);
                ++std::get<1>(*p);
            }
        }

        --count;
        return res;
    }

private:
    using I = typename std::vector<T>::const_iterator;
    using E = std::tuple<I, std::size_t, std::size_t>;
    std::vector<E> tuples;
    int count;

    template <typename... Args>
    void append(std::vector<T> const& vec, Args&&... args)
    {
        append(vec);
        append(args...);
    }

    void append(std::vector<T> const& vec)
    {
        count *= vec.size();
        tuples.emplace_back(std::cbegin(vec), 0ul, vec.size());
    }
};

int main(int argc, char** argv)
{
    std::vector<int> a { 1, 2 };
    std::vector<int> b { 3, 4 };
    std::vector<int> c { 5, 6 };
    std::vector<int> d { 7, 8, 9 };

    std::vector<std::vector<int>> s{ a, b, c, d };

    cartesian_product<int> p(a, b, c);
    cartesian_product<int> q(s);
    cartesian_product<int> r(std::vector<std::vector<int>>{ a, b, c, d });

    auto print = [](auto&& vec) { for (auto v : vec) std::cout << v << " "; std::cout << "\n"; };

    while (p.has_next())
        print(p.next());

    return 0;
}

Answer 1

Don't limit Cartesian products to arithmetic types

You shouldn't limit your class to only allow products of vectors of a type that satisfies std::is_arithmetic. Why shouldn't I be able to do a Cartesian product of a std::string and a std::chrono::time_point for example? There is no actual multiplication involved in a Cartesian product after all.

Your class will likely force copies of vectors to be made

In this constructor:

cartesian_product(std::vector<std::vector<T>> const& sequences) {...}

The parameter sequences is a reference, so you might think that this doesn't cause any copies to be made. However, that is only true if the caller already has a vector of vectors lying around. In your own example usage in main(), you have four vectors a, b, c and d, but then you create the vector of vectors s which causes a copy to be made of the four original vectors. And the following line constructs a temporary that also makes copies:

cartesian_product<int> r(std::vector<std::vector<int>>{ a, b, c, d });

Support more containers besides std::vector

You only support products of std::vector<T>, but what if I have my data in a regular array, a std::array, a std::list or any other container? Again, it is an unnecessary restriction. Try to rewrite it so any type of container works. Either have it accept a reference to a container object directly, or have it accept iterators like the STL algorithms do.

Return a tuple instead of a vector

A std::vector will allocate memory on the heap, which will impact performance. And since you know the size of the result, you can return a std::tuple instead, which has the advantage that it can be unpacked using C++17's structured bindings. Apart from that, with a std::tuple the value types of each input vector/array/etc can be different, whereas your solution requires all of them to be the same,

Add iterators to your class

Indeed, it makes sense to add iterators to your class. In fact, it already basically keeps track of everything that an iterator would do, and next() is the equivalent of an iterator's operator++(). Ideally, you want to be able to write something like:

std::vector<std::string> a_vector{"foo", "bar", "baz"};
std::list<int> b_vector{4, 5, 6, 7};

for (auto [a_element, b_element]: cartesian_product(a_vector, b_vector))
    std::cout << a_element << ", " << b_element << "\n";

And then expect the following result:

foo, 4
foo, 5
foo, 6
foo, 7
bar, 4
bar, 5
...

This also avoids the need for a has_next() function.