Что значит «навязчивая» структура данных?

Я видел термин навязчивый, используемый для описания структур данных, таких как списки и стеки, но что он означает?

Можете ли вы привести пример кода навязчивой структуры данных и чем она отличается от ненавязчивой?

Кроме того, зачем делать это навязчивым (или ненавязчивым)? Каковы преимущества? Какие недостатки?

Навязчивая структура данных - это такая структура, которая требует помощи от элементов, которые она намеревается хранить, чтобы сохранить их.

Позвольте мне перефразировать это. Когда вы помещаете что-то в эту структуру данных, это «что-то» каким-то образом узнает о том, что оно находится в этой структуре данных. Добавление элемента в структуру данных изменяет элемент.

Например, вы можете построить ненавязчивое двоичное дерево, в котором каждый узел имеет ссылку на левое и правое поддеревья и ссылку на значение элемента этого узла.

Или вы можете создать навязчивое дерево, в котором ссылки на эти поддеревья встроены в само значение.

Примером навязчивой структуры данных может быть упорядоченный список изменяемых элементов. Если элемент изменяется, список необходимо переупорядочить, поэтому объект списка должен нарушить конфиденциальность элементов, чтобы добиться их взаимодействия. то есть. элемент должен знать список, в котором он находится, и сообщать ему об изменениях.

ORM-системы обычно вращаются вокруг навязчивых структур данных, чтобы минимизировать итерацию по большим спискам объектов. Например, если вы получите список всех сотрудников в базе данных, затем измените имя одного из них и захотите сохранить его обратно в базу данных, навязчивый список сотрудников будет сообщен при изменении объекта сотрудника, потому что это объект знает, в каком списке он находится.

Ненавязчивый список не будет сообщен, и ему придется выяснить, что изменилось и как изменилось само по себе.

В интрузивном контейнере сами данные отвечают за хранение необходимой информации для контейнера. Это означает, что с одной стороны тип данных должен быть специализирован в зависимости от того, как он будет храниться, с другой стороны, это означает, что данные «знают», как они хранятся, и, таким образом, могут быть немного лучше оптимизированы.

Неинтрузивная:

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;

Интрузивный:

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;

Лично я предпочитаю навязчивый дизайн за его прозрачность.