Skip to content
Learn Rust
Theme

Collections: Maps, Sets, Queues and Heaps

Standard library · 2 of 5

std::collections has what lies beyond Vec: a hash map, a sorted map, sets, a double-ended queue, a priority queue and a linked list. All of them ship with the standard library, and the docs say Vec and HashMap are the right starting point.

Coming from GoGo gives you a map and a slice, and container/heap for a priority queue. Rust adds BTreeMap (keys kept sorted), HashSet, VecDeque (a queue) and BinaryHeap, which pops the largest first, so wrap items in Reverse for smallest first.

Coming from KotlinBTreeMap is sortedMapOf (a java.util.TreeMap on the JVM), VecDeque is Kotlin's own ArrayDeque, and HashSet is hashSetOf, not setOf, which remembers insertion order. The catch is BinaryHeap, which pops the largest first where java.util.PriorityQueue pops the smallest, so wrap items in Reverse.

Coming from PythonHashSet is set, VecDeque is deque, and BinaryHeap replaces heapq, but it pops the largest first, so wrap items in Reverse. BTreeMap keeps keys sorted, which no Python built-in does.

Coming from TypeScriptHashMap and HashSet are like Map and Set, but a Rust HashMap does not remember insertion order. VecDeque is a queue you can add to and remove from at both ends, and BinaryHeap and BTreeMap have no built-in JavaScript equivalent.

Coming from JavaHashMap, BTreeMap, HashSet, VecDeque and BinaryHeap map to HashMap, TreeMap, HashSet, ArrayDeque and PriorityQueue. Watch the heap: PriorityQueue gives the smallest first, BinaryHeap gives the largest, so wrap items in Reverse to flip it.

Coming from C#Dictionary, SortedDictionary, HashSet, Queue<T> and PriorityQueue are close to HashMap, BTreeMap, HashSet, VecDeque and BinaryHeap. Queue<T> only adds at the back, where VecDeque adds at both ends. BinaryHeap pops the largest first, the opposite of C#'s PriorityQueue. And map[key] += 1 doesn't compile on a Rust map: use entry(key).or_insert(0).

Coming from CThe C standard library has qsort and bsearch but no map, set, deque or heap, so you'd use sorted arrays and hand-rolled lookups. Rust ships a hash map, a sorted map, sets, a deque and a heap, all generic and freeing their own memory.

Coming from C++HashMap, BTreeMap, HashSet, VecDeque and BinaryHeap correspond to unordered_map, map, unordered_set, deque and priority_queue, and priority_queue is a max-heap too. counts[w] += 1 doesn't compile, because Rust's [] never inserts; use entry(w).or_insert(0).

The quick comparison

Rustsrc/main.rsRun ↗
use std::cmp::Reverse;
use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet, VecDeque};


fn main() {
    let text = "the cat saw the dog and the cat ran";


    // HashMap: count words. Iteration order is unspecified, so sort before printing.
    let mut counts: HashMap<&str, u32> = HashMap::new();
    for w in text.split_whitespace() {
        *counts.entry(w).or_insert(0) += 1;
    }
    let mut pairs: Vec<(&str, u32)> = counts.into_iter().collect();
    pairs.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(b.0)));
    println!("top: {:?}", &pairs[..3]);


    // BTreeMap: keys always come out sorted
    let mut by_name = BTreeMap::new();
    by_name.insert("zoe", 31);
    by_name.insert("ana", 30);
    by_name.insert("mia", 28);
    println!("sorted: {by_name:?}");


    // HashSet: unique items, fast "is it in there?"
    let seen: HashSet<&str> = text.split_whitespace().collect();
    println!(
        "{} unique words, has dog: {}",
        seen.len(),
        seen.contains("dog")
    );


    // VecDeque: a queue. Push at the back, pop at the front, both cheap.
    let mut queue = VecDeque::from(["a", "b"]);
    queue.push_back("c");
    let first = queue.pop_front();
    println!("served {first:?}, waiting {queue:?}");


    // BinaryHeap pops the largest first. Wrap in Reverse to get the smallest.
    let mut heap = BinaryHeap::new();
    for n in [5, 1, 8, 3] {
        heap.push(Reverse(n));
    }
    print!("smallest first:");
    while let Some(Reverse(n)) = heap.pop() {
        print!(" {n}");
    }
    println!();
}
$ cargo run
top: [("the", 3), ("cat", 2), ("and", 1)]
sorted: {"ana": 30, "mia": 28, "zoe": 31}
6 unique words, has dog: true
served Some("a"), waiting ["b", "c"]
smallest first: 1 3 5 8
package main


import (
  "container/heap"
  "fmt"
  "maps"
  "slices"
  "sort"
  "strings"
)


// container/heap needs you to write these five methods
type IntHeap []int


func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
  old := *h
  x := old[len(old)-1]
  *h = old[:len(old)-1]
  return x
}


func main() {
  text := "the cat saw the dog and the cat ran"


  counts := map[string]int{}
  for _, w := range strings.Fields(text) {
    counts[w]++
  }
  type pair struct {
    word string
    n    int
  }
  var pairs []pair
  for w, n := range counts {
    pairs = append(pairs, pair{w, n})
  }
  sort.Slice(pairs, func(i, j int) bool {
    if pairs[i].n != pairs[j].n {
      return pairs[i].n > pairs[j].n
    }
    return pairs[i].word < pairs[j].word
  })
  fmt.Println("top:", pairs[:3])


  // no sorted map: sort the keys yourself
  byName := map[string]int{"zoe": 31, "ana": 30, "mia": 28}
  fmt.Print("sorted:")
  for _, k := range slices.Sorted(maps.Keys(byName)) {
    fmt.Print(" ", k, "=", byName[k])
  }
  fmt.Println()


  // a set is a map to empty structs
  seen := map[string]struct{}{}
  for _, w := range strings.Fields(text) {
    seen[w] = struct{}{}
  }
  _, hasDog := seen["dog"]
  fmt.Println(len(seen), "unique words, has dog:", hasDog)


  queue := []string{"a", "b"}
  queue = append(queue, "c")
  first := queue[0]
  queue = queue[1:]
  fmt.Println("served", first, "waiting", queue)


  h := &IntHeap{}
  for _, n := range []int{5, 1, 8, 3} {
    heap.Push(h, n)
  }
  fmt.Print("smallest first:")
  for h.Len() > 0 {
    fmt.Print(" ", heap.Pop(h))
  }
  fmt.Println()
}
$ go run main.go
top: [{the 3} {cat 2} {and 1}]
sorted: ana=30 mia=28 zoe=31
6 unique words, has dog: true
served a waiting [b c]
smallest first: 1 3 5 8
import java.util.PriorityQueue


fun main() {
    val text = "the cat saw the dog and the cat ran"


    val counts = text.split(" ").groupingBy { it }.eachCount()
    val top = counts.entries
        .sortedWith(compareBy({ -it.value }, { it.key }))
        .take(3)
        .map { it.key to it.value }
    println("top: $top")


    val byName = sortedMapOf("zoe" to 31, "ana" to 30, "mia" to 28)
    println("sorted: $byName")


    val seen = text.split(" ").toSet()
    println("${seen.size} unique words, has dog: ${"dog" in seen}")


    val queue = ArrayDeque(listOf("a", "b"))
    queue.addLast("c")
    val first = queue.removeFirst()
    println("served $first, waiting $queue")


    val heap = PriorityQueue(listOf(5, 1, 8, 3))
    print("smallest first:")
    while (heap.isNotEmpty()) print(" ${heap.poll()}")
    println()
}
$ kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar
top: [(the, 3), (cat, 2), (and, 1)]
sorted: {ana=30, mia=28, zoe=31}
6 unique words, has dog: true
served a, waiting [b, c]
smallest first: 1 3 5 8
import heapq
from collections import Counter, deque


text = "the cat saw the dog and the cat ran"


# Counter: count words, then sort by count and then by word
counts = Counter(text.split())
top = sorted(counts.items(), key=lambda p: (-p[1], p[0]))[:3]
print(f"top: {top}")


# no sorted dict in std: dicts keep insertion order, so sort the items
by_name = {"zoe": 31, "ana": 30, "mia": 28}
print(f"sorted: {dict(sorted(by_name.items()))}")


# set: unique items, fast "is it in there?"
seen = set(text.split())
print(f"{len(seen)} unique words, has dog: {'dog' in seen}")


# deque: a queue. Append at the back, pop at the front, both cheap.
queue = deque(["a", "b"])
queue.append("c")
first = queue.popleft()
print(f"served {first!r}, waiting {list(queue)}")


# heapq turns a plain list into a heap that pops the smallest first
heap: list[int] = []
for n in [5, 1, 8, 3]:
    heapq.heappush(heap, n)
print("smallest first:", end="")
while heap:
    print(f" {heapq.heappop(heap)}", end="")
print()
$ python3 main.py
top: [('the', 3), ('cat', 2), ('and', 1)]
sorted: {'ana': 30, 'mia': 28, 'zoe': 31}
6 unique words, has dog: True
served 'a', waiting ['b', 'c']
smallest first: 1 3 5 8
const text = "the cat saw the dog and the cat ran";


