c++ - for - std:: remove con vector:: borrar y comportamiento indefinido

vector c++ español

Question

En toda la web veo que las personas usan la expresión borrar / eliminar para los vectores C ++ de esta manera:

#include <vector> // the general-purpose vector container
#include <iostream>
#include <algorithm> // remove and remove_if
int main()
{
  // initialises a vector that holds the numbers from 0-9.
  std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // removes all elements with the value 5
  v.erase( std::remove( v.begin(), v.end(), 5 ), v.end() );

  return 0;
}

Es decir, si quiero borrar todos los elementos que coinciden con algunos criterios (por ejemplo, el número 5 de un vector de int s), entonces uso std::remove o std::remove_if junto con vector.erase así:

vector.erase( std::remove( vector.begin(), vector.end(), <some_value>), vector.end());

Esto funciona bien en general; std::remove (y remove_if ) copiará (o usará la semántica de movimiento en C ++ 11) los elementos que se van a eliminar hasta el final del vector, por lo que el vector de nuestro ejemplo anterior se verá así:

{0, 1, 2, 3, 4, 6, 7, 8, 9, 5 };

Con el elemento 5 en negrita porque ha sido movido hasta el final.

Ahora, std::remove le devolverá un iterador, que luego usaremos en erase para borrar los elementos. Bonito.

Pero, ¿qué pasa con el siguiente ejemplo?

int main()
{
  // initialises an empty vector.
  std::vector<int> v = {};

  // removes all elements with the value 5
  v.erase( std::remove( v.begin(), v.end(), 5 ), v.end() );

  return 0;
}

Esto parece funcionar como se espera (sin borrar nada, no segfaulting, etc.) en todas las plataformas en las que lo ejecuto, pero sé que solo porque algo funciona, no significa que no sea un comportamiento indefinido.

La reference rápida para vector.erase dice esto (énfasis mío):

iterator erase (const_iterator first, const_iterator last);

first, last son

Iteradores que especifican un rango dentro del vector] a eliminar: [first,last) . es decir, el rango incluye todos los elementos entre el first y el last , incluido el elemento señalado por el primero pero no el señalado por el last . Los tipos de miembros const_iterator y const_iterator son tipos de iteradores de acceso aleatorio que apuntan a elementos.

Entonces, ¿es el vector.erase(vector.end(),vector.end()) ?

Esto es lo que dice la referencia rápida sobre la seguridad de excepciones:

Si los elementos eliminados incluyen el último elemento del contenedor, no se lanzan excepciones (garantía de no-throw). De lo contrario, se garantiza que el contenedor terminará en un estado válido (garantía básica). Una position o range no válido causa un comportamiento indefinido.

Entonces, la respuesta, al menos para mí, parece ser "SÍ", y esta respuesta de StackOverflow parece ser compatible.

Por lo tanto, ¿es incorrecto el idioma común?

Asumiendo que es un comportamiento indefinido, cualquier llamada a remove podría devolver un iterador a vector.end() que debería verificarse antes de llamar a vector.erase , y llamar a eliminar en un vector vacío parece devolver vector.end : ( IDEOne para el código a continuación) )

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
   vector<int> myInts;
   auto anIter = std::remove(myInts.begin(),myInts.end(),5);
   if (anIter == myInts.end())
      std::cout << "iterator = myInts.end()";
}

Finalmente, mi pregunta:

¿Debe el idioma eliminar / borrar real ser esto?

auto endOfRangeIterator = std::remove(vector.begin(), vector.end(), <value>);
if (endOfRangeIterator != vector.end())
   vector.erase(endOfRangeIterator, vector.end())

Answer 1

Entonces, ¿es el comportamiento indefinido de vector.erase (vector.end (), vector.end ())?

No. Debido a la afirmación que está justo al lado de la que usted hizo hincapié:

Iteradores que especifican un rango dentro del vector] a eliminar: [primero, último). es decir, el rango incluye todos los elementos entre el primero y el último, incluido el elemento señalado por el primero pero no el señalado por el último .

Entonces, vector.erase(vector.end(),vector.end()) no intenta borrar vector.end() porque está apuntado por el last parámetro.

Por supuesto, esta definición es ambigua y esas declaraciones pueden interpretarse como contradictorias. La fraseología citada no es utilizada por la norma.

Answer 2

24.2.1 / 7 La mayoría de las plantillas algorítmicas de la biblioteca que operan en estructuras de datos tienen interfaces que usan rangos. Un rango es un par de iteradores que designan el comienzo y el final del cálculo. Un rango [i,i) es un rango vacío ; en general, un rango [i,j) refiere a los elementos en la estructura de datos que comienzan con el elemento apuntado por i y hasta, pero sin incluir, el elemento apuntado por j .

Énfasis mío

Además, la descripción de erase usted cita no es el texto normativo en el estándar. El estándar tiene esto que decir (Tabla 100):

a.erase(q1,q2)

Efectos : borra los elementos en el rango [q1, q2).

Esto no requiere que q1 sea ​​desreferenciable. Si [q1, q2) es un rango vacío (por 24.2.1 / 7), entonces no hay elementos en el rango, por lo que ninguno se borrará.

Answer 3

Creo que lo más importante en tu cita es:

Iteradores que especifican un rango dentro del vector] a eliminar: [primero, último). es decir, el rango incluye todos los elementos entre el primero y el último, incluido el elemento señalado por el primero pero no el señalado por el último . Los tipos de miembros iterator y const_iterator son tipos de iteradores de acceso aleatorio que apuntan a elementos.

Como hemos encontrado en los comentarios, esta cita de reference es incorrecta. Esto no violará las reglas en caso de ( v.end, v.end) pero será incorrecto en caso de

#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 3 };

    v.erase( v.begin(), v.begin());
}

porque afirmación que se contradice con

el rango incluye (...), incluido el elemento apuntado por v.begin () pero no el apuntado por v.begin ().

no puede ser una declaración válida.

Norma n3337 de C ++ en § 23.2.2 Requisitos de contenedores de secuencia La Tabla 100 especifica que

a.erase(q1,q2) devuelve el iterator . Y nota es:

Requiere: para vector y deque, T será MoveAssignable. Efectos: borra los elementos en el rango [q1, q2) .

Y esto es lo que dice sobre el rango [i,j) en el § 24.2.1 / 7 Requisitos del iterador

La mayoría de las plantillas algorítmicas de la biblioteca que operan en estructuras de datos tienen interfaces que usan rangos. Un rango es un par de iteradores que designan el comienzo y el final del cálculo. Un rango [i, i) es un rango vacío; en general, un rango [i, j) se refiere a los elementos en la estructura de datos que comienzan con el elemento apuntado por i y hasta, pero sin incluir, el elemento apuntado por j . El rango [i, j) es válido si y solo si j es alcanzable desde i. El resultado de la aplicación de funciones en la biblioteca a rangos no válidos no está definido.

Por lo tanto para responder a sus preguntas

Pero, ¿qué pasa con el siguiente ejemplo?

cplusplus.com está equivocado en este caso

Entonces, ¿es el comportamiento indefinido de vector.erase (vector.end (), vector.end ())?

No, no se desencadena un comportamiento indefinido.

Por lo tanto, ¿es incorrecto el idioma común?

No, es correcto

¿Debe el idioma eliminar / borrar real ser esto?

No hay necesidad de esto, aunque también está bien.