Ch 9: std::vec - 向量操作

1. 引言

Vec<T> 是 Rust 中最常用的动态数组类型，提供了高效的随机访问和动态增长能力。本章将详细讲解 Vec 的核心操作方法，包括元素的增删改查以及迭代器相关操作。

2. Vec 基础回顾

fn main() {
    // 创建空 Vec
    let mut v: Vec<i32> = Vec::new();

    // 使用 vec! 宏
    let v = vec![1, 2, 3];

    // with_capacity 预分配
    let mut v = Vec::with_capacity(10);
    v.push(1);
}

3. push 和 pop - 栈操作

push 在末尾添加元素，pop 从末尾移除并返回元素：

push - 添加元素：

fn main() {
    let mut v = Vec::new();

    v.push(1);
    v.push(2);
    v.push(3);

    println!("{:?}", v);  // [1, 2, 3]
}

pop - 移除并返回末尾元素：

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

    // pop 返回 Option<T>
    while let Some(item) = v.pop() {
        println!("popped: {}", item);
    }

    println!("{:?}", v);  // []
}

push 和 pop 的时间复杂度：O(1) 均摊

4. insert 和 remove - 任意位置操作

insert 在指定位置插入元素，remove 移除并返回指定位置的元素：

insert - 插入元素：

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

    v.insert(0, 10);  // 在索引 0 处插入
    println!("{:?}", v);  // [10, 1, 2, 3]

    v.insert(2, 20);  // 在索引 2 处插入
    println!("{:?}", v);  // [10, 1, 20, 2, 3]
}

remove - 移除元素：

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

    let removed = v.remove(2);  // 移除索引 2 的元素
    println!("removed: {}", removed);  // 3
    println!("{:?}", v);  // [1, 2, 4, 5]
}

注意： insert 和 remove 的时间复杂度为 O(n)，因为需要移动元素。

5. drain - 区间移除

drain 移除一个区间的元素并返回迭代器：

方法签名：

pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
where
    R: RangeBounds<usize>,

示例：

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

    // 移除索引 [1, 4) 的元素
    let drained: Vec<_> = v.drain(1..4).collect();

    println!("drained: {:?}", drained);  // [2, 3, 4]
    println!("{:?}", v);                 // [1, 5]
}

使用 ranges：

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

    // 使用 RangeFrom
    v.drain(2..);
    println!("{:?}", v);  // [1, 2]

    let mut v = vec![1, 2, 3, 4, 5];

    // 使用 RangeTo
    v.drain(..2);
    println!("{:?}", v);  // [3, 4, 5]
}

6. splice - 替换区间

splice 用另一个迭代器替换指定区间的元素：

方法签名：

pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter>
where
    R: RangeBounds<usize>,
    I: IntoIterator<Item = T>,

示例：

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

    // 替换索引 [1, 3) 的元素
    let replaced = v.splice(1..3, vec![10, 20, 30]);

    println!("replaced: {:?}", replaced.collect::<Vec<_>>());  // [2, 3]
    println!("{:?}", v);  // [1, 10, 20, 30, 4, 5]
}

splice 保留原元素：

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

    // 用空迭代器替换，相当于删除
    v.splice(1..3, vec![]);

    println!("{:?}", v);  // [1]
}

7. Vec::from_iter - 从迭代器创建

Vec::from_iter 从迭代器创建 Vec：

方法签名：

pub fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Vec<A, Global>

示例：

fn main() {
    // 从迭代器创建
    let v: Vec<i32> = (0..5).collect();
    println!("{:?}", v);  // [0, 1, 2, 3, 4]

    // 从 map
    let v: Vec<i32> = (0..5).map(|x| x * 2).collect();
    println!("{:?}", v);  // [0, 2, 4, 6, 8]

    // 从 filter
    let v: Vec<i32> = (0..10).filter(|x| x % 2 == 0).collect();
    println!("{:?}", v);  // [0, 2, 4, 6, 8]
}

实现自己的 from_iter：

use std::iter::FromIterator;

#[derive(Debug)]
struct MyCollection(Vec<i32>);

impl FromIterator<i32> for MyCollection {
    fn from_iter<T: IntoIterator<Item = i32>>(iter: T) -> Self {
        let v: Vec<i32> = iter.into_iter().map(|x| x + 1).collect();
        MyCollection(v)
    }
}

fn main() {
    let c: MyCollection = (0..5).collect();
    println!("{:?}", c.0);  // [1, 2, 3, 4, 5]
}

8. 其他常用方法

extend - 扩展 Vec：

fn main() {
    let mut v = vec![1, 2];
    v.extend(vec![3, 4, 5]);
    println!("{:?}", v);  // [1, 2, 3, 4, 5]

    // 从迭代器扩展
    v.extend(6..=8);
    println!("{:?}", v);  // [1, 2, 3, 4, 5, 6, 7, 8]
}

resize - 调整大小：

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

    // 扩展，用 0 填充新位置
    v.resize(5, 0);
    println!("{:?}", v);  // [1, 2, 3, 0, 0]

    // 缩小
    v.resize(2, 0);
    println!("{:?}", v);  // [1, 2]
}

truncate - 截断：

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

    v.truncate(3);
    println!("{:?}", v);  // [1, 2, 3]
}

clear - 清空：

fn main() {
    let mut v = vec![1, 2, 3];
    v.clear();
    println!("len: {}", v.len());  // 0
    println!("is_empty: {}", v.is_empty());  // true
}

9. 实战示例：简单的栈实现

struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack { items: Vec::new() }
    }

    fn push(&mut self, item: T) {
        self.items.push(item);
    }

    fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    fn peek(&self) -> Option<&T> {
        self.items.last()
    }

    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    fn len(&self) -> usize {
        self.items.len()
    }
}

fn main() {
    let mut stack = Stack::new();

    stack.push(1);
    stack.push(2);
    stack.push(3);

    println!("peek: {:?}", stack.peek());  // Some(3)
    println!("len: {}", stack.len());      // 3

    while let Some(item) = stack.pop() {
        println!("popped: {}", item);
    }

    println!("is_empty: {}", stack.is_empty());  // true
}

10. 需要注意的点

1. push 的均摊复杂度：虽然有时需要重新分配，但均摊复杂度是 O(1)。

2. insert 和 remove 的性能：这两个操作需要移动元素，复杂度是 O(n)。

3. drain 不会释放容量：被 drain 的元素被移除，但 Vec 的容量保持不变。

4. Vec::from_iter vs collect：Vec::from_iter 是 FromIterator 的实现，.collect() 在目标类型是 Vec 时调用它。

5. resize vs truncate：resize 可以增大或缩小并填充默认值，truncate 只能缩小。

11. 总结

Vec 是 Rust 中最常用的集合类型：

方法	作用	复杂度
push	末尾添加元素	O(1) 均摊
pop	末尾移除元素	O(1)
insert	指定位置插入	O(n)
remove	指定位置移除	O(n)
drain	区间移除并迭代	O(n)
splice	区间替换	O(n)
extend	扩展 Vec	O(n)
resize	调整大小	O(n)
clear	清空	O(n)

熟练掌握这些方法，能够高效地处理动态数组数据。