algoritmo para eliminar elementos en la intersección de dos conjuntos

Question

Tengo una aplicación Visual Studio 2008 C++ 03 donde tengo dos contenedores estándar. Me gustaría eliminar de un contenedor todos los elementos que están presentes en el otro contenedor (la intersección de los conjuntos).

algo como esto:

std::vector<int> items = /* 1, 2, 3, 4, 5, 6, 7 */; 
std::set<int> items_to_remove = /* 2, 4, 5*/; 

std::some_algorithm(items.begin, items.end(), items_to_remove.begin(), items_to_remove.end()); 

assert(items == /* 1, 3, 6, 7 */) 

¿Existe un algoritmo existente o patrón que va a hacer esto o tengo que rodar mi propia?

Gracias

Answer 1

intento con:

items.erase(
    std::remove_if(
     items.begin(), items.end() 
     , std::bind1st(
      std::mem_fun(&std::set<int>::count) 
      , items_to_remove 
     ) 
    ) 
    , items.end() 
); 

std::remove(_if) no quita realmente nada, ya que funciona con iteradores y no contenedores. Lo que hace es reordenar los elementos que se eliminarán al final del rango y devuelve un iterador al nuevo extremo del contenedor. A continuación, llama al erase para eliminar realmente del contenedor todos los elementos después del nuevo extremo.

Actualización: Si no recuerdo mal, el enlace a una función miembro de un componente de la biblioteca estándar no es C++ estándar, ya que las implementaciones pueden agregar parámetros predeterminados a la función. Sería más seguro al crear su propia función o predicado de objeto de función que verifica si el elemento está contenido en el conjunto de elementos para eliminar.

Answer 2

Puede usar std::erase en combinación con std::remove para esto. Existe un modismo en C++ llamado Erase - Remove idiom, que lo ayudará a lograrlo.

Answer 3

Asumiendo que tiene dos conjuntos, A y B, y desea eliminar de B, la intersección, I, de (A,B) tal que I = A^B, los resultados finales serán: A (izquierda intacta)
B' = B-I

teoría completa:
http://math.comsci.us/sets/difference.html

Esto es bastante simple.

1. crear y rellenar A y B
2. crear un tercer vector intermedio, I
3. Copiar el contenido de B en I
4. Para cada elemento a_j de A, que contiene j elementos, la búsqueda I de el elemento a_j; Si no se encuentra el elemento en I, y eliminar

Por último, el código para eliminar un elemento individual se puede encontrar aquí:
How do I remove an item from a stl vector with a certain value?

Y el código para buscar un elemento está aquí:
How to find if an item is present in a std::vector?

¡Buena suerte!

Answer 4

Personalmente, prefiero crear pequeños ayudantes para esto (que reutilizo mucho).

template <typename Container> 
class InPredicate { 
public: 
    InPredicate(Container const& c): _c(c) {} 

    template <typename U> 
    bool operator()(U const& u) { 
     return std::find(_c.begin(), _c.end(), u) != _c.end(); 
    } 

private: 
    Container const& _c; 
}; 

// Typical builder for automatic type deduction 
template <typename Container> 
InPredicate<Container> in(Container const& c) { 
    return InPredicate<Container>(c); 
} 

Esto también ayuda a tener un cierto algoritmo de erase_if

template <typename Container, typename Predicate> 
void erase_if(Container& c, Predicate p) { 
    c.erase(std::remove_if(c.begin(), c.end(), p), c.end()); 
} 

Y luego:

erase_if(items, in(items_to_remove)); 

que es bastante legible :)

Answer 5

Una solución más:

Hay un algoritmo proporcionado estándar set_difference que se puede usar para esto. Pero requiere un contenedor adicional para contener el resultado. Yo personalmente prefiero hacerlo en el lugar.

std::vector<int> items; 
//say items = [1,2,3,4,5,6,7,8,9] 

std::set<int>items_to_remove; 
//say items_to_remove = <2,4,5> 

std::vector<int>result(items.size()); //as this algorithm uses output 
          //iterator not inserter iterator for result. 

std::vector<int>::iterator new_end = std::set_difference(items.begin(), 
items.end(),items_to_remove.begin(),items_to_remove.end(),result.begin()); 

result.erase(new_end,result.end()); // to erase unwanted elements at the 
            // end. 

Answer 6

He aquí una más "práctico" método local que no requiere funciones muy elaboradas ni tampoco los vectores que habrá que resolver:

#include <vector> 

template <class TYPE> 
void remove_intersection(std::vector<TYPE> &items, const std::vector<TYPE> &items_to_remove) 
{ 
    for (int i = 0; i < (int)items_to_remove.size(); i++) { 
     for (int j = 0; j < (int)items.size(); j++) { 
      if (items_to_remove[i] == items[j]) { 
       items.erase(items.begin() + j); 
       j--;//Roll back the iterator to prevent skipping over 
      } 
     } 
    } 
} 

si se sabe que la multiplicidad en cada set es 1 (no es multiset), entonces puede reemplazar la línea j--; con break; para un mejor rendimiento.