2012-02-02 18 views
5

el siguiente código termina con un volcado del núcleo. ¿Qué hago mal?std :: merge fusionando dos std :: vector coredump

std::vector<int> a; 
a.push_back(1); 
a.push_back(4); 
a.push_back(7); 
std::vector<int> b; 
b.push_back(2); 
b.push_back(5); 
b.push_back(8); 
std::vector<int> c; 
c.clear(); 


std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); 
for (it=c.begin(); it!=c.end(); ++it) 
    std::cout << *it << endl; 

¿Hay alguna otra función de la fusión en el STL o impulso que podría utilizar?

Gracias!

Respuesta

2
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c)); 
                ^^^^^^^^^^^^^^^^^^^^^^^ 

Lo que pasa es que si pasa c.begin(), la función de fusión comenzará a escribir valores en *c.begin(), *(c.begin() + 1) etc, lo que conduce a un comportamiento indefinido, incluyendo volcado de memoria. Tienes dos opciones aquí.

  • c Asegúrese de que es lo suficientemente grande para contener todos los valores que se fusionan va a escribir en él. Por ejemplo, puede llamar al c.resize(a.size()+b.size()); antes de llamar al merge
  • Pase un std::back_insert_iterator. El ejemplo de esto se da al principio en mi respuesta. Cada vez que realice *it = x donde it es back_insert_iterator, se push_back x en el contenedor subyacente.

Se puede encontrar información sobre el inserto de inserción posterior en here. back_inserter es solo una función de conveniencia para que no escriba muchos argumentos de plantilla.

9

El problema es que su c está vacío porque se inicializó sin elementos, sin mencionar la llamada innecesaria al clear(). std::merge() toma un iterador de salida como su último argumento. Si c.begin() se refiere al comienzo de std::vector que ya contiene elementos suficientes, entonces esto no es un problema, esos elementos simplemente se sobrescribirán. Tal como está, está invocando un comportamiento indefinido escribiendo valores en la memoria pasado al final del vector.

Para garantizar que c tiene espacio suficiente para los elementos, se puede hacer esto:

c.resize(a.size() + b.size()); 
std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); 

Sin embargo, es más idiomático utilizar un std::back_insert_iterator, un iterador de salida que llama push_back(). Para una mejor eficacia, puede llamar al reserve() en el vector de antemano. Esto asegura que c solo necesita asignar memoria una vez, en lugar de crecer durante la llamada al std::merge(). La solución final se parece a esto:

#include <iterator> 

// ... 

c.reserve(a.size() + b.size()); 
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c)); 
+0

Su respuesta es correcta, pero no utilizaría el término 'reserva ', ya que significa algo completamente diferente de' resize'. –

+0

¿Por qué eligió llamar a la segunda solución "mejor"? Yo diría lo contrario, ya que se conoce el tamaño y la primera variante es ciertamente más eficiente y no realmente más compleja que la segunda. –

+1

@KonradRudolph: el segundo es menos propenso a errores, y más general, puede conocer el tamaño en este caso, pero a veces no. – Fanael

2

Usted está tratando de almacenar los resultados en c, que está vacía, y como tal, no tiene espacio suficiente para almacenar todos ellos (de hecho, que doesn no tiene suficiente espacio para almacenar nada). Trate de usar back_insert_iterator, que push_back los elementos en su lugar:

std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c)); 
1

c no es lo suficientemente grande como para contener la combinación.Pruebe:

#include <iterator> 
... 
std::merge(a.begin(), a.end(), 
      b.begin(), b.end(), 
      std::back_inserter(c));