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

language-agnostic data-structures

Question

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

¿Puede dar un ejemplo de código de una estructura de datos intrusiva, y cómo difiere de una no intrusiva?

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

Answer 1

En un contenedor intrusivo, los datos son responsables de almacenar la información necesaria para el contenedor. Esto significa que, por un lado, el tipo de datos debe especializarse en función de cómo se almacenará, 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.

Answer 2

Una estructura de datos intrusiva es aquella que requiere ayuda de los elementos que intenta almacenar para 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 tenga una referencia a los subárboles izquierdo y derecho, y una referencia al valor del elemento de ese nodo.

O bien, puede crear uno intrusivo en el que las referencias a esos subárboles estén incorporadas 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, se le avisará a la lista intrusiva de empleados cuándo cambió el objeto empleado porque el objeto sabe en qué lista está.

Una lista no intrusiva no sería contada, y tendría que descubrir qué cambió y cómo cambió por sí misma.