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
.