c++ - example - tr1:: unordered_set unión e intersección

unordered_map c++

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, puedo escribir una función por mi cuenta, pero me pregunto si hay una función incorporada de tr1. Muchas gracias.

Answer 1

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 2

basado en la respuesta anterior: versión de C ++ 11, si el conjunto admite una función de find() rápida find() (los 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;
    }
}

Answer 3

Veo que set_intersection() et al. del encabezado del algorithm no funcionará, ya que requieren explícitamente que sus entradas sean ordenadas, 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 en realidad debería proporcionarle un rendimiento casi óptimo, ya que las búsquedas sucesivas en hash B irán al mismo hash (suponiendo que ambos los 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 un código para unordered_set_difference() , puede ajustarlo para crear las versiones para set union y 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;
}

Suponiendo que tiene dos unordered_set , x e 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 de la respuesta de bdonlan , esto realmente funcionará para cualquier tipo de clave, y cualquier combinación de tipos de contenedor (aunque el uso de set_intersection() será, por supuesto, más rápido si los contenedores fuente están ordenados).

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