Is there some STL function to get cartesian product of two C++ vectors?

Question

Suppose

b =  ["good ", "bad "]
a  = ["apple","mango"]
then output = ["good apple","good mango","bad apple","bad mango"]

I know this can be done with nested for loops but is there some elegant one liner for doing this using C++ STL?

Answer 1

Given vector<string> a and vector<string> b you can use for_each:

vector<string> output(size(a) * size(b));

for_each(begin(output), end(output), [&, it = 0U](auto& i) mutable {
    i = a[it / size(b)] + ' ' + b[it % size(b)];
    ++it;
});

Live Example

EDIT:

We've initialized output with enough room to contain every combination of a and b. Then we'll step through each element of output and assign it.

We'll want to use the 1^st element of a for the first size(b) elements of output, and the 2^nd element of a for the second size(b) elements, and so on. So we'll do this by indexing with it / size(b). We'll want to combine that by iteration through b's elements.

it will move to the next index for each element of output but the indexing needs to wrap or it will be out of bounds when it == size(b), to do that we use it % size(b).

EDIT2:

In this question through benchmarking I'd discovered the phenomenon that modulo and division are expensive operations for iteration. I've done the same test here. For the purpose of isolating the algorithms I'm just doing the Cartesian summation on a vector<int> not vector<string>.

First off we can see the two algorithms result in differing assembly. My algorithm as written above requires 585 lines of assembly. 588 lines were required by my interpretation of MSalter's code

vector<string> output(size(testValues1) * size(testValues2));
auto i = begin(output);

std::for_each(cbegin(a), cend(a), [&](const auto& A) { std::for_each(cbegin(b), cend(b), [&](const auto& B) { *i++ = A + ' ' + B; }); });

I have placed a pretty solid benchmarking test here: http://ideone.com/1YpzIO In the test I've only got it set to do 100 tests yet MSalters' algorithm always wins. Locally using Visual Studio 2015 in release with 10,000,000 tests MSalters algorithm finishes in about 2/3 the time it takes mine.

Clearly modulo isn't a great method of indexing :(

Answer 2

Here is a one-liner (copied from Jonathan Mee's answer posted here):

for(size_t i = 0, s = a.size(); i < output.size(); ++i) output[i] = b[i/s] + ' ' + a[i%s];

Full example here.

Answer 3

There's no direct solution; I checked the whole of <algorithm>. None of the functions produce an output of length M*N.

What you can do is call std::for_each on the first range, using a lambda which calls std::for_each on the second range (!)

std::vector<std::string> a, b;
std::for_each(a.begin(), a.end(), 
  [&](std::string A) { std::for_each(b.begin(), b.end(),
      [A](std::string B) { std::cout << A << '/' << B << '\n';  }
);});

But that's just a nested loop in STL.