如何将 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] 使用 Vec<T> 实现 ToOwned 作为Owned 关联类型。

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

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

use small_vec::{Array, SmallVec};

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

struct SliceWrap<T>([T]);

请注意 SliceWrap<T> 是一个未定大小的类型，因为 [T] 是，所以我们总是在指针后面使用它。我们这样做很重要，因为当我们在 SmallVecWrap<A> 上实施 Borrow 时，它将是 Borrow<SliceWrap<T>>，而不是 Borrow<&SliceWrap<T>>。也就是说，Borrow 使用未确定大小的类型作为其类型参数（我想可能没有它就可以做到，但是你会有一个额外的间接层，你将无法在切片上使用变异方法）。

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

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

如果您决定始终遵循包装类型的方法，您可能希望将新类型的字段设置为 public（例如 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],
}

然后你可以为 SliceWrap<T, A> 实现 ToOwned，用 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>，除非您已进行基准测试并确定这些小分配会显着降低您的程序速度。

如何将 SmallVec 与 Cow 一起使用

How to use SmallVec with Cow

copy-on-write

rust