IntrusiveDList is a class that provides a double linked list using pointers embeded in the object. IntrusiveDList also acts as a queue. No memory management is done - objects can be added to and removed from the list but the allocation and deallocation of the objects must be handled outside the class. This class supports an STL compliant bidirectional iteration.


template<typename L>
class IntrusiveDList

A double linked list / queue based on links inside the objects. The element type, T, is deduced from the return type of the link accessor methods in L.

Template Parameters:
 L – List item descriptor

The descriptor, L, is a type that provides the operations on list elements required by the container.

type value_type

The type of elements in the container, deduced from the return types of the link accessor methods in L.

static value_type *&next_ptr(value_type *elt)

Return a reference to the next element pointer embedded in the element elt.

static value_type *&prev_ptr(value_type *elt)

Return a reference to the previous element pointer embedded in the element elt.

value_type *head()

Return a pointer to the head element in the list. This may be nullptr if the list is empty.

value_type *tail()

Return a pointer to the tail element in the list. This may be nullptr if the list is empty.

IntrusiveDList &clear()

Remove all elements from the list. This only removes, no deallocation nor destruction is performed.

size_t count() const

Return the number of elements in the list.

IntrusiveDList &append(value_type *elt)

Append elt to the list.

IntrusiveDList &prepend(value_type *elt)

Prepend elt to the list.

value_type *take_head()

Remove the head element and return a pointer to it. May be nullptr if the list is empty.

value_type *take_tail()

Remove the tail element and return a pointer to it. May be nullptr if the list is empty.


An instance of IntrusiveDList acts as a container for items, maintaining a doubly linked list / queue of the objects and tracking the number of objects in the container. There are methods for appending, prepending, and inserting (both before and after a specific element already in the list). Some care must be taken because it is too expensive to check for an element already being in the list or in another list. The internal links are set to nullptr, therefore one simple check for being in a list is if either internal link is not nullptr. This requires initializing the internal links to nullptr.


In this example the goal is to have a list of Message objects. First the class is declared along with the internal linkage support.

class Message
  using self_type = Message; ///< Self reference type.

  // Message severity level.

  std::string _text; // Text of the message.
  Severity _severity{LVL_DEBUG};
  int _indent{0}; // indentation level for display.

  // Intrusive list support.
  struct Linkage {
    static self_type *&next_ptr(self_type *); // Link accessor.
    static self_type *&prev_ptr(self_type *); // Link accessor.

    self_type *_next{nullptr}; // Forward link.
    self_type *_prev{nullptr}; // Backward link.
  } _link;

  bool is_in_list() const;

  friend class Container;

The struct Linkage is used both to provide the descriptor to IntrusiveDList and to contain the link pointers. This isn’t necessary - the links could have been direct members and the implementation of the link accessor methods adjusted. Because the links are intended to be used only by a specific container class (Container) the struct is made protected.

The implementation of the link accessor methods.

Message::Linkage::next_ptr(self_type *that) -> self_type *&
  return that->_link._next;
Message::Linkage::prev_ptr(self_type *that) -> self_type *&
  return that->_link._prev;

A method to check if the message is in a list.

Message::is_in_list() const
  return _link._next || _link._prev;

The container class for the messages could be implemented as

class Container
  using self_type   = Container;
  using MessageList = IntrusiveDList<Message::Linkage>;


  template <typename... Args> self_type &debug(std::string_view fmt, Args &&... args);

  size_t count() const;
  self_type &clear();
  Message::Severity max_severity() const;
  void print() const;

  MessageList _msgs;

The debug method takes a format string (fmt) and an arbitrary set of arguments, formats the arguments in to the string, and adds the new message to the list.

template <typename... Args>
Container::debug(std::string_view fmt, Args &&... args) -> self_type &
  Message *msg = new Message;
  ts::bwprintv(msg->_text, fmt, std::forward_as_tuple(args...));
  msg->_severity = Message::LVL_DEBUG;
  return *this;

The print method demonstrates the use of the range for loop on a list.

Container::print() const
  for (auto &&elt : _msgs) {
    std::cout << static_cast<unsigned int>(elt._severity) << ": " << elt._text << std::endl;

The maximum severity level can also be computed even more easily using std::max_element. This find the element with the maximum severity and returns that severity, or LVL_DEBUG if no element is found (which happens if the list is empty).

Container::max_severity() const
  auto spot = std::max_element(_msgs.begin(), _msgs.end(),
                               [](Message const &lhs, Message const &rhs) { return lhs._severity < rhs._severity; });
  return spot == _msgs.end() ? Message::Severity::LVL_DEBUG : spot->_severity;

Other methods for the various severity levels would be implemented in a similar fashion. Because the intrusive list does not do memory management, the container must clean that up itself, as in the clear method. A bit of care must be exercised because the links are in the elements, and these links are used for iteration therefore using an iterator that references a deleted object is risky. One approach, illustrated here, is to use IntrusiveDList::take_head() to remove the element before destroying it. Another option is to allocation the elements in a MemArena to avoid the need for any explicit cleanup.

Container::clear() -> self_type &
  Message *msg;
  while (nullptr != (msg = _msgs.take_head())) {
    delete msg;
  return *this;

Design Notes

The historic goal of this class is to replace the DLL list support. The benefits of this are

  • Remove dependency on the C preprocessor.
  • Provide greater flexibility in the internal link members. Because of the use of the descriptor and its static methods, the links can be anywhere in the object, including in nested structures or super classes. The links are declared like normal members and do not require specific macros.
  • Provide STL compliant iteration. This makes the class easier to use in general and particularly in the case of range for loops.
  • Track the number of items in the list.
  • Provide queue support, which is of such low marginal expense there is, IMHO, no point in providing a separate class for it.