Rust.gg

Vec 与切片 ​

本章把「数据放在哪里」和「怎么处理数据」一次讲透：Vec/String/HashMap 决定数据的形状， 迭代器决定处理的写法。学完这一章，你的 Rust 代码会从「能跑」变成「像 Rust」。 前置知识：所有权与借用、 结构体、枚举与 trait。 基准环境：rustc 1.98.1 / cargo 1.98.1，Rust 2024 edition，Windows 11 + PowerShell。

本章目标 ​

  • 能熟练用 Vec<T> 完成增删改查，并说清 v[i] 与 v.get(i) 的取舍、容量（capacity）与重新分配的关系。
  • 能解释 let first = &v[0]; v.push(4); 为什么报 E0502，并条件反射地给出三种修法。
  • 能把 &[T] / &mut [T] 当作函数参数的首选，说清它为什么比 &Vec<T> 更好。
  • 能解释 String 是 UTF-8 字节序列，为什么 s[0] 不合法、&s[0..2] 可能 panic，并会用 chars()/char_indices()/get() 安全处理。
  • 能用 HashMap 的 entry API 写出一次查找完成「有则改、无则插」的代码，并按需在 HashMap/BTreeMap/HashSet 之间选型。
  • 能读懂 Iterator 的 next(&mut self) -> Option<Self::Item> 签名，理解惰性求值（lazy evaluation），写出 20 行以内的迭代器链替代 30 行命令式循环，并自己实现 Iterator（含 size_hint）、IntoIterator 与 impl Iterator<Item = ...> 返回类型。

Vec<T>：唯一需要精通的可增长数组 ​

三种创建方式与它们的差别 ​

Vec<T> 是「堆上连续、长度可变、拥有元素」的数组。它在栈上存三个机器字 （ptr/len/capacity），元素本体在堆上。

rust
fn main() {
    let a: Vec<i32> = Vec::new();          // 空向量：不分配堆内存（ptr 是悬垂对齐指针）
    let b = vec![1, 2, 3];                 // 宏写法：元素个数即长度
    let c = vec![0u8; 4];                  // 值 + 重复次数，等价于 [0, 0, 0, 0]
    let mut d = Vec::with_capacity(1024);  // 一次分配好 1024 个元素的空间，len 仍为 0
    d.push(1);

    println!("{} {} {} {}", a.len(), b.len(), c.len(), d.len());   // 输出：0 3 4 1
    println!("d 的容量 = {}", d.capacity());                        // 输出：d 的容量 = 1024
}

三种方式的取舍：

写法何时用代价
Vec::new()后面要靠 push 填，且数量不确定首次 push 时才分配（容量 4 起步）
vec![a, b, c]元素在写代码时已知一次分配，容量通常等于长度
vec![x; n]元素可 Clone 且都要同一个初值需要 T: Clone（不能用于只有 Copy 之外语义的类型构造）
Vec::with_capacity(n)已知大概多少个元素一次分配，避免多次搬移与拷贝

⚠️ 陷阱：vec![String::new(); 3] 是合法的（String: Clone），得到三个独立的空字符串； 但 vec![mutex.lock(); 3] 这类「想复制同一份资源」的意图会失败， 因为 MutexGuard 不是 Clone。要复制句柄请用 vec![Arc::clone(&x); 3]。

💡 对照：Python 的 list 与 JS 的 Array 是异质的（可以 [1, "a", None]）， 每个元素是一个指向堆对象的指针；Rust 的 Vec<T> 是同质的，元素在内存里紧挨着存放， 所以 Vec<i32> 的 100 万个元素就是连续的 4 MB，而不是 100 万个装箱对象。 C++ 的 std::vector<T> 与 Rust 的 Vec<T> 语义最接近，但 C++ 的拷贝是隐式的， Rust 的 Vec 不实现 Copy，赋值即 move。

增删改查速览 ​

