Implementing Custom Collections

When domain requirements call for a specialized data structure—such as a fixed-capacity ring buffer, a dense bitset, an LRU cache, or a trie—implementing a custom collection in Rust follows standard library trait conventions so the collection integrates seamlessly with indexing (col[i]), collect(), extend(), and standard formatting.

Standard Trait Checklist for a Custom Collection `MyCollection<T>`:
  1. Construction:  `Default`, `with_capacity(n)`, `FromIterator<T>` (enables `.collect()`)
  2. Mutation:      `Extend<T>` (enables `.extend(iter)`)
  3. Inspection:    `len(&self) -> usize`, `is_empty(&self) -> bool`
  4. Indexing:      `Index<Idx>` & `IndexMut<Idx>` (enables `col[i]`)
  5. Value Traits:  `Debug`, `Clone`, `PartialEq`, `Eq`, `Hash`
  6. Iteration:     `IntoIterator` for `MyCollection<T>`, `&MyCollection<T>`, `&mut MyCollection<T>`

Implementing a Dense BitSet Collection with Standard Traits

Instead of storing Vec<bool> (which uses 1 full byte / 8 bits per boolean), a dense BitSet packs 64 boolean flags into each u64 word—cutting memory usage by 8x and allowing bitwise set operations (union, intersection, count_ones) to process 64 elements per CPU instruction:

use std::fmt;
use std::iter::FromIterator;

#[derive(Clone, PartialEq, Eq, Default)]
pub struct BitSet {
    words: Vec<u64>,
}

impl BitSet {
    pub fn with_bit_capacity(bits: usize) -> Self {
        let num_words = bits.div_ceil(64);
        Self {
            words: vec![0u64; num_words],
        }
    }

    #[inline]
    pub fn insert(&mut self, bit: usize) {
        let word_idx = bit / 64;
        let bit_offset = bit % 64;
        if word_idx >= self.words.len() {
            self.words.resize(word_idx + 1, 0);
        }
        self.words[word_idx] |= 1u64 << bit_offset;
    }

    #[inline]
    pub fn remove(&mut self, bit: usize) -> bool {
        let word_idx = bit / 64;
        let bit_offset = bit % 64;
        if let Some(word) = self.words.get_mut(word_idx) {
            let mask = 1u64 << bit_offset;
            let was_set = (*word & mask) != 0;
            *word &= !mask;
            was_set
        } else {
            false
        }
    }

    #[inline]
    pub fn contains(&self, bit: usize) -> bool {
        let word_idx = bit / 64;
        let bit_offset = bit % 64;
        self.words
            .get(word_idx)
            .is_some_and(|&w| (w & (1u64 << bit_offset)) != 0)
    }

    /// Counts total set bits in O(words) using the hardware `POPCNT` instruction!
    pub fn len(&self) -> usize {
        self.words.iter().map(|w| w.count_ones() as usize).sum()
    }

    pub fn is_empty(&self) -> bool {
        self.words.iter().all(|&w| w == 0)
    }

    /// Computes in-place set intersection (`self &= other`) at 64 bits per cycle!
    pub fn intersect_with(&mut self, other: &Self) {
        self.words.truncate(other.words.len());
        for (a, &b) in self.words.iter_mut().zip(other.words.iter()) {
            *a &= b;
        }
    }
}

/// Implementing `FromIterator<usize>` allows `.collect::<BitSet>()` on any iterator!
impl FromIterator<usize> for BitSet {
    fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
        let mut set = Self::default();
        set.extend(iter);
        set
    }
}

/// Implementing `Extend<usize>` allows `set.extend(...)`!
impl Extend<usize> for BitSet {
    fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I) {
        for bit in iter {
            self.insert(bit);
        }
    }
}

impl fmt::Debug for BitSet {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut list = f.debug_set();
        for (word_idx, &word) in self.words.iter().enumerate() {
            let mut rem = word;
            while rem != 0 {
                let tz = rem.trailing_zeros() as usize;
                list.entry(&(word_idx * 64 + tz));
                rem &= rem - 1; // Clear lowest set bit (`blsr` instruction)
            }
        }
        list.finish()
    }
}

fn main() {
    // Collect directly into our custom `BitSet` via `FromIterator`!
    let mut set_a: BitSet = [1, 5, 64, 130].into_iter().collect();
    let set_b: BitSet = [5, 12, 130, 200].into_iter().collect();

    assert_eq!(set_a.len(), 4);
    assert!(set_a.contains(64));
    assert!(!set_a.contains(63));

    set_a.intersect_with(&set_b);
    println!("Intersection BitSet (len={}): {set_a:?}", set_a.len());
}

Intersection BitSet (len=2): {5, 130}