Rust Vec和LinkedList容器使用

Rust Vec 容器使用

Vec 简介

在 Rust 中，Vec（Vector 的缩写）是一种动态数组类型，它在堆上分配内存，能够根据需要动态地增长或收缩。Vec 是标准库中最常用的数据结构之一，广泛应用于各种场景，例如存储一系列元素、构建动态集合等。Vec 是一个泛型类型，这意味着它可以存储任何类型的数据，只要这些类型满足一定的约束条件。

Vec 的创建

1. 使用 vec! 宏创建 Vec vec! 宏是创建 Vec 的一种便捷方式，可以在初始化时指定元素。例如：

let numbers = vec![1, 2, 3, 4, 5];
println!("{:?}", numbers);

在上述代码中，vec! 宏创建了一个包含整数 1 到 5 的 Vec。println!("{:?}") 用于打印 Vec 的内容，{:?} 是 Rust 格式化字符串中的调试格式化标志，适用于 Debug 特征实现的类型，Vec 已经实现了 Debug 特征。

2. 使用 Vec::new 创建空 Vec 如果需要先创建一个空的 Vec，然后再添加元素，可以使用 Vec::new 方法：

let mut empty_vec: Vec<i32> = Vec::new();
empty_vec.push(10);
println!("{:?}", empty_vec);

这里首先使用 Vec::new 创建了一个空的 Vec，类型标注为 Vec<i32>，表示这个 Vec 只能存储 i32 类型的整数。然后使用 push 方法向 Vec 中添加了一个元素 10。

Vec 的内存管理

1. 动态内存分配 Vec 在堆上分配内存来存储其元素。当 Vec 需要更多空间来存储新元素时，它会重新分配内存。重新分配内存涉及到在堆上申请一块更大的内存块，将原来的元素复制到新的内存块中，然后释放旧的内存块。这种操作的时间复杂度为 O(n)，因为需要复制所有元素。为了减少频繁的重新分配，Vec 会预先分配一些额外的空间，这就是容量（capacity）的概念。

2. 容量和长度 Vec 的长度（len）表示当前 Vec 中实际存储的元素数量，而容量（capacity）表示 Vec 在不重新分配内存的情况下最多能存储的元素数量。可以使用 len 方法获取 Vec 的长度，使用 capacity 方法获取 Vec 的容量。例如：

let mut numbers = vec![1, 2, 3];
println!("Length: {}", numbers.len());
println!("Capacity: {}", numbers.capacity());

在上述代码中，numbers 的初始长度为 3，容量也为 3。当添加更多元素时，如果当前容量不足，Vec 会自动增加容量。例如：

let mut numbers = vec![1, 2, 3];
numbers.push(4);
println!("Length: {}", numbers.len());
println!("Capacity: {}", numbers.capacity());

在这个例子中，添加第四个元素后，Vec 的长度变为 4，容量可能会增加（具体增加多少取决于 Rust 标准库的实现策略，通常会增加一倍）。

Vec 的元素访问

1. 通过索引访问 可以像访问数组一样通过索引访问 Vec 中的元素。例如：

let numbers = vec![1, 2, 3];
let first = numbers[0];
println!("The first number is: {}", first);

但是需要注意，使用索引访问 Vec 时，如果索引超出范围，程序会发生 panic。例如：

let numbers = vec![1, 2, 3];
let out_of_bounds = numbers[3]; // 这会导致 panic

2. 使用 get 方法安全访问 为了安全地访问 Vec 中的元素，可以使用 get 方法。get 方法返回一个 Option 类型，如果索引有效则返回 Some 包裹的元素，否则返回 None。例如：

let numbers = vec![1, 2, 3];
if let Some(element) = numbers.get(2) {
    println!("The third number is: {}", element);
} else {
    println!("Index out of bounds");
}

在上述代码中，get(2) 成功获取到索引为 2 的元素，因为 Vec 的索引从 0 开始，长度为 3，索引 2 是有效的。

