Ordered Collections

Ordered Set Operations

BTreeSet<T> supports the same set-algebra methods and bitwise operators as HashSet<T>—union, intersection, difference, and symmetric_difference—with the added guarantee that every resulting iterator yields elements in strictly ascending T: Ord order.

Set Algebra Methods and Operators on BTreeSet<T>

Set Operation Lazy Sorted Iterator (Item = &T) Eager Operator (-> BTreeSet<T>, requires T: Clone)
Union ($A \cup B$) a.union(&b) &a | &b
Intersection ($A \cap B$) a.intersection(&b) &a & &b
Difference ($A \setminus B$) a.difference(&b) &a - &b
Symmetric Difference ($A \triangle B$) a.symmetric_difference(&b) &a ^ &b
Subset / Superset / Disjoint a.is_subset(&b), a.is_superset(&b), a.is_disjoint(&b) — (bool)

How Ordered Set Iterators Work (Sorted Merge vs. Seek)

Because both BTreeSet inputs are already sorted in ascending order:

  1. When the two sets have comparable sizes, .union(&b), .intersection(&b), .difference(&b), and .symmetric_difference(&b) perform a two-pointer sorted merge in $O(|a| + |b|)$ time.
  2. When one set is much smaller than the other (for example, intersecting a 3-element set with a 100,000-element set), BTreeSet's .intersection() and .difference() automatically switch to $O(|a| \log |b|)$ tree lookups on the larger set.
use std::collections::BTreeSet;

fn main() {
    let cluster_a = BTreeSet::from(["node-1", "node-2", "node-3", "node-4"]);
    let cluster_b = BTreeSet::from(["node-3", "node-4", "node-5"]);

    // Every lazy set-operation iterator yields items in sorted ascending order:
    let union: Vec<&str> = cluster_a.union(&cluster_b).copied().collect();
    let both: Vec<&str> = cluster_a.intersection(&cluster_b).copied().collect();
    let only_a: Vec<&str> = cluster_a.difference(&cluster_b).copied().collect();
    let xor: Vec<&str> = cluster_a.symmetric_difference(&cluster_b).copied().collect();

    println!("Union (A ∪ B):        {union:?}");
    println!("Intersection (A ∩ B): {both:?}");
    println!("Difference (A \\ B):   {only_a:?}");
    println!("Symm. Diff (A △ B):   {xor:?}");
}

Union (A ∪ B):        ["node-1", "node-2", "node-3", "node-4", "node-5"]
Intersection (A ∩ B): ["node-3", "node-4"]
Difference (A \ B):   ["node-1", "node-2"]
Symm. Diff (A △ B):   ["node-1", "node-2", "node-5"]

Comparing Sets for Equality and Lexicographical Order

Because BTreeSet<T> iterates in deterministic sorted order:

  • set_a == set_b compares elements pairwise in $O(n)$ time (stopping immediately if set_a.len() != set_b.len()).
  • set_a < set_b (Ord and PartialOrd) compares two BTreeSet<T> instances lexicographically by their sorted elements.