C ++ Iterator de por vida y detección de invalidación

8

Según lo que se considera idiomático en C ++ 11:

  • ¿Debería un iterador en un contenedor personalizado sobrevivir al contenedor en sí mismo siendo destruido?
  • ¿Debería ser posible detectar cuando un iterador se invalida?
  • ¿están condicionados los anteriores a las "compilaciones de depuración" en la práctica?

Detalles : Recientemente he estado repasando mi C ++ y aprendiendo a usar C ++ 11. Como parte de eso, he estado escribiendo un contenedor idiomático alrededor de la biblioteca de uriparser . Parte de esto es envolver la representación de la lista vinculada de componentes de ruta analizados. 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 de basura, es asegurar que los objetos aleatorios no desaparezcan de los usuarios si cometen un error con respecto a las vidas. Para tener en cuenta esto, tanto el PathListcontenedor como sus iteradores mantienen un shared_ptrobjeto de estado interno real. Esto garantiza que, mientras exista algo que apunte a esos datos, también existirán los datos.

Sin embargo, al mirar el STL (y mucha búsqueda), no parece que los contenedores C ++ lo garanticen. Tengo esta horrible sospecha de que la expectativa es simplemente dejar que se destruyan los contenedores, invalidando cualquier iterador junto con él. std::vectorciertamente parece permitir que los iteradores se invaliden y aún funcionen (incorrectamente).

Lo que quiero saber es: ¿qué se espera del código "bueno" / idiomático de C ++ 11? Teniendo en cuenta los nuevos y brillantes punteros inteligentes, parece extraño que STL le permita volar fácilmente las piernas al perder accidentalmente un iterador. ¿Utilizar shared_ptrlos 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 conectar esto a "C ++ 11 idiomático" evite las cargas de subjetividad ...)

DK.
fuente

Respuestas:

10

Está utilizando shared_ptra los datos de respaldo una ineficiencia innecesaria

Sí, obliga a una indirección adicional y una asignación adicional por elemento, y en los programas multiproceso cada incremento / decremento del recuento de referencia es muy costoso incluso si un contenedor dado se usa solo dentro de un solo hilo.

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

Dado que ninguno de estos gastos generales es necesario, sino que son más bien depuraciones (y recuerde, la vida útil incorrecta del iterador es un error de lógica estática, no un comportamiento extraño en tiempo de ejecución), nadie le agradecería por ralentizar su código correcto para detectar sus errores.


Entonces, a la pregunta original:

¿Debería un iterador en un contenedor personalizado sobrevivir al contenedor en sí mismo siendo destruido?

La verdadera pregunta es si el costo de rastrear todos los iteradores en vivo en un contenedor e invalidarlos cuando se destruye el contenedor, ¿debe imponerse a las personas cuyo código es correcto?

Creo que probablemente no, aunque si hay algún caso en el que es realmente difícil administrar correctamente la vida útil de los iteradores y está dispuesto a recibir el golpe, se podría agregar como opción un contenedor dedicado (o adaptador de contenedor) que brinde este servicio .

Alternativamente, cambiar a una implementación de depuración basada en un indicador del compilador puede ser razonable, pero es un cambio mucho más grande y costoso que la mayoría de los controlados por DEBUG / NDEBUG. Ciertamente es un cambio más grande que eliminar las declaraciones de aserción o usar un asignador de depuración.


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

Inútil
fuente
"¿el costo de rastrear todos los iteradores en vivo en un contenedor e invalidarlos cuando se destruye el contenedor debe imponerse a las personas cuyo código es correcto?" diablos no en absoluto . Como indica su publicación, uno de los lemas de facto de C ++ es "no paga por lo que no usa". Esto es por una muy buena razón: paralizaría muchos proyectos bien programados si tuvieran que hacer verificaciones de sentido contra todas las cosas tontas que un mal programador podría hacer. Pero, por supuesto, como usted indicó, si alguien realmente quiere eso ... tiene las herramientas para implementarlo (y mantenerlo). ¡Lo mejor de ambos mundos!
underscore_d
7

En C ++, si deja que el contenedor se destruya, los iteradores se vuelven inválidos. Por lo menos, esto significa que el iterador es inútil, y si intenta desreferenciarlo, pueden suceder muchas cosas malas (exactamente qué tan malo depende de la implementación, pero generalmente es bastante malo).

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

Ahora, ¿podrías escribir un contenedor que guarde 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 que esté debidamente documentado (y, por supuesto, depurado). Simplemente no es cómo funcionan los contenedores STL.

Michael Kohne
fuente
1
Tenga en cuenta que puede ir mal de trasladar al centinela a un comportamiento indefinido
monstruo de trinquete
@ratchetfreak: sí, eso es cierto. En el caso en cuestión (iteradores en un contenedor), generalmente no hay una buena manera de definir el valor sentinal, por lo que la forma habitual de C ++ (y el comportamiento de la STL) tiende hacia un "comportamiento indefinido".
Michael Kohne
5

Una de las diferencias (a menudo no mencionadas) entre los lenguajes C ++ y GC es que el lenguaje principal 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 función virtual indirección) o la gestión de objetos 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_ptro unique_ptr) son solo herramientas para ayudar en esta tarea en los casos muy particulares (y frecuentes) de que un objeto es "compartido" por diferentes propietarios (y desea que el último lo destruya) o necesita moverse a través de contextos teniendo siempre un único contexto que lo posee.

Los interadores, por diseño, tienen sentido solo durante ... una iteración, y por lo tanto no deben "almacenarse para su uso posterior" ya que a lo que se refieren no se les garantiza que permanezcan igual o que permanezcan allí (un contenedor puede reubicarse contenido al crecer o reducirse ... invalidar todo). Los contenedores basados ​​en enlaces (como los lists) son una excepción a esta regla general, no la regla en sí misma.

En el idiomático C ++ 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 "seguimiento de vida" de B de A.

shared_ptry weak_ptrayuda donde este idioma es demasiado restrictivo, al permitir respectivamente las políticas de "no desaparezcas hasta que todos lo permitamos" o las políticas de "si te vas solo déjanos un mensaje". Pero tienen un costo, ya que, para hacerlo, tienen que asignar algunos datos auxiliares.

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

Emilio Garavaglia
fuente
4

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

  • puede prevenirse 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 dice qué operaciones invalidan a los iteradores (la destrucción del contenedor siempre está entre ellos) y el acceso al iterador no válido es 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 causar un resultado completamente impredecible.

Es una buena práctica proporcionar comprobaciones opcionales que se puedan activar en modo de depuración (con los #definevalores predeterminados activados si _DEBUGestá definido y desactivado si NDEBUGestá).

Sin embargo, recuerde que C ++ está diseñado para manejar casos en los que uno necesita cada bit de rendimiento y las comprobaciones pueden ser bastante costosas a veces, ya que los iteradores a menudo se usan en bucles cerrados, por lo que no los habilite de forma predeterminada.

En nuestro proyecto de trabajo, tuve que deshabilitar la verificación de iteradores en la biblioteca estándar de Microsoft incluso en modo de depuración, porque algunos contenedores usan otros contenedores e iteradores internamente y ¡destruir uno enorme me tomó media hora debido a las verificaciones!

Jan Hudec
fuente