it-swarm-ru.tech

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

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

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

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

96
Rudiger

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

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

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

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

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

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

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

88
Lasse Vågsæther Karlsen

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

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

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;

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

18
API-Beast