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

How would you go about creating a stack-allocated vector-like container with some fixed upper limit on the number of elements it can contain? You can see my attempt at this below, but it doesn't compile:

// 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] error: cannot move out of type stackvec::StackVec，它定义了Drop trait

This is the compile-time error I get: [1] error: cannot move out of type stackvec::StackVec<T>, which defines the Drop trait

推荐答案

我已经写了一个实现，我会回顾一下亮点.

I've written an implementation, and I'll go over the highlights.

完整代码可在 crates.io/arrayvec (API 文档)

使用 trait(称为 Array)对不同的数组大小进行抽象.它需要提供原始指针，以便我们可以将数组用作后备存储.

Use a trait (called Array) to abstract over different array sizes. It needs to provide raw pointers so that we can use the array as backing storage.

/// 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 风格中，我们只能为特定的数组大小实现此 trait.我用宏覆盖了一些小尺寸:

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> 并使用 ptr::write 在最后时刻用 None 覆盖它来做到这一点代码>丢弃.

We need to suppress the default drop of the embedded array. You can do this by in theory using Option<Array> and using ptr::write to overwrite it with None at the last moment in Drop.

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

We must however use our own enum, similar to Option for one reason: We need to avoid non-nullable pointer optimization that applies to enums that have the same representation as Option. Then in Drop we do the crucial inhibition of the inner array's default destructor: we forcibly overwrite our enum. Only after destructing all the elements, of course.

/// 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 的一大特色！

We implement Deref<Target=[T]> and DerefMut and get tons of slice methods for free. This is a great feature of 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 始终为 Flag::Alive(A).考虑到这一点，我们应该能够进行优化.(此处标记了 FIXME.)

The ArrayVec type has an invariant, that the Flag<A> is always Flag::Alive(A) when the value is alive. We should be able to optimize with this in mind. (A FIXME is marked there.)

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 数据结构非常重要的点.

Thank you kmky for asking question! Exploring this answer led to the creation of arrayvec linked above, and uncovered some of the points that were very important to have it be a safe rust data structure.