Duración del iterador C ++ y detección de invalidación

8

Basado en lo que se considera idiomático en C ++ 11:

  • ¿Debería un iterador en un contenedor personalizado sobrevivir al contenedor que está siendo destruido?
  • ¿debería ser posible detectar cuándo un iterador se invalida?
  • ¿las condiciones anteriores están condicionadas a las "compilaciones de depuración" en la práctica?

Detalles : Recientemente he estado actualizando mi C ++ y aprendiendo a manejar C ++ 11. Como parte de eso, he estado escribiendo un envoltorio idiomático alrededor de la biblioteca de uriparsers . Parte de esto es envolver la representación de la lista enlazada de los componentes de la ruta analizada. Estoy buscando consejos sobre lo que es idiomático para los contenedores.

Una cosa que me preocupa, proveniente más recientemente de los lenguajes recolectados en la basura, es garantizar que los objetos aleatorios no solo vayan desapareciendo en los usuarios si cometen un error con respecto a la vida útil. Para tener en cuenta esto, tanto el contenedor PathList como sus iteradores mantienen un shared_ptr al objeto de estado interno real. Esto garantiza que mientras cualquier cosa que apunte a esos datos exista, también existirán los datos.

Sin embargo, al observar el STL (y lotes de búsqueda), no parece que los contenedores de C ++ lo garanticen. Tengo la horrible sospecha de que la expectativa es dejar que los contenedores se destruyan, invalidando cualquier iterador junto con él. std::vector ciertamente parece permitir que los iteradores se invaliden y sigan funcionando (incorrectamente).

Lo que quiero saber es: ¿qué se espera del código "bueno" / idiomatic C ++ 11? Dados los nuevos y brillantes indicadores inteligentes, parece un poco extraño que STL le permita volar sus piernas fácilmente al filtrar accidentalmente un iterador. ¿El uso de shared_ptr en los datos de respaldo es una ineficiencia innecesaria, una buena idea para la depuración o algo que se espera que STL simplemente no haga?

(Espero que al basar esto en "C ++ 11 idiomático" evite los cargos de subjetividad ...)

    
pregunta DK. 27.06.2012 - 10:48

4 respuestas

10
  

Está usando shared_ptr a los datos de respaldo una ineficiencia innecesaria

Sí: fuerza una indirección adicional y una asignación extra por elemento, y en los programas de subprocesos múltiples, cada incremento / decremento del recuento de referencia es incluso extra caro si un contenedor determinado se usa solo dentro de una sola hilo.

Todo esto puede estar bien, e incluso deseable, en algunas situaciones, pero la regla general es no imponer los gastos generales innecesarios que el usuario no puede evitar , incluso cuando son inútiles.

Dado que ninguno de estos gastos generales es necesario, sino más bien una depuración de las sutilezas (y recuerde, la duración incorrecta del iterador es un error de lógica estática, no un comportamiento de tiempo de ejecución extraño), nadie le agradecería que redujera su velocidad correcta código para detectar tus errores.

Entonces, a la pregunta original:

  

¿Debería un iterador en un contenedor personalizado sobrevivir al contenedor que está siendo destruido?

la pregunta real es si el costo de rastrear todos los iteradores en vivo en un contenedor y de invalidarlos cuando se destruye el contenedor, ¿se aplicará a las personas cuyo código es correcto?

Creo que probablemente no, aunque si hay algún caso en el que sea realmente difícil administrar el tiempo de vida del iterador correctamente y esté dispuesto a recibir el impacto, se puede agregar un contenedor dedicado (o adaptador de contenedor) que proporcione este servicio como una opción .

Alternativamente, el cambio a una implementación de depuración basada en un indicador de compilador puede ser razonable, pero es un cambio mucho más grande y más costoso que la mayoría que está controlada por DEBUG / NDEBUG. Sin duda, es un cambio mayor que eliminar las declaraciones de afirmación o usar un asignador de depuración.

Olvidé mencionar, pero tu solución de usar shared_ptr en todas partes no necesariamente soluciona tu error de todos modos: puede simplemente cambiarlo por un error diferente , es decir, una pérdida de memoria.

    
respondido por el Useless 27.06.2012 - 13:38
7

En C ++, si dejas que el contenedor se destruya, los iteradores se vuelven inválidos. Como mínimo, esto significa que el iterador es inútil, y si intentas desreferenciarlo, entonces pueden suceder muchas cosas malas (exactamente lo malo depende de la implementación, pero generalmente es bastante malo).

