352 Intermediate

352: BTreeSet Sorted

Functional Programming

Tutorial

The Problem

When you need a set that maintains elements in sorted order — for range membership tests, sorted output, or ordered iteration — BTreeSet is the right choice over HashSet. Like BTreeMap, it uses a B-tree internally, giving O(log n) insert/remove/contains and guaranteed sorted iteration. This is the structure behind sorted unique element collections in databases (sorted indexes), lexicographic ordering for string sets, and anywhere you need both deduplication and sorted traversal without re-sorting after each insertion.

🎯 Learning Outcomes

• Construct a BTreeSet<T> from a Vec<T> (automatically deduplicates and sorts)

• Use set operations: union, intersection, difference, symmetric_difference

• Iterate in sorted order without explicit sorting

• Use .range(lo..=hi) for efficient range membership queries

• Understand that BTreeSet<T> requires T: Ord (not just Hash + Eq)

• Recognize when BTreeSet beats HashSet (sorted output, range queries)

Code Example

#![allow(clippy::all)]
//! # BTreeSet Sorted
//! Sorted set with set operations.

use std::collections::BTreeSet;

pub fn sorted_set<T: Ord>(items: Vec<T>) -> BTreeSet<T> {
    items.into_iter().collect()
}

pub fn union<T: Ord + Clone>(a: &BTreeSet<T>, b: &BTreeSet<T>) -> BTreeSet<T> {
    a.union(b).cloned().collect()
}

pub fn intersection<T: Ord + Clone>(a: &BTreeSet<T>, b: &BTreeSet<T>) -> BTreeSet<T> {
    a.intersection(b).cloned().collect()
}

pub fn difference<T: Ord + Clone>(a: &BTreeSet<T>, b: &BTreeSet<T>) -> BTreeSet<T> {
    a.difference(b).cloned().collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sorted_order() {
        let s = sorted_set(vec![3, 1, 4, 1, 5]);
        let v: Vec<_> = s.iter().cloned().collect();
        assert_eq!(v, vec![1, 3, 4, 5]); // sorted, deduplicated
    }
    #[test]
    fn set_operations() {
        let a = sorted_set(vec![1, 2, 3]);
        let b = sorted_set(vec![2, 3, 4]);
        assert_eq!(
            intersection(&a, &b).iter().cloned().collect::<Vec<_>>(),
            vec![2, 3]
        );
        assert_eq!(
            difference(&a, &b).iter().cloned().collect::<Vec<_>>(),
            vec![1]
        );
    }
}

(* OCaml: ordered sets via Set module *)
module IS = Set.Make(Int)

let () =
  let a = IS.of_list [1;3;5;7;9] in
  let b = IS.of_list [3;5;6;7;8] in
  IS.iter (Printf.printf "%d ") (IS.inter a b); print_newline ();
  IS.iter (Printf.printf "%d ") (IS.union a b); print_newline ();
  IS.iter (Printf.printf "%d ") (IS.diff a b); print_newline ()

Key Differences

Aspect	Rust `BTreeSet`	OCaml `Set.Make`
Mutability	In-place (`insert`, `remove`)	Persistent (new set returned)
Set operations	Return iterator, collect to set	Return new set directly
Ordering	`T: Ord` (total order)	`compare` function via functor
Range query	`.range(lo..=hi)` iterator	`filter` (O(n)) or split then traverse
Deduplication	On insert	On insert

OCaml Approach

OCaml's Set.Make functor creates ordered sets:

module IntSet = Set.Make(Int)

let sorted_set items =
  List.fold_left (fun s x -> IntSet.add x s) IntSet.empty items

let union a b = IntSet.union a b
let inter a b  = IntSet.inter a b
let diff a b   = IntSet.diff a b

OCaml's Set is a purely functional AVL tree — operations return new sets. Set.union, Set.inter, Set.diff all run in O(m log(n/m)) for sets of size n and m. Like Rust's BTreeSet, iteration is always sorted.

Full Source

#![allow(clippy::all)]
//! # BTreeSet Sorted
//! Sorted set with set operations.

use std::collections::BTreeSet;

pub fn sorted_set<T: Ord>(items: Vec<T>) -> BTreeSet<T> {
    items.into_iter().collect()
}

pub fn union<T: Ord + Clone>(a: &BTreeSet<T>, b: &BTreeSet<T>) -> BTreeSet<T> {
    a.union(b).cloned().collect()
}

pub fn intersection<T: Ord + Clone>(a: &BTreeSet<T>, b: &BTreeSet<T>) -> BTreeSet<T> {
    a.intersection(b).cloned().collect()
}

pub fn difference<T: Ord + Clone>(a: &BTreeSet<T>, b: &BTreeSet<T>) -> BTreeSet<T> {
    a.difference(b).cloned().collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sorted_order() {
        let s = sorted_set(vec![3, 1, 4, 1, 5]);
        let v: Vec<_> = s.iter().cloned().collect();
        assert_eq!(v, vec![1, 3, 4, 5]); // sorted, deduplicated
    }
    #[test]
    fn set_operations() {
        let a = sorted_set(vec![1, 2, 3]);
        let b = sorted_set(vec![2, 3, 4]);
        assert_eq!(
            intersection(&a, &b).iter().cloned().collect::<Vec<_>>(),
            vec![2, 3]
        );
        assert_eq!(
            difference(&a, &b).iter().cloned().collect::<Vec<_>>(),
            vec![1]
        );
    }
}

(* OCaml: ordered sets via Set module *)
module IS = Set.Make(Int)

let () =
  let a = IS.of_list [1;3;5;7;9] in
  let b = IS.of_list [3;5;6;7;8] in
  IS.iter (Printf.printf "%d ") (IS.inter a b); print_newline ();
  IS.iter (Printf.printf "%d ") (IS.union a b); print_newline ();
  IS.iter (Printf.printf "%d ") (IS.diff a b); print_newline ()

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sorted_order() {
        let s = sorted_set(vec![3, 1, 4, 1, 5]);
        let v: Vec<_> = s.iter().cloned().collect();
        assert_eq!(v, vec![1, 3, 4, 5]); // sorted, deduplicated
    }
    #[test]
    fn set_operations() {
        let a = sorted_set(vec![1, 2, 3]);
        let b = sorted_set(vec![2, 3, 4]);
        assert_eq!(
            intersection(&a, &b).iter().cloned().collect::<Vec<_>>(),
            vec![2, 3]
        );
        assert_eq!(
            difference(&a, &b).iter().cloned().collect::<Vec<_>>(),
            vec![1]
        );
    }
}

Deep Comparison

OCaml vs Rust: Btreeset Sorted

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Sorted unique words: Read a list of words, lowercase them, and collect into a BTreeSet<String>; verify the output is deduplicated and alphabetically sorted.

Set difference chain: Given three sets A, B, C, compute elements that are in A but not in B or C using chained difference calls; compare with a.iter().filter(|x| !b.contains(x) && !c.contains(x)).

Range member test: Given a BTreeSet<i32> of reserved port numbers, write is_port_range_free(set, start, end) -> bool using .range(start..=end).next().is_none() — O(log n) instead of scanning.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust