Что значит для структуры данных быть «навязчивой»? - PullRequest
Новая
       27

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

98 голосов
/ 15 февраля 2011

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

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

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

Ответы [ 2 ]

89 голосов
/ 15 февраля 2011

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

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

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

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

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

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

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

18 голосов
/ 25 февраля 2014

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

Ненавязчивый: 

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;

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

...