Làm cách nào để nhận các ký tự chung cho hai vectơ trong C++?

Question

Tôi đang cố gắng so sánh hai đối tượng vectơ và trả lại một vectơ đơn chứa tất cả các ký tự xuất hiện trong cả hai vectơ.

Làm thế nào tôi sẽ thực hiện điều này mà không cần viết một phương pháp thủ công phức tạp nào so sánh mọi char trong vector đầu tiên với mỗi char trong vector thứ hai và sử dụng if để thêm nó vào vector thứ ba (sẽ được trả về) chúng phù hợp.

Có lẽ sự thiếu kinh nghiệm thực tế của tôi với vectơ là làm cho tôi tưởng tượng điều này sẽ khó hơn nó thực sự, nhưng tôi nghi ngờ có một số cách đơn giản hơn mà tôi không thể tìm thấy thông qua tìm kiếm.

Answer 1

Tôi nghĩ bạn đang tìm kiếm std::set_intersection. Tuy nhiên, các vectơ nguồn phải được sắp xếp. Nếu bạn không quan tâm đến thứ tự của vector đầu ra của bạn, bạn luôn có thể chạy nó trên các bản sao được sắp xếp của các vectơ nguồn của bạn.

Và BTW, cách ngây thơ thủ công không phức tạp khủng khiếp. Với hai vectơ nguồn s1 và s2, và một vector điểm đến dest, bạn có thể viết cái gì đó trông như thế này:

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

Bạn có rất nhiều lựa chọn cho các find bước tùy thuộc vào sự lựa chọn của bạn của cấu trúc dữ liệu.

Answer 2

Có lẽ bạn nên sử dụng std :: strings thay vì vectơ, nếu bạn có ký tự trong đó? Chuỗi có nhiều chức năng để tìm kiếm v.v.

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

Sử dụng set_intersection. Dưới đây là một ví dụ làm việc:

#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

Nếu tôi phải làm điều này trên hai vectơ không được phân loại (không có sự giúp đỡ viện), tôi nghĩ rằng tôi muốn thêm vào tất cả các yếu tố của một đến một Hashtable sau đó lặp qua thứ hai nhìn lên mỗi - cần phải hiệu quả hơn cả việc sắp xếp cả hai danh sách trước.

Answer 6

Điều này không mở rộng vượt quá loại char tiêu chuẩn (có thể để unicode, tùy thuộc vào ứng dụng), nhưng nếu bạn quan tâm đến việc này trong O (n) thời gian, điều này sẽ làm việc.

#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

Kể từ khi nó quay ra từ câu hỏi sau của bạn, bạn chỉ thực sự quan tâm đến 26 ký tự:

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

Trong thực tế, một bitset<UCHAR_MAX> là nhỏ trên hầu hết các kiến ​​trúc. Chỉ cần xem ra cho những DSP với các ký tự 32-bit, và phải thận trọng thích ứng với kỹ thuật này để wchar_t.

Với BOOST_FOREACH, mã thậm chí trông hợp lý:

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