tr1::unordered_set объединение и пересечение

Я вижу, что set_intersection() и др. из заголовка algorithm не будет работать, поскольку они явно требуют сортировки своих входных данных — думаю, вы уже исключили их.

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

Вот некоторый код для unordered_set_difference(), вы можете настроить его, чтобы сделать версии для объединения наборов и различий наборов:

template <typename InIt1, typename InIt2, typename OutIt>
OutIt unordered_set_intersection(InIt1 b1, InIt1 e1, InIt2 b2, InIt2 e2, OutIt out) {
    while (!(b1 == e1)) {
        if (!(std::find(b2, e2, *b1) == e2)) {
            *out = *b1;
            ++out;
        }

        ++b1;
    }

    return out;
}

Предполагая, что у вас есть два unordered_set, x и y, вы можете поместить их пересечение в z, используя:

unordered_set_intersection(
    x.begin(), x.end(),
    y.begin(), y.end(),
    inserter(z, z.begin())
);

В отличие от ответа bdonlan, это будет работать для любого ключа типов и любой комбинации типов контейнеров (хотя использование set_intersection(), конечно, будет быстрее, если исходные контейнеры отсортированы).

ПРИМЕЧАНИЕ. Если ведра заполнены, вероятно, быстрее скопировать каждый хэш в vector, отсортировать их и set_intersection() там, поскольку поиск в ведре, содержащем n элементов, выполняется O(n).

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

Например:

void us_isect(std::tr1::unordered_set<int> &out,
        const std::tr1::unordered_set<int> &in1,
        const std::tr1::unordered_set<int> &in2)
{
    out.clear();
    if (in2.size() < in1.size()) {
        us_isect(out, in2, in1);
        return;
    }
    for (std::tr1::unordered_set<int>::const_iterator it = in1.begin(); it != in1.end(); it++)
    {
        if (in2.find(*it) != in2.end())
            out.insert(*it);
    }
}

void us_union(std::tr1::unordered_set<int> &out,
        const std::tr1::unordered_set<int> &in1,
        const std::tr1::unordered_set<int> &in2)
{
    out.clear();
    out.insert(in1.begin(), in1.end());
    out.insert(in2.begin(), in2.end());
}

на основе предыдущего ответа: версия С++ 11, если набор поддерживает функцию быстрого поиска find() (эффективно перемещаются возвращаемые значения)

/** Intersection and union function for unordered containers which support a fast lookup function find()
 *  Return values are moved by move-semantics, for c++11/c++14 this is efficient, otherwise it results in a copy
 */

namespace unorderedHelpers {

    template<typename UnorderedIn1, typename UnorderedIn2,
             typename UnorderedOut = UnorderedIn1>
    UnorderedOut makeIntersection(const  UnorderedIn1 &in1, const  UnorderedIn2 &in2)
    {
        if (in2.size() < in1.size()) {
            return makeIntersection<UnorderedIn2,UnorderedIn1,UnorderedOut>(in2, in1);
        }

        UnorderedOut out;
        auto e = in2.end();
        for(auto & v : in1)
        {
            if (in2.find(v) != e){
                out.insert(v);
            }
        }
        return out;
    }

    template<typename UnorderedIn1, typename UnorderedIn2,
             typename UnorderedOut = UnorderedIn1>
    UnorderedOut makeUnion(const UnorderedIn1 &in1, const UnorderedIn2 &in2)
    {
        UnorderedOut out;
        out.insert(in1.begin(), in1.end());
        out.insert(in2.begin(), in2.end());
        return out;
    }
}