rust
fn main() {
    let mut v = vec![10, 20, 30];

    v.push(40);                          // 尾部追加，均摊 O(1)
    assert_eq!(v.pop(), Some(40));       // 尾部弹出并返回，O(1)
    v.insert(0, 5);                      // 指定位置插入，O(n)：后面所有元素右移
    assert_eq!(v.remove(0), 5);          // 删除并返回该位置的值，O(n)：元素左移
    v[0] = 11;                           // 索引赋值：越界直接 panic
    assert_eq!(v[0], 11);
    assert_eq!(v.get(1), Some(&20));     // get 返回 Option<&T>
    assert_eq!(v.get(99), None);
    assert_eq!(v.first(), Some(&11));    // 等价于 get(0)
    assert_eq!(v.last(), Some(&30));     // 最后一个
    assert_eq!(v.len(), 3);
    v.clear();                           // 清空：len 归零，容量保留
    assert!(v.is_empty());
    assert_eq!(v.capacity() >= 3, true); // clear 不释放堆内存
    println!("ok");
}
需求方法复杂度备注
尾部追加push(x)均摊 O(1)可能触发重新分配
尾部弹出pop()O(1)返回 Option<T>，空时是 None
任意位置插入insert(i, x)O(n)i > len 时 panic
任意位置删除remove(i)O(n)返回被删的值；i >= len 时 panic
读取（可 panic）v[i]O(1)越界 panic，带边界检查
读取（安全）get(i) / first() / last()O(1)返回 Option<&T>
就地修改v[i] = xO(1)需要 let mut v
追加整个切片extend_from_slice(&[..])均摊 O(k)要求 T: Clone
取出整段drain(1..3)O(n)返回迭代器，可复用原容量
保序删除retain(|x| ...)O(n)一次遍历删除所有不满足条件的元素

⚠️ 陷阱：Vec::remove(0) 和 Vec::insert(0, x) 都是 O(n)。 用它们当队列（每次从头部取任务）会退化成 O(n²)。 需要双端进出请用 std::collections::VecDeque（见「速查表」 与练习 10）。

越界 panic 还是 Option：编译器为什么不能静态检查 ​

rust
fn main() {
    let v = vec![1, 2, 3];
    let i = std::env::args().count();     // 运行期才知道的值，编译器无法预判
    if i < 100 {
        println!("{:?}", v.get(i));       // 安全：返回 Option，越界是 None
    }
    // println!("{}", v[i]);              // 危险：i 一旦 >= 3 就 panic
}

Vec 的长度是运行期数据，而索引值可能来自用户输入、文件、网络。 编译器要静态证明 i < v.len() 就得做全程序的值域分析 —— 这在有函数调用、循环、 动态输入的现实程序里不可判定。Rust 的处理方式是把选择权交给你：

写法越界时用在哪
v[i]panic（index out of bounds: the len is 3 but the index is 3）逻辑上「绝不可能越界」，越界即 bug
v.get(i)返回 None索引来自外部、越界是正常业务分支
v.get(i).copied().unwrap_or(0)返回默认值需要「容错取值」
v.get_mut(i)返回 Option<&mut T>需要就地修改

🧠 原理：Rust 的 Index trait 定义为 fn index(&self, index: Idx) -> &Self::Output， 它必须返回引用，因此无法表达「可能失败」；失败只能用 panic。 这就是为什么「不 panic 的取值」另起一个方法叫 get，而不是让 [] 返回 Option。 换句话说：v[i] ≡ *v.get(i).expect("index out of bounds")。

🧠 原理：定长数组 [T; N] 的长度写在类型里，所以常量下标越界能在编译期发现： let a = [1, 2, 3]; a[5]; 编译失败（deny 级别的 unconditional_panic lint）——

error: this operation will panic at runtime
 --> src\main.rs:3:20
  |
3 |     println!("{}", a[5]);
  |                    ^^^^ index out of bounds: the length is 3 but the index is 5
  |
  = note: `#[deny(unconditional_panic)]` on by default

Vec<T> 的 len 是运行期数据，同样的检查就做不到了 —— 「能静态查的它一定查，查不了才退化成运行期检查」是 Rust 的一贯取向。

容量、重新分配与 with_capacity 的重要性 ​

Vec 的 len 是「已初始化元素个数」，capacity 是「不重新分配的前提下最多能装多少」。 len <= capacity 恒成立。当 push 遇到 len == capacity 时，Vec 会：

  1. 向分配器申请一块更大的新内存（当前实现是几何增长，近似翻倍）；
  2. 把旧元素按位搬移（不是逐个 clone，因为所有权跟着走）；
  3. 释放旧内存；
  4. 把新元素写进去。
