tr1 :: unordered_set unión e intersección

Question

¿Cómo hacer intersección y unión para conjuntos del tipo tr1 :: unordered_set en C++? No puedo encontrar mucha referencia al respecto.

Cualquier referencia y código serán muy apreciados. Muchas gracias.

Actualización: Acabo de adivinar que tr1 :: unordered_set debería proporcionar la función de intersección, unión, diferencia .. Dado que esa es la operación básica de los conjuntos. Por supuesto que puedo escribir una función yo solo, pero me pregunto si hay una función incorporada de tr1. Muchas gracias.

Answer 1

veo que set_intersection() et al. del encabezado algorithm no funcionará, ya que requieren explícitamente que se ordenen sus entradas, supongo que ya las descartó.

Se me ocurre que el enfoque "ingenuo" de iterar a través de hash A y buscar cada elemento en hash B realmente debería proporcionarle un rendimiento casi óptimo, ya que las búsquedas sucesivas en hash B irán al mismo hash. (suponiendo que ambos hashes están usando la misma función hash). Eso debería darte una localidad de memoria decente, aunque estos cubos casi con seguridad se implementan como listas vinculadas.

Aquí hay algo de código para unordered_set_difference(), puede modificarlo para hacer las versiones para unión de conjuntos y establecer la diferencia:

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

Asumiendo que tiene dos unordered_set s, x y y, puede poner su intersección en z usando:

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

a diferencia bdonlan's answer, esto va a funcionar para cualquier tipo de clave, y cualquier combinación de c ontainer tipos (aunque el uso de set_intersection() será, por supuesto, más rápido si los contenedores de origen están ordenados).

NOTA: Si las ocupaciones de cubetas son altas, es probable que sea más rápido copiar cada hash en un vector, ordenarlas y set_intersection() allí, ya que la búsqueda dentro de un depósito que contiene n elementos es O (n).

Answer 2

No hay mucho para eso: para intersectar, simplemente revise cada elemento de uno y asegúrese de que esté en el otro. Para la unión, agregue todos los elementos de ambos conjuntos de entrada.

Por ejemplo:

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

basado en la respuesta anterior: C++ 11 versión, si el conjunto es compatible con una función rápida mirar hacia arriba find() (valores de retorno se mueven de manera eficiente)

/** 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; 
    } 
}