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.
use std::collections::BTreeSet; let mut s = BTreeSet::new(); s.insert(5); s.insert(2); // iterates 2, 5
Try it
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.
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
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,lastare O(log n); iteration is O(n). - Same algebra as
HashSet:union,intersection,difference,symmetric_difference,is_subset,is_superset,is_disjointand the|,&,-,^operators. See HashSet union, intersection, difference. - Hashable and comparable: a
BTreeSet<T>isHash,OrdandEqwhenTis, so you can nest sets (BTreeSet<BTreeSet<u8>>) or use them as map keys. - Floats:
f64has no totalOrd; wrap in a newtype usingtotal_cmpor 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 belowx;set.range(x..).next()the smallest at or abovex. pop_first/pop_last(since 1.66) turn it into a double-ended priority queue without duplicates.