rust - 如何将 SmallVec 与 Cow 一起使用

Question

我想将 SmallVec 与 Cow 一起使用。我试过这个:

use smallvec::SmallVec;
use std::borrow::Cow;

fn main() {
    let s = "hello world".to_owned();
    let mut s = Cow::Borrowed(s.as_bytes());
    clear_subslice(&mut s, 2, 6);
}

fn clear_subslice(text: &mut Cow<'_, [u8]>, start: usize, end: usize) {
    match text {
        Cow::Borrowed(v) => {
            if !v[start..end].iter().all(|&c| c == b' ') {
                let mut v = SmallVec::from_slice(v);
                v[start..end].iter_mut().for_each(|c| *c = b' ');
                *text = Cow::Owned(v);
            }
        }
        Cow::Owned(v) => {
            v[start..end].iter_mut().for_each(|c| *c = b' ');
        }
    }
}

error[E0271]: type mismatch resolving `<[u8] as std::borrow::ToOwned>::Owned == smallvec::SmallVec<_>`
  --> src/main.rs:16:25
   |
16 |                 *text = Cow::Owned(v);
   |                         ^^^^^^^^^^^^^ expected struct `std::vec::Vec`, found struct `smallvec::SmallVec`
   |
   = note: expected type `std::vec::Vec<u8>`
              found type `smallvec::SmallVec<_>`

它只适用于为特定类型实现了 ToOwned 的类型。在这种情况下，&[u8] 具有使用目标 Vec 实现的 ToOwned。

我尝试实现ToOwned，目标为SmallVec，但没有成功。

是否可以将 SmallVec 与 Cow 一起使用？

我知道的一种解决方案是使用自定义 Cow 枚举:

pub enum SmallCow<'a, A: Array> {
    Borrowed(&'a [A::Item]),
    Owned(SmallVec<A>),
}

还有其他办法吗？

Answer 1

事实是Cow<'a, T>需要 T实现ToOwned和 Cow<'a, T> 的拥有版本是关联类型 Owned的 ToOwned .此外，Owned , 必须实现 Borrow<T> .就目前而言，Cow<'a, [u8]> 只能使用 Vec<u8>作为其拥有的变体，因为 [T]工具 ToOwned与 Vec<T>作为 Owned关联类型。

我看到两个选项供您选择。您可以自己实现 Cow使用不同特征边界的(或者如您所建议的，只是专门针对您的确切用例)，或者您可以使用新类型来包装 [u8]和 SmallVec<A>并实现 ToOwned在 [u8] 的 wrapper 上和 Borrow<SliceWrapper<u8>>在 SmallVec<A> 的 wrapper 上.我将专注于后者，因为您似乎已经涵盖了前者。

新类型是一个包装器，本质上，它声明了一个新类型，它等同于原始类型，但没有任何特征或方法。通常的方法是使用元组结构。

use small_vec::{Array, SmallVec};

struct SmallVecWrap<A: Array>(SmallVec<A>);

struct SliceWrap<T>([T]);

注意 SliceWrap<T>自 [T] 以来是未调整大小的类型是的，所以我们总是在指针后面使用它。我们这样做很重要，因为当我们实现 Borrow 时在 SmallVecWrap<A> , 它将是 Borrow<SliceWrap<T>> , 而不是 Borrow<&SliceWrap<T>> .即 Borrow使用未调整大小的类型作为其类型参数(我想没有它可能是可能的，但你会有一个额外的间接层，你将无法在切片)。

我在使用这种方法时遇到的一个主要问题是似乎没有办法将 &[u8]进入&SliceWrap<u8>没有不安全的 block 。这确实有一定的意义，因为在没有任何额外信息的情况下，这两种类型在语义上可能是不同的。例如，NonZeroU8处于类似情况，但转换 u8 没有意义进入NonZeroU8不检查它是否为零。 RFC#1909，unsized rvalues，可能对此有所帮助，但我无法让它工作。我会注意到 MIRI 在您的测试用例上运行时没有发现任何问题。

