Index-Oriented Programming in Rust


id_collections: Index-Oriented Programming in Rust



It is common in Rust to define custom wrapper types (sometimes called "newtypes") around integer types, in order to better communicate the intended meaning of those types, and to catch mistakes arising from mixing up integer values with different meanings. For example, one might define two different types representing "user ids" and "group ids":

struct UserId(u32);
struct GroupId(u32);

The id_collections crate provides data structures designed to work with these kinds of strongly-typed wrappers around integer types:

  • The IdVec<I, T> type is a vector which uses a custom index type I instead of usize.
  • The IdMap<I, T> type is a map backed by a vector. It's similar to IdVec<I, T>, except that its set of keys is not required to occupy a contiguous range, so you can fill in its entries out of order.
  • The Count<I> type provides a type-safe way to represent the size of a range of custom ids.

To use the structures in this library with your application's id types, your id types need to implement the Id trait. The easiest way to implement the Id trait is to use the #[id_type] attribute macro:

use id_collections::id_type;

struct UserId(u32);

struct GroupId(u32);

After you've implemented Id, you can use your custom id type as the index type for an IdVec:

use id_collections::IdVec;

let mut users: IdVec<UserId, &str> = IdVec::new();
let alice_id: UserId = users.push("Alice");
let bob_id: UserId = users.push("Bob");

assert_eq!(users[alice_id], "Alice");
assert_eq!(users[bob_id], "Bob");

Using IdVec prevents you from accidentally mixing up different id types:

let group = GroupId(1);
let name = users[group]; // error: expected 'UserId', found 'GroupId'!

If you need a collection which supports discontiguous keys, you can use IdMap:

use id_collections::IdMap;

let mut users: IdMap<UserId, &str> = IdMap::new();
users.insert(UserId(5), "Alice");
users.insert(UserId(10), "Bob");
assert_eq!(users[UserId(5)], "Alice");
assert_eq!(users[UserId(10)], "Bob");

Example: Calculating Directory Sizes

One of the main motivating use cases for the id_collections crate is to implement graph algorithms. The following example shows how IdVec, IdMap, and Count can be used together to implement a simple depth-first graph traversal which computes the size of each directory in an in-memory representation of a filesystem:

use id_collections::{id_type, IdMap, IdVec};

struct FileId(usize);

struct DirectoryId(usize);

