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;
}

Bibliography

• Fuchsia. “Introduction to Fbl Intrusive Containers.” Accessed May 12, 2024. https://fuchsia.dev/fuchsia-src/development/languages/c-cpp/fbl_containers_guide/introduction.