Vec 的遍历

1. 使用 for 循环遍历 这是最常见的遍历 Vec 的方式。例如：

let numbers = vec![1, 2, 3];
for number in numbers {
    println!("Number: {}", number);
}

在这个 for 循环中，number 会依次绑定到 Vec 中的每个元素。

2. 使用迭代器遍历 Vec 实现了 Iterator 特征，因此可以使用迭代器方法进行遍历。例如，使用 for_each 方法：

let numbers = vec![1, 2, 3];
numbers.iter().for_each(|number| println!("Number: {}", number));

这里 numbers.iter() 返回一个迭代器，for_each 方法对迭代器中的每个元素执行给定的闭包。迭代器提供了更多灵活的操作，例如过滤、映射等。例如，使用 filter 和 map 方法：

let numbers = vec![1, 2, 3, 4, 5];
let even_squared: Vec<i32> = numbers.iter()
    .filter(|&&number| number % 2 == 0)
    .map(|&number| number * number)
    .collect();
println!("{:?}", even_squared);

在上述代码中，filter 方法过滤出偶数，map 方法将每个偶数平方，最后 collect 方法将迭代器收集成一个新的 Vec。

Vec 的修改操作

1. 添加元素 除了前面提到的 push 方法，还可以使用 extend 方法将另一个可迭代对象的所有元素添加到 Vec 中。例如：

let mut numbers = vec![1, 2];
let more_numbers = vec![3, 4];
numbers.extend(more_numbers);
println!("{:?}", numbers);

这里 extend 方法将 more_numbers 中的所有元素添加到 numbers 中。

2. 删除元素 pop 方法用于删除并返回 Vec 的最后一个元素。例如：

let mut numbers = vec![1, 2, 3];
let last = numbers.pop();
println!("Last number: {:?}", last);
println!("Remaining numbers: {:?}", numbers);

在上述代码中，pop 方法返回 Some(3)，并将 numbers 修改为 [1, 2]。如果 Vec 为空，pop 方法返回 None。还可以使用 remove 方法删除指定索引位置的元素：

let mut numbers = vec![1, 2, 3];
let removed = numbers.remove(1);
println!("Removed number: {}", removed);
println!("Remaining numbers: {:?}", numbers);

这里 remove(1) 删除了索引为 1 的元素 2，并返回该元素。

Rust LinkedList 容器使用

LinkedList 简介

LinkedList 是 Rust 标准库中提供的双向链表数据结构。与 Vec 不同，LinkedList 的元素在内存中并不是连续存储的，而是通过节点（node）相互连接。每个节点包含数据和指向前一个节点与后一个节点的指针。这种结构使得在链表的任意位置插入和删除元素的时间复杂度为 O(1)，但访问链表中的元素需要从头或从尾开始遍历，时间复杂度为 O(n)。LinkedList 也是一个泛型类型，可以存储任何类型的数据。

LinkedList 的创建

1. 使用 LinkedList::new 创建空链表

use std::collections::LinkedList;

let mut list: LinkedList<i32> = LinkedList::new();
list.push_back(1);
list.push_back(2);
println!("{:?}", list);

在上述代码中，首先使用 LinkedList::new 创建了一个空的 LinkedList，类型标注为 LinkedList<i32>，表示这个链表只能存储 i32 类型的整数。然后使用 push_back 方法向链表的尾部添加了两个元素 1 和 2。

2. 从可迭代对象创建链表 可以使用 from_iter 方法从任何实现了 IntoIterator 特征的对象创建 LinkedList。例如：

use std::collections::LinkedList;

let numbers = vec![1, 2, 3];
let list: LinkedList<i32> = LinkedList::from_iter(numbers);
println!("{:?}", list);

这里将一个 Vec 转换为 LinkedList，from_iter 方法会消耗 numbers，并将其元素逐个添加到 LinkedList 中。

LinkedList 的内存管理

