¿Qué significa que una estructura de datos sea "intrusiva"?

He visto el término intrusivo utilizado para describir estructuras de datos como listas y pilas, pero ¿qué significa?

¿Puede dar un ejemplo de código de una estructura de datos intrusiva y en qué se diferencia de una no intrusiva?

Además, ¿por qué hacerlo intrusivo (o no intrusivo)? ¿Cuales son los beneficios? ¿Cuales son las desventajas?

Una estructura de datos intrusiva es aquella que requiere la ayuda de los elementos que pretende almacenar para poder almacenarlos.

Déjame reformular eso. Cuando pones algo en esa estructura de datos, ese "algo" se da cuenta del hecho de que está en esa estructura de datos, de alguna manera. Agregar el elemento a la estructura de datos cambia el elemento.

Por ejemplo, puede construir un árbol binario no intrusivo, donde cada nodo tiene una referencia a los subárboles izquierdo y derecho, y una referencia al valor del elemento de ese nodo.

O puede crear uno intrusivo en el que las referencias a esos subárboles estén integradas en el valor mismo.

Un ejemplo de una estructura de datos intrusiva sería una lista ordenada de elementos que son mutables. Si el elemento cambia, la lista debe reordenarse, por lo que el objeto de la lista debe inmiscuirse en la privacidad de los elementos para obtener su cooperación. es decir. el elemento debe conocer la lista en la que se encuentra e informarle de los cambios.

Los sistemas ORM generalmente giran en torno a estructuras de datos intrusivas, para minimizar la iteración sobre grandes listas de objetos. Por ejemplo, si recupera una lista de todos los empleados en la base de datos, luego cambia el nombre de uno de ellos y desea guardarlo nuevamente en la base de datos, la lista intrusiva de empleados se le informará cuando el objeto empleado cambie porque eso El objeto sabe en qué lista se encuentra.

Una lista no intrusiva no se informaría y tendría que averiguar qué cambió y cómo cambió por sí mismo.

En un contenedor intrusivo, los propios datos se encargan de almacenar la información necesaria para el contenedor. Eso significa que, por un lado, el tipo de datos debe especializarse dependiendo de cómo se almacenarán, por otro lado, significa que los datos "saben" cómo se almacenan y, por lo tanto, se pueden optimizar un poco mejor.

No intrusivo:

template<typename T>
class LinkedList
{
  struct ListItem
  {
    T Value;
    ListItem* Prev;
    ListItem* Next;
  };

  ListItem* FirstItem;
  ListItem* LastItem;

  [...]
  ListItem* append(T&& val)
  {
    LastItem = LastItem.Next = new ListItem{val, LastItem, nullptr};
  };
};

LinkedList<int> IntList;

Intruso:

template<typename T>
class LinkedList
{
  T* FirstItem;
  T* LastItem;

  [...]
  T* append(T&& val)
  {
    T* newValue = new T(val);
    newValue.Next = nullptr;
    newValue.Prev = LastItem;
    LastItem.Next = newValue;
    LastItem = newValue;
  };
};

struct IntListItem
{
  int Value;
  IntListItem* Prev;
  IntListItem* Next;
};

LinkedList<IntListItem> IntList;

Personalmente prefiero el diseño intrusivo por su transparencia.