data-structures - 一种调整堆栈大小(或其他可动态调整大小的类型)的方法

Question

首先，我读过这个问题:

• What's the right way to make a stack (or other dynamically resizable vector-like thing) in Rust?

问题

所选答案只是告诉提问者使用标准库而不是解释实现，如果我的目标是构建一些东西，这很好。除了我正在尝试了解堆栈的实现，同时遵循为 Java 编写的数据结构教科书 (Robert Sedgwick 和 Kevin Wayne 的算法)，他们通过调整数组的大小来实现堆栈 < em>(第 136 页)。

我正在实现 resize 方法，结果发现数组的大小需要是一个常量表达式。

meta: are arrays in rust called slices?

use std::mem;

struct DynamicStack<T> {
  length: uint,
  internal: Box<[T]>,
}

impl<T> DynamicStack<T> {
  fn new() -> DynamicStack<T> {
    DynamicStack {
      length: 0,
      internal: box [],
    }
  }

  fn resize(&mut self, new_size: uint) {
    let mut temp: Box<[T, ..new_size]> = box unsafe { mem::uninitialized() };

    // ^^ error: expected constant expr for array 
    // length: non-constant path in constant expr

    // code for copying elements from self.internal

    self.internal = temp;
  }
}

为简洁起见，编译器错误是这样的

.../src/lib.rs:51:23: 51:38 error: expected constant expr for array length: non-constant path in constant expr
.../src/lib.rs:51     let mut temp: Box<[T, ..new_size]> = box unsafe { mem::uninitialized() };
                                        ^~~~~~~~~~~~~~~
.../src/lib.rs:51:23: 51:38 error: expected constant expr for array length: non-constant path in constant expr
.../src/lib.rs:51     let mut temp: Box<[T, ..new_size]> = box unsafe { mem::uninitialized() };
                                        ^~~~~~~~~~~~~~~

问题

当然有一种方法可以在 Rust 中初始化一个数组，其大小在运行时确定(即使它是不安全的)？您能否也解释一下您的回答中发生了什么？

其他尝试

我认为有可能实现堆栈

struct DynamicStack<T> {
  length: uint,
  internal: Box<Optional<T>>
}

但我不想通过匹配可选值的开销来去除不安全的内存操作，但这仍然没有解决未知数组大小的问题。

我也试过这个(甚至没有编译)

fn resize(&mut self, new_size: uint) {
  let mut temp: Box<[T]> = box [];
  let current_size = self.internal.len();

  for i in range(0, current_size) {
    temp[i] = self.internal[i];
  }
  for i in range(current_size, new_size) {
    temp[i] = unsafe { mem::uninitialized() };
  }

  self.internal = temp;
}

我得到了这个编译器错误

.../src/lib.rs:55:17: 55:21 error: cannot move out of dereference of `&mut`-pointer
.../src/lib.rs:55       temp[i] = self.internal[i];
                                  ^~~~
.../src/lib.rs:71:19: 71:30 error: cannot use `self.length` because it was mutably borrowed
.../src/lib.rs:71       self.resize(self.length * 2);
                                    ^~~~~~~~~~~
.../src/lib.rs:71:7: 71:11 note: borrow of `*self` occurs here
.../src/lib.rs:71       self.resize(self.length * 2);
                        ^~~~
.../src/lib.rs:79:18: 79:22 error: cannot move out of dereference of `&mut`-pointer
.../src/lib.rs:79     let result = self.internal[self.length];
                                   ^~~~
.../src/lib.rs:79:9: 79:15 note: attempting to move value to here
.../src/lib.rs:79     let result = self.internal[self.length];
                          ^~~~~~
.../src/lib.rs:79:9: 79:15 help: to prevent the move, use `ref result` or `ref mut result` to capture value by reference
.../src/lib.rs:79     let result = self.internal[self.length];

我也看过这个，但是我已经有一段时间没有做过任何 C/C++了

• How should you do pointer arithmetic in rust?

Answer 1

Surely there is a way in Rust to initialize an array with it's size determined at runtime?

不，Rust 数组仅能够以编译时已知的大小创建。事实上，每个类型和大小的元组构成了一个新类型! Rust 编译器使用该信息进行优化。

一旦你需要一组在运行时确定的东西，你必须添加运行时检查以确保 Rust 的 safety guarantees总是有效的。例如，您无法访问未初始化的内存(例如离开一组项目的开头或结尾)。

如果您真的想沿着这条路走下去，我希望您将不得不亲自动手处理一些直接的内存分配和不安全的代码。本质上，您将构建一个较小版本的 Vec 本身!为此，您可以查看 source of Vec .

在高层次上，您需要分配足够大的内存块来容纳 N 个某种类型的对象。然后您可以提供访问这些元素的方法，在后台使用指针算法。添加更多元素时，可以分配更多空间并移动旧值。有很多细微差别可能会出现也可能不会出现，但听起来您正处于一段有趣旅程的开始!

编辑

当然，您可以选择假装 Vec 的大部分方法根本不存在，而只使用与 Java 数组类似的方法。不过，您仍然需要使用 Option 来避免未初始化的值。