Skip to content
Tutorials Center
My learning

Topics

Rust Reference ยท Collections

Rust BTreeSet<T> type

Reference for Rust BTreeSet<T>: a sorted set of unique values with O(log n) operations, ordered iteration, range queries, first/last and set algebra.

BTreeSet<T> is the sorted counterpart of HashSet<T>. It stores each distinct value once, keeps the values in ascending order according to Ord, and is backed by the same B-tree as BTreeMap. Iteration is always sorted, so output is deterministic.

Choose it when you need sorted unique values, the smallest or largest element, ranges, or predecessor/successor queries. Choose HashSet when you only need fast membership and do not care about order.

Rust
use std::collections::BTreeSet;

let mut s = BTreeSet::new();
s.insert(5);
s.insert(2);
// iterates 2, 5

Try it

Rust Sorted unique values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Rust Set algebra in sorted order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Syntax

Rust
pub struct BTreeSet<T, A = Global> { /* private */ }

impl<T> BTreeSet<T> {
    pub const fn new() -> BTreeSet<T>;
}

impl<T: Ord> BTreeSet<T> {
    pub fn insert(&mut self, value: T) -> bool;
    pub fn contains<Q>(&self, value: &Q) -> bool where T: Borrow<Q>, Q: Ord + ?Sized;
    pub fn remove<Q>(&mut self, value: &Q) -> bool where T: Borrow<Q>, Q: Ord + ?Sized;
    pub fn first(&self) -> Option<&T>;
    pub fn last(&self) -> Option<&T>;
    pub fn pop_first(&mut self) -> Option<T>;
    pub fn pop_last(&mut self) -> Option<T>;
    pub fn range<K, R>(&self, range: R) -> Range<'_, T> where R: RangeBounds<K>;
    pub fn split_off<Q>(&mut self, value: &Q) -> BTreeSet<T>;
    pub fn append(&mut self, other: &mut BTreeSet<T>);
}
Name Description
T Element type; must implement Ord.
value The element. insert takes ownership; lookups borrow.
range A range expression or pair of Bounds over elements.
other Set to merge with append; left empty afterwards.

Returns: insert is true when the value was new. remove is true when it was present. first, last and the pop_* methods return Option.

Errors and panics: range panics when start is greater than end, or when both bounds are the same excluded value. Inconsistent Ord implementations give unspecified (but safe) behavior.

Usage notes

  • Complexity: insert, contains, remove, first, last are O(log n); iteration is O(n).
  • Same algebra as HashSet: union, intersection, difference, symmetric_difference, is_subset, is_superset, is_disjoint and the |, &, -, ^ operators. See HashSet union, intersection, difference.
  • Hashable and comparable: a BTreeSet<T> is Hash, Ord and Eq when T is, so you can nest sets (BTreeSet<BTreeSet<u8>>) or use them as map keys.
  • Floats: f64 has no total Ord; wrap in a newtype using total_cmp or use an ordered-float wrapper you write yourself.
  • Sorted deduplication: v.into_iter().collect::<BTreeSet<_>>() sorts and removes duplicates in one step.
  • Predecessor/successor: set.range(..x).next_back() is the largest element below x; set.range(x..).next() the smallest at or above x.
  • pop_first/pop_last (since 1.66) turn it into a double-ended priority queue without duplicates.