rust
fn main() {
    let mut v: Vec<i32> = Vec::new();
    let mut last = v.capacity();
    for i in 0..100 {
        v.push(i);
        if v.capacity() != last {
            println!("len = {:>3} 时扩容到 capacity = {:>3}", v.len(), v.capacity());
            last = v.capacity();
        }
    }
}

输出（1.98.1 实测，具体数值是实现细节，不要写进业务逻辑）： len = 1 → 4、len = 5 → 8、len = 9 → 16、len = 17 → 32、len = 33 → 64、len = 65 → 128。

   几何增长的均摊分析（假设每次翻倍）

   push 次数   1    2    3    4    5    6    7    8    9   ...   16
   是否扩容    ✓    -    -    -    ✓    -    -    -    ✓   ...    ✓
   搬移元素    0    1    2    3    0    1    2    3    0   ...    0
   ─────────────────────────────────────────────────────────────────
   总搬移量 = n + n/2 + n/4 + ... < 2n  ⇒  单次 push 均摊 O(1)

如果每次只加 1 个容量，总搬移量是 1+2+…+n = O(n²)，push 就退化成 O(n)。 所以「几何增长」不是为了省内存，而是为了让均摊复杂度成立。

什么时候 with_capacity 是必须的：

rust
fn main() {
    let n = 1_000_000usize;
    let mut v: Vec<u64> = Vec::with_capacity(n);   // 一次分配 8 MB
    for i in 0..n {
        v.push(i as u64);
    }
    println!("{} / {}", v.len(), v.capacity());
}
  • 读大文件 / 解析大 JSON 时已知行数或元素个数；
  • 目标容量很大（百万级）时，翻倍意味着峰值内存可能是最终大小的 2 倍 （旧块 + 新块同时存在）；
  • 与外部 C 接口交换缓冲区、需要稳定地址（as_ptr() 之后不能再 push）时。

⚠️ 陷阱：with_capacity 不改变 len。Vec::with_capacity(10)[0] 依然是越界 panic； 想创建「10 个默认值」应该写 vec![T::default(); 10]。

🚀 进阶：Vec::shrink_to_fit() 可以把容量收缩到接近 len，但它是非强制的 （分配器可以忽略）。Vec::into_boxed_slice() 会做一次「如果多余则重新分配 + 收缩」， 得到不浪费内存的 Box<[T]>，适合长期保存的只读数据。

所有权与借用：E0502 现场解剖 ​

先看一个能编译的版本，理解 first 借走了什么：

rust
fn main() {
    let v = vec![1, 2, 3];
    let first = &v[0];        // &v[0] 是 &i32，借用了 v 的堆缓冲区
    println!("{first}");      // 输出：1
    println!("{v:?}");        // 仍然可以只读访问：共享借用可以并存
}

现在把 v 变成 mut，并在借用还活着的时候追加元素：

rust
// ❌ 此代码无法编译（E0502）
fn main() {
    let mut v = vec![1, 2, 3];
    let first = &v[0];
    v.push(4);                // 想改 v
    println!("{first}");      // 但 first 还在这里用
}

rustc 原始输出（1.98.1 实测）：

error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
 --> src\main.rs:4:5
  |
3 |     let first = &v[0];
  |                  - immutable borrow occurs here
4 |     v.push(4);
  |     ^^^^^^^^^ mutable borrow occurs here
5 |     println!("{first}");
  |               ----- immutable borrow later used here

