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

Question

I've seen the term intrusive used to describe data structures like lists and stacks, but what does it mean?

Can you give a code example of an intrusive data structure, and how it differs from a non-intrusive one?

Also, why make it intrusive (or, non-intrusive)? What are the benefits? What are the disadvantages?

Solution 1

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.

Solution 2

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.

Comments

[Rudiger]

I'd still like to see an example and the pros & cons, but this is a good introduction.

[stonemetal]

Rather than post code I will say that the STL is non intrusive, while Boost.Intrusive is intrusive(obviously).

[stonemetal]

Intrusive Pros: No need to copy your data into an internal structure it can be used as is. Cons: You must break encapsulation on your data to support the containers your data is going to be stored in. It can get tricky if your data needs to be in multiple containers. Non intrusive containers Pros: Better encapsulation no need to modify data for your containers. Cons: Requires a copy of your data to internal node structure.

[Tony Delroy]

boost.org/doc/libs/1_45_0/doc/html/intrusive.html has examples and a good description of pros and cons.

[Paweł Szczur]

Great explanation with examples: boost.org/doc/libs/1_55_0/doc/html/intrusive/…

[Sled]

That final line is curious on account of the usage of the word "transparent" since being in an intrusive container is not transparent to the object.

[API-Beast]

@ArtB It is clearer at conveying how the data is used exactly in the final application, in the case of non-intrusive data you usually have to dig into the containers while for intrusive data you see it from the structure of the data alone.

[Sled]

Well I suppose any usage "transparent" of transparent ought to be qualified as to from which perspective. In my experience "transparent" is often used to indicate that how the data is being handled is invisible to the domain (ie that the domain modelling is pure). If the term is being used both ways, I wonder if there is any value to it.

[API-Beast]

@ArtB Oh! There is some special Computer Science meaning for transparent! Transparent means for me that you can see the internals, e.g. "not obstructing the view", like the term is used in any non-cs context.

[Gohan]

@LasseV.Karlsen link dead

[yogibear]

concise and easy to understand explanation