// Map: count words. It keeps insertion order, so sort for a ranking.
const counts = new Map<string, number>();
for (const w of text.split(" ")) {
  counts.set(w, (counts.get(w) ?? 0) + 1);
}
const pairs = [...counts].sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]));
console.log("top:", pairs.slice(0, 3));


// no sorted map in std: sort the entries yourself
const byName = new Map([["zoe", 31], ["ana", 30], ["mia", 28]]);
console.log("sorted:", new Map([...byName].sort((a, b) => a[0].localeCompare(b[0]))));


// Set: unique items, fast "is it in there?"
const seen = new Set(text.split(" "));
console.log(`${seen.size} unique words, has dog: ${seen.has("dog")}`);


// an array as a queue: shift() takes from the front, but it moves every item
const queue = ["a", "b"];
queue.push("c");
const first = queue.shift();
console.log(`served ${first}, waiting`, queue);


// no priority queue in std: sort a copy (with a number compare, not the default string one)
const heap = [5, 1, 8, 3].sort((a, b) => a - b);
console.log(`smallest first: ${heap.join(" ")}`);
$ tsc --strict --module nodenext --types node main.ts && node main.js
top: [ [ 'the', 3 ], [ 'cat', 2 ], [ 'and', 1 ] ]
sorted: Map(3) { 'ana' => 30, 'mia' => 28, 'zoe' => 31 }
6 unique words, has dog: true
served a, waiting [ 'b', 'c' ]
smallest first: 1 3 5 8
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeMap;


public class Main {
    public static void main(String[] args) {
        String text = "the cat saw the dog and the cat ran";


        // HashMap: count words. Iteration order isn't fixed, so sort before printing.
        Map<String, Integer> counts = new HashMap<>();
        for (String w : text.split(" ")) {
            counts.merge(w, 1, Integer::sum);
        }
        var top = counts.entrySet().stream()
                .sorted(Map.Entry.<String, Integer>comparingByValue().reversed()
                        .thenComparing(Map.Entry.comparingByKey()))
                .limit(3)
                .toList();
        System.out.println("top: " + top);


        // TreeMap: keys always come out sorted
        Map<String, Integer> byName = new TreeMap<>(Map.of("zoe", 31, "ana", 30, "mia", 28));
        System.out.println("sorted: " + byName);


        // HashSet: unique items, fast "is it in there?"
        Set<String> seen = new HashSet<>(List.of(text.split(" ")));
        System.out.println(seen.size() + " unique words, has dog: " + seen.contains("dog"));


        // ArrayDeque: a queue. Add at the back, take from the front.
        ArrayDeque<String> queue = new ArrayDeque<>(List.of("a", "b"));
        queue.addLast("c");
        String first = queue.pollFirst();
        System.out.println("served " + first + ", waiting " + queue);


        // PriorityQueue gives the smallest first
        PriorityQueue<Integer> heap = new PriorityQueue<>(List.of(5, 1, 8, 3));
        System.out.print("smallest first:");
        while (!heap.isEmpty()) {
            System.out.print(" " + heap.poll());
        }
        System.out.println();
    }
}
$ javac Main.java && java Main
top: [the=3, cat=2, and=1]
sorted: {ana=30, mia=28, zoe=31}
6 unique words, has dog: true
served a, waiting [b, c]
smallest first: 1 3 5 8
var text = "the cat saw the dog and the cat ran";


// Dictionary: count words. Iteration order isn't promised, so sort before printing.
var counts = new Dictionary<string, int>();
foreach (var w in text.Split(' '))
{
    counts[w] = counts.GetValueOrDefault(w) + 1;
}
var top = counts
    .OrderByDescending(p => p.Value)
    .ThenBy(p => p.Key, StringComparer.Ordinal)
    .Take(3);
Console.WriteLine($"top: {string.Join(", ", top)}");


// SortedDictionary: keys always come out sorted
var byName = new SortedDictionary<string, int>(StringComparer.Ordinal)
{
    ["zoe"] = 31,
    ["ana"] = 30,
    ["mia"] = 28,
};
Console.WriteLine($"sorted: {string.Join(", ", byName)}");


// HashSet: unique items, fast "is it in there?"
var seen = new HashSet<string>(text.Split(' '));
Console.WriteLine($"{seen.Count} unique words, has dog: {seen.Contains("dog")}");


// Queue: add at the back, take from the front
var queue = new Queue<string>(["a", "b"]);
queue.Enqueue("c");
var first = queue.Dequeue();
Console.WriteLine($"served {first}, waiting [{string.Join(", ", queue)}]");


// PriorityQueue gives the smallest priority first
var heap = new PriorityQueue<int, int>();
foreach (var n in new[] { 5, 1, 8, 3 })
{
    heap.Enqueue(n, n);
}
Console.Write("smallest first:");
while (heap.TryDequeue(out var n, out _))
{
    Console.Write($" {n}");
}
Console.WriteLine();
$ dotnet run
top: [the, 3], [cat, 2], [and, 1]
sorted: [ana, 30], [mia, 28], [zoe, 31]
6 unique words, has dog: True
served a, waiting [b, c]
smallest first: 1 3 5 8
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// C's std has no map, set, queue or heap: arrays plus qsort do the job here
struct Count {
    char word[16];
    int n;
};


int by_count(const void *a, const void *b) {
    const struct Count *x = a, *y = b;
    if (x->n != y->n) return y->n - x->n;
    return strcmp(x->word, y->word);
}


int by_word(const void *a, const void *b) {
    return strcmp(((const struct Count *)a)->word, ((const struct Count *)b)->word);
}


int by_int(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}


int main(void) {
    char text[] = "the cat saw the dog and the cat ran";


    // count words with a linear search (strtok writes into text, so it's an array)
    struct Count counts[16];
    int len = 0;
    for (char *w = strtok(text, " "); w; w = strtok(NULL, " ")) {
        int i = 0;
        while (i < len && strcmp(counts[i].word, w) != 0) i++;
        if (i == len) {
            snprintf(counts[len].word, sizeof counts[len].word, "%s", w);
            counts[len++].n = 0;
        }
        counts[i].n++;
    }
    qsort(counts, (size_t)len, sizeof counts[0], by_count);
    printf("top: %s=%d %s=%d %s=%d\n", counts[0].word, counts[0].n,
           counts[1].word, counts[1].n, counts[2].word, counts[2].n);


    // a "sorted map": sort the array by key
    struct Count by_name[] = {{"zoe", 31}, {"ana", 30}, {"mia", 28}};
    qsort(by_name, 3, sizeof by_name[0], by_word);
    printf("sorted: %s=%d %s=%d %s=%d\n", by_name[0].word, by_name[0].n,
           by_name[1].word, by_name[1].n, by_name[2].word, by_name[2].n);


    // the counts array already holds each word once, so it doubles as a set
    int has_dog = 0;
    for (int i = 0; i < len; i++) has_dog |= strcmp(counts[i].word, "dog") == 0;
    printf("%d unique words, has dog: %s\n", len, has_dog ? "true" : "false");


    // a queue: an array with a read index and a write index
    const char *queue[8] = {"a", "b"};
    int head = 0, tail = 2;
    queue[tail++] = "c";
    const char *first = queue[head++];
    printf("served %s, waiting %s %s\n", first, queue[head], queue[head + 1]);


    // no heap: sort once and read from the front
    int nums[] = {5, 1, 8, 3};
    qsort(nums, 4, sizeof nums[0], by_int);
    printf("smallest first:");
    for (int i = 0; i < 4; i++) printf(" %d", nums[i]);
    printf("\n");
    return 0;
}
$ gcc -Wall -Wextra main.c -o main && ./main
top: the=3 cat=2 and=1
sorted: ana=30 mia=28 zoe=31
6 unique words, has dog: true
served a, waiting b c
smallest first: 1 3 5 8
#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <ranges>
#include <string_view>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>


int main() {
    std::string_view text = "the cat saw the dog and the cat ran";
    auto words = text | std::views::split(' ')
               | std::views::transform([](auto w) { return std::string_view(w.begin(), w.end()); });


    // unordered_map: count words. Iteration order is unspecified, so sort before printing.
    std::unordered_map<std::string_view, int> counts;
    for (auto w : words) counts[w] += 1; // [] inserts 0 for a new word
    std::vector<std::pair<std::string_view, int>> pairs(counts.begin(), counts.end());
    std::ranges::sort(pairs, [](const auto &a, const auto &b) {
        return a.second != b.second ? a.second > b.second : a.first < b.first;
    });
    std::cout << "top:";
    for (auto &[w, n] : pairs | std::views::take(3)) std::cout << " " << w << "=" << n;
    std::cout << "\n";


    // std::map: keys always come out sorted
    std::map<std::string_view, int> by_name{{"zoe", 31}, {"ana", 30}, {"mia", 28}};
    std::cout << "sorted:";
    for (auto &[name, age] : by_name) std::cout << " " << name << "=" << age;
    std::cout << "\n";


    // unordered_set: unique items, fast "is it in there?"
    std::unordered_set<std::string_view> seen(words.begin(), words.end());
    std::cout << seen.size() << " unique words, has dog: " << std::boolalpha << seen.contains("dog") << "\n";


    // deque: push at the back, pop at the front
    std::deque<std::string_view> queue{"a", "b"};
    queue.push_back("c");
    auto first = queue.front();
    queue.pop_front();
    std::cout << "served " << first << ", waiting " << queue[0] << " " << queue[1] << "\n";


    // priority_queue pops the largest first. std::greater flips it to the smallest.
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
    for (int n : {5, 1, 8, 3}) heap.push(n);
    std::cout << "smallest first:";
    while (!heap.empty()) {
        std::cout << " " << heap.top();
        heap.pop();
    }
    std::cout << "\n";
}
$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main
top: the=3 cat=2 and=1
sorted: ana=30 mia=28 zoe=31
6 unique words, has dog: true
served a, waiting b c
smallest first: 1 3 5 8

