Comportamiento extraño con vector :: erase y std :: remove_if con rango final diferente de vector.end()

Question

Necesito eliminar elementos del medio de un estándar :: vector.

así que he intentado:

struct IsEven { 
    bool operator()(int ele) 
    { 
     return ele % 2 == 0; 
    } 
}; 

    int elements[] = {1, 2, 3, 4, 5, 6}; 
    std::vector<int> ints(elements, elements+6); 

    std::vector<int>::iterator it = std::remove_if(ints.begin() + 2, ints.begin() + 4, IsEven()); 
    ints.erase(it, ints.end()); 

Después de esto, se esperaría que el vector tiene ints: [1, 2, 3, 5, 6].

En el depurador de Visual Studio 2008, después de la línea std::remove_if, los elementos de ints se modifican, supongo que tengo algún tipo de comportamiento indefinido aquí.

Entonces, ¿cómo elimino los elementos de un Rango de un vector?

Answer 1

Edit: Lo sentimos, la versión original de esto era incorrecta. Fijo.

Esto es lo que está pasando. Su aportación a remove_if es:

1 2 3 4 5 6 
    ^ ^
    begin end 

y el algoritmo remove_if mira a todos los números entre begin y end (incluyendo begin, pero excluyendo end), y elimina todos los elementos entre que coincidan con su predicado. Así que después de remove_if carreras, su vector se parece a esto

1 2 3 ? 5 6 
    ^^ 
    begin new_end 

Dónde ? es un valor que no creo es determinista, aunque si se garantiza que sea algo sería 4. Y new_end, que apunta al nuevo extremo de la secuencia de entrada que le dio, con los elementos coincidentes ahora eliminados, es lo que devuelve std::remove_if. Tenga en cuenta que std::remove_if no toca nada más allá de la subsecuencia que le diste. Esto podría tener más sentido con un ejemplo más extendido.

decir que esta es su entrada:

1 2 3 4 5 6 7 8 9 10 
    ^   ^
    begin   end 

Después std::remove_if, se obtiene:

1 2 3 5 7 ? ? 8 9 10 
    ^ ^
    begin  new_end 

pensar en esto por un momento. Lo que ha hecho es eliminar el 4 y el 6 de la subsecuencia, y luego desplazar todo hacia abajo en la subsecuencia hacia abajo para completar los elementos eliminados, y luego mover el iterador end al nuevo final de la misma subsecuencia. El objetivo es satisfacer el requisito de que la secuencia (begin, new_end] que produce sea la misma que la subsecuencia (begin,) que transfirió, pero con ciertos elementos eliminados. Cualquier cosa que exceda el end que haya pasado. se deja intacto.

lo que quiere deshacerse de, a continuación, es todo lo que entre el iterador final que fue devuelto, y el iterador final original, que le dio. Estos son los valores ? "basura". Así su llamada de borrado debería ser:

ints.erase(it, ints.begin()+4); 

La llamada a erase que acaba de borrar todo más allá del final de la subsecuencia en la que realizó la eliminación, que no es lo que desea aquí.

Lo que lo hace complicado es que el algoritmo remove_if en realidad no llama al erase(), o cambia el tamaño del vector en cualquier punto. Simplemente cambia elementos y deja algunos elementos "basura" después del final de la subsecuencia que solicitó que procesara. Esto parece tonto, pero la razón por la que STL lo hace de esta manera es evitar el problema con los iteradores invalidados que trajo el doublep (y poder ejecutar cosas que no son contenedores STL, como matrices en bruto).

Answer 2

Borrando elementos en std::vector invalida iteradores más allá del elemento eliminado, por lo que no puede usar funciones "extrañas" que aceptan rangos. Tienes que hacer eso de una manera diferente.

EDIT:

En general, se puede utilizar el hecho de que el borrado de un elemento "cambia" todos los elementos en posiciones más una vuelta. Algo como esto:

for (size_t scan = 2, end = 4; scan != end;) 
    { 
    if (/* some predicate on ints[scan] */) 
     { 
     ints.erase (ints.begin() + scan); 
     --end; 
     } 
    else 
     ++scan; 
    } 

Tenga en cuenta que std::vector no es adecuado para los elementos en el medio de borrar. Deberías considerar algo más (std::list?) Si lo haces a menudo.

EDIT 2:

Como ha aclarado comentarios, primer párrafo no es cierto. En tal caso, std::remove_if debería ser más eficiente que lo que sugerí en la primera edición, por lo tanto, ignore esta respuesta. (Conservándolo para los comentarios.)

Answer 3

El comportamiento no es extraño: está borrando el rango incorrecto. std::remove_if mueve elementos que "elimina" al final del rango de entrada. En este caso, lo que está buscando sería hacer:

ints.erase(it, ints.begin() + 4 /* your end of range */); 

De C++ en una cáscara de nuez:

La plantilla de función remove_if "elimina" elementos para los que Pred vuelve falsa de el rango [primero, último). El valor de retorno es uno más allá del nuevo fin del rango. El orden relativo de los elementos que no se eliminan es estable.

Nada se borra realmente del contenedor subyacente ; en su lugar, los elementos a la derecha se asignan a las nuevas posiciones , por lo que sobrescriben los elementos para los cuales pred devuelve falso. Consulte la Figura 13-13 (en remove_copy) para ver un ejemplo del proceso de eliminación.