C++ invalidación de iterador multimap

Question

Estoy tratando de averiguar cómo funcionan los iteradores std::multimap, por lo tanto, he creado un ejemplo simple que muestra la esencia de mi problema. Si no comentario el caso 1, espero que el iterador apunte al primer elemento con la clave 1, pero en realidad imprime todos los valores asociados con la clave 0 (como que nada se borró) y a veces falla, probablemente porque el iterador no es válido. Sin embargo, si se elimina el caso 2, todos los valores con la clave 1 se borran correctamente.

¿Hay alguna manera de saber cuál es el siguiente iterador válido para el multimap después del borrado? (por ejemplo std::vector.erase(...) devuelve uno)

std::multimap<int, int> m; 

for(int j=0; j<3; ++j) { 
    for(int i=0; i<5; ++i) { 
     m.insert(std::make_pair(j, i)); 
    } 
} 

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

Answer 1

La causa del problema

Cuando se llama a m.erase(0) en ti ejemplo, it puntos en un elemento con la tecla 0 - por lo it se invalida. m.erase(1) funciona, porque cuando se llama por primera vez, it no apunta a un elemento con la clave 1, por lo que no se ve afectado. En iteraciones posteriores, no quedan elementos con la clave 1, por lo que no se borra nada, y ningún iterador se ve afectado.

La solución

multimap no tiene un -method erase que devuelve la siguiente iterador válida. Una alternativa es llamar al it = m.upper_bound(deleted_key); después de la eliminación. Sin embargo, esto es logarítmico, lo que podría ser demasiado lento para su escenario (erase(x) y upper_bound serían dos operaciones logarítmicas).

Suponiendo que desea borrar la clave de su iterador está apuntando a, usted podría hacer algo como esto (si no, erase está muy bien, por supuesto, no probado):

std::multimap<int, int>::iterator interval_start = m.begin(); 
for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end(); ++it) { 
    if(interval_start->first < it->first) // new interval starts here 
     interval_start == it; 
    if((*it).second == 3) { 
     std::multimap<int, int>::iterator interval_end = it; 
     while((interval_end != m.end()) && (interval_end->first == it->first)) { 
      ++interval_end; // search for end of interval - O(n) 
     } 
     m.erase(interval_start, interval_end); // erase interval - amortized O(1) 
     it = interval_end; // set it to first iterator that was not erased 
     interval_start = interval_end; // remember start of new interval 
    } 
} 

Este utiliza la operación lineal , todo el resto es tiempo constante. Si su mapa es muy grande y solo tiene pocos elementos con las mismas teclas, es probable que sea más rápido. Sin embargo, si tiene muchos elementos con las mismas teclas, la búsqueda para el final del intervalo probablemente se realice mejor usando upper_bound (O(log n) en lugar de O(n) al buscar el final del intervalo).

Answer 2

primera respuesta

std::multimap<int, int> m; 
// ^^^^^^^^ 
std::map<int, int>::iterator it=m.begin(); 
// ^^^ 

Hum ....

segunda respuesta, Re: pregunta

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    .... stuff .... 
     m.erase(1); // container mutation 
    .... stuff .... 
} 

editado ser extremadamente cuidadoso cuando estás mutando un contenedor (cualquier contenedor) cuando lo estás iterando, como tú podría invalidar un iterador del que dependas

Los llamados "contenedores a base de nodo" (list, set, map ...) son los más robustos invalidación WRT contenedor iterador: sólo invalidan los iteradores a los elementos eliminados (no hay manera de que estos iteradores no sean invalidado).

En este caso, debe verificar que el elemento que va a eliminar no sea realmente *it.

No estoy muy seguro de lo que realmente está tratando de hacer con su ciclo.

Answer 3

cuando borra el iterador no es válido. en su lugar, recuerde el siguiente elemento y luego bórrelo:

std::map<int,int>::iterator next = m + 1; 
m.erase 
m = next; 

Answer 4

Al observar su código, creo que su ++ está causando el problema. Lo estás asignando a un lugar que podría haber sido eliminado. moverlo hasta el final, después de la instrucción if y la prueba. de este modo:

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
    ++it; 
} 

Answer 5

(Edited)

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

Además de invalidación de it iterador debido a m.erase que puede ocurrir, dependiendo del contenido de multimap (ya cubiertos en otra respuesta) siempre existe el problema de que deja de hacer referencia m.end() iterador en la última iteración de su for loop cuando hace if((*it).second == 3) cada vez que ejecuta su programa.

Sugiero ejecutar y depurar con compilaciones de depuración. Estoy casi seguro de que cada implementación de una biblioteca estándar sana debe contener afirmar para detectar la desreferenciación end().

Answer 6

Algunos tipos de arriba ya han respondido que estás jugando con un fuego.

Además, creo que se está olvidando que el mapa múltiple es un mapa ordenado, por lo que está iterando desde las teclas más pequeñas hasta las más grandes. Por lo tanto, en el primer caso, se eliminan las claves después de imprimir algunas, pero en el segundo caso se eliminan justo antes de ir a ellas.