如何为 Bitvector 实现自定义切片

Question

我正在实现一个 Bitvector。我的问题是 - 如何实现切片功能？这是我的代码（我在代码之后尝试过的事情）：

use core::ops::Range;
use std::ops::Index;

pub struct Bitvec {
    vec: Vec<u8>,
}

impl Bitvec {
    pub fn new(capacity: usize) -> Bitvec {
        Bitvec {
            vec: Vec::with_capacity(capacity),
        }
    }

    pub fn bit_at(&self, index: usize) -> bool {
        let mask = 2u8.pow(7 - (index % 8) as u32);
        self.vec.get(index / 8).unwrap() & mask == mask
    }

    pub fn push(&mut self, val: u8) {
        self.vec.push(val);
    }
}

impl Index<usize> for Bitvec {
    type Output = bool;
    fn index(&self, index: usize) -> &Self::Output {
        match self.bit_at(index) {
            true => &true,
            false => &false,
        }
    }
}

impl Index<Range<usize> for Bitvec {
    type Output = ??;
    fn index(&self, index: Range<usize>) -> &Self::Output {
        //What should go here?
    }
}

fn main() {
    let mut bv = Bitvec::new(20);
    bv.push(0b1011_0011);
    assert_eq!(bv.bit_at(0), true);
    assert_eq!(bv.bit_at(1), false);

    assert_eq!(bv[0], true);
    assert_eq!(bv[1], false);

    let slice = bv[2..4]; //should return a slice that represents the two bits of [11]
}

Bitvec 的 Index 的含义是什么 return?

我尝试过的事情：

创建一个包含开始和结束的结构 BitSlice，然后 returning 那个。由于我需要让 BitSlice 持有对 Bitvec 的引用，因此我最终与借用检查器进行了一辈子的斗争。也不能 return 来自 index(...) 函数的 &BitSlice。
让 Bitvec 拥有一个 BitSlice，但运行陷入类似的问题，其中 BitSlice 和 Bitvec 相互引用
让 Bitvec 拥有一个 Option，但运行也会遇到生命周期问题。

Answer 1

像 &str 或 &[u8] 这样的切片类型是胖指针，包含指向某些数据的指针和长度。类型 &[T] 是结构的语法糖，类似于：

struct Slice<'a, T> {
    data: *const T,
    len: usize,
    _lifetime: PhantomData<&'a T>,
}

需要注意的是 ABI 不稳定，因此您不能对这些字段的顺序做出任何假设。

指针总是指向一个字节，而不是一个位，因此指向 BitVec 切片的胖指针还需要包含切片在第一个字节内开始位置的位偏移量：

pub struct BitSlice<'a> {
    offset: u8,
    len: usize,
    ptr: *const u8,
    _lifetime: PhantomData<&'a u8>,
}

你可以构造其中之一，但是Index::index特征方法returns&Self::Output。无法将 BitSlice<'a> 转换为 &'a [T]。

可能可以将长度和偏移量合并为一个 usize，并且要非常小心地访问它。 Here's a semi-complete sketch，但该实现中可能存在健全性漏洞。当然，如果你是 Rust 初学者，你不应该尝试它！

如何为 Bitvector 实现自定义切片

How to implement a custom slice for a Bitvector

boolean

slice

rust

data-structures