What's different

  • Which one? Vec for a list, HashMap/HashSet for lookups, BTreeMap/BTreeSet when you need keys in order or ranges like map.range(10..20), VecDeque for a queue, BinaryHeap for "give me the biggest next".
  • The std docs call a HashMap's order "arbitrary", and the default hasher (the code that turns a key into a number) is randomly seeded, so the order can differ between runs. If the output has to be stable, sort it or use a BTreeMap.
  • text.split_whitespace().collect() builds a HashSet because of the type you wrote on the left: collect() can build any collection, and the annotation picks which. The set holds &str views into text, so no word is copied. That works because text lives longer than seen, and the compiler checks that for you.
  • VecDeque is a ring buffer. The docs give adding or removing at either end a cost of O(1) (amortized for adding: averaged over the occasional resize). Removing the first item of a Vec is O(n): every other item shifts down.
  • Reverse(n) is a tiny wrapper that flips the comparison, so the max-heap hands out the smallest n first. The heap itself is unchanged.
Gotcha

Bumping a counter with map[key] += 1

Looks fine: in Go, Python, TypeScript, Java, C# and C++ it runs fine. Rust won't compile it.

Works in Go. In Rust it's just a rule.Kotlin refuses this too. Same idea, different words.Works in Python. In Rust it's just a rule.Works in TypeScript. In Rust it's just a rule.Works in Java. In Rust it's just a rule.Works in C#. In Rust it's just a rule.No direct equivalent in C. Just a Rust rule.Works in C++. In Rust it's just a rule.
Rustsrc/main.rs✗ won't compile
use std::collections::HashMap;


fn main() {
    let mut counts: HashMap<&str, u32> = HashMap::new();
    counts.insert("cat", 0);
    for w in "cat cat".split(' ') {
        counts[w] += 1;
    }
    println!("{counts:?}");
}
package main


import (
  "fmt"
  "strings"
)


func main() {
  counts := map[string]int{}
  counts["cat"] = 0
  for _, w := range strings.Split("cat cat", " ") {
    counts[w] += 1
  }
  fmt.Println(counts)
}
$ go run main.go✓ runs
map[cat:2]
Kotlin✗ refuses too

Kotlin refuses this too, for a different reason: counts[w] is an Int? (the key might be missing), so counts[w] += 1 doesn't compile. You write counts[w] = (counts[w] ?: 0) + 1 or use merge.

fun main() {
    val counts = mutableMapOf<String, Int>()
    counts["cat"] = 0
    for (w in "cat cat".split(" ")) {
        counts[w] += 1
    }
    println(counts)
}
Main.kt:5:19: error: operator call is prohibited on a nullable receiver of type 'Int?'. Use '?.'-qualified call instead.
        counts[w] += 1
                  ^^
counts: dict[str, int] = {}
counts["cat"] = 0
for w in "cat cat".split(" "):
    counts[w] += 1
print(counts)
$ python3 main.py✓ runs
{'cat': 2}
const counts: Record<string, number> = {};
counts["cat"] = 0;
for (const w of "cat cat".split(" ")) {
  counts[w] += 1;
}
console.log(counts);
$ tsc --strict --module nodenext --types node main.ts && node main.js✓ runs
{ cat: 2 }
import java.util.HashMap;
import java.util.Map;


public class Main {
    public static void main(String[] args) {
        Map<String, Integer> counts = new HashMap<>();
        counts.put("cat", 0);
        for (String w : "cat cat".split(" ")) {
            counts.put(w, counts.get(w) + 1);
        }
        System.out.println(counts);
    }
}
$ javac Main.java && java Main✓ runs
{cat=2}
var counts = new Dictionary<string, int>();
counts["cat"] = 0;
foreach (var w in "cat cat".Split(' '))
{
    counts[w] += 1;
}
Console.WriteLine(string.Join(", ", counts));
$ dotnet run✓ runs
[cat, 2]
Cno equivalent

C has no map type and no operator overloading, so counts[w] can't take a string key; you call your own lookup function, as in the lesson.

#include <iostream>
#include <map>
#include <string>


int main() {
    std::map<std::string, unsigned> counts;
    counts["cat"] = 0;
    for (std::string w : {"cat", "cat"}) {
        counts[w] += 1;
    }
    for (const auto &[word, n] : counts) std::cout << word << ": " << n << "\n";
}
$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main✓ runs
cat: 2
What does the compiler say? Guess first, then open.
$ cargo buildWhat is E0594?
error[E0594]: cannot assign to data in an index of `HashMap<&str, u32>`
 --> src/main.rs:7:9
  |
7 |         counts[w] += 1;
  |         ^^^^^^^^^^^^^^ cannot assign
  |
  = help: trait `IndexMut` is required to modify indexed content, but it is not implemented for `HashMap<&str, u32>`
  = help: to modify a `HashMap<&str, u32>`, use `.get_mut()`, `.insert()` or the entry API
What happens in Go

Go runs this and prints map[cat:2]. counts[w] += 1 works for any key, because a missing one starts at 0.

What happens in Kotlin

Kotlin refuses this too, for a different reason: counts[w] is an Int? (the key might be missing), so counts[w] += 1 doesn't compile. You write counts[w] = (counts[w] ?: 0) + 1 or use merge.

What happens in Python

Python prints {'cat': 2}. counts[w] += 1 works because the key is already there. With a missing key it would raise KeyError, which is why counting code usually reaches for Counter or defaultdict(int).

What happens in TypeScript

Prints { cat: 2 }. On a plain object counts[w] += 1 compiles and works when the key exists. A missing key would quietly give NaN, since undefined + 1 is NaN.

What happens in Java

Java's Map has no [], so the natural line is counts.put(w, counts.get(w) + 1), and it prints {cat=2}. If the key were missing, get would return null and the + 1 would throw a NullPointerException.

What happens in C#

The Dictionary indexer supports +=, so this prints [cat, 2]. Because the key is already there it works; with a missing key it would throw a KeyNotFoundException.

What happens in C

C has no map type and no operator overloading, so counts[w] can't take a string key; you call your own lookup function, as in the lesson.

What happens in C++

counts[w] += 1 works on std::map and prints cat: 2. Be aware that [] quietly inserts a 0 for any missing key, even when you only meant to read it.

What Rust sees

counts[w] is read-only in Rust. A HashMap implements Index (read with []) but not IndexMut, so you cannot assign through it, whether or not the key exists.

Why Rust says no

This is a rule of the library, not a safety proof. A write through [] would have to either panic on a missing key or insert one, and HashMap chose to offer no write through [] at all. Writes go through methods that say what happens: entry(w).or_insert(0) (insert if missing), get_mut(w) (an Option, so you handle missing), or insert.

The fix

Compiles and runs.

Rust, fixedsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let mut counts: HashMap<&str, u32> = HashMap::new();
    counts.insert("cat", 0);
    for w in "cat cat".split(' ') {
        *counts.entry(w).or_insert(0) += 1; // insert 0 if missing, then add 1
    }
    println!("{counts:?}");
}
$ cargo run
{"cat": 2}

The toolkit

std::collections holds the containers beyond Vec: HashMap and HashSet, BTreeMap and BTreeSet, VecDeque, BinaryHeap and LinkedList. The module docs open with advice worth hearing first: “you should probably just use Vec or HashMap”, because the others “have specific use cases where they are the optimal choice”. This page is about those use cases. Vectors and Maps already cover the two basics, entry, retain, with_capacity and a first look at BTreeMap and sets. Outputs come from Linux on 64-bit ARM with Rust 1.99.1.

Which collection?

check-table.rs, check-set-index.fail.rs and check-linked-index.fail.rs assert every cell below except the hashed loop order, which the docs call “arbitrary” and no test can prove:

Use it for Loop order A repeated item x[i] or x[&key]
Vec a list, or a stack (push and pop at the end) by position kept yes
VecDeque a queue: add at one end, take from the other front to back kept yes
HashMap, HashSet a value found by key; “have I seen this?” arbitrary replaces or is refused map: yes, set: no
BTreeMap, BTreeSet keys in order, a range of keys, the smallest or largest sorted by key replaces or is refused map: yes, set: no
BinaryHeap the biggest item next iter: arbitrary; pop, into_sorted_vec: ordered kept no
LinkedList joining two long lists in O(1) front to back kept no

