clase - vector iterator c++

C++ std:: vector<>:: iterator no es un puntero, ¿por qué? (6)

Solo una pequeña introducción, con palabras sencillas. En C ++, los iteradores son "cosas" en las que puede escribir al menos el operador de desreferencia *it , el operador incrementador ++it , y para iteradores bidireccionales más avanzados, decrementar --it , y por último, pero no menos importante, para acceso aleatorio los iteradores que necesitamos el operador lo indexan it[] y posiblemente la suma y resta.

Tales "cosas" en C ++ son objetos de tipos con las sobrecargas de operadores correspondientes, o punteros simples y simples.

std::vector<> es una clase contenedora que envuelve una matriz continua, por lo que el puntero como iterador tiene sentido. En las redes, y en algunas publicaciones, puede encontrar vector.begin() utilizado como puntero.

La razón para usar un puntero es menos sobrecarga, mayor rendimiento, especialmente si un compilador optimizador detecta la iteración y hace lo suyo (instrucciones de vectores y demás). Usar iteradores puede ser más difícil de optimizar para el compilador.

Sabiendo esto, mi pregunta es ¿por qué las implementaciones STL modernas, digamos MSVC ++ 2013 o libstdc ++ en Mingw 4.7, usan una clase especial para iteradores vectoriales?

La razón para usar un puntero es menos sobrecarga, mayor rendimiento, especialmente si un compilador optimizador detecta la iteración y hace lo suyo (instrucciones de vectores y demás). Usar iteradores puede ser más difícil de optimizar para el compilador.

Este es el malentendido en el corazón de la pregunta. Una implementación de clase bien formada no tendrá sobrecarga, y un rendimiento idéntico, todo porque el compilador puede optimizar la abstracción y tratar la clase de iterador como un puntero en el caso de std::vector .

Dicho esto,

MSVC ++ 2013 o libstdc ++ en Mingw 4.7, use una clase especial para iteradores vectoriales

porque ven que agregar una capa de class iterator de abstracción para definir el concepto de iteración sobre un std::vector es más beneficioso que usar un puntero común para este propósito.

Las abstracciones tienen un conjunto diferente de costos en comparación con los beneficios, por lo general, la complejidad agregada del diseño (no necesariamente relacionada con el rendimiento o los gastos generales) a cambio de flexibilidad, pruebas futuras, ocultando los detalles de la implementación. Los compiladores anteriores decidieron que esta complejidad agregada es un costo apropiado para pagar los beneficios de tener una abstracción.

La razón para usar un puntero es menos sobrecarga, mayor rendimiento, especialmente si un compilador optimizador detecta la iteración y hace lo suyo (instrucciones de vectores y demás). Usar iteradores puede ser más difícil de optimizar para el compilador.

Puede ser, pero no lo es. Si su implementación no es completamente sencilla, una estructura que envuelva un puntero alcanzará la misma velocidad.

Teniendo esto en cuenta, es fácil ver que los beneficios simples, como mejores mensajes de diagnóstico (nombrar el iterador en lugar de T *), mejor resolución de sobrecarga, ADL y verificación de depuración hacen que la estructura sea un claro ganador sobre el puntero. El puntero en bruto no tiene ventajas.

Debido a que STL fue diseñado con la idea de que puedes escribir algo que itere sobre un iterador, no importa si ese iterador es simplemente equivalente a un puntero a un elemento de arrays contiguos a la memoria (como std::array o std::vector ) o algo así. como una lista enlazada, un conjunto de claves, algo que se genera sobre la marcha en el acceso, etc.

Además, no se deje engañar: en el caso de vectores, la anulación de referencias (sin opciones de depuración) simplemente se puede descomponer en una inhabilitación de la desreferencia del puntero, por lo que no habría sobrecarga después de la compilación.

Es completamente correcto que vector::iterator podría implementarse con un simple puntero (consulte here ); de hecho, el concepto de iterador se basa en el de un puntero a un elemento de matriz. Para otros contenedores, como map , list o deque , sin embargo, un puntero no funcionará en absoluto. Entonces, ¿por qué no se hace esto? Aquí hay tres razones por las que una implementación de clase es preferible a un puntero en bruto.

Implementar un iterador como tipo separado permite una funcionalidad adicional (más allá de lo requerido por el estándar), por ejemplo ( agregado en la edición después del comentario de Quentins ) la posibilidad de agregar aserciones cuando se elimina la referencia de un iterador, por ejemplo, en el modo de depuración.
resolución de sobrecarga Si el iterador fuera un puntero T* , podría pasarse como un argumento válido a una función que toma T* , mientras que esto no sería posible con un tipo de iterador. De este modo, hacer que std::vector<>::iterator un puntero, de hecho, cambia el comportamiento del código existente. Consideremos, por ejemplo,
template<typename It> void foo(It begin, It end); void foo(const double*a, const double*b, size_t n=0); std::vector<double> vec; foo(vec.begin(), vec.end()); // which foo is called?
búsqueda dependiente del argumento (ADL; señalada por juanchopanza) Si realiza una llamada no calificada, ADL garantiza que las funciones en el namespace std de namespace std buscarán solo si los argumentos son tipos definidos en el namespace std de namespace std . Asi que,
std::vector<double> vec; sort(vec.begin(), vec.end()); // calls std::sort sort(vec.data(), vec.data()+vec.size()); // fails to compile
std::sort no se encuentra si vector<>::iterator fuera un simple puntero.

La implementación del iterador se define por la implementación , siempre que cumpla con los requisitos de la norma. Podría ser un puntero para vector , que funcionaría. Hay varias razones para no usar un puntero;

Consistencia con otros recipientes.
soporte de depuración y comprobación de errores
resolución de sobrecarga, los iteradores basados en clase permiten que las sobrecargas funcionen diferenciándolos de los punteros simples

Si todos los iteradores fueran punteros, entonces ++it en un map no lo incrementaría al siguiente elemento ya que no se requiere que la memoria no sea contigua. Más allá de la memoria contigua de std:::vector mayoría de los contenedores estándar requieren punteros "más inteligentes", por lo tanto, iteradores.

Los requisitos físicos del iterador se combinan muy bien con el requisito lógico de que el movimiento entre elementos es un "lenguaje" bien definido que consiste en iterar sobre ellos, no solo moverse a la siguiente ubicación de memoria.

Este fue uno de los requisitos de diseño originales y objetivos de la STL; la relación ortogonal entre los contenedores, los algoritmos y la conexión de los dos a través de los iteradores.

Ahora que son clases, puede agregar una gran cantidad de chequeos de errores y de sanidad al código de depuración (y luego eliminarlo para obtener un código de versión más optimizado).

Dados los aspectos positivos que traen los iteradores basados en la clase, ¿por qué debería o no debería usar punteros para los iteradores de std::vector - consistencia? Las implementaciones tempranas de std::vector sí utilizaron punteros simples, puede usarlos para vector . Una vez que tenga que usar clases para los otros iteradores, dados los aspectos positivos que aportan, aplicar eso al vector convierte en una buena idea.

Superé este obstáculo molesto al eliminar la referencia e inmediatamente al referirme al iterador nuevamente. Parece ridículo, pero satisface a MSVC ...

class Thing { . . . }; void handleThing(Thing* thing) { // do stuff } vector<Thing> vec; // put some elements into vec now for (auto it = vec.begin(); it != vec.end(); ++it) // handleThing(it); // this doesn''t work, would have been elegant .. handleThing(&*it); // this DOES work