Ben Chuanlong Du's Blog

It is never too late to learn.

Set in Rust

Things on this page are fragmentary and immature notes/thoughts of the author. Please read with your own judgement!

In [ ]:
:timing
:sccache 1

Tips and Traps

  1. Summary of Collections in Rust has a good summary on when to each which collection in Rust.

  2. Struct std::collections::HashSet has a good discussion on implementation details on HashSet and things to note when use it.

  3. BTreeSet is an alternative B-Tree-based implementation to HashSet. Elements in BTreeSet are sorted while elements in a HashSet are not sorted.

  4. TinySet provides a few collections that are optimized to scale in size well for small numbers of elements, while still scaling well in time (and size) for numbers of elements.

In [2]:
use std::collections::HashSet;

capacity

Creates an empty HashSet with the specified capacity. The hash set will be able to hold at least capacity elements without reallocating. If capacity is 0, the hash set will not allocate.

In [13]:
{
    let s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    s.capacity()
}
Out[13]:
7
In [15]:
{
    let s: HashSet<i32> = HashSet::with_capacity(20);
    s.capacity()
}
Out[15]:
28

clear

In [18]:
{
    let mut s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    s.clear();
    s
}
Out[18]:
{}

contains

In [20]:
{
    let mut s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    s.contains(&1)
}
Out[20]:
true
In [21]:
{
    let mut s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    s.contains(&10)
}
Out[21]:
false

difference

In [6]:
{
    let s1: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    let s2: HashSet<i32> = [3, 4].iter().cloned().collect();
    println!("s1 - s2: {:?}", &s1 - &s2);
    println!("s1: {:?}", s1);
}

s1 - s2: {1, 0, 2}
s1: {0, 2, 3, 1, 4}
Out[6]:
()
In [9]:
{
    let s1: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    let s2: HashSet<i32> = [3, 4].iter().cloned().collect();
    println!("s1.difference(s2): {:?}", s1.difference(&s2));
    println!("s1: {:?}", s1);
}

s1.difference(s2): [0, 2, 1]
s1: {0, 2, 3, 4, 1}
Out[9]:
()

get

In [23]:
let s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
s.get(&1)
Out[23]:
Some(1)
In [24]:
let s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
s.get(&10)
Out[24]:
None

get_or_insert

In [12]:
#![feature(hash_set_entry)]
{
    let s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    let v = s.get_or_insert(5);
    println!("v: {}", v);
    println!("{:?}", s);
}

    let v = s.get_or_insert(5);
              ^^^^^^^^^^^^^ 
use of unstable library feature 'hash_set_entry'

insert

In [26]:
{
    let mut s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    s.insert(100);
    s
}
Out[26]:
{4, 100, 0, 1, 2, 3}

intersection

In [33]:
let s1: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
let s2: HashSet<i32> = [3, 4, 5, 6, 7].iter().cloned().collect();
s1.intersection(&s2)
Out[33]:
[3, 4]

is_disjoin

In [34]:
let s1: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
let s2: HashSet<i32> = [3, 4, 5, 6, 7].iter().cloned().collect();
s1.is_disjoint(&s2)
Out[34]:
false
In [35]:
let s1: HashSet<i32> = [0, 1, 2, 3].iter().cloned().collect();
let s2: HashSet<i32> = [4, 5, 6, 7].iter().cloned().collect();
s1.is_disjoint(&s2)
Out[35]:
true

replace

This is the same as the function get_or_insert.

In [29]:
{
    let mut s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    s.replace(1);
    s
}
Out[29]:
{2, 4, 0, 3, 1}
In [30]:
{
    let mut s: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    s.replace(100);
    s
}
Out[30]:
{2, 3, 0, 100, 4, 1}

BTreeSet as An Alternative to HashSet

BTreeSet is implemented based on B-Tree (binary search tree with each node containing a continuous array to improve caching performance). The main feature of BTreeSet compared to HashSet is that elements in a BTreeSet are sorted!

In [3]:
use std::collections::BTreeSet;
In [6]:
let s: BTreeSet<i32> = [0, 1, 2, 3, 4, 2, 3, 4, 3, 4, 4].iter().cloned().collect();
s
Out[6]:
{0, 1, 2, 3, 4}
In [5]:
let s = BTreeSet::from([0, 1, 2, 3, 4, 2, 3, 4, 3, 4, 4]);
s
Out[5]:
{0, 1, 2, 3, 4}

References

Module std::collections

Struct std::collections::HashSet

Struct std::collections::BTreeSet

Struct std::collections::BTreeMap

Rust Collections Case Study: BTreeMap

In [ ]:

Comments