Co to znaczy, że struktura danych jest „inwazyjna”?

Widziałem termin inwazyjny używany do opisywania struktur danych, takich jak listy i stosy, ale co to oznacza?

Czy możesz podać przykład kodu przedstawiający uciążliwą strukturę danych i czym różni się ona od nieinwazyjnej?

Poza tym, po co robić to natrętne (lub nieinwazyjne)? Jakie są korzyści? Jakie są wady?

Inwazyjna struktura danych to taka, która wymaga pomocy elementów, które zamierza przechowywać w celu ich przechowywania.

Pozwólcie, że to przeredaguję. Kiedy umieszczasz coś w tej strukturze danych, to „coś” staje się świadome faktu, że w jakiś sposób znajduje się w tej strukturze danych. Dodanie elementu do struktury danych powoduje zmianę elementu.

Na przykład można zbudować nieinwazyjne drzewo binarne, w którym każdy węzeł ma odniesienie do lewego i prawego drzewa podrzędnego oraz odniesienie do wartości elementu tego węzła.

Lub możesz zbudować natrętne, w którym odniesienia do tych drzew podrzędnych są osadzone w samej wartości.

Przykładem inwazyjnej struktury danych może być uporządkowana lista elementów, które można modyfikować. Jeśli element się zmieni, lista musi zostać zmieniona, więc obiekt listy musi naruszyć prywatność elementów, aby uzyskać ich współpracę. to znaczy. element musi wiedzieć o liście, na której się znajduje, i informować go o zmianach.

Systemy ORM zwykle obracają się wokół inwazyjnych struktur danych, aby zminimalizować iterację dużych list obiektów. Na przykład, jeśli pobierzesz listę wszystkich pracowników w bazie danych, a następnie zmienisz nazwisko jednego z nich i zechcesz zapisać go z powrotem w bazie danych, natrętna lista pracowników zostanie poinformowana o zmianie obiektu pracownika, ponieważ obiekt wie, na której liście się znajduje.

Lista nieinwazyjna nie byłaby podawana i musiałaby samodzielnie dowiedzieć się, co się zmieniło i jak się zmieniło.

W inwazyjnym kontenerze same dane są odpowiedzialne za przechowywanie niezbędnych informacji o kontenerze. Oznacza to, że z jednej strony typ danych musi być wyspecjalizowany w zależności od tego, jak będą przechowywane, z drugiej strony oznacza to, że dane „wiedzą”, w jaki sposób są przechowywane i dzięki temu mogą być nieco lepiej zoptymalizowane.

Nieinwazyjny:

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;

Natrętny:

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;

Osobiście wolę natrętny projekt ze względu na jego przejrzystość.