intrusive-collections keeps your objects in the tree instead of the tree in your objects

The node lives in your type, not in a box the collection owns

intrusive-collections is a Rust library for creating intrusive collections, currently supporting singly-linked and doubly-linked lists as well as red-black trees.

The word intrusive is the whole idea, and the README states the consequence plainly: intrusive collections don't require any dynamic memory allocation since they simply keep track of existing objects rather than allocating new ones.

In a normal collection, you hand the collection a value and it allocates a node, wraps the value and links the node. In an intrusive collection, the links are fields inside your own type, and the collection is a set of pointers to those fields. A list of jobs is not a list of boxed job handles, it is a list that walks your job struct's next pointer.

Two things follow from that. The allocation cost per element disappears, which matters when you have a large number of small elements, and the elements can live wherever you put them, including on the stack, in an arena, or in a fixed buffer. The price is that your types carry fields they would not otherwise have, which is a layout decision you have to make up front.

The crate is on crates.io as intrusive-collections, the author is Amanieu d'Antras, the licence is MIT OR Apache-2.0, and the documentation lives on docs.rs.

No unsafe code in your code, which is the part that matters most

The feature list has five entries, and the one that decides whether you use the crate is the third: you can safely manipulate intrusive collections without any unsafe code.

That is a real constraint on the design, not a claim about the internals. An intrusive list has to mutate a node's links while it is linked into the list, and a naive implementation would need raw pointers to do that. This library does it in a way where the caller never writes unsafe, which means the invariants it maintains are checked by the library rather than by your code review.

The consequence for an adopter is concrete. If you are working on a project with a strict unsafe policy, or you simply do not want to reason about pointer validity, this crate removes an entire class of work from your crate. The unsafe is still there, inside the library, but it is in one place and the API does not ask you to uphold anything.

The other four features are supporting cast. Compatibility with #[no_std] means the collections can be used without the standard library, which is what you want in embedded work. A single object can be a member of multiple intrusive collections simultaneously, so the same node can sit in a work queue and in a priority index at the same time. And the collections provide a Cursor-based interface, which allows safe mutation while iterating, the problem that makes naive linked list iteration in Rust so awkward that the borrow checker normally forbids it.

The Cursor is the ergonomic centre of the crate. Being able to remove the current element, or mutate it, while walking the collection is what turns an intrusive list from a structure you are afraid of into one you can use.

The features list is short, and the nightly one does nothing yet

The crate ships two Cargo features, and the README describes both precisely.

The alloc feature is enabled by default, and it implements IntrusivePointer for Box, Rc and Arc. That is the feature that lets the collections own their elements, in the sense that a Box, an Rc or an Arc can be used as the backing store for the links. Without it, the collections are non-owning, and you are responsible for the lifetime of what the links point at.

The nightly feature is described as reserved for future nightly-only features, and the README says it currently has no effect.

That is worth pausing on, because a feature flag that does nothing is usually a signal about what is coming. It means the author has a plan that needs a nightly compiler, and the flag is already in the manifest so that dependants can opt in when the time comes. It also means that today, enabling nightly changes nothing except the dependency graph.

The version in the manifest is 0.10.3, the edition is 2018 and the minimum Rust version is 1.82, which is a useful thing to know if you support older toolchains. The package keywords are intrusive, no_std, list and rbtree, and the categories are data-structures and no-std, so the crate is discoverable by people looking for exactly this kind of structure.

The dependency list is short, which for a data structure crate is a good sign. The dev dependencies are rand, rand_xorshift and typed-arena, and the last one is a hint about how the test suite checks its work, since an arena is the natural way to give many nodes stable addresses for a test.

Adding it to a Cargo project, and where the real documentation is

The Usage section of the README is short. You add the dependency to your Cargo.toml.

[dependencies]
intrusive-collections = "0.10"

After that, the README points you at the documentation rather than walking through an example, with two links: the docs.rs page for the published crate and the generated API documentation for the master branch.

That is a real difference in documentation style from most Rust crates, and it has consequences for how you evaluate the project. There is no worked example in the README, no listing of the type names, and no explanation of how to get from your own struct to a list membership. The reference is the documentation, and the documentation is generated from the source with rustdoc.

The repository does carry a DESIGN.md at the top level, and that is the file to read before you write code. For a crate whose API is mostly self explanatory once you know the model, a design document plus generated reference is a coherent documentation strategy. It is also the kind of strategy that makes the first hour with the crate slower, so budget for it.

The examples the README does point to are in the documentation itself, and the crate is on crates.io at version 0.10, so the version you depend on and the version you read about are the same thing.

Why a linked list beats a Vec in some places, and when it does not

It is worth being concrete about the trade, because intrusive collections are the kind of thing people reach for out of habit and then regret.

The case for an intrusive list is removal cost and pointer stability. Removing an element from a Vec is a shift of everything after it, and removing from a linked list is a pointer write. And in an intrusive list the element does not move, because the list holds a pointer to it, so any other reference to that element stays valid. For a job queue where entries are added and removed constantly, and where something else also holds a reference to the job, that combination is worth real money.

The case against is simpler. A Vec is one allocation and contiguous memory, which is better for iteration, better for cache behaviour, and simpler. If you only append and then iterate, an intrusive list gives you nothing.

The red-black tree is the case where the trade is strongest, because the standard library has no linked, order-preserving structure; BTreeMap covers ordered maps, but not lists. If you need ordering by key, this crate is filling a gap that the standard library leaves.

There is a third option worth naming, which is an index map or a slab plus a vector, where the slab owns the nodes and gives you stable indices that act as handles. That is the same design goal reached differently, and for many workloads it is simpler than embedding link fields in your types. The difference is that a slab puts the links in one place, while an intrusive collection puts them in your type.

Where intrusive collections are the wrong choice

Three cases, and they are common enough to state plainly.

The first is a general purpose list or map. The standard library covers Vec, VecDeque, HashMap, BTreeMap and HashSet, and all of them are simpler, better documented and faster for the workloads they are good at. Reaching for an intrusive structure when you have no measured allocation problem is paying for a layout decision you do not need.

The second is when your node types cannot carry the link fields. The intrusive model requires your type to contain the intrusive pointers, which means those fields are part of your public type, they affect its size and its layout, and they are visible to everything that constructs your type. If your type is a public API, that is a real cost, and it is not reversible once published. A slab avoids it by keeping the links in a separate structure and handing out indices.

The third is the non-owning case, and it is a sharp edge rather than a prohibition. Without the alloc feature there is no IntrusivePointer for Box, Rc or Arc, so the collections are non-owning and the lifetime of the pointed-to data is your problem. That is a legitimate configuration for a kernel or a game engine with its own arena, and a source of use-after-free bugs in an application, where the compiler will not catch it because the safe API is doing the pointing.

One more practical note. The README does not describe thread safety guarantees, so if you need a collection shared across threads, check the documentation for what Send and Sync the types implement before you assume the safe API is also the concurrent API.

Editorial conclusion

Adopt intrusive-collections if you are building a graph, a job scheduler or a low level structure in Rust and need per node links without a heap allocation per element, particularly in a no_std context. Do not adopt it if you want a general purpose list or map, since the standard library covers that and the intrusive model asks you to embed link fields in your own types. Before you commit, read DESIGN.md in the repository, and decide how your node types will carry the intrusive links, because that layout decision is the part you cannot undo later.

Frequently asked questions

Official sources

1. Amanieu/intrusive-rs on GitHub
2. Issues
3. License: Apache-2.0
4. README