The standard docs also give costs, with n items and i a position. ~ means expected and * amortized (averaged over the occasional resize):

get(i) insert(i) remove(i) range
Vec O(1) O(n-i)* O(n-i) none
VecDeque O(1) O(min(i, n-i))* O(min(i, n-i)) none
HashMap O(1)~ O(1)~* O(1)~ none
BTreeMap O(log n) O(log n) O(log n) O(log n)

These are the docs’ tables, not measurements. Big-O ignores constant factors, so it cannot rank collections on a small input; for equal costs the docs say “Vec is generally going to be faster than VecDeque, and VecDeque is generally going to be faster than LinkedList”. Rule a collection out with the tables, then measure.

Sets: union and friends

The set methods return iterators, and the operators &, |, - and ^ build a new set (cloning the items, so T: Clone). Both sets must be the same kind, hashed or sorted (check-set-needs.fail.rs: E0308 for a mixed pair, E0369 without Clone). A HashSet has no promised order, so sort before printing:

Rustsrc/main.rsRun ↗
use std::collections::HashSet;


fn sorted<'a>(set: &HashSet<&'a str>) -> Vec<&'a str> {
    let mut v: Vec<&str> = set.iter().copied().collect();
    v.sort();
    v
}


fn main() {
    let rust: HashSet<&str> = HashSet::from(["ana", "bo", "cy", "dee"]);
    let go: HashSet<&str> = HashSet::from(["cy", "dee", "eli"]);


    // The order of a HashSet is not specified, so sort before printing.
    println!("union: {:?}", sorted(&rust.union(&go).copied().collect()));
    println!("intersection: {:?}", sorted(&(&rust & &go)));
    println!("difference: {:?}", sorted(&(&rust - &go)));
    println!("symmetric difference: {:?}", sorted(&(&rust ^ &go)));


    let team: HashSet<&str> = HashSet::from(["cy", "dee"]);
    println!("team is subset of rust: {}", team.is_subset(&rust));
    println!("rust is superset of team: {}", rust.is_superset(&team));
    println!("rust and go disjoint: {}", rust.is_disjoint(&go));


    // `insert` says whether the value was new; `take` removes and returns it.
    let mut seen = HashSet::new();
    println!("insert cy: {}", seen.insert("cy"));
    println!("insert cy again: {}", seen.insert("cy"));
    println!(
        "take cy: {:?}, take cy again: {:?}",
        seen.take("cy"),
        seen.take("cy")
    );
}
$ cargo run
union: ["ana", "bo", "cy", "dee", "eli"]
intersection: ["cy", "dee"]
difference: ["ana", "bo"]
symmetric difference: ["ana", "bo", "eli"]
team is subset of rust: true
rust is superset of team: true
rust and go disjoint: false
insert cy: true
insert cy again: false
take cy: Some("cy"), take cy again: None

insert returns true only when the item was new, which makes it the one-line way to spot a repeat.

BTreeMap: more than sorted

Maps showed first_key_value and range. The same type also offers entry with sorted keys, nearest-key lookups, removal from both ends, and cutting the map in two:

Rustsrc/main.rsRun ↗
use std::collections::BTreeMap;
use std::ops::Bound::{Excluded, Included, Unbounded};


fn main() {
    // entry works like HashMap's, and the keys stay sorted.
    let mut by_len: BTreeMap<usize, Vec<&str>> = BTreeMap::new();
    for w in ["fig", "apple", "kiwi", "pear", "plum", "date", "lime"] {
        by_len.entry(w.len()).or_default().push(w);
    }
    println!("by length: {by_len:?}");


    let mut log: BTreeMap<u32, &str> = BTreeMap::new();
    for (t, e) in [
        (10, "boot"),
        (25, "login"),
        (40, "upload"),
        (55, "logout"),
        (70, "halt"),
    ] {
        log.insert(t, e);
    }
    // range takes any range of keys, or a pair of Bounds for the odd cases.
    println!("25..=55: {:?}", log.range(25..=55).collect::<Vec<_>>());
    println!(
        "after 25, not 25: {:?}",
        log.range((Excluded(25), Unbounded))
            .map(|(t, _)| *t)
            .collect::<Vec<_>>()
    );
    println!(
        "up to and including 40: {:?}",
        log.range((Unbounded, Included(40)))
            .map(|(t, _)| *t)
            .collect::<Vec<_>>()
    );
    // the nearest key at or before 30, and at or after 30
    println!("floor(30): {:?}", log.range(..=30).next_back());
    println!("ceiling(30): {:?}", log.range(30..).next());


    // smallest and largest: peek or remove
    println!(
        "first: {:?}, last: {:?}",
        log.first_key_value(),
        log.last_key_value()
    );
    println!("pop_first: {:?}", log.pop_first());
    println!("pop_last: {:?}", log.pop_last());


    // split_off moves everything from a key upward into a new map
    let later = log.split_off(&40);
    println!("kept: {log:?}, split off: {later:?}");
}
$ cargo run
by length: {3: ["fig"], 4: ["kiwi", "pear", "plum", "date", "lime"], 5: ["apple"]}
25..=55: [(25, "login"), (40, "upload"), (55, "logout")]
after 25, not 25: [40, 55, 70]
up to and including 40: [10, 25, 40]
floor(30): Some((25, "login"))
ceiling(30): Some((40, "upload"))
first: Some((10, "boot")), last: Some((70, "halt"))
pop_first: Some((10, "boot"))
pop_last: Some((70, "halt"))
kept: {25: "login"}, split off: {40: "upload", 55: "logout"}

range takes a normal range of keys, or a pair of Bounds (Included(x), Excluded(x) or Unbounded) for cases a range cannot spell, such as “after 25, but not 25”. It panics on a range that runs backwards:

Rustsrc/main.rs! panics at runtimeRun ↗
use std::collections::BTreeMap;


fn main() {
    let log: BTreeMap<u32, &str> = BTreeMap::from([(10, "boot"), (70, "halt")]);
    let (from, to) = (50, 20);
    println!("asking for {from}..{to}");
    let found: Vec<_> = log.range(from..to).collect();
    println!("found: {found:?}");
}
$ cargo run
asking for 50..20

thread 'main' (1) panicked at /rustc/58cf8f9c35b355199727627d07ae34a4e2846d67/library/alloc/src/collections/btree/search.rs:121:21:
range start is greater than range end in BTreeMap
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Check from < to when the bounds come from a user. BTreeSet has range, first, pop_first and split_off too.

VecDeque: a queue you can index

VecDeque adds and removes at both ends. Iteration goes front to back whatever the layout, and q[i] works.

Rustsrc/main.rsRun ↗
use std::collections::VecDeque;


fn main() {
    let mut q: VecDeque<&str> = VecDeque::new();
    q.push_back("b");
    q.push_back("c");
    q.push_front("a");
    println!("queue: {q:?}, len {}", q.len());
    println!("front: {:?}, back: {:?}", q.front(), q.back());
    println!("index 1: {}", q[1]);
    println!("pop_front: {:?}", q.pop_front());
    println!("pop_back: {:?}", q.pop_back());
    println!("left: {q:?}");


    // iteration goes front to back, whatever the layout in memory
    let mut ring: VecDeque<i32> = (1..=5).collect();
    ring.rotate_left(2);
    println!("rotated: {ring:?}");
    // a deque is not a slice; ask for one when you need one
    ring.make_contiguous().sort();
    println!("sorted: {ring:?}");
    println!("as a slice: {:?}", ring.as_slices());
}
$ cargo run
queue: ["a", "b", "c"], len 3
front: Some("a"), back: Some("c")
index 1: b
pop_front: Some("a")
pop_back: Some("c")
left: ["b"]
rotated: [3, 4, 5, 1, 2]
sorted: [1, 2, 3, 4, 5]
as a slice: ([1, 2, 3, 4, 5], [])

Its items may sit in two pieces of memory (Going deeper shows how). A VecDeque is not a slice: for sort or a slice-only function, call make_contiguous, which moves the items into one piece and hands back a &mut [T].

BinaryHeap: the biggest next

A BinaryHeap is a priority queue, and it is a max-heap: pop gives the greatest item by Ord. peek looks without removing, into_sorted_vec ends the heap and gives a Vec sorted ascending (smallest first), and peek_mut changes the top in place and restores the heap’s order when the reference goes away. Wrap items in std::cmp::Reverse to flip the order:

Rustsrc/main.rsRun ↗
use std::cmp::Reverse;
use std::collections::BinaryHeap;


fn main() {
    let mut heap = BinaryHeap::from([3, 9, 4, 1]);
    println!("peek: {:?}, len {}", heap.peek(), heap.len());
    heap.push(7);
    print!("pop order:");
    while let Some(n) = heap.pop() {
        print!(" {n}");
    }
    println!();


    // Reverse flips the order, so the smallest comes out first
    let mut small: BinaryHeap<Reverse<i32>> = [3, 9, 4, 1].into_iter().map(Reverse).collect();
    println!("smallest: {:?}", small.pop().map(|Reverse(n)| n));


    // tuples compare field by field: put the priority first
    let mut jobs = BinaryHeap::new();
    jobs.push((2, "write"));
    jobs.push((5, "deploy"));
    jobs.push((2, "test"));
    println!("jobs, smallest first: {:?}", jobs.into_sorted_vec());


    // peek_mut lets you change the largest item in place
    let mut h = BinaryHeap::from([5, 8, 2]);
    if let Some(mut top) = h.peek_mut() {
        *top = 1;
    }
    println!("after lowering the top: peek {:?}", h.peek());
}
$ cargo run
peek: Some(9), len 4
pop order: 9 7 4 3 1
smallest: Some(1)
jobs, smallest first: [(2, "test"), (2, "write"), (5, "deploy")]
after lowering the top: peek Some(5)