1. 节点式内存分配 LinkedList 的每个节点在堆上独立分配内存。这种方式与 Vec 的连续内存分配不同，Vec 是在一块连续的内存区域存储所有元素。由于节点是独立分配的，LinkedList 在内存使用上相对更灵活，但也会因为每个节点的额外指针开销而占用更多内存。例如，对于一个存储 i32 类型元素的 LinkedList，每个节点除了存储 i32 类型的数据外，还需要存储两个指针（一个指向前一个节点，一个指向后一个节点），假设指针大小为 8 字节（在 64 位系统上），i32 类型大小为 4 字节，那么每个节点至少占用 20 字节（8 + 8 + 4）的内存。

2. 内存释放 当 LinkedList 被销毁时，其所有节点的内存会被自动释放。Rust 的所有权系统和自动内存管理机制确保了内存的正确释放，避免了内存泄漏。例如：

use std::collections::LinkedList;

{
    let mut list = LinkedList::new();
    list.push_back(1);
    list.push_back(2);
} // 这里 list 超出作用域，其所有节点的内存会被自动释放

在这个代码块中，当 list 超出作用域时，LinkedList 的析构函数会被调用，释放所有节点的内存。

LinkedList 的元素访问

1. 遍历访问 由于 LinkedList 的元素在内存中不连续，不能像 Vec 那样通过索引直接访问。要访问 LinkedList 中的元素，需要遍历链表。例如，使用 for 循环遍历链表：

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);

for number in &list {
    println!("Number: {}", number);
}

在上述代码中，通过 for 循环遍历 list，number 依次绑定到链表中的每个元素。

2. 使用迭代器访问 LinkedList 实现了 Iterator 特征，可以使用迭代器方法进行更灵活的访问。例如，使用 iter 方法获取一个不可变迭代器：

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);

let sum: i32 = list.iter().sum();
println!("Sum: {}", sum);

这里 list.iter() 返回一个不可变迭代器，sum 方法将迭代器中的所有元素相加。还可以使用 into_iter 方法获取一个可变迭代器，该迭代器会消耗 LinkedList：

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);

let mut new_list: LinkedList<i32> = LinkedList::new();
let iter = list.into_iter();
for number in iter {
    if number % 2 == 0 {
        new_list.push_back(number);
    }
}
println!("New list: {:?}", new_list);

在这个例子中，into_iter 方法返回一个可变迭代器，通过遍历原 LinkedList，将其中的偶数添加到新的 LinkedList 中。

LinkedList 的修改操作

1. 添加元素 LinkedList 提供了 push_front 和 push_back 方法分别用于在链表的头部和尾部添加元素。例如：

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_front(1);
list.push_back(2);
println!("{:?}", list);

这里先在链表头部添加了元素 1，然后在尾部添加了元素 2。还可以使用 insert 方法在指定位置插入元素。例如：

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_back(1);
list.push_back(3);

let middle = list.iter_mut().nth(1).unwrap();
list.insert_after(middle, 2);
println!("{:?}", list);

在上述代码中，首先创建了一个包含 1 和 3 的链表，然后通过 iter_mut 方法获取可变迭代器，使用 nth 方法找到索引为 1 的节点（这里是包含 3 的节点），最后使用 insert_after 方法在该节点之后插入元素 2。

2. 删除元素 pop_front 和 pop_back 方法分别用于删除并返回链表头部和尾部的元素。例如：

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);

let front = list.pop_front();
let back = list.pop_back();
println!("Front: {:?}", front);
println!("Back: {:?}", back);

在这个例子中，pop_front 方法返回 Some(1)，pop_back 方法返回 Some(2)。还可以使用 remove 方法删除指定节点。例如：

use std::collections::LinkedList;

let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);

let node = list.iter_mut().nth(1).unwrap();
list.remove(node);
println!("{:?}", list);

这里通过 iter_mut 和 nth 方法找到索引为 1 的节点（包含 2 的节点），然后使用 remove 方法删除该节点，最终链表变为 [1, 3]。

