No entiendo por qué un iterador de vector debe invalidarse cuando ocurre una reasignación.¿Por qué se invalida vector :: iterator en la reasignación?
¿No se pudo evitar esto simplemente almacenando offset - en lugar de un puntero - en el iterador?
¿Por qué vector no está diseñado de esta manera?
sólo para añadir una citación a la justificación en función del rendimiento: el diseño de C++, BS pensó que era vital que clases de plantilla como std::vector se acercan a las características de rendimiento de las matrices nativas:
Una de las razones para el énfasis en la eficiencia en el tiempo de ejecución ... fue que quería que las plantillas fueran lo suficientemente eficientes en tiempo y espacio para ser usadas con tipos de bajo nivel tales como matrices y listas.
...
alternativas de más alto nivel - por ejemplo, una matriz de rango comprobado con un tamaño() operación, una matriz multidimensional, un tipo de vector con operaciones de vectores numéricos adecuados y copia la semántica, etc. . - Sería aceptado por los usuarios de solo si su tiempo de ejecución, espacio y comodidad de notación se acercaran a los de las matrices integradas.
En otras palabras, el mecanismo de lenguaje que proporciona los tipos parametrizados debe ser tal que un usuario afectado pueda permitirse eliminar el uso de matrices en favor de una clase de biblioteca estándar.
Bjarne Stroustrup, Diseño y Evolución de C++, p.342.
Debería almacenar tanto el desplazamiento como un puntero al propio objeto vectorial.
Según lo especificado, el iterador puede ser simplemente un puntero, que ocupa menos espacio.
Porque para que los iteradores lo hagan, tendrían que almacenar un puntero al objeto vector. Para cada acceso a datos, tendrían que seguir el puntero al vector, luego seguir el puntero a la ubicación actual de la matriz de datos, luego agregar la compensación * el tamaño del elemento. Eso sería mucho más lento y necesitaría más memoria para el miembro size_type.
Sin duda, es un buen compromiso a veces y sería bueno poder elegirlo cuando lo desee, pero es más lento y voluminoso que el uso de matriz directa (estilo C). std::vector fue minuciosamente analizado para el rendimiento cuando se introdujo el STL, y la implementación normal se optimiza para el espacio y la velocidad sobre este factor de conveniencia/confiabilidad, del mismo modo que la matriz equivalente operator[] es tan rápida como las matrices pero menos segura que at().
+1 me hubiera gustado aceptar esta pero la respuesta de Nate fue una cita! : \ ¡Gracias! – Mehrdad
Cuántas veces he deseado que '[]' sea el acceso marcado y 'at' el que no se haya marcado :( –
@Matthieu: ¡estuvo de acuerdo! Puede ser agradable alardear de lo deslumbrantemente rápido que es su código, pero la mayoría de las veces si usa 'at()' y guarda el tiempo de depuración para crear perfiles, de todos modos terminará más rápido ... :-) –
Hay muchas razones para estas decisiones. Como señalaron otros, la implementación más básica de iterator para un vector es un indicador simple del elemento. Para poder manejar iteradores push_back tendría que modificarse para manejar un puntero en el vector y una posición, en el acceso a través del operador, el puntero del vector debería ser desreferenciado, el puntero a los datos obtenidos y la posición añadida, con una desreferencia adicional.
Si bien esa no sería la implementación más eficiente, no es realmente un factor limitante. La implementación predeterminada de los iteradores en las bibliotecas de VS/Dinkumware (incluso en versión) son iteradores verificados, que administran una cantidad equivalente de información.
El problema real viene con otras operaciones de mutación. Considere insertar/borrar en el medio del vector. Para mantener la validez de todos los iteradores, el contenedor tendría que rastrear todas las instancias de los iteradores y adaptar el campo de posición para que sigan refiriéndose al mismo elemento (que ha sido desplazado por la inserción/eliminación).
+1 para referencia de inserción/borrado. –
"adaptar el campo de posición para que sigan haciendo referencia al mismo elemento (que ha sido desplazado por la inserción/eliminación)." - esa es solo una noción de "validez" - es tan probable que el cliente quiera referirse al elemento N-ésimo independientemente de las inserciones/eliminaciones (aceptando la responsabilidad de garantizar que todavía haya un enésimo elemento). Por separado, el Estándar C++ 11 23.3.6.5.1 y 23.4.6.5.3 permite la invalidación de iteradores/referencias en o después del punto de una inserción o borrado, incluso con iteradores "normales". –
@TonyDelroy: un iterador se refiere a un elemento en un contenedor. Si después de obtener un iterador, el iterador ya no se refiere al mismo elemento que sería una violación en el contrato. Considere los operadores en los iteradores: 'auto it = std :: find (v.begin(), v.end(), value); v.erase (v.begin() + 5); 'en este punto (asumiendo su premisa) no hay garantía de que' * it == value' para un vector, pero si 'v' fuera una lista, entonces lo haría estar garantizado Ahora ha roto el contrato del iterador en diferentes iteradores, con una semántica completamente diferente. –
Puede agregar seguridad al envolver el estándar std::vector<T>::iterator, pero no puede agregar velocidad al envolver un extension::vector<T>::safe_iterator. Ese es un principio general y explica muchas opciones de diseño de C++.
I un iterador no se invalidó, ¿debería apuntar al mismo elemento o a la misma posición después de una inserción anterior? En otras palabras, incluso si no hubiera problemas de rendimiento, no es trivial decidir qué definición alternativa usar.
No entiendo esta respuesta ... – Mehrdad
La pregunta es sobre reasignaciones, no inserciones. F.ex. un 'push_back' puede desencadenar una reasignación. – curiousguy
TL; DR - porque usted está negociando reglas simples para la invalidación de acciones mucho más complicadas de acción a distancia.
Tenga en cuenta que "almacenar un puntero al objeto vector" podría causar nuevos casos de invalidación. Por ejemplo, hoy swap preserva la validez del iterador, si un puntero (o referencia) al vector se almacena dentro de los iteradores, ya no podría. Todas las operaciones que mueven los metadatos del vector en sí (vector-de-vectores, ¿alguien?) Invalidaría los iteradores.
Su operación es "el iterador no es válido cuando se invalida un puntero/referencia al elemento" porque "el iterador no es válido cuando se invalida un puntero/referencia al vector".
Los argumentos de rendimiento no importan mucho, porque la implementación alternativa propuesta ni siquiera es correcta.
Sí, realmente ya no tengo esta pregunta jaja. Creo que me di cuenta de esto no mucho después de hacer esta pregunta. ¡Gracias! +1 – Mehrdad
+1 buena pregunta. – Nawaz
@Nawaz: ¡Gracias! :) – Mehrdad
Cada vez que inserte en cualquier lugar menos el final o la clasificación, etc., deberá cambiar todos los desplazamientos. –