Tuples and derive(Ord) compare field by field, so put the priority first. Ties fall to the next field:

Rustsrc/main.rsRun ↗
use std::cmp::Reverse;
use std::collections::BinaryHeap;


// derive(Ord) compares the fields in the order they are written
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Job {
    priority: u8,
    name: &'static str,
}


fn main() {
    let jobs = [(2, "test"), (9, "alert"), (2, "write"), (9, "deploy")];


    let mut heap = BinaryHeap::new();
    for (priority, name) in jobs {
        heap.push(Job { priority, name });
    }
    println!("derive(Ord):");
    while let Some(Job { priority, name }) = heap.pop() {
        println!("  {priority} {name}");
    }


    // Arrival order breaks the tie if the item carries an arrival number. Reverse makes
    // the earlier arrival the greater one, so it comes out first.
    let mut fifo = BinaryHeap::new();
    for (arrival, (priority, name)) in jobs.into_iter().enumerate() {
        fifo.push((priority, Reverse(arrival), name));
    }
    println!("with an arrival number:");
    while let Some((priority, _, name)) = fifo.pop() {
        println!("  {priority} {name}");
    }
}
$ cargo run
derive(Ord):
  9 deploy
  9 alert
  2 write
  2 test
with an arrival number:
  9 alert
  9 deploy
  2 test
  2 write

Both deploy and alert have priority 9, and deploy came out first although alert was pushed first, because "deploy" > "alert". The docs promise no first-in, first-out order among equal items. For one, give each item an arrival number, compared last and in Reverse so the earlier arrival counts as greater (the second half).

A BinaryHeap has no comparator argument and no update in place: the order comes from the item’s Ord, so a different order means a wrapper type or a tuple. There is no remove by value, no contains and no decrease-key (check-heap-missing.fail.rs gets E0599 for new_by, remove and contains). To change a priority, push a new entry and skip the old one when it pops.

The classic use is shortest paths. Dijkstra’s algorithm, for costs that are never negative, repeatedly fixes the cost of the cheapest node not yet fixed, and a min-heap (Reverse) of (cost, node) pairs finds it:

Rustsrc/main.rsRun ↗
use std::cmp::Reverse;
use std::collections::BinaryHeap;


/// `edges[a]` lists `(b, cost)` pairs. Returns the cheapest cost from `start` to each node.
fn shortest(edges: &[Vec<(usize, u32)>], start: usize) -> Vec<Option<u32>> {
    let mut best: Vec<Option<u32>> = vec![None; edges.len()];
    let mut todo = BinaryHeap::new();
    todo.push(Reverse((0, start)));
    while let Some(Reverse((cost, node))) = todo.pop() {
        if best[node].is_some() {
            continue; // an older, dearer entry for a node whose cost is already fixed
        }
        best[node] = Some(cost);
        for &(next, step) in &edges[node] {
            if best[next].is_none() {
                todo.push(Reverse((cost + step, next)));
            }
        }
    }
    best
}


fn main() {
    //   0 --4--> 1 --1--> 3
    //   0 --1--> 2 --2--> 1      node 4 has no way in
    //   2 --7--> 3
    let edges = vec![
        vec![(1, 4), (2, 1)],
        vec![(3, 1)],
        vec![(1, 2), (3, 7)],
        vec![],
        vec![],
    ];
    println!("costs from 0: {:?}", shortest(&edges, 0));
}
$ cargo run
costs from 0: [Some(0), Some(3), Some(1), Some(4), None]

Node 4 has no way in, so its answer is None. A cost cannot be lowered in the heap, so an entry is pushed for each route found, a node can pop more than once, and the loop skips the later, dearer entries.

LinkedList: one row

The docs say “It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache”. The index lists reasons to use one anyway, among them that you can’t tolerate amortization or want to “efficiently split and append lists”. append joins two lists in O(1), but split_off still walks to the split point (O(n) in the docs); check-table.rs runs both. There is no x[i] (E0608, check-linked-index.fail.rs). And an insert or remove at a position you already hold is not on stable Rust: remove and the cursor methods are unstable, E0658 on 1.99.1 (check-linked-unstable.fail.rs).

What the items must provide

Vec, VecDeque and LinkedList need nothing from their items. HashMap keys and HashSet items need Hash and Eq (Maps); BTreeMap keys, BTreeSet items and BinaryHeap items need Ord (Common traits).

derive gives your own types these traits; an order other than the derived one is a hand-written Ord, as the last exercise has you write. Leave one out and the error names it:

Rustsrc/main.rs✗ won't compile
use std::collections::{BTreeSet, HashSet};


#[derive(Debug, PartialEq, Eq, Hash)]
struct Tag(String);


fn main() {
    let mut hashed = HashSet::new(); // Tag has Hash and Eq: fine
    hashed.insert(Tag("a".into()));


    let mut sorted = BTreeSet::new(); // Tag has no Ord
    sorted.insert(Tag("a".into()));
    println!("{} {}", hashed.len(), sorted.len());
}
$ cargo buildWhat is E0277?
error[E0277]: the trait bound `Tag: Ord` is not satisfied
  --> src/main.rs:11:12
   |
11 |     sorted.insert(Tag("a".into()));
   |            ^^^^^^ --------------- `Tag` doesn't satisfy the trait bound
   |            |
   |            the trait `Ord` is not implemented for `Tag`
   |
help: consider annotating `Tag` with `#[derive(Ord)]`
   |
 4 + #[derive(Ord)]
 5 | struct Tag(String);
  ... (notes pointing into the standard library trimmed)

The classic case is a float. f64 has no Ord because NaN is not equal to anything, so neither BinaryHeap<f64> nor BTreeSet<f64> compiles (check-float-btree.fail.rs):

Rustsrc/main.rs✗ won't compile
use std::collections::BinaryHeap;


fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(2.5_f64);
    heap.push(0.5);
    println!("{:?}", heap.pop());
}
$ cargo buildWhat is E0277?
error[E0277]: the trait bound `f64: Ord` is not satisfied
 --> src/main.rs:5:10
  |
5 |     heap.push(2.5_f64);
  |          ^^^^ ------- `f64` doesn't satisfy the trait bound
  |          |
  |          the trait `Ord` is not implemented for `f64`
  |
  = help: the following other types implement trait `Ord`:
            i128
            i16
            i32
            i64
            i8
            isize
            u128
            u16
          and 4 others
  ... (notes pointing into the standard library trimmed)

error[E0599]: the method `push` exists for struct `BinaryHeap<f64>`, but its trait bounds were not satisfied
 --> src/main.rs:6:10
  |
6 |     heap.push(0.5);
  |          ^^^^ method cannot be called on `BinaryHeap<f64>` due to unsatisfied trait bounds
  |
  = note: the following trait bounds were not satisfied:
          `f64: Ord`

error[E0599]: the method `pop` exists for struct `BinaryHeap<f64>`, but its trait bounds were not satisfied
 --> src/main.rs:7:27
  |
7 |     println!("{:?}", heap.pop());
  |                           ^^^ method cannot be called on `BinaryHeap<f64>` due to unsatisfied trait bounds
  |
  = note: the following trait bounds were not satisfied:
          `f64: Ord`

Some errors have detailed explanations: E0277, E0599.

The usual fix is a wrapper whose Ord calls f64::total_cmp, which orders every value, NaN included (the ordered-float crate packages the idea):

Rustsrc/main.rsRun ↗
use std::cmp::Ordering;
use std::collections::BinaryHeap;


/// A float that can be ordered: `total_cmp` puts every value, NaN included, in one order.
#[derive(Debug, PartialEq)]
struct Score(f64);


impl Eq for Score {}
impl PartialOrd for Score {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl Ord for Score {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.total_cmp(&other.0)
    }
}


fn main() {
    let mut heap = BinaryHeap::new();
    for x in [2.5, 0.5, 9.0, -1.0] {
        heap.push(Score(x));
    }
    println!("largest: {:?}", heap.pop());
    println!("next: {:?}", heap.pop());
}
$ cargo run
largest: Some(Score(9.0))
next: Some(Score(2.5))

Housekeeping

The docs say “Rust’s collections never automatically shrink”; shrink_to_fit gives memory back. extract_if is retain that hands you the items it removes. It is stable on Vec (1.87), on HashMap and HashSet (1.88), and on BTreeMap and BTreeSet (1.91):

Rustsrc/main.rsRun ↗
use std::collections::{BTreeMap, VecDeque};


