使用泛型作为位向量时,不能应用二进制操作!=

Question

我正在实现一个Bit Vector类作为练习,但是只知道Rust不到一周,我遇到了以下代码的问题:

use std::cmp::Eq;
use std::ops::BitAnd;
use std::ops::Index;
use std::ops::Not;

struct BitVector<S = usize> 
    where S: Sized + BitAnd<usize> + Not + Eq {
    data: Vec<S>,
    capacity: usize
}

impl<S> BitVector<S>
    where S: Sized + BitAnd<usize> + Not + Eq {
    fn with_capacity(capacity: usize) -> BitVector {
        let len = (capacity / (std::mem::size_of::<S>() * 8)) + 1;
        BitVector { data: vec![0; len], capacity: capacity }
    }
}

impl<S> Index<usize> for BitVector<S>
    where S: Sized + BitAnd<usize> + Not + Eq {
    type Output = bool;

    fn index(&self, index: usize) -> &bool {
        let data_index = index / (std::mem::size_of::<S>() * 8);
        let remainder = index % (std::mem::size_of::<S>() * 8);
        (self.data[data_index] & (1 << remainder)) != 0
    }
}

这个想法是S可以的,例如一个u8,u16,u32,u64并usize确保其设置为0在with_capacity创建一个位值S由所有零的.

我得到的错误如下:

lib.rs:27:10:27:50错误:二进制操作!=不能应用于<S as std::ops::BitAnd<usize>>::Output[E0369]
lib.rs:27(self.data [data_index]&(1 << remaining))!= 0
^ ~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lib.rs:27:10:27:50求助:运行rustc --explain E0369看一下
lib.rs:27:10:27:50 的详细解释注意:lib.rs:27 std::cmp::PartialEq可能缺少一个实现<S as std::ops::BitAnd<usize>>::Output
(self.data [data_index]&(1 << remainder))!= 0 ^〜 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
错误:中止由于先前的错误
错误:无法编译bit-vector.

Answer 1

这里这个特殊的错误,简单来说,是指Output的BitAndING S和usize没有实现PartialEq.一个解决将是增加一个约束S的BitAnd<usize>小号Output是S:

BitAnd<usize, Output = S>

在此之后,您将遇到另一个错误,因为您正在比较BitAnd的值0而不是类型的值S.要修复它你可以定义自己的Zero特性并使用它或使用Rust的不稳定std::num::Zero并比较S::zero().

您还必须S: Copy这样做,以便BitAnd不消耗该值(或S: Clone在调用之前添加并显式克隆BitAnd::bitand).

最后你会遇到一个错误,你index必须返回一段&bool时间才能返回bool.您可以使用技巧bit-vec用于定义2个静态:

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

返回&TRUE或&FALSE从index.

最终工作(每夜)代码:

#![feature(zero_one)]

use std::cmp::Eq;
use std::num::Zero;
use std::ops::BitAnd;
use std::ops::Index;
use std::ops::Not;

struct BitVector<S = usize>
    where S: Sized + BitAnd<usize, Output = S> + Not + Eq + Copy + Zero
{
    data: Vec<S>,
    capacity: usize,
}

impl<S> BitVector<S>
    where S: Sized + BitAnd<usize, Output = S> + Not + Eq + Copy + Zero
{
    fn with_capacity(capacity: usize) -> BitVector {
        let len = (capacity / (std::mem::size_of::<S>() * 8)) + 1;
        BitVector {
            data: vec![0; len],
            capacity: capacity,
        }
    }
}

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

impl<S> Index<usize> for BitVector<S>
    where S: Sized + BitAnd<usize, Output = S> + Not + Eq + Copy + Zero
{
    type Output = bool;

    fn index(&self, index: usize) -> &bool {
        let data_index = index / (std::mem::size_of::<S>() * 8);
        let remainder = index % (std::mem::size_of::<S>() * 8);
        if (self.data[data_index] & (1 << remainder)) != S::zero() {
            &TRUE
        } else {
            &FALSE
        }
    }
}

fn main() {
}