Common data structures and algorithms in Rust


Contest Algorithms in Rust Version Documentation license Downloads Build Status Gitter

A collection of classic data structures and algorithms, emphasizing usability, beauty and clarity over full generality. As such, this should be viewed not as a blackbox library, but as a whitebox cookbook demonstrating the design and implementation of algorithms. I hope it will be useful to students and educators, as well as fans of algorithmic programming contests.

This repository is distributed under the MIT License. Contest submissions need not include the license text. Enjoy!

For Students and Educators

When learning a new algorithm or data structure, it's often helpful to see or play with a concrete implementation. As such, this repository catalogues several classic algorithms in their simplest forms.

In addition, the Rust language has outstanding pedagogical attributes. Its compiler acts as a teacher, enforcing strict discipline while pointing to clearer ways to structure one's logic.

For Programming Contests

The original intent of this project was to build a reference for use in programming contests. As a result, it contains algorithms that are frequently useful to have in one's toolkit, with an emphasis on code that is concise and easy to modify under time pressure.

Most competitive programmers rely on C++ for its fast execution time. However, it's notoriously unsafe, diverting a considerable share of the contestant's time and attention on mistake prevention and debugging. Java is the next most popular choice, offering a little safety at some expense to speed of coding and execution.

To my delight, I found that Rust eliminates entire classes of bugs, while reducing visual clutter to make the rest easier to spot. And, it's fast. There's a learning curve, to be sure. However, a proficient Rust programmer stands to gain a competitive advantage as well as a more pleasant experience!

Some contest sites and online judges that support Rust:

The following support pre-2018 versions of Rust:

For help in getting started, you may check out some of my past submissions.

Programming Language Advocacy

My other goal is to appeal to developers who feel limited by ancient (yet still mainstream) programming languages, by demonstrating the power of modern techniques.

Rather than try to persuade you with words, this repository aims to show by example. If you'd like to learn the language, I recommend the official book or Programming Rust.



Graph representations

  • Integer index-based adjacency list representation
  • Disjoint set union

Elementary graph algorithms

  • Euler path and tour
  • Kruskal's minimum spanning tree
  • Dijkstra's single-source shortest paths
  • DFS pre-order traversal

Connected components

  • Connected components
  • Strongly connected components
  • Bridges and 2-edge-connected components
  • Articulation points and 2-vertex-connected components
  • Topological sort
  • 2-SAT solver

Network flows

  • Dinic's blocking maximum flow
  • Minimum cut
  • Hopcroft-Karp bipartite matching
  • Minimum cost maximum flow


Number theory

  • Greatest common divisor
  • Canonical solution to Bezout's identity
  • Miller's primality test

Generic FFT

  • Fast Fourier transform
  • Number theoretic transform
  • Convolution


  • Rational numbers
  • Complex numbers
  • Linear algebra
  • Safe modular arithmetic

Ordering and search

  • Comparator for PartialOrd
  • Binary search: drop-in replacements for C++ lower_bound()/upper_bound()
  • Merge and mergesort
  • Coordinate compression
  • Online convex hull trick (update and query the upper envelope of a set of lines)

Associative range query

  • Statically allocated binary indexed ARQ tree (a.k.a. generic segtree with lazy propagation)
  • Dynamically allocated ARQ tree, optionally sparse and persistent
  • Mo's algorithm (a.k.a. query square root decomposition)


  • Utility for reading input data ergonomically
  • File and standard I/O examples