fn main() {
    // extract_if hands out what it removes; retain just drops what it rejects
    let mut v: Vec<u32> = (1..=10).collect();
    let removed: Vec<u32> = v.extract_if(.., |n| *n % 3 == 0).collect();
    println!("Vec extract_if multiples of 3: removed {removed:?}, left {v:?}");


    let mut m: BTreeMap<u32, &str> = BTreeMap::from([(1, "a"), (2, "b"), (3, "c"), (4, "d")]);
    let odd: Vec<(u32, &str)> = m.extract_if(.., |k, _| k % 2 == 1).collect();
    println!("BTreeMap extract_if odd keys: removed {odd:?}, left {m:?}");


    let mut q: VecDeque<u32> = (1..=6).collect();
    q.retain(|n| n % 2 == 1);
    println!("VecDeque after retain odd: {q:?}");
}
$ cargo run
Vec extract_if multiples of 3: removed [3, 6, 9], left [1, 2, 4, 5, 7, 8, 10]
BTreeMap extract_if odd keys: removed [(1, "a"), (3, "c")], left {2: "b", 4: "d"}
VecDeque after retain odd: [1, 3, 5]

Going deeper

How VecDeque keeps both ends cheap

A Vec keeps its items at the start of its buffer, so remove(0) moves every other item down. A VecDeque is, in the docs’ words, “a growable ring buffer”: the buffer is a circle and a head position says where the first item is. Removing from the front moves the head; adding at the back may wrap round to free space at the buffer’s start. This program fills a capacity-4 deque, pops two items, pushes two more and asks for the pieces:

Rustsrc/main.rsRun ↗
use std::collections::VecDeque;


fn main() {
    let mut q: VecDeque<u32> = VecDeque::with_capacity(4);
    println!("capacity: {}", q.capacity());
    println!("bytes in a VecDeque<u32>: {}", size_of::<VecDeque<u32>>());
    println!("bytes in a Vec<u32>: {}", size_of::<Vec<u32>>());
    q.extend([1, 2, 3, 4]);
    println!("full:          {:?}", q.as_slices());
    q.pop_front();
    q.pop_front();
    println!("two popped:    {:?}", q.as_slices());
    q.push_back(5);
    q.push_back(6);
    // The new items did not move the old ones: they wrapped round to the free front.
    println!("two pushed:    {:?}", q.as_slices());
    println!("iteration:     {:?}", q.iter().collect::<Vec<_>>());
    println!("capacity still {}", q.capacity());
    q.make_contiguous();
    println!("contiguous:    {:?}", q.as_slices());
}
$ cargo run
capacity: 4
bytes in a VecDeque<u32>: 32
bytes in a Vec<u32>: 24
full:          ([1, 2, 3, 4], [])
two popped:    ([3, 4], [])
two pushed:    ([3, 4], [5, 6])
iteration:     [3, 4, 5, 6]
capacity still 4
contiguous:    ([3, 4, 5, 6], [])

After the pushes, the items 3, 4 and 5, 6 are two slices, though the deque still iterates 3, 4, 5, 6. make_contiguous moves them into one. A deque is a Vec-sized header plus one word, 32 bytes here against 24.

VecDeque<u32>: capacity 4, after pop_front twice, then push_back 5 and push_back 6
STACKHEAPq: VecDeque<u32>ptrhead 2len 4cap 4buffer: slots 0 to 35634
A simplified picture. The program proves the two slices, [3, 4] then [5, 6], the capacity of 4 and the 32-byte header. The field names and slot positions are the natural reading of a ring buffer; the real fields are private and can change.

== and cmp must agree

A BTreeMap or BTreeSet decides that two keys are the same with cmp alone: insert, contains, range and the set operations never call ==. collect and From differ: they also use == to drop repeats. The Ord docs say PartialEq, PartialOrd and Ord must agree. This Word compares by cmp ignoring case but by == on exact spelling, which shows what a disagreement costs:

Rustsrc/main.rsRun ↗
use std::cmp::Ordering;
use std::collections::BTreeSet;
use std::sync::atomic::{AtomicUsize, Ordering as Atomic};


static EQ_CALLS: AtomicUsize = AtomicUsize::new(0);


