Как получить символы, общие для двух векторов в C ++?

Question

Я пытаюсь сравнить два векторных объекта и вернуть один вектор, содержащий все символы, которые появляются в обоих векторах.

Как бы я поступил так без написания какого-то ужасно сложного ручного метода, который сравнивает каждый символ в первом векторе с каждым символом во втором векторе и используя if, чтобы добавить его в третий вектор (который будет возвращен), если матч.

Может быть, из-за отсутствия у меня опыта работы с векторами мне кажется, что это будет сложнее, чем на самом деле, но я подозреваю, что есть какой-то более простой способ, который я не смог найти с помощью поиска.

Answer 1

Я думаю, что вы ищете std::set_intersection. Однако исходные векторы должны быть отсортированы. Если вам не важен порядок выходного вектора, вы всегда можете запустить его на отсортированных копиях исходных векторов.

И кстати, ручной наивный способ не слишком сложен. Учитывая два исходных вектора s1 и s2 и целевой вектор dest, вы можете написать что-то похожее на это:

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

У вас есть много вариантов для шага find в зависимости от вашего выбора структуры данных.

Answer 2

Если бы мне пришлось делать это на двух несортированных векторах (без помощи библиотеки), я думаю, что я бы добавил все элементы одного в хеш-таблицу, а затем перебрал бы второй, просматривая каждый - должен быть более эффективным, чем сортировка обоих сначала перечисляет.

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

Это не распространяется далеко за пределы стандартного типа символов (может быть, в Юникоде, в зависимости от приложения), но если вы заинтересованы сделать это за O (n) время, это должно сработать.

#include &#60vector&#62
#include &#60string&#62
#include &#60iostream&#62

std::vector&#60char&#62 intersect(const std::vector&#60bool&#62& x,
                            const std::vector&#60bool&#62& y)
{
    std::vector&#60char&#62 rv;

    std::vector&#60bool&#62::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&#60bool&#62 poll(const std::vector&#60char&#62& x)
{
    std::vector&#60bool&#62 rv(256, false);

    for (std::vector&#60char&#62::const_iterator i = x.begin(); i != x.end(); ++i)
        rv[*i] = true;

    return rv;
}

std::vector&#60char&#62 build(const std::string& val)
{
    std::vector&#60char&#62 rv;

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

    return rv;
}

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

    std::vector&#60char&#62 intersection = intersect(poll(x1), poll(x2));

    for (std::vector&#60char&#62::iterator i=intersection.begin();
            i != intersection.end(); ++i)
        std::cout &#60&#60 *i;

    std::cout &#60&#60 std::endl;

    return 0;
}

Answer 5

Использовать set_intersection . Вот рабочий образец:

#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 6

Поскольку, как выяснилось из вашего более позднего вопроса, вас интересуют только 26 символов:

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

На самом деле bitset<UCHAR_MAX> мало практически на всех архитектурах. Просто следите за тем DSP с 32-битными символами и будьте осторожны, адаптируя эту технику к wchar_t.

С BOOST_FOREACH код выглядит даже разумно:

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

Answer 7

Может быть, вы должны использовать std :: strings вместо векторов, если в них есть символы? Строки имеют множество функций для поиска и т. Д.