struct DirectoryContents {
    files: Vec<FileId>,
    subdirectories: Vec<DirectoryId>,

/// Calculate the size of each directory in `directories`.
/// `directories` may contain file and directory "hard links" (i.e., a file or directory may
/// be pointed to by multiple parent directories), but for simplicity we assume that the
/// filesystem may not contain cycles (i.e., a directory is not allowed to directly or
/// indirectly contain itself).
fn calculate_sizes(
    file_sizes: &IdVec<FileId, u64>,
    directories: &IdVec<DirectoryId, DirectoryContents>,
) -> IdVec<DirectoryId, u64> {
    fn calculate_size_rec(
        file_sizes: &IdVec<FileId, u64>,
        directories: &IdVec<DirectoryId, DirectoryContents>,
        directory_sizes: &mut IdMap<DirectoryId, u64>,
        directory: DirectoryId,
    ) -> u64 {
        if let Some(&cached_size) = directory_sizes.get(directory) {
            return cached_size;

        let mut size = 0;
        for file in &directories[directory].files {
            size += file_sizes[file];
        for &subdirectory in &directories[directory].subdirectories {
            size +=
                calculate_size_rec(file_sizes, directories, directory_sizes, subdirectory);
        directory_sizes.insert_vacant(directory, size);

    let mut directory_sizes = IdMap::with_capacity(directories.len());
    for directory in directories.count() {
        calculate_size_rec(file_sizes, directories, &mut directory_sizes, directory);

You might also like...
A short exercise to introduce people to the Rust programming language

Searching primes by brute force This code is ment to be an exercice to teach rust and give a first impression on how to work with the language during

A repository for showcasing my knowledge of the Rust programming language, and continuing to learn the language.

Learning Rust I started learning the Rust programming language before using GitHub, but increased its usage afterwards. I have found it to be a fast a

The Rust Programming Language, Chapter 8, Exercise 1

Rust Common Collections - Exercise 1 In the book The Rust Programming Language by Steve Klabnik and Carol Nichols, chapter 8 - Common Collections - pr

Functional Reactive Programming library for Rust

Carboxyl is a library for functional reactive programming in Rust, a functional and composable approach to handle events in interactive applications.

Rust Programming Fundamentals - one course to rule them all, one course to find them...

Ultimate Rust Crash Course This is the companion repository for the Ultimate Rust Crash Course published online, presented live at O'Reilly virtual ev

The Ribbon Programming Language, made in Rust.

The Ribbon Programming Language (WIP) This language is designed to be quick to write and is heavily inspired by Rust, which is also the language it wa

A simple programming language for something between C and Rust.

inuc inuc is a systems programming language that is something between C and Rust. Features : [] Strong , static typing (type inference not a priority

🇵🇪 Rust programming, in Spanish.
🇵🇪 Rust programming, in Spanish.

rustico Doing it for the fun. Aren't you cansado from writting Rust Programs in English? Do you like saying "chales" a lot? Would you like to try some

Learn programming with Rust as a first language (book)

Learn programming with Rust as first language This is a book to learn programming from scratch. Read the book here: LI

William Brandon
Programming language theory and compilers research. UC Berkeley Computer Science and Math, Fall '20.
William Brandon
This repository serves as the backend for the Torrust Index project.


Torrust 6 Dec 15, 2022
The Devils' Programming Language (Quantum Programming Language)

devilslang has roots in Scheme and ML-flavored languages: it's the culmination of everything I expect from a programming language, including the desire to keep everything as minimalistic and concise as possible. At its core, devilslang is lambda-calculus with pattern-matching, structural types, fiber-based concurrency, and syntactic extension.

Devils' Language 2 Aug 26, 2022
clone of grep cli written in Rust. From Chapter 12 of the Rust Programming Language book

minigrep is a clone of the grep cli in rust Minigrep will find a query string in a file. To test it out, clone the project and run cargo run body poem

Raunak Singh 1 Dec 14, 2021
The Rust Compiler Collection is a collection of compilers for various languages, written with The Rust Programming Language.

rcc The Rust Compiler Collection is a collection of compilers for various languages, written with The Rust Programming Language. Compilers Language Co

null 2 Jan 17, 2022
Game Boy Emulator written in Rust, as a way to fully grasp the Rust programming language

Flan's Game Boy Emulator Game Boy Emulator written in Rust, as a way to get hands-on with the Rust programming language, and creating a proper project

Flan 3 Dec 31, 2022
A minimal version of 'grep' implemented in Rust. Exercise in the "The Rust Programming Language" book.

Minigrep - A simple grep-like tool implemented in Rust This simple CLI tool searches for a given pattern in a specified file and as a result, it print

Filip Szutkowski 3 Mar 15, 2024
Nixt is an interpreted programming language written in Rust

Nixt Nixt is an interpreted lisp inspired programming language written in Rust Index About Examples Installation Build About Nixt goal is to provide a

Wafelack 17 Jul 18, 2022
a function programming language for real world applications made in rust

a function programming language for real world applications made in rust

Tanay Pingalkar 6 Jun 12, 2022
Rust implementation of µKanren, a featherweight relational programming language.

µKanren-rs This is a Rust implementation of µKanren, a featherweight relational programming language. See the original Scheme implementation here for

Eric Zhang 99 Dec 8, 2022
This repository contains the source of "The Rust Programming Language" book.

The Rust Programming Language This repository contains the source of "The Rust Programming Language" book. The book is available in dead-tree form fro

The Rust Programming Language 11.2k Jan 8, 2023