147

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?

skaffman
  • 398,947
  • 96
  • 818
  • 769
Rudiger
  • 1,473
  • 2
  • 10
  • 5

2 Answers2

130

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.

Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
  • 13
    I'd still like to see an example and the pros & cons, but this is a good introduction. – Rudiger Feb 15 '11 at 14:30
  • Rather than post code I will say that the STL is non intrusive, while Boost.Intrusive is intrusive(obviously). – stonemetal Feb 15 '11 at 16:05
  • 2
    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. – stonemetal Feb 15 '11 at 16:11
  • 4
    http://www.boost.org/doc/libs/1_45_0/doc/html/intrusive.html has examples and a good description of pros and cons. – Tony Delroy Feb 16 '11 at 06:37
  • 6
    Great explanation with examples: http://www.boost.org/doc/libs/1_55_0/doc/html/intrusive/intrusive_vs_nontrusive.html – Paweł Szczur Apr 24 '14 at 08:34
  • @LasseV.Karlsen link dead – Gohan Sep 22 '14 at 03:28
  • concise and easy to understand explanation – yogibear Jan 18 '18 at 22:44
26

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.

API-Beast
  • 723
  • 5
  • 10
  • 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. – Sled May 20 '14 at 12:55
  • @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. – API-Beast May 20 '14 at 14:24
  • 1
    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. – Sled May 20 '14 at 14:44
  • 2
    @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. – API-Beast May 21 '14 at 02:28