Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What does it mean for a data structure to be "intrusive"?

People also ask

What is an intrusive data structure?

An intrusive container is a data structure that can be used to hold a collection of objects where the bookkeeping used to track membership in the container is stored in the objects themselves instead of holding the object alongside of the bookkeeping in a structure.

What is an intrusive container?

Intrusive, touching the definition of a type is sometimes a crucial issue. In intrusive containers you don't store a copy of an object, but rather the original object is linked with other objects in the container. Objects don't need copy-constructors or assignment operators to be stored in intrusive containers.

What is intrusive list?

An intrusive list is one where the pointer to the next list node is stored in the same structure as the node data. This is normally A Bad Thing, as it ties the data to the specific list implementation.


An intrusive data structure is one that requires help from the elements it intends to store in order to store them.

Let me reword that. When you put something into that data structure, that "something" becomes aware of the fact that it is in that data structure, in some way. Adding the element to the data structure changes the element.

For instance, you can build a non-intrusive binary tree, where each node have a reference to the left and right sub-trees, and a reference to the element value of that node.

Or, you can build an intrusive one where the references to those sub-trees are embedded into the value itself.

An example of an intrusive data structure would be an ordered list of elements that are mutable. If the element changes, the list needs to be reordered, so the list object has to intrude on the privacy of the elements in order to get their cooperation. ie. the element has to know about the list it is in, and inform it of changes.

ORM-systems usually revolve around intrusive data structures, to minimize iteration over large lists of objects. For instance, if you retrieve a list of all the employees in the database, then change the name of one of them, and want to save it back to the database, the intrusive list of employees would be told when the employee object changed because that object knows which list it is in.

A non-intrusive list would not be told, and would have to figure out what changed and how it changed by itself.


In a intrusive container the data itself is responsible for storing the necessary information for the container. That means that on the one side the data type needs to be specialized depending on how it will be stored, on the other side it means that the data "knows" how it is stored and thus can be optimized slightly better.

Non-intrusive:

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;

Intrusive:

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;

Personally I prefer intrusive design for it's transparency.