这种方法的另一个问题是，您必须始终遵循包装类型(例如示例代码中的 v.0)，然后可能重新包装返回值，或者重新实现您需要的所有特征和方法。同样的问题适用于 SmallCow<'a, A>方法，但您只需要实现 Cow<'a, T>的特征和方法，而且没有那么多。

如果您决定始终遵循包装类型的方法，您可能希望将新类型的字段公开(例如 SliceWrap<T>(pub [T]) )，以便您可以在这个模块之外使用它们。

这种方法的最后一个问题还是 ToOwned . ToOwned需要单一类型转换为 SmallVecWrap<A>不是单一类型，即使 A 的元素类型是固定的。例如，&[u8]可以有效地转换为 SmallVecWrap<[u8, 1]> , SmallVecWrap<[u8, 2]>等。一种可能的解决方法是附加类型 A至 SliceWrap<T> :

struct SliceWrap<T, A: Array> {
    array: std::marker::PhantomData<A>,
    slice: [T],
}

然后你可以实现ToOwned对于 SliceWrap<T, A>与 Owned作为SmallVecWrap<A> .

无论如何，这是完整的示例。

use smallvec::{Array, SmallVec}; // 0.6.10
use std::borrow::{Borrow, Cow, ToOwned};

struct SmallVecWrap<A: Array>(SmallVec<A>);

#[repr(transparent)]
struct SliceWrap<T>([T]);

impl<T> SliceWrap<T> {
    // for convenience
    fn from_slice(slice: &[T]) -> &Self {
        // As far as I can tell, there's no way to do this without unsafe.
        // This should be safe since SliceWrap<T> is transparently a [T].
        // All we're doing is changing a (fat) pointer to a [T]
        // into a (fat) pointer to SliceWrap<T>.
        // I won't claim expertise on this, though.
        unsafe { &*((slice as *const [T]) as *const SliceWrap<T>) }
        //          ^                   ^
        // These parentheses aren't needed, but it's clearer this way
    }

    // I guess we didn't need this
    #[allow(dead_code)]
    fn from_mut_slice(slice: &mut [T]) -> &mut Self {
        // Same caveats apply
        unsafe { &mut *((slice as *mut [T]) as *mut SliceWrap<T>) }
    }
}

impl<A: Array> Borrow<SliceWrap<A::Item>> for SmallVecWrap<A> {
    fn borrow(&self) -> &SliceWrap<A::Item> {
        SliceWrap::from_slice(self.0.borrow())
    }
}

// Note: We have to choose a particular array size
// to use for the owned SmallVec<A>.
const OWNED_ARRAY_SIZE: usize = 4;
impl<T: Clone> ToOwned for SliceWrap<T> {
    type Owned = SmallVecWrap<[T; OWNED_ARRAY_SIZE]>;

    fn to_owned(&self) -> SmallVecWrap<[T; OWNED_ARRAY_SIZE]> {
        SmallVecWrap(self.0.into())
    }
}

fn main() {
    let s = "hello world".to_owned();
    let mut s = Cow::Borrowed(SliceWrap::from_slice(s.as_bytes()));
    clear_subslice(&mut s, 2, 6);
}

fn clear_subslice(text: &mut Cow<'_, SliceWrap<u8>>, start: usize, end: usize) {
    match text {
        Cow::Borrowed(v) => {
            if !v.0[start..end].iter().all(|&c| c == b' ') {
                let mut v = SmallVec::from_slice(&v.0);
                v[start..end].iter_mut().for_each(|c| *c = b' ');
                *text = Cow::Owned(SmallVecWrap(v));
            }
        }
        Cow::Owned(v) => {
            v.0[start..end].iter_mut().for_each(|c| *c = b' ');
        }
    }
}

(playground)

---

您还有第三种选择:不要使用 SmallVec<A>除非您已经进行基准测试并确定这些小分配会显着减慢您的程序。