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

Я думаю, вы ищете 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 в зависимости от выбранной вами структуры данных.

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

Используйте 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;
}

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

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

Поскольку из вашего более позднего вопроса выясняется, что вам действительно нужны только 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;
    }
}

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