Intrusive Containers

Overview

An intrusive container is a data structure used to hold a collection of objects in which membership bookkeeping is stored in the objects themselves rather than a separate structure. For example, consider the following struct:

struct Point {
  float x, y;
}

A non-intrusive implementation of a doubly linked list would look as follows:

struct ListNode {
  struct Point val;
  struct ListNode *next, *prev;
}

An intrusive implementation would instead modify Point like so:

struct Point {
  float x, y;
  struct Point *next, *prev;
}