O que significa uma estrutura de dados ser “intrusiva”?

Já vi o termo intrusivo ser usado para descrever estruturas de dados como listas e pilhas, mas o que isso significa?

Você pode dar um exemplo de código de uma estrutura de dados intrusiva e como ela difere de uma não intrusiva?

Além disso, por que torná-lo intrusivo (ou não intrusivo)? Quais são os benefícios? Quais são as desvantagens?

Uma estrutura de dados intrusiva é aquela que requer ajuda dos elementos que pretende armazenar para armazená-los.

Deixe-me reformular isso. Quando você coloca algo nessa estrutura de dados, esse "algo" se torna ciente do fato de que está nessa estrutura de dados, de alguma forma. Adicionar o elemento à estrutura de dados altera o elemento.

Por exemplo, você pode construir uma árvore binária não intrusiva, em que cada nó tem uma referência às subárvores esquerda e direita e uma referência ao valor do elemento desse nó.

Ou você pode construir um intrusivo em que as referências a essas subárvores sejam incorporadas ao próprio valor.

Um exemplo de uma estrutura de dados intrusiva seria uma lista ordenada de elementos mutáveis. Se o elemento for alterado, a lista precisará ser reordenada, de modo que o objeto de lista terá que se intrometer na privacidade dos elementos para obter sua cooperação. ie. o elemento deve saber sobre a lista em que está e informá-lo sobre as mudanças.

Os sistemas ORM geralmente giram em torno de estruturas de dados intrusivas, para minimizar a iteração em grandes listas de objetos. Por exemplo, se você recuperar uma lista de todos os funcionários no banco de dados, alterar o nome de um deles e salvá-la de volta no banco de dados, a lista intrusiva de funcionários será informada quando o objeto funcionário for alterado porque objeto sabe em qual lista está.

Uma lista não intrusiva não seria contada e teria que descobrir o que mudou e como mudou por si só.

Em um contêiner intrusivo, os próprios dados são responsáveis ​​por armazenar as informações necessárias para o contêiner. Isso significa que, por um lado, o tipo de dados precisa ser especializado dependendo de como será armazenado, por outro lado, significa que os dados "sabem" como estão armazenados e, portanto, podem ser otimizados um pouco melhor.

Não 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;

Intrusivo:

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;

Pessoalmente, prefiro um design intrusivo pela sua transparência.