如何创建堆栈分配的类似矢量的容器？

Question

您将如何创建一个堆栈分配的类似向量的容器，它可以包含一个固定的元素数量上限？你可以在下面看到我的尝试，但它没有编译：

// The following is at crate level
#![feature(unsafe_destructor)]

use std::mem;
use std::ptr;
use std::slice::Iter;

pub struct StackVec<T> {
    buf: [T; 10],
    len: usize,
}

impl<T> StackVec<T> {
    pub fn new() -> StackVec<T> {
        StackVec {
            buf: unsafe { mem::uninitialized() },
            len: 0,
        }
    }

    pub fn iter(&self) -> Iter<T> {
        (&self.buf[..self.len]).iter()
    }

    pub fn push(&mut self, value: T) {
        unsafe { ptr::write(self.buf.get_mut(self.len).unwrap(), value); }
        self.len += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            None
        } else {
            unsafe {
                self.len -= 1;
                Some(ptr::read(self.buf.get(self.len).unwrap()))
            }
        }
    }
}

#[unsafe_destructor]
impl<T> Drop for StackVec<T>
    where T: Drop
{
    fn drop(&mut self) {
        for elem in self.iter() {
            unsafe { ptr::read(elem); }
        }
        unsafe { mem::forget(self.buf); } // ERROR: [1]
    }
}

这是我得到的编译时错误：
[1] 错误：无法移出类型 stackvec::StackVec<T>，它定义了 Drop 特征

Answer 1

我的猜测是编译器不知道数组的哪些元素是 "free" 以及当删除数组时哪些元素需要运行的析构函数。

尝试存储 Option<T>，它有一个 .take() 方法，可以让您将元素移出数组。

Answer 2

我已经写了一个实现，我将回顾重点。

完整代码可在 crates.io/arrayvec (API doc)
使用特征（称为 Array）对不同的数组大小进行抽象。它需要提供原始指针，以便我们可以将数组用作后备存储。

/// Trait for fixed size arrays.
pub unsafe trait Array {
    /// The array's element type
    type Item;
    unsafe fn new() -> Self;
    fn as_ptr(&self) -> *const Self::Item;
    fn as_mut_ptr(&mut self) -> *mut Self::Item;
    fn capacity() -> usize;
}

在当代的 Rust 风格中，我们只能为特定的数组大小实现这个特性。我用宏覆盖了一些小尺寸：

macro_rules! fix_array_impl {
    ($len:expr ) => (
        unsafe impl<T> Array for [T; $len] {
            type Item = T;
            /// Note: Returning an uninitialized value here only works
            /// if we can be sure the data is never used. The nullable pointer
            /// inside enum optimization conflicts with this this for example,
            /// so we need to be extra careful. See `Flag` enum.
            unsafe fn new() -> [T; $len] { mem::uninitialized() }
            fn as_ptr(&self) -> *const T { self as *const _ as *const _ }
            fn as_mut_ptr(&mut self) -> *mut T { self as *mut _ as *mut _}
            fn capacity() -> usize { $len }
        }
    )
}

macro_rules! fix_array_impl_recursive {
    () => ();
    ($len:expr, $($more:expr,)*) => (
        fix_array_impl!($len);
        fix_array_impl_recursive!($($more,)*);
    );
}

fix_array_impl_recursive!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
                          16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
                          32, 40, 48, 56, 64, 72, 96, 128, 160, 192, 224,);

我们需要抑制嵌入数组的默认丢弃。您可以通过在理论上使用 Option<Array> 并在 Drop.

ptr::write

None

但我们必须使用我们自己的枚举，类似于Option，原因之一：我们需要避免适用的非空指针优化与 Option 具有相同表示的枚举。然后在 Drop 中，我们对内部数组的默认析构函数进行了关键的抑制：我们强行覆盖了我们的枚举。当然，只有在销毁所有元素之后。

/// Make sure the non-nullable pointer optimization does not occur!
#[repr(u8)]
enum Flag<T> {
    Dropped,
    Alive(T),
}

/// A vector with a fixed capacity.
pub struct ArrayVec<A: Array> {
    len: u8,
    xs: Flag<A>,
}

impl<A: Array> Drop for ArrayVec<A> {
    fn drop(&mut self) {
        // clear all elements, then inhibit drop of inner array
        while let Some(_) = self.pop() { }
        unsafe {
            ptr::write(&mut self.xs, Flag::Dropped);
        }
    }
}

我们实施 Deref<Target=[T]> 和 DerefMut 并免费获得大量切片方法。这是 Rust 的一大特色！

impl<A: Array> Deref for ArrayVec<A> {
    type Target = [A::Item];
    fn deref(&self) -> &[A::Item] {
        unsafe {
            slice::from_raw_parts(self.inner_ref().as_ptr(), self.len())
        }
    }
}

ArrayVec 类型有一个不变量，当值存在时 Flag<A> 总是 Flag::Alive(A)。考虑到这一点，我们应该能够进行优化。（一个 FIXME 被标记在那里。）

fn inner_mut(&mut self) -> &mut A {
    // FIXME: Optimize this, we know it's always present.
    match self.xs {
        Flag::Alive(ref mut xs) => xs,
        _ => unreachable!(),
    }
}

谢谢 kmky 的提问！探索这个答案导致了上面链接的 arrayvec 的创建，并发现了一些使其成为安全的 Rust 数据结构非常重要的要点。

如何创建堆栈分配的类似矢量的容器？

How can I create a stack-allocated vector-like container?

vector

stack

rust