¿Cómo obtengo caracteres comunes a dos vectores en C++?

Question

Estoy tratando de comparar dos objetos vectoriales y devolver un solo vector que contenga todos los caracteres que aparecen en ambos vectores.

¿Cómo podría hacer esto sin escribir un método manual horriblemente complejo que compara cada carácter en el primer vector con cada carácter en el segundo vector y usando un if para agregarlo a un tercer vector (que se devolvería) si coinciden.

Tal vez mi falta de experiencia real con vectores me hace imaginar que esto será más difícil de lo que realmente es, pero sospecho que hay una manera más simple que no he podido encontrar a través de la búsqueda.

Answer 1

Creo que estás buscando std::set_intersection. Sin embargo, los vectores fuente deben ser ordenados. Si no le importa el orden de su vector de salida, siempre puede ejecutarlo en copias ordenadas de sus vectores de origen.

Y, por cierto, la forma manual ingenua no es terriblemente compleja. Dados dos vectores de código s1 y s2, y un vector de destino dest, podría escribir algo que se parece a esto:

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

Tienes un montón de opciones para el paso find dependiendo de su elección de la estructura de datos.

Answer 2

Quizás debería usar std :: cadenas en lugar de vectores, si tiene caracteres en ellas? Las cadenas tienen mucha funcionalidad para buscar, etc.

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

Use set_intersection. He aquí una muestra de trabajo:

#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

Si tuviera que hacer esto en dos vectores no clasificados (sin la ayuda de la biblioteca), creo que me gustaría añadir todos los elementos de una a una tabla hash entonces iterar a través del segundo mirando hacia arriba cada uno - debería ser más eficiente que ordenar primero ambas listas.

Answer 6

Esto no se extiende mucho más allá del tipo de char estándar (tal vez a unicode, dependiendo de la aplicación), pero si estás interesado en hacerlo en tiempo O (n), esto debería funcionar.

#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

Dado que resulta de su pregunta más tarde que en realidad sólo se preocupan por 26 caracteres:

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

De hecho, un bitset<UCHAR_MAX> es pequeña en casi todas las arquitecturas. Solo ten cuidado con esos DSP con caracteres de 32 bits, y ten cuidado al adaptar esta técnica al wchar_t.

Con BOOST_FOREACH, el código incluso parece razonable:

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