En un lenguaje como C ++, es responsabilidad del programador mantener esas cosas en orden. Esa es una de las fortalezas del lenguaje, ya que puede depender bastante de cuándo suceden las cosas (¿eliminó un objeto? Eso significa que en el momento de la eliminación, se llamará al destructor y se liberará la memoria, y usted puede depender). en eso), pero también significa que no puedes ir manteniendo iteradores en contenedores por todas partes y luego eliminar ese contenedor.

Ahora, ¿podrías escribir un contenedor que mantenga los datos hasta que todos los iteradores hayan desaparecido? Por supuesto, claramente tienes eso en marcha. Esa NO es la forma habitual de C ++, pero no tiene nada de malo, siempre y cuando esté debidamente documentada (y por supuesto, depurada). Simplemente no es cómo funcionan los contenedores STL.

    
respondido por el Michael Kohne 27.06.2012 - 13:35
5

Una de las diferencias (a menudo no dichas) entre los lenguajes C ++ y GC es que el lenguaje general de C ++ supone que todas las clases son clases de valor.

Hay punteros y referencias, pero en su mayoría están relegados al permitir el envío polimórfico (a través de la dirección virtual de la función) o el manejo de un objeto cuya vida útil debe sobrevivir a la del bloque que los creó.

En este último caso, es responsabilidad del programador definir la política y la política sobre quién crea y quién y cuándo debe destruir. Los punteros inteligentes (como shared_ptr o unique_ptr ) son solo herramientas para ayudar en esta tarea en los casos muy particulares (y frecuentes) que un objeto es "compartido" por diferentes propietarios (y desea que el último lo destruya) o debe moverse a través de contextos teniendo siempre un solo contexto que lo posee.

Los intérpretes, por su diseño, solo tienen sentido durante ... una iteración, y por lo tanto no deben "almacenarse para su uso posterior", ya que no se permite que permanezcan iguales o permanezcan allí (un contenedor). puede reubicar su contenido al crecer o reducirse ... invalidando todo). Los contenedores basados en enlaces (como list s) son una excepción a esta regla general, no la regla en sí misma.

En el C ++ idiomático si A "necesita" B, B debe ser propiedad de un lugar que viva más tiempo que el lugar que posee A, por lo tanto, no se requiere un "seguimiento de la vida" de B desde A.

shared_ptr y weak_ptr ayudan cuando este idioma es demasiado restrictivo, al permitir respectivamente las políticas de "no desaparecerás hasta que todos nos permitamos" o "si te vas, solo deja un mensaje para nosotros" . Pero tienen un costo, ya que, para hacer eso, tienen que asignar algunos datos auxiliares.

El siguiente paso son gc_ptr-s (que la biblioteca estándar no ofrece, pero que puede implementar si lo desea, usando, por ejemplo, los algoritmos de barrido de marca y amplificación) donde las estructuras de seguimiento serán aún más complejas y más procesador intensivo es su mantenimiento.

    
respondido por el Emilio Garavaglia 27.06.2012 - 16:29
4

En C ++ es idiomático hacer cualquier cosa que

  • se puede prevenir mediante una codificación cuidadosa y
  • incurriría en costos de tiempo de ejecución para protegerse contra

un comportamiento indefinido .

En el caso particular de los iteradores, la documentación de cada contenedor indica qué operaciones invalidan los iteradores (la destrucción del contenedor siempre está entre ellos) y el acceso a un iterador no válido es un comportamiento indefinido. En la práctica, significa que el tiempo de ejecución accederá ciegamente al puntero que ya no es válido. Por lo general, se bloquea, pero puede dañar la memoria y provocar un resultado completamente impredecible.

Proporcionar comprobaciones opcionales que se pueden activar en modo de depuración (con #define que por defecto está activado si _DEBUG está definido y deshabilitado si NDEBUG es) es una buena práctica.

Sin embargo, recuerde que C ++ está diseñado para manejar casos en los que se necesita todo el rendimiento y las comprobaciones pueden ser bastante costosas a veces, ya que los iteradores se usan a menudo en bucles reducidos, así que no los habilite de forma predeterminada.

En nuestro proyecto de trabajo tuve que deshabilitar la comprobación de iteradores en la biblioteca estándar de Microsoft incluso en el modo de depuración, porque algunos contenedores usan otros contenedores e iteradores internamente y solo destruir una enorme estaba demorando media hora debido a las comprobaciones.

    
respondido por el Jan Hudec 28.06.2012 - 08:53

Lea otras preguntas en las etiquetas