c++ - vectorial - escalares y vectores

std:: diferencias de vectores

Question

¿Cómo se determina cuáles son las diferencias de 2 vectores?

Tengo el vector<int> v1 y el vector<int> v2 ;

Lo que estoy buscando es un vector<int> vDifferences que contiene solo elementos que están solo en v1 o v2 .

¿Hay una manera estándar de hacer esto?

Answer 1

¿Desea elementos tanto de v1 como de v2 que sean únicos y no en la otra secuencia? Eso me suena a std::set_symmetric_difference .

Copia los elementos del rango [first1, last1) que no están presentes en el rango [first2, last2), y los elementos del rango [first2, last2) que no están presentes en el rango [first1, last1) al rango comenzando en el resultado. Los elementos en el rango construido están ordenados.

Answer 2

Aquí está la respuesta completa y correcta . Antes de poder set_symmetric_difference algoritmo set_symmetric_difference , se deben ordenar los rangos de origen:

  using namespace std; // For brevity, don''t do this in your own code...

  vector<int> v1;
  vector<int> v2;

  // ... Populate v1 and v2

  // For the set_symmetric_difference algorithm to work, 
  // the source ranges must be ordered!    
  vector<int> sortedV1(v1);
  vector<int> sortedV2(v2);

  sort(sortedV1.begin(),sortedV1.end());
  sort(sortedV2.begin(),sortedV2.end());

  // Now that we have sorted ranges (i.e., containers), find the differences    
  vector<int> vDifferences;

  set_symmetric_difference(
    sortedV1.begin(),
    sortedV1.end(),
    sortedV2.begin(),
    sortedV2.end(),
    back_inserter(vDifferences));

  // ... do something with the differences

Se debe tener en cuenta que la clasificación es una operación costosa (es decir, O (n log n) para implementaciones STL comunes ). Especialmente para el caso de que uno o ambos contenedores sean muy grandes (es decir, millones de enteros o más), un algoritmo diferente que use tablas hash puede ser preferible en función de la complejidad algorítmica. Aquí hay una descripción de alto nivel de este algoritmo:

1. Cargue cada contenedor en una tabla hash.
2. Si los dos contenedores difieren en tamaño, la tabla hash correspondiente a la más pequeña se utilizará para el recorrido en el Paso 3. De lo contrario, se utilizará la primera de las dos tablas hash.
3. Recorra la tabla hash elegida en el Paso 2 y verifique si cada elemento está presente en ambas tablas hash. Si lo es, quítalo de los dos. La razón por la que se prefiere la tabla hash más pequeña para el recorrido es porque las búsquedas en la tabla hash están en el O (1) promedio independientemente del tamaño del contenedor. Por lo tanto, el tiempo para recorrer es una función lineal de n (es decir, O (n) ), donde n es el tamaño de la tabla hash que se está recorriendo.
4. Tome la unión de los elementos restantes en las tablas hash y almacene el resultado en un contenedor de diferencia.

C ++ 11 nos ofrece cierta capacidad para una solución de este tipo al estandarizar el contenedor unordered_multiset . También utilicé el nuevo uso de la palabra clave auto para las inicializaciones explícitas para hacer que la siguiente solución basada en tabla hash sea más concisa:

using namespace std; // For brevity, don''t do this in your own code...

// The remove_common_items function template removes some and / or all of the
// items that appear in both of the multisets that are passed to it. It uses the
// items in the first multiset as the criteria for the multi-presence test.
template <typename tVal>
void remove_common_items(unordered_multiset<tVal> &ms1, 
                         unordered_multiset<tVal> &ms2)
{
  // Go through the first hash table
  for (auto cims1=ms1.cbegin();cims1!=ms1.cend();)
  {
    // Find the current item in the second hash table
    auto cims2=ms2.find(*cims1);

    // Is it present?
    if (cims2!=ms2.end())
    {
      // If so, remove it from both hash tables
      cims1=ms1.erase(cims1);
      ms2.erase(cims2);
    }
    else // If not
      ++cims1; // Move on to the next item
  }
}

int main()
{
  vector<int> v1;
  vector<int> v2;

  // ... Populate v1 and v2

  // Create two hash tables that contain the values
  // from their respective initial containers    
  unordered_multiset<int> ms1(v1.begin(),v1.end());
  unordered_multiset<int> ms2(v2.begin(),v2.end());

  // Remove common items from both containers based on the smallest
  if (v1.size()<=v2.size)
    remove_common_items(ms1,ms2);
  else
    remove_common_items(ms2,ms1);

  // Create a vector of the union of the remaining items
  vector<int> vDifferences(ms1.begin(),ms1.end());

  vDifferences.insert(vDifferences.end(),ms2.begin(),ms2.end());

  // ... do something with the differences
}

Para determinar qué solución es mejor para una situación particular, perfilar ambos algoritmos sería un curso de acción inteligente. Aunque la solución basada en la tabla hash está en O (n), requiere más código y hace más trabajo por duplicado encontrado (es decir, eliminaciones de tabla hash). También (lamentablemente) utiliza una función de diferenciación personalizada en lugar de un algoritmo STL estándar.

Cabe señalar que ambas soluciones presentan las diferencias en un orden que probablemente sea muy diferente del orden en que aparecieron los elementos en los contenedores originales. Hay una forma de evitar esto utilizando una variante de la solución de tabla hash. Sigue una descripción de alto nivel (que solo difiere en el Paso 4 de la solución anterior):

1. Cargue cada contenedor en una tabla hash.
2. Si los dos contenedores difieren en tamaño, la tabla hash más pequeña se usará para recorrer en el Paso 3. De lo contrario, se utilizará el primero de los dos.
3. Recorra la tabla hash elegida en el Paso 2 y verifique si cada elemento está presente en ambas tablas hash. Si lo es, quítalo de los dos.
4. Para formar el contenedor de diferencia, recorra los contenedores originales en orden (es decir, el primer contenedor antes del segundo). Busque cada elemento de cada contenedor en su tabla hash respectiva. Si se encuentra, el elemento se agregará al contenedor de diferencias y se eliminará de su tabla hash. Los elementos que no estén presentes en las tablas hash respectivas se omitirán. Por lo tanto, solo los elementos que están presentes en las tablas de hash terminarán en el contenedor de diferencia y su orden de aparición seguirá siendo el mismo que en los contenedores originales, ya que esos contenedores dictan el orden del recorrido final.

Para mantener el orden original, el Paso 4 se ha vuelto más costoso que en la solución anterior, especialmente si el número de artículos eliminados es alto. Esto es porque:

1. Todos los elementos se probarán por segunda vez para que la elegibilidad aparezca en el contenedor de diferencias, a través de una prueba de presencia en sus respectivas tablas hash.
2. A las tablas hash se les eliminará el resto de sus elementos uno por uno cuando se forme el contenedor de diferencia, como parte del presente en la prueba de diferencia del Elemento 1.