Générer le produit cartésien de 2 vecteur <string> s En place?

Question

Si je veux obtenir le produit cartésien de ces deux vector<string> s:

vector<string> final{"a","b","c"}; 
vector<string> temp{"1","2"}; 

Mais je veux mettre le résultat dans final, de sorte que finale contiendrait:

a1
a2
b1
b2
c1
c2

Je voudrais faire cela sans créer de tableau temporaire. Est-il possible de faire cela? Si c'est important, l'ordre de final n'est pas important.

Answer 1

Vous pouvez essayer l'approche suivante

#include <iostream> 
#include <vector> 
#include <string> 

int main() 
{ 
    std::vector<std::string> final{ "a", "b", "c" }; 
    std::vector<std::string> temp{ "1", "2" }; 

    auto n = final.size(); 

    final.resize(final.size() * temp.size()); 

    for (auto i = n, j = final.size(); i != 0; --i) 
    { 

     for (auto it = temp.rbegin(); it != temp.rend(); ++it) 
     { 
      final[--j] = final[i-1] + *it; 
     } 

    } 

    for (const auto &s : final) std::cout << s << ' '; 
    std::cout << std::endl; 

    return 0; 
} 

La sortie du programme est

a1 a2 b1 b2 c1 c2 

Answer 2

Essayez la fonction cartésienne:

#include <vector> 
#include <string> 

using namespace std; 

void cartesian(vector<string>& f, vector<string> &o) { 
int oldfsize = f.size(); 
f.resize(oldfsize * o.size()); 
for (int i = o.size() - 1; i>=0; i--) { 
    for (int j = 0; j < oldfsize; j++) { 
    f[i*oldfsize + j] = f[j] + o[i]; 
    } 
} 
} 


int main() 
{ 
vector<string> f{"a","b","c"}; 
vector<string> temp{"1","2"}; 
cartesian(f, temp); 
for (auto &s: f) { 
    printf("%s\n", s.c_str()); 
} 
} 

Answer 3

Cela fonctionne pour moi:

void testCartesianString(vector<string>& final, 
         vector<string>const& temp) 
{ 
    size_t size1 = final.size(); 
    size_t size2 = temp.size(); 

    // Step 1. 
    // Transform final to : {"a","a","b","b","c","c"} 
    final.resize(size1*size2); 
    for (size_t i = size1; i > 0; --i) 
    { 
     for (size_t j = (i-1)*size2; j < i*size2; ++j) 
     { 
     final[j] = final[i-1]; 
     } 
    } 

    // Step 2. 
    // Now fix the values and 
    // change final to : {"a1","a2","b1","b2","c1","c2"} 
    for (size_t i = 0; i < size1; ++i) 
    { 
     for (size_t j = 0; j < size2; ++j) 
     { 
     final[i*size2+j] = final[i*size2+j] + temp[j]; 
     cout << final[i*size2+j] << " "; 
     } 
     cout << endl; 
    } 
} 

Answer 4

Ceci est juste une option de préférence personnelle à la solution Vald from Moscow. Je pense que cela peut être plus rapide pour les tableaux dynamiques car il y aurait moins de ramification. Mais je n'ai pas eu l'occasion d'écrire un banc d'essai de chronométrage.

Compte tenu des entrées et vector<string> finalvector<string> temp:

const auto size = testValues1.first.size(); 

testValues1.first.resize(size * testValues1.second.size()); 

for (int i = testValues1.first.size() - 1; i >= 0; --i){ 
    testValues1.first[i] = testValues1.first[i % size] + testValues1.second[i/size]; 
} 

EDIT:

Nope, cette solution est plus lent pas plus rapide: http://ideone.com/e.js/kVIttT

Et généralement beaucoup plus rapide, mais je ne savoir pourquoi ...

Dans tous les cas, préférez Réponse de Vlad from Moscow