HashSet and BTreeSet

A set is a map with no values: it stores unique keys and answers whether one is present. The two types are the same pair as the maps: HashSet for constant-time lookups and BTreeSet for a sorted iteration. Both are in the same module and share the trait requirements of their map.

The lesson covers the operations a program needs: insert, contains, deduplication, the three set operations, the ordered set and the rule that keeps floats out. Every print of a hash set is sorted first, because the iteration order is not specified.

insert and contains

insert returns true when the value was new and false when it was already there, which is how a visited set reports a cycle. contains answers the membership question without changing anything.

The program inserts one name twice and asks whether it is present. The second insert returns false, and the length stays one.

use std::collections::HashSet; fn main() { let mut seen = HashSet::new(); println!("{}", seen.insert("ada")); println!("{}", seen.insert("ada")); println!("{}", seen.contains("ada")); println!("{}", seen.len()); }

rustc --edition 2024 insert.rs
./insert

true
false
true
1

The boolean from insert is the cheapest cycle check in a graph walk. The lesson on maps explains the hashing behind the constant lookup.

Removing duplicates

Collecting a list into a set removes the duplicates, and collecting it back gives a list of unique values. That is two passes and one allocation per pass, which is fine for a few thousand items.

The program deduplicates five numbers and sorts the result so the output is stable. The three unique values print in ascending order.

use std::collections::HashSet; fn main() { let values = [3, 1, 3, 2, 1]; let unique: HashSet<i32> = values.into_iter().collect(); let mut list: Vec<i32> = unique.into_iter().collect(); list.sort(); println!("{list:?}"); }

rustc --edition 2024 dedup.rs
./dedup

[1, 2, 3]

A sorted vector can also deduplicate in place with dedup, which keeps the order of the first occurrence. The set is the right choice when the order does not matter.

Union, intersection and difference

The three operations return iterators, so they are lazy and need a consumer. union gives everything in either set, intersection the common values and difference what is in the first only.

The program applies all three to two sets, collects each into a vector and sorts it. The outputs are the four values, the shared three and the two left values.

use std::collections::HashSet; fn main() { let a: HashSet<i32> = [1, 2, 3].into_iter().collect(); let b: HashSet<i32> = [3, 4].into_iter().collect(); let mut union: Vec<i32> = a.union(&b).copied().collect(); union.sort(); let mut inter: Vec<i32> = a.intersection(&b).copied().collect(); inter.sort(); let mut diff: Vec<i32> = a.difference(&b).copied().collect(); diff.sort(); println!("{union:?} {inter:?} {diff:?}"); }

rustc --edition 2024 ops.rs
./ops

[1, 2, 3, 4] [3] [1, 2]

The iterators borrow the sets, so the sets stay available. The lesson on iterator adaptors explains the lazy shape they share with map and filter.

BTreeSet keeps the order

A BTreeSet iterates in sorted order, which makes it the set to use for a deterministic report. The keys need Ord, and the operations cost a logarithm rather than a constant.

The program collects three words in a scrambled order and prints them. The output is alphabetical without a sort call.

use std::collections::BTreeSet; fn main() { let words: BTreeSet<&str> = ["pear", "apple", "fig"].into_iter().collect(); for word in &words { print!("{word} "); } println!(); }

rustc --edition 2024 btree.rs
./btree

apple fig pear

Choosing between the two is the same decision as for maps, and the ordered set also supports ranges over its keys. The next lesson moves to the sequence containers.

A float cannot be a key

A hash set needs Hash and Eq, and a float implements neither: two NaN values are not equal, so the set could not decide what a duplicate is. The compiler reports E0277 at the insert.

The program inserts a float into a set. The error names the missing trait, and the fix is a key type such as the bit pattern in an integer.

use std::collections::HashSet; fn main() { let mut values = HashSet::new(); values.insert(1.5); println!("{}", values.len()); }

rustc --edition 2024 float_err.rs

error[E0277]: the trait bound `{float}: Eq` is not satisfied
--> float_err.rs:5:12
|
5 | values.insert(1.5);
| ^^^^^^ the trait `Eq` is not implemented for `{float}`
|
= help: the following other types implement trait `Eq`:
i128
i16
i32
i64
i8
isize
u128
u16
and 4 others
note: required by a bound in `HashSet::<T, S, A>::insert`
--> /rustc/31fca3adb283cc9dfd56b49cdee9a96eb9c96ffd/library/std/src/collections/hash/set.rs:1034:4

error[E0277]: the trait bound `{float}: Hash` is not satisfied
--> float_err.rs:5:12
|
5 | values.insert(1.5);
| ^^^^^^ the trait `Hash` is not implemented for `{float}`
|
= help: the following other types implement trait `Hash`:
i128
i16
i32
i64
i8
isize
u128
u16
and 4 others
note: required by a bound in `HashSet::<T, S, A>::insert`
--> /rustc/31fca3adb283cc9dfd56b49cdee9a96eb9c96ffd/library/std/src/collections/hash/set.rs:1034:4

error: aborting due to 2 previous errors

For more information about this error, try `rustc --explain E0277`.

The same rule keeps floats out of a HashMap key and out of a sort that needs Ord. The lesson on operator traits shows where Eq would come from.

Exercises

1. Count the unique words of a sentence with a set and print the count.
2. Build two sets from two slices and print their intersection in sorted order.
3. Use the boolean from insert to stop a loop when a value repeats.

The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev