c++ - purposes - Listas intrusivas

hashtags (4)

No he podido encontrar demasiada información sobre ellos en línea. ¿Qué son y cuándo se usan típicamente?

Gracias.

Aquí hay una breve descripción que también es válida para listas:

I. Contenedores intrusivos.

El objeto a almacenar contiene información adicional para permitir la integración en el contenedor. Ejemplo:
struct Node { Node* next; // additional Node* prev; // information T data; }
1. Pros:
almacena los objetos mismos.

No implica la gestión de la memoria.

La iteración es más rápida.
Mejores garantías de excepción.
La previsibilidad en la inserción y eliminación de objetos. (no se requiere administración de memoria adicional (no predecible).)
Mejor localidad de memoria.
2. Contras:
contiene datos adicionales para la integración de contenedores. (cada tipo de tienda debe adaptarse (modificarse) a los requisitos del contenedor.)
precaución con los posibles efectos secundarios al cambiar el contenido del objeto almacenado (especialmente para contenedores asociativos).
Gestión de por vida del objeto insertado, independientemente del contenedor.
un posible objeto puede eliminarse antes de borrarse del contenedor, lo que lleva a la invalidación del iterador.
Los contenedores intrusivos NO se pueden copiar ni son asignables.

II. Contenedores no instructivos (contenedores estándar C ++)

El objeto no "sabe" y contiene detalles sobre el contenedor en el que se almacenará. Ejemplo:
struct Node { T data; }
1. Pros:
No contiene información adicional sobre la integración del contenedor.
Vida útil del objeto gestionado por el contenedor. (menos complejo.)
2. Contras:
almacenar copias de valores pasados por el usuario. (construcción in situ posible)
Un objeto solo puede pertenecer a un contenedor. (o el contenido debe almacenar punteros a objetos).
sobrecarga en el almacenamiento de copias. (contabilidad en cada asignación)
~~los objetos no copiables o no movibles NO PUEDEN almacenarse en contenedores no intrusivos.~~
no puede almacenar objetos derivados y aún mantener su tipo original. (rebanar - pierde polimorfismo.)

De hecho, me gusta el modelo intrusivo

Es mejor en la memoria (no muchas asignaciones pequeñas para que las cosas apunten a otras cosas)
Te permite tener un objeto que existe en varios contenedores
Te permite encontrar un elemento con un modo de búsqueda (hash) pero luego encontrar el siguiente elemento en orden lexográfico ( no es lo mismo que el # 2, pero también puede ser completado el multi_index_container de boost , pero ten en cuenta que multi_index_container tiene ciertos defectos que no son problemas con la intrusión)

Intrusivo es bueno
Solo necesita saber lo que está haciendo (lo que es cierto para cualquier contenedor)

Las listas de intrusivos son listas donde los objetos son cabezas o celdas de listas. Son cosas buenas o malas dependiendo del contexto.

Dentro de algún módulo definido (grupo de clases no seguras que trabajan juntas) puede ser el MEJOR medio para vincular las relaciones entre las clases. Permiten la administración directa y completa sin costo de relaciones comunes como la unicidad (por ejemplo, las manzanas no aparecen dos veces en appletrees, y esto no necesita ninguna clave para esto, y las manzanas no pertenecen a dos árboles distintos), son navegables en ambas direcciones (acceso directo al appletree dado una manzana y a las manzanas dado un appletree). Todas las operaciones básicas son O (1) (sin búsqueda en algún contenedor externo).

La lista intrusiva es MUY MALA entre dos módulos. Debido a que estarán vinculados, y la justificación de los módulos es la gestión de la independencia del código.

Una lista intrusiva es aquella en la que el puntero al siguiente nodo de la lista se almacena en la misma estructura que los datos del nodo. Esto es normalmente algo malo, ya que vincula los datos a la implementación de la lista específica. La mayoría de las bibliotecas de clases (por ejemplo, la Biblioteca estándar de C ++) utilizan listas no intrusivas, donde los datos no saben nada sobre la implementación de la lista (u otro contenedor).