BTreeMap and HashSet

BTreeMap ordered iteration and range queries, plus HashSet membership and set operations with sorted output.

BTreeMap, BTreeSet, HashSet, and HashMap all live in std::collections. HashMap has its own page, including get, entry, and the original ordered-maps recipe that compares values with a BTreeMap. This page does not repeat those HashMap APIs. It covers ordered maps and sets, and HashSet membership and set operations.

BTreeMap and BTreeSet iterate in key or value order when the type implements Ord. HashSet and HashMap iteration order is not specified and is not stable. Examples that print a HashSet collect the items and sort them first. {:?} of a HashSet is also unordered and is not hard-coded as expected output.

Examples were compiled with rustc 1.90.0 using --edition=2024 and run as a plain binary. See the Rust 1.90.0 documentation for the complete API.

Rust reference overview →

API index

APISummary
BTreeMap::insert, BTreeMap::range, BTreeMap::first_key_value, BTreeMap::last_key_valueInsert into an ordered map, walk a key range, and read the first and last entries. Iteration is in key order.
HashSet::insert, HashSet::contains, HashSet::intersection, HashSet::difference, HashSet::union, BTreeSetTest membership in a HashSet, compute set operations, and sort the results. Use BTreeSet when iteration should follow Ord.

BTreeMap order and range

BTreeMap stores key/value pairs in key order. insert takes &mut self and returns the previous value if the key was present. get borrows the map and looks up a key through Borrow, so a BTreeMap<String, _> can be queried with a &str. first_key_value and last_key_value return the smallest and largest keys. range takes a RangeBounds and yields a borrow of each pair in that interval; a half-open range such as "b".."d" includes "b" and "c" and excludes "d".

BTreeMap::insert, BTreeMap::range, BTreeMap::first_key_value, BTreeMap::last_key_value

pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where K: Ord
pub fn range<T, R>(&self, range: R) -> Range<'_, K, V>
    where T: Ord + ?Sized, K: Borrow<T> + Ord, R: RangeBounds<T>
pub fn first_key_value(&self) -> Option<(&K, &V)>
    where K: Ord
pub fn last_key_value(&self) -> Option<(&K, &V)>
    where K: Ord

Insert into an ordered map, walk a key range, and read the first and last entries. Iteration is in key order.

ParameterDescription
key / valueinsert takes ownership of the key and value. The key type must implement Ord.
rangeA range bound such as "b".."d", "b".., or ..= "c". Keys are borrowed for the comparison.

Returns: insert returns Option<V> with the previous value. range returns an iterator of (&K, &V). first_key_value and last_key_value return Option<(&K, &V)>.

  • Keys were inserted as c, a, b, d and printed in key order as a, b, c, d. That order is part of the BTreeMap contract, unlike HashMap.
  • The HashMap page still holds the original compare-in-key-order recipe. See the related links.
rust
use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("c", 3);
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("d", 4);
    print!("btree-iter");
    for (k, v) in &map {
        print!(" {k}={v}");
    }
    println!();
    print!("range");
    for (k, v) in map.range("b".."d") {
        print!(" {k}={v}");
    }
    println!();
    println!("first {:?} last {:?}", map.first_key_value(), map.last_key_value());
}

Expected output

btree-iter a=1 b=2 c=3 d=4
range b=2 c=3
first Some(("a", 1)) last Some(("d", 4))

Related: HashMap page, Original ordered-maps recipe

Official documentation →

HashSet and BTreeSet

HashSet::insert returns true when the value was newly added and false when it was already present. contains borrows the set and, through Borrow, can query a HashSet<String> with a &str. intersection, difference, and union return iterators over the corresponding set operation. Those iterators have no specified order, so the example collects and sorts the items before printing. BTreeSet requires Ord and iterates in value order, so its collected items can be printed without a separate sort when the order of the type is the order you want.

HashSet::insert, HashSet::contains, HashSet::intersection, HashSet::difference, HashSet::union, BTreeSet

pub fn insert(&mut self, value: T) -> bool
pub fn contains<Q>(&self, value: &Q) -> bool
    where T: Borrow<Q>, Q: Hash + Eq + ?Sized
pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S>
pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S>
pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S>
pub fn insert(&mut self, value: T) -> bool
    where T: Ord  // BTreeSet

Test membership in a HashSet, compute set operations, and sort the results. Use BTreeSet when iteration should follow Ord.

ParameterDescription
valueinsert takes ownership of the value. contains borrows a query type that the value can be borrowed as.
otherThe second set for intersection, difference, or union. The iterators borrow both sets.

Returns: HashSet::insert and BTreeSet::insert return whether the value was newly inserted. contains returns a bool. The set-operation methods return iterators of borrowed items.

  • Do not assert the raw order of HashSet::iter or of {:?} on a HashSet.
  • difference here is set minus other, so "a" and "c" remain after subtracting {"b", "d"}.
rust
use std::collections::{BTreeSet, HashSet};

fn main() {
    let mut set = HashSet::new();
    println!("insert-a {}", set.insert("a"));
    println!("insert-a-again {}", set.insert("a"));
    println!("contains-b {}", set.contains("b"));
    set.insert("b");
    set.insert("c");
    let other = HashSet::from(["b", "d"]);
    let mut inter: Vec<_> = set.intersection(&other).copied().collect();
    inter.sort();
    let mut diff: Vec<_> = set.difference(&other).copied().collect();
    diff.sort();
    let mut union: Vec<_> = set.union(&other).copied().collect();
    union.sort();
    println!("inter {inter:?} diff {diff:?} union {union:?}");
    let btree = BTreeSet::from(["c", "a", "b"]);
    let ordered: Vec<_> = btree.iter().copied().collect();
    println!("btreeset {ordered:?}");
}

Expected output

insert-a true
insert-a-again false
contains-b false
inter ["b"] diff ["a", "c"] union ["a", "b", "c", "d"]
btreeset ["a", "b", "c"]

Related: HashMap page

Official documentation →