如何创建堆栈分配的类向量容器? [英] How can I create a stack-allocated vector-like container?

问题描述

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

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] 错误:无法移出类型 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 文档)

使用特征(称为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 风格中，我们只能为特定的数组大小实现这个特性.我用宏覆盖了一些小尺寸:

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

  • 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 和 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.

    这篇关于如何创建堆栈分配的类向量容器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！