/// A word whose `cmp` ignores case but whose `==` does not: the two disagree on purpose.
#[derive(Debug, Eq)]
struct Word(&'static str);


impl PartialEq for Word {
    fn eq(&self, other: &Self) -> bool {
        EQ_CALLS.fetch_add(1, Atomic::SeqCst);
        self.0 == other.0
    }
}
impl PartialOrd for Word {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl Ord for Word {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.to_lowercase().cmp(&other.0.to_lowercase())
    }
}


fn eq_calls() -> usize {
    EQ_CALLS.load(Atomic::SeqCst)
}


fn main() {
    let mut set = BTreeSet::new();
    println!("insert Ana: {}", set.insert(Word("Ana")));
    println!("insert ana: {}", set.insert(Word("ana")));
    println!("inserted: {set:?}, `==` called {} times", eq_calls());


    let collected: BTreeSet<Word> = [Word("Ana"), Word("ana")].into_iter().collect();
    println!("collected: {collected:?}, `==` called {} times", eq_calls());
}
$ cargo run
insert Ana: true
insert ana: false
inserted: {Word("Ana")}, `==` called 0 times
collected: {Word("Ana"), Word("ana")}, `==` called 1 times

insert refused ana without calling == once, and collect kept both spellings, because == said they differ. A HashMap has the same rule: equal keys must hash equally, which derive guarantees and a hand-written pair can break. A key whose ordering changes while it is in the map is, say the docs, “a logic error” with unspecified results, “encapsulated to the BTreeMap” and not undefined behaviour. The map owns its keys, so ordinary code has no second handle to change one; the docs name the ways in: interior mutability (Cell, RefCell: Smart pointers), global state, I/O or unsafe.

Practice

Try it

Replace each todo!() and run until it prints all checks passed. The checks count things (live values, equality tests, memory addresses), so the quick wrong answer fails.

The k largest, in bounded memory

Return the k largest items from a stream, largest first; equal items each count. Reading is test scaffolding that counts how many exist at once, so sorting the whole stream fails. Keep a min-heap of the best k so far.

Starterexercises/top_k.rs
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::sync::atomic::{AtomicUsize, Ordering};


static LIVE: AtomicUsize = AtomicUsize::new(0);
static PEAK: AtomicUsize = AtomicUsize::new(0);


/// Test scaffolding: a reading that counts how many readings exist at once. A real
/// stream is too big to hold, so `top_k` must never keep more than a few of these alive.
#[derive(PartialEq, Eq, PartialOrd, Ord)]
pub struct Reading(u32);


impl Reading {
    fn new(value: u32) -> Reading {
        let live = LIVE.fetch_add(1, Ordering::SeqCst) + 1;
        PEAK.fetch_max(live, Ordering::SeqCst);
        Reading(value)
    }
}


impl Drop for Reading {
    fn drop(&mut self) {
        LIVE.fetch_sub(1, Ordering::SeqCst);
    }
}


/// The `k` largest items in the stream, largest first. Equal items each count. A stream
/// with fewer than `k` items gives all of them. Use a `BinaryHeap`: sorting the whole
/// stream would keep every reading alive.
pub fn top_k<T: Ord>(stream: impl Iterator<Item = T>, k: usize) -> Vec<T> {
    todo!("a min-heap (Reverse) holding the k best so far; pop when it grows past k")
}


fn run(values: &[u32], k: usize) -> (Vec<u32>, usize) {
    LIVE.store(0, Ordering::SeqCst);
    PEAK.store(0, Ordering::SeqCst);
    let top: Vec<u32> = top_k(values.iter().map(|&v| Reading::new(v)), k)
        .into_iter()
        .map(|r| r.0)
        .collect();
    assert_eq!(
        LIVE.load(Ordering::SeqCst),
        0,
        "every reading must be dropped"
    );
    (top, PEAK.load(Ordering::SeqCst))
}


fn main() {
    let (top, _) = run(&[4, 9, 1, 7, 9, 3], 3);
    assert_eq!(top, [9, 9, 7], "equal values each count");


    let (top, _) = run(&[5, 2], 5);
    assert_eq!(top, [5, 2], "fewer readings than k gives them all");


    let (top, _) = run(&[], 3);
    assert!(top.is_empty(), "an empty stream");


    let (top, _) = run(&[8, 6], 0);
    assert!(top.is_empty(), "k = 0");


    // A long stream: 5,000 readings, keep 5.
    let values: Vec<u32> = (0..5_000u32).map(|i| (i * 7_919 + 13) % 10_007).collect();
    let mut expected = values.clone();
    expected.sort_by(|a, b| b.cmp(a));
    expected.truncate(5);
    let (top, peak) = run(&values, 5);
    assert_eq!(top, expected);
    assert!(
        peak <= 6,
        "up to {peak} readings were alive at once: keep only k (plus the new one)"
    );
    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution
One solutionexercises/top_k.solution.rsRun ↗
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::sync::atomic::{AtomicUsize, Ordering};


static LIVE: AtomicUsize = AtomicUsize::new(0);
static PEAK: AtomicUsize = AtomicUsize::new(0);


/// Test scaffolding: a reading that counts how many readings exist at once. A real
/// stream is too big to hold, so `top_k` must never keep more than a few of these alive.
#[derive(PartialEq, Eq, PartialOrd, Ord)]
pub struct Reading(u32);


impl Reading {
    fn new(value: u32) -> Reading {
        let live = LIVE.fetch_add(1, Ordering::SeqCst) + 1;
        PEAK.fetch_max(live, Ordering::SeqCst);
        Reading(value)
    }
}


impl Drop for Reading {
    fn drop(&mut self) {
        LIVE.fetch_sub(1, Ordering::SeqCst);
    }
}


/// The `k` largest items in the stream, largest first. Equal items each count. A stream
/// with fewer than `k` items gives all of them. Use a `BinaryHeap`: sorting the whole
/// stream would keep every reading alive.
pub fn top_k<T: Ord>(stream: impl Iterator<Item = T>, k: usize) -> Vec<T> {
    let mut best = BinaryHeap::new();
    for item in stream {
        best.push(Reverse(item));
        if best.len() > k {
            best.pop();
        }
    }
    // Ascending order of Reverse<T> is largest first by T.
    best.into_sorted_vec()
        .into_iter()
        .map(|Reverse(t)| t)
        .collect()
}


fn run(values: &[u32], k: usize) -> (Vec<u32>, usize) {
    LIVE.store(0, Ordering::SeqCst);
    PEAK.store(0, Ordering::SeqCst);
    let top: Vec<u32> = top_k(values.iter().map(|&v| Reading::new(v)), k)
        .into_iter()
        .map(|r| r.0)
        .collect();
    assert_eq!(
        LIVE.load(Ordering::SeqCst),
        0,
        "every reading must be dropped"
    );
    (top, PEAK.load(Ordering::SeqCst))
}


fn main() {
    let (top, _) = run(&[4, 9, 1, 7, 9, 3], 3);
    assert_eq!(top, [9, 9, 7], "equal values each count");


    let (top, _) = run(&[5, 2], 5);
    assert_eq!(top, [5, 2], "fewer readings than k gives them all");


    let (top, _) = run(&[], 3);
    assert!(top.is_empty(), "an empty stream");


    let (top, _) = run(&[8, 6], 0);
    assert!(top.is_empty(), "k = 0");


    // A long stream: 5,000 readings, keep 5.
    let values: Vec<u32> = (0..5_000u32).map(|i| (i * 7_919 + 13) % 10_007).collect();
    let mut expected = values.clone();
    expected.sort_by(|a, b| b.cmp(a));
    expected.truncate(5);
    let (top, peak) = run(&values, 5);
    assert_eq!(top, expected);
    assert!(
        peak <= 6,
        "up to {peak} readings were alive at once: keep only k (plus the new one)"
    );
    println!("all checks passed");
}
$ cargo run
all checks passed

Distinct items, first-seen order

Return the distinct items in the order they first appear. A HashSet finds repeats quickly but forgets the order it was filled in, so it cannot be the whole answer. The checks count equality tests across 4,000 items, so a Vec that is asked contains for each item fails.

Starterexercises/first_seen.rs
use std::collections::HashSet;
use std::hash::Hash;
use std::sync::atomic::{AtomicUsize, Ordering};


static EQ_CALLS: AtomicUsize = AtomicUsize::new(0);


/// An id that counts every equality test made with it.
#[derive(Debug, Clone, Hash, Eq)]
pub struct Id(u32);


impl PartialEq for Id {
    fn eq(&self, other: &Self) -> bool {
        EQ_CALLS.fetch_add(1, Ordering::SeqCst);
        self.0 == other.0
    }
}


/// The distinct items, each once, in the order they first appear.
/// `first_seen(&[3, 1, 3, 2, 1])` is `[3, 1, 2]`. Sorting would lose the order, and
/// asking a `Vec` "do you contain it?" for every item compares each item with many others.
/// A `HashSet` finds repeats quickly, but it forgets the order it was filled in.
pub fn first_seen<T: Hash + Eq + Clone>(items: &[T]) -> Vec<T> {
    todo!("one collection remembers what has been seen; another holds the answer in order")
}


fn main() {
    assert_eq!(first_seen(&[3, 1, 3, 2, 1]), [3, 1, 2]);
    assert_eq!(first_seen(&["b", "a", "b"]), ["b", "a"]);
    assert_eq!(first_seen::<i32>(&[]), []);
    assert_eq!(first_seen(&[7]), [7]);
    assert_eq!(first_seen(&[5, 5, 5]), [5]);


    let ids: Vec<Id> = (0..4_000u32).map(|i| Id((i * 31) % 1_000)).collect();
    EQ_CALLS.store(0, Ordering::SeqCst);
    let unique = first_seen(&ids);
    let calls = EQ_CALLS.load(Ordering::SeqCst);
    assert_eq!(unique.len(), 1_000);
    assert_eq!(unique[0], Id(0));
    assert_eq!(unique[1], Id(31));
    assert!(
        calls < 20_000,
        "made {calls} equality tests for 4,000 items: use a set, not a list"
    );
    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution
One solutionexercises/first_seen.solution.rsRun ↗
use std::collections::HashSet;
use std::hash::Hash;
use std::sync::atomic::{AtomicUsize, Ordering};


static EQ_CALLS: AtomicUsize = AtomicUsize::new(0);


/// An id that counts every equality test made with it.
#[derive(Debug, Clone, Hash, Eq)]
pub struct Id(u32);


impl PartialEq for Id {
    fn eq(&self, other: &Self) -> bool {
        EQ_CALLS.fetch_add(1, Ordering::SeqCst);
        self.0 == other.0
    }
}


/// The distinct items, each once, in the order they first appear.
/// `first_seen(&[3, 1, 3, 2, 1])` is `[3, 1, 2]`. Sorting would lose the order, and
/// asking a `Vec` "do you contain it?" for every item compares each item with many others.
/// A `HashSet` finds repeats quickly, but it forgets the order it was filled in.
pub fn first_seen<T: Hash + Eq + Clone>(items: &[T]) -> Vec<T> {
    let mut seen = HashSet::new();
    let mut out = Vec::new();
    for item in items {
        if seen.insert(item.clone()) {
            out.push(item.clone());
        }
    }
    out
}


fn main() {
    assert_eq!(first_seen(&[3, 1, 3, 2, 1]), [3, 1, 2]);
    assert_eq!(first_seen(&["b", "a", "b"]), ["b", "a"]);
    assert_eq!(first_seen::<i32>(&[]), []);
    assert_eq!(first_seen(&[7]), [7]);
    assert_eq!(first_seen(&[5, 5, 5]), [5]);


    let ids: Vec<Id> = (0..4_000u32).map(|i| Id((i * 31) % 1_000)).collect();
    EQ_CALLS.store(0, Ordering::SeqCst);
    let unique = first_seen(&ids);
    let calls = EQ_CALLS.load(Ordering::SeqCst);
    assert_eq!(unique.len(), 1_000);
    assert_eq!(unique[0], Id(0));
    assert_eq!(unique[1], Id(31));
    assert!(
        calls < 20_000,
        "made {calls} equality tests for 4,000 items: use a set, not a list"
    );
    println!("all checks passed");
}
$ cargo run
all checks passed

A queue of turns

The job at the front of the queue gets one turn of quantum units of work. If it has work left it goes to the back; otherwise it leaves. Write serve, one turn. The checks record where each waiting job sits in memory: pop_front takes O(1), so it cannot move the others, but rebuilding the queue (into a Vec, remove(0), back) does and fails.

Starterexercises/round_robin.rs
use std::collections::{HashMap, VecDeque};


/// A job that needs `left` more units of work.
#[derive(Debug)]
pub struct Job {
    name: &'static str,
    left: u32,
}


/// Give the job at the front of the queue one turn of `quantum` units of work.
/// If it still has work left it goes to the back of the queue; otherwise it is finished
/// and leaves. Returns the name of the job that had the turn, or `None` for an empty queue.
pub fn serve(queue: &mut VecDeque<Job>, quantum: u32) -> Option<&'static str> {
    todo!("take the job from one end of the queue; if it is not finished, put it back at the other")
}


fn address(job: &Job) -> usize {
    job as *const Job as usize
}


fn main() {
    let job = |name, left| Job { name, left };


    // A small queue, turn by turn: a needs 3 units, b needs 1, c needs 2.
    let mut q = VecDeque::from([job("a", 3), job("b", 1), job("c", 2)]);
    let mut turns = Vec::new();
    while let Some(name) = serve(&mut q, 2) {
        turns.push(name);
        assert!(
            turns.len() < 100,
            "the queue never empties: a finished job must leave"
        );
    }
    assert_eq!(turns, ["a", "b", "c", "a"], "who gets each turn");
    assert!(q.is_empty());
    assert_eq!(serve(&mut q, 2), None, "an empty queue");


    // A long queue. Names come from a leaked list so they are 'static.
    let names: Vec<&'static str> = (0..300)
        .map(|i| &*Box::leak(format!("job{i}").into_boxed_str()))
        .collect();
    let work = |i: usize| 1 + (i as u32 * 7) % 5;
    let mut q = VecDeque::with_capacity(names.len() + 1);
    q.extend(names.iter().enumerate().map(|(i, &n)| job(n, work(i))));


    // The turns the plain rule gives: go round the jobs in order until all are done.
    let mut left: Vec<u32> = (0..names.len()).map(work).collect();
    let mut expected = Vec::new();
    while left.iter().any(|&l| l > 0) {
        for (i, l) in left.iter_mut().enumerate() {
            if *l > 0 {
                *l = l.saturating_sub(2);
                expected.push(names[i]);
            }
        }
    }


    // pop_front is O(1), so it cannot move the other jobs: each job's address may change
    // only when that job itself was just moved to the back.
    let mut at: HashMap<&str, usize> = q.iter().map(|j| (j.name, address(j))).collect();
    let mut turns = Vec::new();
    while let Some(name) = serve(&mut q, 2) {
        turns.push(name);
        assert!(
            turns.len() <= expected.len(),
            "more turns than the jobs need"
        );
        for j in q.iter() {
            let now = address(j);
            if j.name == name {
                at.insert(j.name, now);
            } else {
                assert_eq!(
                    at[j.name], now,
                    "{} moved in memory: take from one end and add to the other, do not rebuild the queue",
                    j.name
                );
            }
        }
    }
    assert_eq!(turns, expected, "who gets each turn");
    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution
One solutionexercises/round_robin.solution.rsRun ↗
use std::collections::{HashMap, VecDeque};


/// A job that needs `left` more units of work.
#[derive(Debug)]
pub struct Job {
    name: &'static str,
    left: u32,
}


/// Give the job at the front of the queue one turn of `quantum` units of work.
/// If it still has work left it goes to the back of the queue; otherwise it is finished
/// and leaves. Returns the name of the job that had the turn, or `None` for an empty queue.
pub fn serve(queue: &mut VecDeque<Job>, quantum: u32) -> Option<&'static str> {
    let mut job = queue.pop_front()?;
    job.left = job.left.saturating_sub(quantum);
    let name = job.name;
    if job.left > 0 {
        queue.push_back(job);
    }
    Some(name)
}


fn address(job: &Job) -> usize {
    job as *const Job as usize
}


fn main() {
    let job = |name, left| Job { name, left };


    // A small queue, turn by turn: a needs 3 units, b needs 1, c needs 2.
    let mut q = VecDeque::from([job("a", 3), job("b", 1), job("c", 2)]);
    let mut turns = Vec::new();
    while let Some(name) = serve(&mut q, 2) {
        turns.push(name);
        assert!(
            turns.len() < 100,
            "the queue never empties: a finished job must leave"
        );
    }
    assert_eq!(turns, ["a", "b", "c", "a"], "who gets each turn");
    assert!(q.is_empty());
    assert_eq!(serve(&mut q, 2), None, "an empty queue");


    // A long queue. Names come from a leaked list so they are 'static.
    let names: Vec<&'static str> = (0..300)
        .map(|i| &*Box::leak(format!("job{i}").into_boxed_str()))
        .collect();
    let work = |i: usize| 1 + (i as u32 * 7) % 5;
    let mut q = VecDeque::with_capacity(names.len() + 1);
    q.extend(names.iter().enumerate().map(|(i, &n)| job(n, work(i))));


    // The turns the plain rule gives: go round the jobs in order until all are done.
    let mut left: Vec<u32> = (0..names.len()).map(work).collect();
    let mut expected = Vec::new();
    while left.iter().any(|&l| l > 0) {
        for (i, l) in left.iter_mut().enumerate() {
            if *l > 0 {
                *l = l.saturating_sub(2);
                expected.push(names[i]);
            }
        }
    }


    // pop_front is O(1), so it cannot move the other jobs: each job's address may change
    // only when that job itself was just moved to the back.
    let mut at: HashMap<&str, usize> = q.iter().map(|j| (j.name, address(j))).collect();
    let mut turns = Vec::new();
    while let Some(name) = serve(&mut q, 2) {
        turns.push(name);
        assert!(
            turns.len() <= expected.len(),
            "more turns than the jobs need"
        );
        for j in q.iter() {
            let now = address(j);
            if j.name == name {
                at.insert(j.name, now);
            } else {
                assert_eq!(
                    at[j.name], now,
                    "{} moved in memory: take from one end and add to the other, do not rebuild the queue",
                    j.name
                );
            }
        }
    }
    assert_eq!(turns, expected, "who gets each turn");
    println!("all checks passed");
}
$ cargo run
all checks passed

A comparator becomes Ord

Highest priority first; among equals, the earlier due day; then the smaller name. Write Ord for Task by hand (a derive gets the due days the wrong way round) and run_order with a BinaryHeap. The checks test each rule of cmp, including that it says Equal only for tasks that are ==.

Starterexercises/run_order.rs
use std::cmp::Ordering;
use std::collections::BinaryHeap;


/// A task. The heap hands out the greatest task first, so "greater" must mean "do it sooner".
#[derive(Debug, PartialEq, Eq)]
pub struct Task {
    priority: u8,
    due: u32,
    name: &'static str,
}


/// Higher `priority` is greater. For equal priorities the earlier `due` day is greater.
/// If those tie too, the smaller `name` is greater, so that `cmp` returns `Equal` only for
/// tasks that are `==`.
impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        todo!(
            "priority, then due day, then name: for each one, which way round must the comparison go?"
        )
    }
}


impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}


/// The names of the tasks in the order they should be done, using a `BinaryHeap`.
pub fn run_order(tasks: Vec<Task>) -> Vec<&'static str> {
    todo!("put the tasks in a BinaryHeap, then pop them all")
}


fn main() {
    let t = |priority, due, name| Task {
        priority,
        due,
        name,
    };


    // Each comparison is one rule of the order.
    assert!(t(2, 9, "x") > t(1, 1, "y"), "higher priority wins");
    assert!(
        t(1, 3, "x") > t(1, 5, "y"),
        "same priority: earlier due wins"
    );
    assert!(
        t(1, 3, "a") > t(1, 3, "b"),
        "same priority and due: smaller name wins"
    );
    assert_eq!(t(1, 3, "a").cmp(&t(1, 3, "a")), Ordering::Equal);
    assert_ne!(
        t(1, 3, "a").cmp(&t(1, 3, "b")),
        Ordering::Equal,
        "cmp may say Equal only for tasks that are =="
    );


    let tasks = vec![
        t(1, 4, "report"),
        t(3, 7, "deploy"),
        t(3, 2, "hotfix"),
        t(1, 4, "backup"),
        t(2, 1, "review"),
        t(3, 7, "alert"),
    ];
    assert_eq!(
        run_order(tasks),
        ["hotfix", "alert", "deploy", "review", "backup", "report"]
    );
    assert!(run_order(Vec::new()).is_empty());
    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution
One solutionexercises/run_order.solution.rsRun ↗
use std::cmp::Ordering;
use std::collections::BinaryHeap;


/// A task. The heap hands out the greatest task first, so "greater" must mean "do it sooner".
#[derive(Debug, PartialEq, Eq)]
pub struct Task {
    priority: u8,
    due: u32,
    name: &'static str,
}


/// Higher `priority` is greater. For equal priorities the earlier `due` day is greater.
/// If those tie too, the smaller `name` is greater, so that `cmp` returns `Equal` only for
/// tasks that are `==`.
impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority)
            .then(other.due.cmp(&self.due))
            .then(other.name.cmp(self.name))
    }
}


impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}


/// The names of the tasks in the order they should be done, using a `BinaryHeap`.
pub fn run_order(tasks: Vec<Task>) -> Vec<&'static str> {
    let mut heap = BinaryHeap::from(tasks);
    let mut order = Vec::new();
    while let Some(task) = heap.pop() {
        order.push(task.name);
    }
    order
}


fn main() {
    let t = |priority, due, name| Task {
        priority,
        due,
        name,
    };


    // Each comparison is one rule of the order.
    assert!(t(2, 9, "x") > t(1, 1, "y"), "higher priority wins");
    assert!(
        t(1, 3, "x") > t(1, 5, "y"),
        "same priority: earlier due wins"
    );
    assert!(
        t(1, 3, "a") > t(1, 3, "b"),
        "same priority and due: smaller name wins"
    );
    assert_eq!(t(1, 3, "a").cmp(&t(1, 3, "a")), Ordering::Equal);
    assert_ne!(
        t(1, 3, "a").cmp(&t(1, 3, "b")),
        Ordering::Equal,
        "cmp may say Equal only for tasks that are =="
    );


    let tasks = vec![
        t(1, 4, "report"),
        t(3, 7, "deploy"),
        t(3, 2, "hotfix"),
        t(1, 4, "backup"),
        t(2, 1, "review"),
        t(3, 7, "alert"),
    ];
    assert_eq!(
        run_order(tasks),
        ["hotfix", "alert", "deploy", "review", "backup", "report"]
    );
    assert!(run_order(Vec::new()).is_empty());
    println!("all checks passed");
}
$ cargo run
all checks passed

Read more

Learn Rust is an independent project, not affiliated with the Rust Project or the Rust Foundation. Code and text are under the MIT licence.Source on GitHub.