tr1 :: unordered_set объединение и пересечение - PullRequest
Новая
       29

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

21 голосов
/ 22 мая 2009

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

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

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

Ответы [ 3 ]

17 голосов
/ 22 мая 2009

Я вижу, что 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 s, 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).

14 голосов
/ 22 мая 2009

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

Например: 

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());
}
2 голосов
/ 03 августа 2015

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