# orium/rpds: Persistent Data Structures for Rust

> rpds is a Rust crate for fully persistent collections that retain previous versions through structural sharing. It fits code that needs branching histories, snapshots, or rollback-like state models, while mutable methods avoid persistence overhead when old versions are unnecessary.

**orium/rpds** — Rust persistent data structures

- Repository: https://github.com/orium/rpds
- Stars: 1,787 · Forks: 77
- Language: Rust
- License: MIT
- Published: 2026-10-16 · Updated: 2026-10-16 · Language: en
- Canonical page: https://hysenlabs.com/projects/orium-rpds

## What rpds Changes About Collection Updates

rpds addresses a specific problem in Rust applications that need to keep more than one version of a collection. A conventional mutable `Vec`, map, or set changes in place, so preserving an earlier state usually requires cloning data or building a separate application-level history. A persistent collection treats updates as operations that return a new version. The previous version remains available, and unchanged parts of the collection can be shared between versions through structural sharing.

That model is useful for editors with undo histories, state machines that explore several branches, compilers and interpreters that retain intermediate environments, and configuration systems that compare old and new states. It is also relevant when different parts of a program need different but related snapshots at the same time. The README describes the crate as providing fully persistent data structures with structural sharing, so its central benefit is version retention rather than merely a different collection syntax.

The crate is aimed at Rust developers who need collection semantics compatible with persistent state. It is not a general-purpose database, a serialization framework, or a replacement for every standard Rust collection. The README does not claim automatic persistence across process restarts, and the crate does not describe a storage format for saving versions to disk.

## The rpds Collection Set

rpds exposes eight collection types in the README: `List`, `Vector`, `Stack`, `Queue`, `HashTrieMap`, `HashTrieSet`, `RedBlackTreeMap`, and `RedBlackTreeSet`. Each collection supports the persistent update style described above. The collection families differ mainly in their ordering, indexing, hashing, or tree behavior, so choosing one is a choice about the shape and lookup semantics needed by the application.

`List` is a functional list. `Vector` is an indexable sequence, and the README links its implementation to a two-part explanation of persistent vectors. `Stack` provides last-in, first-out behavior and is described as a `List` in disguise. `Queue` provides first-in, first-out behavior. These choices cover common sequence workflows while preserving earlier collection values.

The two map families make a more direct contrast. `HashTrieMap` uses a hash array mapped trie, while `RedBlackTreeMap` uses a red-black tree. `HashTrieSet` is implemented with `HashTrieMap`, and `RedBlackTreeSet` is implemented with `RedBlackTreeMap`. The README therefore gives both hash-oriented and tree-oriented persistent collection options, but it does not document detailed complexity guarantees or compare their performance in this project. Based on the implementation names, a project that requires ordered map or set operations has a different choice from one that primarily needs hash-based membership or key lookup.

## Creating and Updating a Persistent List

The simplest first use is to add `rpds` as a Cargo dependency. The README shows a version placeholder rather than a fixed release, so the exact value must be chosen by the application. After adding the dependency, a collection can be created with `new`, updated by returning a new value, and queried through methods such as `first`, `get`, `contains`, or indexing.

This example follows the README's `List` example. The original `list` remains available after `push_front`, while `a_list` becomes the newer version. The final `drop_first` demonstrates that operations can also remove an element while preserving the earlier relationship described by the example.

```rust
use rpds::List;

let list = List::new().push_front("list");
assert_eq!(list.first(), Some(&"list"));

let a_list = list.push_front("a");
assert_eq!(a_list.first(), Some(&"a"));

let list_dropped = a_list.drop_first().unwrap();
assert_eq!(list_dropped, list);
```

The important detail is that the update calls are not written through `mut`. The variables refer to distinct persistent versions, and the original value is not discarded by the update. Applications that need several related states should store those returned values, rather than expecting a persistent collection to mutate its existing binding automatically.

## Hash Trie Maps and Ordered Red-Black Trees

The README presents `HashTrieMap` and `RedBlackTreeMap` as separate ways to build a persistent map. In the hash trie example, updating the map with `insert` produces a new map while the original map remains usable. Removing a key returns another map that no longer contains that key. The same pattern applies to `HashTrieSet`, which is implemented with `HashTrieMap`.

