gpt4 book ai didi

vector - 如何创建堆栈分配的类似矢量的容器?

转载 作者:行者123 更新时间:2023-11-29 07:46:42 25 4
gpt4 key购买 nike

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

// 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性状

最佳答案

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

  • 完整代码可在 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> 来做到这一点并使用 ptr::writeNone 覆盖它在 Drop 的最后一刻.

  • 但是我们必须使用我们自己的枚举,类似于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 数据结构非常重要的要点。

关于vector - 如何创建堆栈分配的类似矢量的容器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29239586/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com