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

Как сделать пересечение и объединение для наборов типа tr1:: unordered_set в С++? Я не могу найти много ссылок на это.

Любая ссылка и код будут высоко оценены. Большое вам спасибо.

Обновление: я просто догадался, что tr1:: unordered_set должен предоставить функцию для пересечения, объединения, разности. Так как это основная операция множеств. Конечно, я могу написать функцию самостоятельно, но мне просто интересно, есть ли встроенная функция из tr1. Большое вам спасибо.

Ответ 1

Я вижу, что set_intersection() et al. из заголовка 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 s, x и y, вы можете поместить их пересечение в z, используя:

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

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

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

Ответ 2

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

Например:

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

Ответ 3

на основе предыдущего ответа: С++ 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;
    }
}