```rust
use rpds::HashTrieMap;

let map_en = HashTrieMap::new()
    .insert(0, "zero")
    .insert(1, "one");
assert_eq!(map_en.get(&1), Some(&"one"));

let map_pt = map_en
    .insert(1, "um")
    .insert(2, "dois");
assert_eq!(map_pt.get(&2), Some(&"dois"));

let map_pt_binary = map_pt.remove(&2);
assert_eq!(map_pt_binary.get(&2), None);
```

`RedBlackTreeMap` follows the same persistent interface but uses a red-black tree. Its README example also exposes ordering through `first`, which is not shown in the hash trie example. That is the practical distinction stated by the repository: choose the hash trie family for hash-based map behavior, or choose the red-black tree family when the tree representation and ordering are relevant. The README does not provide enough information to promise that one family will be faster for a particular workload, so selection should be based on required semantics and measurements in the adopting project.

## Adding rpds and Choosing Mutable Updates

rpds also offers mutable methods for cases where previous versions are not needed. The README says these methods are generally faster, so the crate does not force persistent overhead onto every update path. A mutable set can be built with `insert_mut`, cloned when a snapshot is needed, and then used with the persistent `insert` method to create another version.

The Cargo configuration shown in the README uses the package name `rpds` and a version placeholder. The repository's `Cargo.toml` identifies the package version as `1.2.2-pre`, while the release information lists published versions through `v1.2.1`. For an application, the version should be selected through the project's normal Cargo dependency policy rather than copied from unreleased package metadata.

```toml
[dependencies]
rpds = "<version>"
```

The crate's `Cargo.toml` declares Rust edition `2024` and `rust-version` `1.85.0`. Its default feature is `std`; the optional `rayon` feature enables parallelism support, and `serde` is also optional. The README does not provide a complete feature tutorial. Check those feature declarations before depending on serialization or parallel processing.

## Persistence Costs, Alternatives, and Licensing

The main limitation is that persistence carries a cost when the application does not need it. Each persistent update may create new nodes or otherwise allocate additional structure, even though unchanged data is shared. The README acknowledges this tradeoff by presenting mutable methods as generally faster. A single current mutable collection is a better fit when no code will inspect an older version.

Another limitation is documentation depth. The README gives examples for each collection, but it does not specify detailed complexity tables, memory retention behavior, serialization instructions, rollback procedures, or workload-specific performance results. The repository contains `benches/`, but the README does not explain those benchmarks or provide results. Consult `release-notes.md`, `CONTRIBUTING.md`, and the CI configuration directly when upgrade or contribution decisions matter.

A standard mutable collection is the relevant alternative when updates happen in place and historical versions are discarded. Its approach is simpler because it does not retain multiple reachable versions or share unchanged nodes between persistent states. rpds is the appropriate alternative when a program must read both an old and a new version after an update.

The crate is not archived, and the last push was on 2026-10-03. Recent release information includes `v1.2.1` dated 2026-05-15, `v1.2.0` dated 2025-11-10, and `v1.1.2` dated 2025-10-06. The project is released under the `MIT` license. That license permits use and modification under its stated terms, but an adopter should read `LICENSE.md` for the applicable conditions and notices.

## Conclusion

Adopt rpds when Rust code must retain multiple versions of collections or branch state without copying every unchanged node. Do not choose it for ordinary local collections where old versions are never read or where mutable `Vec`, maps, and sets are sufficient. Check the `Cargo.toml` dependency first, confirm that the required collection API fits your state model, and decide whether persistence or mutable methods better match each update path.

## FAQ

### What problem does orium/rpds solve in Rust?

It provides fully persistent data structures with structural sharing, allowing an update to return a new version while the previous version remains available. The README lists lists, vectors, stacks, queues, maps, and sets as the available types.

### How do I add orium/rpds to a Rust project?

Add `rpds` to the `[dependencies]` section of `Cargo.toml` using a version appropriate for the application. The README uses `<version>` as a placeholder, while the repository metadata currently declares `1.2.2-pre`.

### When should I use mutable methods in orium/rpds?

Use mutable methods when previous versions are unnecessary. The README says they are generally faster, and its example uses `insert_mut` before cloning a value and creating a persistent version with `insert`.

## Sources

- [Issues](https://github.com/orium/rpds/issues)
- [License: MIT](https://github.com/orium/rpds/blob/main/LICENSE)
- [orium/rpds on GitHub](https://github.com/orium/rpds)
- [README](https://github.com/orium/rpds/blob/main/README.md)
- [Releases](https://github.com/orium/rpds/releases)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/orium-rpds