Rust 标准库学习:Vec

图片来自pexels.com

接下来的系列博客文章将包含我对Rust 标准库的研究。我已经在分散的地方编写了本系列的部分内容,希望将它们集中在一个地方,以便更好、更容易地访问。每当我发现一些有趣/重要的事情需要记住时,我就会更新。

我指的是Rust stable v1.33.0中的实现。

这篇文章涵盖了我认为重要的std::vec的一些细节。

Vec<T>

Vec<T> 是一个动态数组,它只会自动增长而不会自动收缩。

具有堆分配内容的连续可增长数组类型。

Rust std doc

注意其对应的堆栈分配的固定大小数组[T; N]之间的差异 (此时N需要是一个指定的非负整数。常量泛型有望很快出现)。

好的!让我们开始吧。Vec<T> 包含(指针容量长度)。

Vec 指针

  1. 指针永远不会为空(never be null),因此它享受空指针优化(null-pointer-optimization)。
  2. 指针可能不会实际指向已分配的内存,例如Vec::new(), vec![]Vec::with_capacity(0)

Vec 容量和长度

  1. 向量的容量是指分配给未来元素的空间量,这些元素将被添加到向量上。
  2. 长度是在向量中推入/插入的实际元素的数量。
  3. Vec 分配内存 mem::size_of::<T>() * capacity() > 0. 因此,即使具有正容量,也不会为零大小型(ZST)分配。
  4. 当长度与容量匹配时, 将按一定的增长因子进行(重新)分配。 这使得插入 amortized O(1) 。现在 的增长因子是2。 但是,与其他语言(如C ++,Java等)相比,鉴于任何全局首选分配器,它似乎并不是最佳选择。 启发式的, 1.5 或者比黄金比例略小的数字被认为是最佳的。这是当前打开的相关 issue,我发现很有趣。
  5. 缩水因子呢?比如, 如果我们取出一半的元素,将释放四分之一的内存? 不,实际上!如果取出所有元素,容量将不会改变,从而在堆上留下一个漏洞。 因此,如果你要释放一些内存,请使用shrink_to_fit
  6. 如果需要将 Vec 用于 FFI 或作为 memory-backed 的集合,请确保使用from_raw_parts释放内存,然后显式删除。
  7. 如果在FFI中使用并且需要作为指针传递,为了安全起见请记住在传递(as_mut_ptr() or as_ptr())之前调用 shrink_to_fittruncate 以避免传递未初始化的内存缓冲区。
  8. 如果 coerced into slice,元素的顺序总是保证相同。

这是简化的定义:

struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

// Default Global allocator
struct RawVec<T, A: Alloc = Global> {
    ptr: Unique<T>,
    cap: usize,
    a: A,
}

#[repr(transparent)]
struct Unique<T: ?Sized> {
    pointer: *const T,
    _marker: PhantomData<T>,
}

Unique<T>

  1. #[repr(transparent)] 强制 Unique<T>类型与 *const T 保持一致。
  2. Unique<T>*mut T (wrt T) 的协变版本,并且具有比 NonNull<T>更强的语义。
  3. *mut T不同, 指针必须总是为 non-null.
  4. 事实上, Box<T> 包装了 Unique<T>,即 struct Box<T: ?Sized>(Unique<T>)
  5. 它可以在 nightly 版本使用,通过 #![feature(ptr_internals)] and core::ptr::Unique
  6. 如果 TSend/Sync 那么 Unique<T> 也是 Send/Sync
  7. PhantomData<T>标记的仅对于 rustc dropck 才能理解我们逻辑上拥有一个T导致Unique<T>NonNull<T>之间的主要区别,其中它被定义为
// NonNull<T> doesn't own the referent whereas Unique<T> does
#[repr(transparent)]
struct NonNull<T: ?Sized> {
    pointer: *const T,
}

本文翻译自 Rust std study series: Vec

发表评论

电子邮件地址不会被公开。 必填项已用*标注

+ 74 = 77