Vec 与 LinkedList 的比较

1. 内存布局
   • Vec：在堆上分配一块连续的内存来存储元素，这种连续内存布局使得 Vec 在缓存命中率上表现较好，因为 CPU 缓存通常是以连续内存块为单位进行预取的。例如，在遍历 Vec 时，元素在内存中是连续的，CPU 可以一次性预取多个元素到缓存中，提高访问效率。
   • LinkedList：每个节点在堆上独立分配内存，通过指针连接。这种内存布局使得 LinkedList 在内存使用上更加灵活，不需要连续的大块内存，但由于节点之间的指针开销，会占用更多的内存空间。例如，对于一个包含 1000 个 i32 元素的 Vec 和 LinkedList，Vec 只需要一块能容纳 1000 个 i32（假设 i32 大小为 4 字节，共 4000 字节）的连续内存块，而 LinkedList 除了存储 1000 个 i32 元素所需的 4000 字节外，还需要额外的指针空间（假设每个节点两个指针，每个指针 8 字节，共 16000 字节），总共需要 20000 字节左右的内存。
2. 访问效率
   • Vec：通过索引访问元素的时间复杂度为 O(1)，因为可以根据索引直接计算出元素在内存中的位置。例如，访问 vec[5]，可以直接通过内存地址偏移量快速获取到该元素。但如果需要在 Vec 的中间插入或删除元素，由于需要移动后续元素，时间复杂度为 O(n)。
   • LinkedList：访问元素需要从头或从尾开始遍历，时间复杂度为 O(n)。例如，要访问链表中第 100 个元素，需要从头部或尾部开始，依次移动指针 99 次才能找到该元素。但在链表的任意位置插入和删除元素的时间复杂度为 O(1)，因为只需要修改相关节点的指针即可。
3. 迭代性能
   • Vec：迭代 Vec 时，由于元素在内存中连续，迭代器的实现可以利用 CPU 缓存，性能较好。例如，在对 Vec 进行迭代求和操作时，CPU 可以高效地从连续内存中读取元素，提高计算速度。
   • LinkedList：迭代 LinkedList 时，由于节点在内存中不连续，迭代器需要不断地通过指针访问下一个节点，缓存命中率较低，性能相对较差。例如，同样是迭代求和操作，LinkedList 的迭代器需要频繁地在内存中跳转，导致缓存失效，从而降低计算速度。
4. 适用场景
   • Vec：适用于需要频繁随机访问元素的场景，例如实现数组类型的功能、存储需要快速查找的数据等。同时，如果数据量相对稳定，不需要频繁在中间插入或删除元素，Vec 也是一个很好的选择。例如，实现一个简单的学生成绩管理系统，学生成绩可以存储在 Vec 中，通过学生编号（索引）快速查询成绩。
   • LinkedList：适用于需要频繁在链表中间插入或删除元素的场景，例如实现一个任务队列，新任务可以随时插入到队列中间，完成的任务可以从队列中删除，而不需要移动大量其他元素。另外，如果数据量非常大且内存碎片化严重，LinkedList 由于不需要连续内存块，可能在内存分配上更有优势。例如，在一个实时处理大量网络数据包的系统中，数据包可以使用 LinkedList 存储，根据处理优先级随时插入或删除数据包。

在实际应用中，需要根据具体的需求和场景来选择使用 Vec 还是 LinkedList。如果对随机访问性能要求高，数据相对稳定，选择 Vec；如果对插入和删除操作频繁，对内存连续性要求不高，选择 LinkedList。同时，还需要考虑内存使用、缓存命中率等因素对程序性能的影响。例如，在一个对内存非常敏感的嵌入式系统中，即使插入和删除操作较多，如果数据量不是特别大，也可能优先选择 Vec，以减少内存碎片化和指针开销。而在一个处理海量数据且插入删除操作频繁的大数据处理系统中，LinkedList 可能更适合，尽管其访问性能较差，但可以通过合理的设计和优化来弥补这一不足。