tr1 :: unordered_set union и intersection

Question

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

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

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

Answer 1

Я вижу, что 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's answer, это действительно будет работать для любых типов ключей, а также любое сочетание с типы контейнеров (хотя использование set_intersection(), конечно, будет быстрее, если исходные контейнеры будут отсортированы).

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

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

Answer 3

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