Example of Rust specialization used for specializing structs ala C++

specialization.rs

#![feature(specialization)]

// feature(specialization) is still unstable as per https://github.com/rust-lang/rust/issues/31844>, but min_specialization is not enough for what we want to do, unless we use dyn.

struct VecOrBitset<T: MaybeSpecializedOn> {
    inner: T::VecOrBitsetType
}

impl<T: MaybeSpecializedOn> VecOrBitset<T> {
    fn new(x: impl IntoIterator<Item = T>) -> Self {
        Self {inner: T::VecOrBitsetType::new(x.into_iter())}
    }
    fn get(&self, index: usize) -> Option<&T> {
        self.inner.get(index)
    }
}

trait MaybeSpecializedOn : Sized {
    type VecOrBitsetType : VecOrBitsetImplementation<Item = Self>;
}
impl<T> MaybeSpecializedOn for T {
    default type VecOrBitsetType = VecOrBitsetGeneric<T>;
}
impl MaybeSpecializedOn for bool {
    type VecOrBitsetType = VecOrBitsetBool;
}

trait VecOrBitsetImplementation {
    type Item;
    fn new(x: impl Iterator<Item = Self::Item>) -> Self;
    fn get(&self, index: usize) -> Option<&Self::Item>;
}

#[derive(Default)]
struct VecOrBitsetBool {
    elements: Vec<i8>,
    last_element_size: i8,
}

const TRUE: bool = true;
const FALSE: bool = false;

impl VecOrBitsetImplementation for VecOrBitsetBool {
    type Item = bool;
    fn new(x: impl Iterator<Item = bool>) -> Self {
        let mut result = Self {elements: Vec::with_capacity(x.size_hint().0), last_element_size: 0};
        for bit in x {
            if result.last_element_size == 0 {
                result.elements.push(0);
            }
            let last = result.elements.last_mut().unwrap();
            *last |= (bit as i8) << result.last_element_size;
            result.last_element_size = (result.last_element_size + 1) % 8;
        }
        result
    }
    fn get(&self, index: usize) -> Option<&bool> {
        println!("Hello from bool specialization!");
        if index >= (self.elements.len() - 1) * 8 + (self.last_element_size as usize) {
            None
        } else {
            self.elements.get(index / 8).map(|x| ((x >> (index % 8)) & 1) == 1).map(|x| if x { &TRUE } else { &FALSE })
        }
    }
}


struct VecOrBitsetGeneric<T> {
    elements: Vec<T>,
}

impl<T> VecOrBitsetImplementation for VecOrBitsetGeneric<T> {
    type Item = T;
    fn new(x: impl Iterator<Item = T>) -> Self {
        Self {elements: x.collect()}
    }
    fn get(&self, index: usize) -> Option<&T> {
        println!("Hello from generic specialization!");
        self.elements.get(index)
    }
}

fn main() {
    println!("Hello, world!");
    
    let a = VecOrBitset::new([true, false, false]);
    let b = VecOrBitset::new([1, 2, 3]);
    
    println!("{}", a.get(1).unwrap()); // Hello from bool specialization!
                                       // false
    println!("{}", b.get(2).unwrap()); // Hello from generic specialization!
                                       // 3
}