intrusive_list

Header-only, composition-based, allocation-free double-linked list for C++11.

Getting started

Add list_node as a member to whatever struct you want to keep a list of. Then, you can insert references to that struct into a list.

#include <avakar/intrusive/list.h>
using namespace avakar::intrusive;

struct X {
    // A node maintains a membership in at most one list.
    list_node load_order;

    // If your object is kept in multiple lists, you need a node for each list.
    list_node memory_order;
};

int main()
{
    // Lists are ranges of references. You must specify the node to be used
    // by each list.
    list<X, &X::load_order> load_order_list;

    load_order_list.push_back(x);

    // You can check if a node is attached to a list.
    assert(x.load_order.attached());
    assert(!x.memory_order.attached());

    // You can enumerate elements the way you would any other range.
    for (X & elem: load_order_list) {
        // ...
    }

    list<X, &X::load_order> another_load_order_list;

    // Inserting to another list that uses the same node will detach that
    // node from any list it is currently attached in.
    another_load_order_list.push_back(x);
    assert(load_order_list.empty());

    // You can erase an element with `erase`, but if you have the associated
    // node available, you can use `detach` on the node.
    x.load_order.detach();
    assert(another_load_order_list.empty());
}

Nodes are movable and will carry the list membership with them. Node objects that were moved from will end up detached.

Clearing or destroying a list will detach all its nodes.

Thread-safety

There is none.

CMake integration

Copy this repo into yours, add it as a submodule, or FetchContent it. Either way, make sure this repo is added via add_subdirectory or FetchContent_MakeAvailable, then link against avakar::intrusive_list.