为什么必须拒绝？ 因为 push 可能触发重新分配：旧缓冲区被释放， first 就变成了指向已释放内存的悬垂指针（dangling pointer）。C++ 里这是 UB， Java 里是「你看到的是过期视图」，Rust 里是编译错误。

   push 前的内存布局                    触发扩容的 push 之后
   v ─[ptr|3|3]─► [1][2][3]              v ─[ptr'|4|6]─► [1][2][3][4]   （新地址）
                    ▲                                     旧块已 free
                    └── first 还指着这里 ⇒ 悬垂！

三种修法，按推荐顺序：

rust
fn main() {
    let mut v = vec![1, 2, 3];

    // 修法 1：把值复制出来，让借用立刻结束（元素是 Copy 时最干净）
    let first = v[0];                 // 注意是 v[0] 而不是 &v[0]，产生的是 i32 而不是 &i32
    v.push(4);
    println!("{first}");              // 输出：1

    // 修法 2：缩小借用作用域 —— 把「读」和「写」分开到先后两个块里
    {
        let first_ref = &v[0];
        println!("{first_ref}");      // 输出：1
    }                                 // 借用在这里结束
    v.push(5);

    // 修法 3：调整顺序，先写完再读
    v.push(6);
    let last = v.last().copied().unwrap_or_default();   // Option 链式取值
    println!("{last}");               // 输出：6
}

需要保留引用本身（不只是值）时还有第 4 种：先改完，再统一取引用； 以及把「只读快照」clone() 出来算、算完写回（代价是一次拷贝，但语义最清楚）。

⚠️ 陷阱：let first = &v[0]; v.push(4); 里如果 first 之后完全没用到， 代码其实能编译 —— NLL（非词法生命周期）会在最后一次使用处结束借用。 报 E0502 的前提是「借用被使用的位置」落在了可变借用之后。 想知道自己是不是靠「巧合」通过编译，看 first 的最后一次使用在哪里。

🧠 原理：借用检查器看的是借用区间是否重叠，与花括号无关。 &v[0] 始于第 3 行、终于最后一次使用；v.push(4) 是同一区间内的独占借用； 两者重叠 ⇒ 拒绝。这正是 &T 与 &mut T 互斥规则在集合上的具体表现。

Vec<T> 中 T 的所有权 ​

Vec<T> 拥有它的每一个元素。这条规则推出三件事：

  1. 把元素 push 进 Vec 就是移动进去，之后原变量不可用；
  2. Vec 被 drop 时，元素逐个被 drop（这就是为什么 Vec<String> 不需要手动释放）；
  3. Vec<T> 本身永远不实现 Copy**（Copy 要求「复制即完整独立」，而堆缓冲区不能这样复制）。
rust
fn main() {
    let s = String::from("hello");
    let mut v = Vec::new();
    v.push(s);                 // s 被移动进 v
    // println!("{s}");        // E0382: borrow of moved value: `s`

    let mut v2 = v;            // v 被移动进 v2（堆缓冲区不动，只搬 3 个机器字）
    v2.push(String::from("world"));
    // println!("{v:?}");      // E0382

    let shared: &Vec<String> = &v2;
    println!("{}", shared.len());        // 输出：2
    // v2.push(String::from("!"));       // E0502：shared 还活着
    drop(shared);              // 显式结束借用也可以（但通常靠 NLL 就够了）
    v2.push(String::from("!"));
    println!("{}", v2.len());  // 输出：3
}

从 Vec 里取出元素只有三种合法姿势：

rust
fn main() {
    let v = vec![String::from("a"), String::from("b")];

    let last = v.last().cloned();          // 1) clone：原元素还在
    println!("{last:?}");                  // 输出：Some("b")

    let mut v2 = vec![String::from("a"), String::from("b")];
    let popped = v2.pop();                 // 2) pop：移动出来并缩短长度
    println!("{popped:?}");                // 输出：Some("b")

    let v3 = vec![String::from("a"), String::from("b")];
    let taken: Vec<String> = v3.into_iter().collect();   // 3) into_iter：整体拆开，元素所有权到手
    println!("{}", taken.len());           // 输出：2
}

⚠️ 陷阱：for s in &v { let owned = *s; } 报 E0507（cannot move out of *s which is behind a shared reference）。共享借用只给你「看」的权利；要拿到所有权必须 clone()， 或者把整个 Vec 用 into_iter() 消费掉。

嵌套 Vec<Vec<T>> 与 Vec<(K, V)> ​

rust
fn main() {
    // 嵌套 Vec：每行是独立的堆分配，因此行长度可以不同（锯齿数组 / jagged array）
    let mut grid: Vec<Vec<i32>> = vec![vec![0; 3]; 2];   // 2 行 × 3 列
    grid[1][2] = 5;                                     // 先用外层索引取 &mut Vec<i32>，再索引
    grid[0].push(9);                                    // 第 0 行变成 4 个元素
    println!("{grid:?}");                               // 输出：[[0, 0, 0, 9], [0, 0, 5]]

    // 键值对数组：没有哈希表时的「小规模 O(n) 查找」方案
    let mut pairs: Vec<(String, i32)> = Vec::new();
    pairs.push(("apple".to_string(), 3));
    pairs.push(("banana".to_string(), 7));
    pairs.sort_by_key(|(_, count)| *count);             // 按值排序，闭包参数用模式解构
    for (name, count) in &pairs {
        println!("{name}={count}");
    }
    // 输出：apple=3 / banana=7

    let total: i32 = pairs.iter().map(|(_, c)| c).sum();
    println!("{total}");                                // 输出：10
}

Vec<Vec<T>> 与 Vec<(K, V)> 的选型建议：

数据结构适用不适用
Vec<Vec<T>>行数已知、行长可变、需要 push 单行；矩阵计算（n × m 固定时更该用一维 Vec<T> + 手动 i * m + j）需要 O(1) 按 key 查找
Vec<(K, V)>元素少（< 10）、需要保持插入顺序、需要 sort_by_key 排序频繁查找（O(n)）；应换 HashMap
HashMap<K, V>频繁按 key 查需要有序遍历（换 BTreeMap）

🧠 原理：grid[1][2] = 5 在编译器眼里是两步 IndexMut： (*grid.index_mut(1)).index_mut(2) = 5。第一步返回 &mut Vec<i32>， 第二步在这个 &mut 上再索引 —— 借用检查器能接受，因为第一层的可变借用是沿着链传递的。

切片 &[T]：借来的一段连续内存 ​

从 Vec 和数组取切片 ​

切片是胖指针（fat pointer）：ptr + len，共 16 字节（64 位平台）。 它不拥有数据，只是「向别人借的一段视图」。

rust
fn main() {
    let v = vec![1, 2, 3, 4, 5];
    let a = [10, 20, 30, 40];

    let s1: &[i32] = &v;              // Vec<T> → &[T]：靠 Deref 强制转换（deref coercion）
    let s2: &[i32] = &a;              // 数组 → &[T]
    let s3 = &v[..];                  // 全长
    let s4 = &v[1..];                 // 从 1 到末尾
    let s5 = &v[..3];                 // 从 0 到 3（不含）
    let s6 = &v[1..3];                // 中间一段
    let s7 = &a[2..];                 // 数组的子切片

    println!("{} {} {} {}", s1.len(), s2.len(), s3.len(), s4.len());
    println!("{} {} {}", s5.len(), s6.len(), s7.len());
    // 输出：5 4 5 4 / 3 2 2
    println!("{s6:?}");               // 输出：[2, 3]
}
   &[T] 的运行时表示（栈上 16 字节）
   ┌──────────────┬──────────┐
   │ ptr ─────────┼─► 数据   │   数据仍归 Vec / 数组所有
   │ 0x1f3a_2200  │ len = 2  │
   └──────────────┴──────────┘
   v[1..3] 就是「把 ptr 加 1 个元素宽度、len 设为 2」，零拷贝

💡 对照：&[T] ≈ C++20 的 std::span<T>，也 ≈ Go 的切片（但 Go 切片「共享且可变」， 没有借用检查）。Python 的 list[1:3] 是复制出一个新 list；Rust 的 &v[1..3] 不复制。

rust
fn main() {
    let mut v = vec![5, 3, 9, 1, 7, 2];

    let (left, right) = v.split_at(3);        // 一次拿到两半，O(1)
    println!("{left:?} | {right:?}");         // 输出：[5, 3, 9] | [1, 7, 2]

    for c in v.chunks(2) {                    // 每 2 个一组，最后一组可能更短
        println!("chunk {c:?}");
    }
    // 输出：chunk [5, 3] / chunk [9, 1] / chunk [7, 2]

    for w in v.windows(3) {                   // 长度固定为 3 的滑动窗口，共 len-2 个
        println!("window {w:?}");
    }
    // 输出：window [5, 3, 9] / window [3, 9, 1] / window [9, 1, 7] / window [1, 7, 2]

    v.sort();                                 // 稳定排序（stable sort），按 Ord，O(n log n)
    println!("{v:?}");                        // 输出：[1, 2, 3, 5, 7, 9]

    println!("{:?}", v.binary_search(&5));    // 输出：Ok(3)   —— 找到了，下标 3
    println!("{:?}", v.binary_search(&4));    // 输出：Err(3)  —— 没找到，可插入位置 3

    let text = "a,b,,c";
    let parts: Vec<&str> = text.split(',').collect();
    println!("{parts:?}");                    // 输出：["a", "b", "", "c"]
}
方法作用关键点
split_at(i)切成 (&[T], &[T])i > len 时 panic；split_at_mut(i) 给两个 &mut [T]
chunks(n)每 n 个一组，末尾可能不足n == 0 panic（chunk size must be non-zero）
chunks_exact(n)同上但丢弃不足的尾巴1.31 起；remainder() 取尾巴
windows(n)长度恰为 n 的滑动窗口n == 0 panic（window size must be non-zero）；n > len 时一个都没有
split(pred)按谓词切分，保留空段"a,,b".split(',') 给 3 段
split_terminator(pred)同上但丢掉末尾空段"a,b,".split_terminator(',') 给 2 段
sort()稳定升序，需 T: Ord会分配辅助缓冲
sort_unstable()不稳定但更快更省内存元素相等不可区分时首选
binary_search(&x)二分查找必须先排序，否则结果无意义（不 panic，静默出错）
is_sorted()是否已升序1.82 起可用

⚠️ 陷阱：windows/chunks 在 n == 0 时是运行期 panic，不是编译错误。 当 n 来自配置或用户输入时，先 assert!(n > 0) 或改用 .get(..) 风格做判断。

切片作为函数参数：&[T] 优于 &Vec<T> ​

rust
fn sum_all(values: &[i32]) -> i32 {          // 首选：接受 Vec、数组、子切片
    values.iter().sum()
}

fn sum_owned(values: &Vec<i32>) -> i32 {     // 不推荐：只接受 &Vec<i32>
    values.iter().sum()
}

fn main() {
    let v = vec![1, 2, 3];
    let a = [4, 5];

    println!("{}", sum_all(&v));             // 输出：6
    println!("{}", sum_all(&a));             // 输出：9   —— &Vec<i32> 版本做不到
    println!("{}", sum_all(&v[1..]));        // 输出：5   —— 只处理子段
    println!("{}", sum_owned(&v));           // 输出：6
}

传参决策树：

   函数只需要读元素 ──────────────► &[T]
   函数需要就地修改元素（不改长度）──► &mut [T]
   函数需要 push/pop/改变长度 ─────► &mut Vec<T>
   函数需要把整个集合存起来 ────────► Vec<T>（拿走所有权）

&mut [T] 的例子 —— 注意「改元素」不需要 Vec 本身可变，只需要切片可变：

rust
fn normalize(values: &mut [f64]) {
    let max = values.iter().copied().fold(f64::MIN, f64::max);
    if max > 0.0 {
        for x in values.iter_mut() {
            *x /= max;                       // iter_mut 给 &mut f64，要解引用才能赋值
        }
    }
}

fn main() {
    let mut xs = vec![1.0, 2.0, 4.0];
    normalize(&mut xs);
    println!("{xs:?}");                      // 输出：[0.25, 0.5, 1.0]

    let mut arr = [2.0, 4.0];
    normalize(&mut arr);                     // 数组也能传：&mut [f64; 2] → &mut [f64]
    println!("{arr:?}");                     // 输出：[0.5, 1.0]
}

🧠 原理：&[T] 能接受 &Vec<T> 是因为 Vec<T>: Deref<Target = [T]>（解引用强制转换）， 而 &Vec<T> 不能接受 &[T]（反向不成立）。所以参数类型永远选「更宽松」的那一端。 clippy 的 ptr_arg lint 会自动提示改成 &[T]。

🚀 进阶：split_at_mut 是「同时拿到两段可变切片」的官方出口， 也是 chunks_mut / windows 之外处理「前半段与后半段互相独立」的关键工具： let (a, b) = v.split_at_mut(2); 之后 a 和 b 都是 &mut [T]，借用检查器接受， 因为它能证明两段不重叠。

延伸阅读 ​

内容以 rustc 1.98.1 · Rust 2024 edition 为基准

Rust.gg · 中文 Rust 学习手册