String processing

  • Generic trie
  • Knuth-Morris-Pratt single-pattern string matching
  • Aho-Corasick multi-pattern string matching
  • Suffix array: O(n log n) construction using counting sort
  • Longest common prefix
  • Manacher's linear-time palindrome search
  • Reading lots of integers

    Reading lots of integers

    Reading 2e5 integers from the file.

    Your solution with unsafe gives times:

    > cargo run
    > cargo run
    > cargo run

    Handmade parser over byte stream:

    > cargo run
    > cargo run
    > cargo run
    code with test case attached
    use std::fs;
    use std::io::{self, prelude::*};
    use std::time::Instant;
    use std::error::Error;
    struct Parser
    	it: std::vec::IntoIter<u8>,
    impl Parser
    	fn new(bytes: Vec<u8>) -> Parser {
    		Parser { it: bytes.into_iter() }
    impl Iterator for Parser {
    	type Item = i32;
    	fn next(&mut self) -> Option<Self::Item> {
    		let mut ans = 0;
    		let mut sign = 1;
    		let mut started = false;
    		while let Some(b) = {
    			if b >= b'0' && b <= b'9' {
    				started = true;
    				ans = (b - b'0') as i32 + ans * 10;
    			} else if b == b'-' {
    				sign = -1;
    			} else if started == true {
    		if started {		
    			Some(ans * sign)
    		} else {
    fn read() -> Result<(), Box<dyn Error>> {
    	let mut reader = io::BufReader::new(fs::File::open("stdin.txt")?);
    	let mut bytes: Vec<u8> = Vec::new();
    	reader.read_to_end(&mut bytes)?;
    	let mut parser = Parser::new(bytes);
    	let n ="N")? as usize;
    	let mut v: Vec<i32> = Vec::with_capacity(n);
    	let mut empty = 0;
    	for token in parser {
    		if token == -1 {
    			empty += 1;
    		} else {
    			let token = token - 1;
    fn main() {
    	let instant = Instant::now();
    	if let Err(error) = read() {
    		eprintln!("{:?}", error);
    	println!("{}", instant.elapsed().as_micros() as f64 / 1e6);


    .parse() is an evil. Handmade solution faster in comparison to C++ with -O2 using std::scanf and reading into an array.

    c++ code
    #include <iostream>
    #include <chrono>
    template<typename TimeT = std::chrono::microseconds>
    struct measure
        template<typename F, typename ...Args>
        static double execution(F&& func, Args&&... args)
            auto start = std::chrono::steady_clock::now();
            auto duration = std::chrono::duration_cast< TimeT> 
                                (std::chrono::steady_clock::now() - start);
            return double(duration.count()) / 1e6;
    void solve() {
    	std::freopen("stdin", "r", stdin);
    	std::freopen("stdout", "w", stdout);
    	int n, empty = 0;
    	std::scanf("%d", &n);
    	int v[size_t(2e5)]{-1};
    	for (size_t i = 0, p; i < n; ++i) {
    		std::scanf("%d", v + i);
    int main () {
    	std::cerr << measure<>::execution(solve) << std::endl;
    opened by koutoftimer 8
  • Add Z algorithm implementation and test

    Add Z algorithm implementation and test

    Hi there! I really love what you're doing with this repo. I'm also a competitive programmer (IGM on Codeforces and Rust enthusiast, so having a library like this would be super useful.


    This PR adds the Z algorithm to the library, which is a simple, linear-time alternative to KMP that is useful for some string problems. I ported this from my own C++ implementation.

    Let me know what you think. This is a pretty small change, but I am also interested in porting over some idiomatic splay tree, treap, or link-cut tree code to Rust, since I'm curious how difficult it would be to implement this with ownership. Also, I would like to use Rust as my main language in a future programming competition. :)

    opened by ekzhang 5
  • Online Docs

    Online Docs

    Is there any chance you could get travis to generate html documentation and upload it to GitHub pages after every commit? I usually find the html docs really useful for quickly navigating a project, then you have the "src" link to look at the implementation.

    I did something similar for my gcode-rs project.

    opened by Michael-F-Bryan 4
  • use i64::MAX instead of 0x3f3f3f3f3f3f3f3f

    use i64::MAX instead of 0x3f3f3f3f3f3f3f3f

    seems more rusty to use built-in constants

    it seems that 0x3f3f... is used in competitive programming because...

    1. it is around 2^62 so you can double it without overflowing i64. However it doesn't seem to matter here.
    2. it is easy to type and remember, especially in c++ where you have to include <numeric_limits> and use std::numeric_limits<int64_t>::max(). But in rust i64::MAX is easier to type.
    3. you can do memset(..., 0x3f, ...) tricks. But here we are initializing with vec![Self::INF; self.graph.num_v()] which should have compiler optimizations anyway.

    tests seem to pass...

    opened by dllu 3
  • Open to Open Source?

    Open to Open Source?

    Hey there! I'm a mathematics instructor trying to transition into being a software developer looking for a good first PR and I was wondering if you guys were open to open source contributions. By nature of my job algorithms are kinda my jam and although there are several algorithm repositories on Github, this one seems to be the most recently active one. I mentor both Rust and C on but Rust is the programming language I'm excited about and looking to work with so I figure open source will be a good start.

    opened by bcpeinhardt 3
  • Suggestion: adding primality check and prime factorisation

    Suggestion: adding primality check and prime factorisation

    I just discovered this project and I thought this collection could benefit from implementations of algorithms like Miller-Rabin and Pollard-Rho. Thoughts?

    If this does get the nod, I would love to implement this so I can practice my Rust skills.

    opened by JaroPaska 3
  • Add a DFS iterator to Graph

    Add a DFS iterator to Graph


    Are you taking pull requests? I wrote a dfs method that returns an iterator for your graph class. I'm new to rust so I can't say if its the absolute best. It is iterative and keeps the state in the iterator struct. And of course a couple tests.

    I also used a bit vector because why not :)

    Let me know if this can be of interest and I'll create a proper PR. Otherwise, feel free to close this. Regardless a great repo, thank you !

    use super::graph::Graph;
    use bit_vec::BitVec;
    impl Graph
        fn dfs(&self, v: usize) -> DfsIterator
            // Create a stack for DFS
            let mut stack: Vec<usize> = Vec::new();
            // Push the current source node.
            DfsIterator {
                graph: self,
                visited: BitVec::from_elem(self.num_v(), false),
    pub struct DfsIterator<'a>
        graph: &'a Graph,
        //is vertex visited
        visited: BitVec,
        //stack of vertices
        stack: Vec<usize>,
    impl<'a> Iterator for DfsIterator<'a>
        type Item = usize;
        /// Returns next vertex in the DFS
        fn next(&mut self) -> Option<Self::Item>
            let mut r = None;
            //Code translated/adapted from        
            while !self.stack.is_empty() {
                // Pop a vertex from stack and print it
                let s = self.stack.pop().unwrap();
                // Stack may contain same vertex twice. So
                // we need to print the popped item only
                // if it is not visited.
                if !self.visited[s] {
                    self.visited.set(s, true);
                    r = Some(s);
                // Get all adjacent vertices of the popped vertex s
                // If a adjacent has not been visited, then puah it
                // to the stack.
                for (_e, u) in self.graph.adj_list(s) {
                    if !self.visited[u] {
                if r != None {
                    return r;
            return None;
    mod test
        use super::*;
        fn test_dfs()
            let mut graph = Graph::new(4, 8);
            graph.add_edge(0, 2);
            graph.add_edge(2, 0);
            graph.add_edge(1, 2);
            graph.add_edge(0, 1);
            graph.add_edge(3, 3);
            graph.add_edge(2, 3);
            //start at 2;  -- 2 0 1 3
            let dfs_search = graph.dfs(2).collect::<Vec<_>>();
            assert_eq!(dfs_search, vec![2, 0, 1, 3]);
        fn test_dfs2()
            let mut graph = Graph::new(5, 8);
            graph.add_edge(0, 2);
            graph.add_edge(2, 1);
            graph.add_edge(1, 0);
            graph.add_edge(0, 3);
            graph.add_edge(3, 4);
            graph.add_edge(4, 0);
            let dfs_search = graph.dfs(0).collect::<Vec<_>>();
            assert_eq!(dfs_search, vec![0, 2, 1, 3, 4]);
            //0 3 4 2 1 or
            //0 2 1 3 4
    opened by eric7237cire 3
  • Random number generation

    Random number generation

    One problem I see with using Rust in programming competition websites is that we can't pull in external dependencies like rand. Is there interest in simply offering a very short and sweet random number generator?

    I was thinking about implementing a simple Treap for a dynamic BBST implementation (which is simple enough in Rust's ownership semantics), so maybe it makes sense to just embed a simple PRNG in the file. Options:

    • a linear congruential generator
    • Xorshift variant like the SmallRng used in rand:

    Do you have any opinions about RNGs here?

    opened by ekzhang 2
  • Use tags to make this project searchable on Github

    Use tags to make this project searchable on Github

    It would be cool is this project was properly tagged, to be searchable on Github (for example, using rust, algorithm, etc ...). Tags are located under the name of the project.

    opened by green-coder 2
  • Q: How to use this crate in programming contests?

    Q: How to use this crate in programming contests?

    For instance, how to submit my solution that uses this crate to a codeforces judge? They require your solution to be in one file. Is there any kind of pre-submission script that could handle dumping the entire crate in the solution file?

    opened by mariocynicys 1
Aram Ebtekar
Algorithmist, applied mathematician and mad scientist
Aram Ebtekar
Rust-algorithm-club - Learn algorithms and data structures with Rust

Rust Algorithm Club ?? ?? This repo is under construction. Most materials are written in Chinese. Check it out here if you are able to read Chinese. W

Weihang Lo 360 Dec 28, 2022
Algorithms and Data Structures of all kinds written in Rust.

Classic Algorithms in Rust This repo contains the implementation of various classic algorithms for educational purposes in Rust. Right now, it is in i

Alexander González 49 Dec 14, 2022
rust_aads - Rust Algorithms And Data Structures

rust_aads - Rust Algorithms And Data Structures rust_aads is an open repository with algorithms and data structures, used in computer science and comp

stepa 2 Dec 15, 2022
Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

null 6.5k Dec 31, 2022
Rust data structures and client for the PubChem REST API Rust data structures and client for the PubChem REST API. ?? Usage ?? Compound Create a Compound to query the PubChem API for a single comp

Martin Larralde 2 Jan 18, 2022
Obake is a procedural macro for declaring and maintaining versioned data-structures.

Obake is a procedural macro for declaring and maintaining versioned data-structures. The name 'obake' is taken from the Japanese 'お化け (おばけ)', a class of supernatural beings in Japanese folklore that shapeshift.

Nathan Corbyn 174 Dec 26, 2022
Fast, efficient, and robust memory reclamation for concurrent data structures

Seize Fast, efficient, and robust memory reclamation for concurrent data structures. Introduction Concurrent data structures are faced with the proble

Ibraheem Ahmed 240 Dec 23, 2022
Rust Persistent Data Structures

Rust Persistent Data Structures Rust Persistent Data Structures provides fully persistent data structures with structural sharing. Setup To use rpds a

Diogo Sousa 883 Dec 31, 2022
A proof of concept implementation of cyclic data structures in stable, safe, Rust.

A proof of concept implementation of cyclic data structures in stable, safe, Rust. This demonstrates the combined power of the static-rc crate and the

null 157 Dec 28, 2022
Rust library for string parsing of basic data structures.

afmt Simple rust library for parsing basic data structures from strings. Usage You can specify string formats to any strucute, via the use of the fmt

Eduard 4 May 8, 2021
Library containing various Data Structures implemented using Rust.

rust-data-structures Library containing various Data Structures implemented using Rust. Running You can test the library by running cargo test, an exa

c1m50c 1 Jan 6, 2022
A library for comparing data structures in Rust, oriented toward testing

Delta: Structural differencing in Rust The delta crate defines the trait Delta, along with a derive macro for auto-generating instances of this trait

John Wiegley 19 Oct 7, 2022
A library for comparing data structures in Rust, oriented toward testing

The comparable crate defines the trait [Comparable], along with a derive macro for auto-generating instances of this trait for most data types. Primar

John Wiegley 19 Oct 7, 2022
Collection of Data Structures in Rust

cds - Collection of Data Structures !!! UNDER CONSTRUCTION !!! The version v0.0.1 is a placeholder. License Licensed under either of Apache

Rafael Buchbinder 2 May 23, 2022
Succinct data structures in Rust

sucds: Succinct data structures in Rust sucds contains some succinct data structures written in Rust. Data structures So far, the following data struc

Shunsuke Kanda 43 Dec 3, 2022
Dade is data definition for Rust structures.

dade dade is data definition for Rust structures. For the easy handle of data, the following will support it. Data validation. Data schema conforms Js

odd 3 May 1, 2022
NixEl is a Rust library that turns Nix code into a variety of correct, typed, memory-safe data-structures

?? NixEL Lexer, Parser, Abstract Syntax Tree and Concrete Syntax Tree for the Nix Expressions Language. NixEl is a Rust library that turns Nix code in

Kevin Amado 56 Dec 29, 2022
This repository aims to organize codes related to data structures in Rust. 🦀

Rust Data Structure A project with the objective of introducing the main concepts about data structure using Rust! Explore the docs and learn Rust » R

guto 12 Apr 3, 2023
Garbage Collector(Hyaline- Safe Memory Reclaimation) for lock free data structures

Hyaline-SMR This crate provides garbage collection using hyaline algorithm for building concurrent data structures. When a thread removes an object fr

Abishek 2 Dec 21, 2022