Come posso ottenere caratteri comuni a due vettori in C++?

Question

Sto cercando di confrontare due oggetti vettoriali e restituire un vettore singolo contenente tutti i caratteri che appaiono in entrambi i vettori.

Come dovrei fare questo senza scrivere un metodo manuale orribilmente complesso che confronta ogni carattere nel primo vettore con ogni carattere nel secondo vettore e utilizzando un se per aggiungerlo a un terzo vettore (che verrebbe restituito) se loro corrispondono

Forse la mia mancanza di esperienza reale con i vettori mi fa immaginare che questo sarà più difficile di quanto sia in realtà, ma sospetto che ci sia un modo più semplice che non sono stato in grado di trovare attraverso la ricerca.

Answer 1

Penso che stiate cercando std::set_intersection. Tuttavia, i vettori di origine devono essere ordinati. Se non ti interessa l'ordine del tuo vettore di output, puoi sempre eseguirlo su copie ordinate dei tuoi vettori di origine.

E BTW, il modo ingenuo manuale non è orribilmente complesso. Dati due vettori di origine s1 e s2, e un vettore di destinazione dest, si potrebbe scrivere qualcosa che assomiglia a questo:

for (std::vector<char>::iterator i = s1.begin(); i != s1.end(); ++i) 
{ 
    if (std::find(s2.begin(), s2.end(), *i) != s2.end()) 
    { 
     dest.push_back(*i); 
    } 
} 

Hai un sacco di opzioni per la fase find in base alla scelta della struttura dati.

Answer 2

Forse dovresti usare std: stringhe invece di vettori, se hai dei caratteri al loro interno? Le stringhe hanno un sacco di funzionalità per la ricerca, ecc.

Answer 3

int temp[5000]; // declare this globally if you're going to be 
       // doing a lot of set_intersection calls 

int main() { 

    char x[]={'a','b','c','d','e'}; 
    char y[]={'b','c','g'}; 
    vector<char> v1(x,x+sizeof x/sizeof x[0]); 
    vector<char> v2(y,y+sizeof y/sizeof y[0]); 
    sort(v1.begin(),v1.end()); 
    sort(v2.begin(),v2.end()); // the vectors *must* be sorted!!!!!! 

    vector<char> inter=vector<char>(temp,set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),temp)); // inter contains {'b','c'} 
    int cnt=set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),temp) - temp; // cnt=2 

    for(int i = 0; i < (int)inter.size(); ++i) { 
    cout<<inter[i]<<" "; 
    } 
    cout<<endl; 

    return 0; 
} 

Answer 4

Utilizzare set_intersection. Ecco un esempio di lavoro:

#include <cstdlib> 
#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 

using namespace std; 

int main() 
{ 
    vector<string> v1; 
    v1.push_back("Mary"); 
    v1.push_back("had"); 
    v1.push_back("a"); 

    vector<string> v2; 
    v2.push_back("a"); 
    v2.push_back("little"); 
    v2.push_back("lamb"); 

    sort(v1.begin(), v1.end()); 
    sort(v2.begin(), v2.end()); 

    vector<string> v3; 
    set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3)); 

    copy(v3.begin(), v3.end(), ostream_iterator<string>(cout, "\r\n")); 
    return 0; 
} 

Answer 5

Se dovessi fare questo su due vettori non ordinate (senza aiuto biblioteca), penso che mi piacerebbe aggiungere tutti gli elementi di uno a una tabella hash poi iterare attraverso il secondo alzando ogni - Dovrebbe essere più efficiente dell'ordinamento di entrambi gli elenchi.

Answer 6

Questo non va ben oltre il tipo di char standard (forse per unicode, a seconda dell'applicazione), ma se sei interessato a farlo nel tempo O (n), questo dovrebbe funzionare.

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

std::vector<char> intersect(const std::vector<bool>& x, 
          const std::vector<bool>& y) 
{ 
    std::vector<char> rv; 

    std::vector<bool>::const_iterator ix, iy; 
    size_t i; 

    for (i=0, ix = x.begin(), iy = y.begin(); 
     ix != x.end() && iy != y.end(); 
     ++i, ++ix, ++iy) 
     if (*ix && *iy) rv.push_back((char) i); 

    return rv; 
} 

std::vector<bool> poll(const std::vector<char>& x) 
{ 
    std::vector<bool> rv(256, false); 

    for (std::vector<char>::const_iterator i = x.begin(); i != x.end(); ++i) 
     rv[*i] = true; 

    return rv; 
} 

std::vector<char> build(const std::string& val) 
{ 
    std::vector<char> rv; 

    for (size_t i = 0; i < val.size(); ++i) 
     rv.push_back(val[i]); 

    return rv; 
} 

int main(int argc, char *argv[]) 
{ 
    std::vector<char> x1 = build("The Quick Brown Fox Jumps Over The Lazy Dog"); 
    std::vector<char> x2 = build("Oh give me a home where the buffalo roam"); 

    std::vector<char> intersection = intersect(poll(x1), poll(x2)); 

    for (std::vector<char>::iterator i=intersection.begin(); 
      i != intersection.end(); ++i) 
     std::cout << *i; 

    std::cout << std::endl; 

    return 0; 
} 

Answer 7

Dal momento che risulta dalla tua domanda dopo solamente in realtà si preoccupano di 26 caratteri:

std::bitset<26> in; 
for (std::vector<char>::iterator it = first.begin(); it != first.end(); ++it) { 
    in[*it - 'a'] = true; 
} 
for (std::vector<char>::iterator it = second.begin(); it != second.end(); ++it) { 
    if (in[*it - 'a']) { 
     result.push_back(*it); 
     // this line is only needed if 'second' can contain duplicates 
     in[*it - 'a'] = false; 
    } 
} 

Infatti un bitset<UCHAR_MAX> è piccolo su quasi tutte le architetture. Basta fare attenzione a quei DSP con caratteri a 32 bit e sii prudente nell'adattare questa tecnica a wchar_t.

Con BOOST_FOREACH, il codice sembra ancora ragionevole:

assert(UCHAR_MAX <= 512 && "What kind of crazy machine is this?"); 
std::bitset<UCHAR_MAX> in; 

BOOST_FOREACH(unsigned char c, first) { 
    in[c] = true; 
} 

BOOST_FOREACH(unsigned char c, second) { 
    if (in[c]) { 
     result.push_back(c); 
     // this line is only needed if 'second' can contain duplicates 
     in[c] = false; 
    } 
}