Что означает, что структура данных будет "навязчивой"?

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

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

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;

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