Есть ли какая-нибудь функция STL для получения декартова произведения двух векторов С++?

Предположим, что

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

Я знаю, что это можно сделать с помощью вложенных циклов, но есть ли какой-то элегантный лайнер для этого, используя С++ STL?

Ответ 1

Вот однострочный (скопированный из ответ :

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

Полный пример здесь.

Ответ 2

Учитывая vector<string> a и vector<string> b, вы можете использовать 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:

Мы инициализировали output с достаточным пространством для размещения каждой комбинации a и b. Затем мы пройдем через каждый элемент output и назначим его.

Мы хотим использовать 1 ^st элемент a для первых size(b) элементов output, а элемент ^nda для вторых элементов size(b) и т.д. Поэтому мы сделаем это, индексируя с помощью it / size(b). Мы хотим объединить это путем итерации через элементы b.

it переместится к следующему индексу для каждого элемента output, но индексирование необходимо обернуть или оно будет за пределами границ, когда it == size(b), для этого мы используем it % size(b).

EDIT2:

В этот вопрос через бенчмаркинг Я обнаружил феномен, что модуляция и деление - дорогостоящие операции для итерации. Я сделал тот же тест здесь. В целях выделения алгоритмов я просто делаю декартово суммирование на a vector<int> not vector<string>.

Во-первых, мы можем видеть, что два алгоритма приводят к различной сборке. Мой алгоритм, как указано выше, требует 585 строк сборки. Для моей интерпретации MSalter code потребовалось 588 строк.

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; }); });

Я разместил довольно простую тестовую оценку: http://ideone.com/1YpzIO В тесте я только решил установить 100 тестов но алгоритм MSalters всегда выигрывает. Локально с помощью Visual Studio 2015 в выпуске с 10 000 000 тестов алгоритм MSalters заканчивается примерно через 2/3 времени, затрачиваемого на мой.

Очевидно, что modulo не является отличным методом индексирования: (

Ответ 3

Нет прямого решения; Я проверил все <algorithm>. Ни одна из функций не выводит длину M * N.

Что вы можете сделать, это вызвать std::for_each в первом диапазоне, используя лямбда, которая вызывает std::for_each во втором диапазоне (!)

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';  }
);});

Но это всего лишь вложенный цикл в STL.