Move —— Vector 动态数组
#Move

Vector 是 Move 标准库提供的动态数组类型，用于存储可变长度的同类型数据。本文介绍 Vector 的堆内存模型、为什么必须使用引用操作、常用的增删改查 API，以及在区块链场景下如何通过 swap_remove 优化 Gas 消耗。

1. Vector 与内存模型

vector<T> 是 Move 标准库提供的动态数组，用于存储同类型的一组数据。

内存模型：

  • Struct 或基础类型： 大小固定，通常存储在 栈 (Stack) 上。
  • Vector： 大小可变，元数据必须存储在 堆 (Heap) 上。栈上仅保留指针、长度和容量。

为什么 Vector 必须用引用？

操作 Vector 必须使用引用 (& / &mut)。 如果不传引用直接传值，会触发 Deep Copy (深拷贝)，复制堆上所有数据，导致极高的 Gas 消耗。

1
2
3
4
5
6
7
8
9
10
       栈 (Stack)                         堆 (Heap)
+-------------------+              +-----------------------+
|    变量 v         |              | [ 元素 0: 10  ]       |
|  +--------------+ |              | [ 元素 1: 20  ]       |
|  | ptr: 0xH999 -+-+------------> | [ 元素 2: 30  ]       |
|  | len: 3      | |              | [ ...         ]       |
|  | capacity: 8 | |              +-----------------------+
|  +--------------+ |                    真实数据存储
+-------------------+
    元数据（管理信息）

Vector 的三个核心元数据：

  1. ptr (指针)：指向堆上实际数据的地址
  2. len (长度)：当前存储了多少个元素
  3. capacity (容量)：堆上预分配了多少空间（通常 > len，减少重新分配次数）

2. 常用操作

2.1 创建 Vector (Creation)

  • vector::empty<T>()：创建一个空数组。
  • vector[]：字面量写法（推荐，代码更简洁），例如 let v = vector[10, 20];。

2.2 状态查询 (读权限 &)

只读取栈上的元数据，极快。

  • vector::length(&v)：返回元素个数。
  • vector::is_empty(&v)：判断长度是否为 0。

2.3 增与删 (写权限 &mut)

改变数组长度，需要操作堆内存。

  • vector::push_back(&mut v, e)：将元素 e Move 进数组末尾。
  • vector::pop_back(&mut v)：弹出并 Return 最后一个元素。

2.4 元素访问与修改 (引用机制)

不移除元素，直接访问堆内存。

  • 读取 (borrow)：vector::borrow(&v, index)
    • 返回 &T (只读引用)。
  • 修改 (borrow_mut)：vector::borrow_mut(&mut v, index)
    • 返回 &mut T (可变引用)。
    • 修改值时必须使用 解引用 (\*)。

3. Gas 优化：删除策略

在区块链上删除中间元素时，必须权衡 顺序保持 与 Gas 成本。

  • remove(&mut v, i)：
    • 行为：删除元素，并将后面所有元素向前平移。
    • 代价：$O(N)。数组越大，Gas 越贵。
  • swap_remove(&mut v, i)：
    • 行为：将待删元素与最后一个元素交换，然后弹出末尾。
    • 代价：$O(1)。极其便宜，但会打乱顺序。

4. 代码演示

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
33
34
35
use std::debug;


public fun main() {
    // 创建
    let mut v = vector[10, 15, 20, 30];
    debug::print(&v);

    // 状态查询 (length, is_empty)
    let r1 = vector::is_empty(&v);
    let r2 = vector::length(&v);
    debug::print(&r1);
    debug::print(&r2);

    // 增加与删除
    vector::push_back(&mut v, 40);
    debug::print(&v);

    vector::pop_back(&mut v);
    debug::print(&v);

    // 引用读写 (borrow, borrow_mut)
    let val_ref = vector::borrow(&v, 2);
    debug::print(&*val_ref);

    let mut_ref = vector::borrow_mut(&mut v, 2);
    *mut_ref = 200;
    debug::print(&v);

    // remove vs swap_remove
    vector::remove(&mut v, 0);
    debug::print(&v);
    vector::swap_remove(&mut v, 0);
    debug::print(&v);
}

5. 操作总结表

操作 函数 权限 时间复杂度 描述
查长度 length & $O(1)$ 返回元素个数
查空 is_empty & $O(1)$ 长度为0返回 true
添加 push_back &mut $O(1)$ 元素移入队尾
弹出 pop_back &mut $O(1)$ 弹出并返回队尾元素
读取 borrow & $O(1)$ 获取元素的只读引用
修改 borrow_mut &mut $O(1)$ 获取元素的可变引用 (需解引用 *)
删除 remove &mut $O(N)$ 删除并保持顺序 (贵)
交换删 swap_remove &mut $O(1)$ 交换删除 (便宜，打乱顺序)
Prev
#Move
Next