青少年编程与数学 02-019 Rust 编程基础 06课题、容器类型

摘要:Rust 是一种系统编程语言，它提供了多种内置的容器类型，用于存储和管理数据。这些容器类型包括向量（Vec）、哈希表（HashMap）、双端队列（VecDeque）、二叉堆（BinaryHeap）、字符串（String）等。每种容器类型都有其独特的特点和适用场景。

关键词：容器类型、集合类型、数据结构、向量、哈希表、双端队列、二叉堆、字符串

---

一、向量（Vec）

Rust 中的 Vec 是一种非常重要的容器类型，它是一个动态数组，类似于其他语言中的数组列表（如 Python 的 list 或 Java 的 ArrayList）。Vec 提供了灵活的内存管理、高效的随机访问以及动态扩展的能力，是 Rust 标准库中最常用的集合类型之一。以下是对 Vec 的详细解析：

（一）基本概念

Vec 是一个动态数组，它在堆上分配内存，并且可以根据需要自动扩展大小。Vec 的全称是 Vec<T>，其中 T 是存储在向量中的元素类型。

特点

• 动态大小：Vec 的大小可以在运行时动态调整。
• 连续存储：元素在内存中是连续存储的，这使得随机访问非常高效。
• 类型安全：所有元素必须是同一类型。
• 所有权和借用规则：遵循 Rust 的所有权和借用规则，确保内存安全。

（二）创建向量

Vec 可以通过多种方式创建：

创建空向量

let vec: Vec<i32> = Vec::new(); // 创建一个空的向量，指定元素类型为 i32

使用宏创建向量

let vec = vec![1, 2, 3]; // 使用 vec! 宏创建一个包含元素的向量

创建带有初始值的向量

let vec = vec![0; 5]; // 创建一个包含 5 个 0 的向量

（三）向量的操作

Vec 提供了多种方法来操作向量中的元素。

添加元素

• push：在向量末尾添加一个元素。

let mut vec = Vec::new();
vec.push(1);
vec.push(2);
vec.push(3); // 向量现在是 [1, 2, 3]

• extend：一次性添加多个元素。

let mut vec = vec![1, 2];
vec.extend([3, 4, 5].iter().cloned()); // 向量现在是 [1, 2, 3, 4, 5]

移除元素

• pop：从向量末尾移除一个元素，并返回该元素。

let mut vec = vec![1, 2, 3];
if let Some(last) = vec.pop() {println!("移除的元素是：{}", last); // 输出：移除的元素是：3
}
// 向量现在是 [1, 2]

• remove：从指定位置移除一个元素。

let mut vec = vec![1, 2, 3];
vec.remove(1); // 移除索引为 1 的元素，即 2
// 向量现在是 [1, 3]

访问元素

• 通过索引访问：可以直接通过索引访问元素。

let vec = vec![1, 2, 3];
println!("第二个元素是：{}", vec[1]); // 输出：第二个元素是：2

• 使用 get 方法：安全地访问元素，返回 Option 类型。

let vec = vec![1, 2, 3];
if let Some(value) = vec.get(1) {println!("第二个元素是：{}", value); // 输出：第二个元素是：2
} else {println!("索引超出范围");
}

遍历向量

• 不可变遍历：使用 for 循环遍历向量中的元素。

let vec = vec![1, 2, 3];
for value in &vec {println!("{}", value); // 输出：1, 2, 3
}

• 可变遍历：使用 for 循环修改向量中的元素。

let mut vec = vec![1, 2, 3];
for value in &mut vec {*value += 1; // 将每个元素加 1
}
println!("{:?}", vec); // 输出：[2, 3, 4]

（四）内存管理

Vec 的内存管理是自动的，但它也有一些重要的机制：

容量和长度

• 长度（len）：表示向量中实际存储的元素数量。
• 容量（capacity）：表示向量分配的内存大小，以元素数量为单位。

let mut vec = Vec::new();
println!("初始长度：{}, 容量：{}", vec.len(), vec.capacity()); // 输出：初始长度：0, 容量：0vec.push(1);
vec.push(2);
println!("添加元素后长度：{}, 容量：{}", vec.len(), vec.capacity()); // 输出：添加元素后长度：2, 容量：4

当向量的长度超过其容量时，Vec 会自动分配更多的内存，并将旧数据复制到新的内存中。这个过程称为“重新分配”（re-allocation）。为了减少重新分配的次数，可以在创建向量时预先分配足够的容量：

let mut vec = Vec::with_capacity(10); // 预分配容量为 10
println!("初始长度：{}, 容量：{}", vec.len(), vec.capacity()); // 输出：初始长度：0, 容量：10

内存释放

当 Vec 超出作用域时，Rust 会自动释放其占用的内存。如果需要手动释放内存，可以使用 clear 方法清空向量，但这不会减少其容量：

let mut vec = vec![1, 2, 3];
vec.clear(); // 清空向量，但容量不变
println!("清空后长度：{}, 容量：{}", vec.len(), vec.capacity()); // 输出：清空后长度：0, 容量：3

（五）性能特点

Vec 的性能特点主要体现在以下几个方面：

随机访问

由于 Vec 的元素在内存中是连续存储的，因此随机访问非常高效，时间复杂度为 O(1)。

插入和删除

• 尾部插入和删除：在向量的尾部插入和删除元素非常高效，时间复杂度为 O(1)。
• 中间插入和删除：在向量的中间插入或删除元素需要移动后续的元素，因此时间复杂度为 O(n)。

内存分配

Vec 采用指数增长的内存分配策略，每次重新分配时会将容量加倍。这种策略可以减少重新分配的次数，从而提高性能。

（六）使用场景

Vec 是一种非常通用的容器类型，适用于以下场景：

• 存储连续的元素序列：例如存储数组、列表等。
• 动态扩展和收缩：需要根据运行时的需求动态调整大小。
• 随机访问：需要频繁地通过索引访问元素。

（七）注意事项

• 索引越界：访问超出范围的索引会导致运行时错误。建议使用 get 方法来安全地访问元素。
• 内存占用：虽然 Vec 提供了动态扩展的能力，但过度使用可能会导致不必要的内存占用。可以通过合理设置初始容量来优化性能。
• 所有权和借用：Vec 遵循 Rust 的所有权和借用规则，因此在使用时需要注意变量的作用域和生命周期。

（八）示例代码

以下是一个完整的示例代码，展示了 Vec 的常见用法：

fn main() {// 创建一个空向量let mut vec: Vec<i32> = Vec::new();// 添加元素vec.push(1);vec.push(2);vec.push(3);println!("向量内容：{:?}", vec); // 输出：向量内容：[1, 2, 3]// 访问元素println!("第二个元素是：{}", vec[1]); // 输出：第二个元素是：2// 安全访问元素if let Some(value) = vec.get(2) {println!("第三个元素是：{}", value); // 输出：第三个元素是：3} else {println!("索引超出范围");}// 遍历向量for value in &vec {println!("{}", value); // 输出：1, 2, 3}// 修改向量vec[1] = 20; // 修改第二个元素println!("修改后的向量：{:?}", vec); // 输出：修改后的向量：[1, 20, 3]// 移除元素if let Some(last) = vec.pop() {println!("移除的元素是：{}", last); // 输出：移除的元素是：3}println!("移除后的向量：{:?}", vec); // 输出：移除后的向量：[1, 20]
}

向量总结

Vec 是 Rust 中非常强大和灵活的动态数组类型，它提供了高效的随机访问、动态扩展和内存管理能力。通过合理使用 Vec，可以有效地管理和操作数据，同时遵循 Rust 的内存安全和性能原则。

二、哈希表（HashMap）

在 Rust 中，HashMap 是一种非常灵活且高效的键值对集合类型，它允许通过键快速查找对应的值。以下是关于 HashMap 的详细解析，包括其特点、用法示例以及一些高级特性。

（一）HashMap 的特点

• 键值对存储：HashMap 存储键值对（key-value pairs），每个键都映射到一个值。
• 快速查找：通过哈希函数实现快速查找，平均时间复杂度为 O(1)。
• 键的唯一性：每个键在 HashMap 中是唯一的。
• 动态大小：大小可以在运行时动态调整。
• 所有权和借用规则：遵循 Rust 的所有权和借用规则，确保内存安全。

（二）创建 HashMap

HashMap 的创建可以通过多种方式实现：

使用 new 方法创建

use std::collections::HashMap;let mut book_reviews = HashMap::new();
book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");

使用 collect 方法从迭代器创建

use std::collections::HashMap;let teams_list = vec![("中国队".to_string(), 100),("美国队".to_string(), 10),("日本队".to_string(), 50),
];let teams_map: HashMap<_, _> = teams_list.into_iter().collect();
println!("{:?}", teams_map);

（三）操作 HashMap

HashMap 提供了多种方法来操作键值对。

插入键值对

book_reviews.insert("Pride and Prejudice", "Very enjoyable.");

查询键值对

if let Some(review) = book_reviews.get("Pride and Prejudice") {println!("Review: {}", review);
} else {println!("No review found.");
}

更新键值对

let stat = book_reviews.entry("Pride and Prejudice").or_insert("No review");
*stat = "Updated review";

删除键值对

book_reviews.remove("Grimms' Fairy Tales");

（四）遍历 HashMap

可以通过迭代器遍历 HashMap 中的所有键值对：

for (book, review) in &book_reviews {println!("{}: {}", book, review);
}

（五）高级特性

• Entry API：HashMap 提供了 Entry API，允许更复杂的操作，例如插入键值对时检查是否已存在。
• 自定义键类型：可以通过派生 Eq 和 Hash 特性来使用自定义类型作为键。
• 性能优化：可以通过 HashMap::with_capacity 预分配容量，减少内存重新分配的次数。

（六）注意事项

• 哈希冲突：虽然 HashMap 的平均查找复杂度为 O(1)，但在最坏情况下（大量哈希冲突）可能会退化到 O(n)。
• 所有权和借用：在使用字符串等类型作为键时，需要注意所有权和借用规则。
• 默认哈希函数：Rust 使用的默认哈希函数是随机化的，以防止恶意攻击，但如果需要更高的性能，可以考虑使用第三方哈希函数。

（七）示例代码

以下是一个完整的示例代码，展示了 HashMap 的常见用法：

use std::collections::HashMap;fn main() {let mut book_reviews = HashMap::new();book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");if let Some(review) = book_reviews.get("Pride and Prejudice") {println!("Review: {}", review);} else {println!("No review found.");}for (book, review) in &book_reviews {println!("{}: {}", book, review);}
}

通过合理使用 HashMap，可以高效地管理和查询键值对数据，同时充分利用 Rust 的内存安全特性。

三、双端队列（VecDeque）

VecDeque 是 Rust 标准库中提供的一个双端队列（Double-Ended Queue）数据结构，它基于可增长的环形缓冲区实现，允许在两端高效地添加和删除元素。以下是关于 VecDeque 的详细解析：

特点

• 两端操作高效：在队列的头部和尾部添加或删除元素的时间复杂度均为 O(1)。
• 动态大小：可以根据需要动态扩展内存，支持灵活的数据操作。
• 内存不连续：VecDeque 的元素在内存中不一定是连续存储的，但可以通过 make_contiguous 方法将其变为连续存储。
• 支持多种操作：提供了丰富的 API，支持迭代、索引访问、排序等操作。

创建 VecDeque

use std::collections::VecDeque;let mut deque = VecDeque::new(); // 创建一个空的双端队列
deque.push_back(1); // 在尾部添加元素
deque.push_front(0); // 在头部添加元素

常见操作

添加元素

• push_back：在队列尾部添加元素。
• push_front：在队列头部添加元素。

删除元素

• pop_front：从队列头部移除元素。
• pop_back：从队列尾部移除元素。

访问元素

• front 和 back：分别获取队列头部和尾部的元素。
• get：通过索引访问元素。

其他操作

• len：获取队列中的元素数量。
• is_empty：检查队列是否为空。
• make_contiguous：将队列中的元素变为连续存储。
• iter 和 iter_mut：分别提供不可变和可变迭代器。

示例代码

以下是一个完整的示例代码，展示了 VecDeque 的常见用法：

use std::collections::VecDeque;fn main() {let mut deque = VecDeque::new();deque.push_back(1);deque.push_back(2);deque.push_front(0);println!("队列内容：{:?}", deque); // 输出：队列内容：[0, 1, 2]println!("队列长度：{}", deque.len()); // 输出：队列长度：3if let Some(front) = deque.pop_front() {println!("从头部移除的元素：{}", front); // 输出：从头部移除的元素：0}if let Some(back) = deque.pop_back() {println!("从尾部移除的元素：{}", back); // 输出：从尾部移除的元素：2}println!("队列内容：{:?}", deque); // 输出：队列内容：[1]
}

高级特性

• as_slices 和 as_mut_slices：将 VecDeque 分解为两个切片，分别表示头部和尾部的元素。
• binary_search_by 和 binary_search_by_key：在有序的 VecDeque 上进行二分查找。
• partition_point：找到满足特定条件的分区点。

通过合理使用 VecDeque，可以高效地实现队列和栈的功能，同时利用 Rust 的内存安全特性。

四、二叉堆（BinaryHeap）

BinaryHeap 是 Rust 标准库中提供的一个基于二叉堆的数据结构，通常用于实现优先队列。它默认是一个最大堆，即堆顶元素是所有元素中最大的。以下是关于 BinaryHeap 的详细解析：

特点

• 最大堆：默认情况下，BinaryHeap 是一个最大堆，堆顶元素是最大的。
• 高效插入和删除：插入和删除操作的时间复杂度为 O(log n)。
• 动态大小：可以根据需要动态调整大小。
• 基于数组实现：底层使用数组实现，支持随机访问。
• 可转换为最小堆：通过 std::cmp::Reverse 包装器或自定义 Ord 实现，可以将 BinaryHeap 转换为最小堆。

创建 BinaryHeap

use std::collections::BinaryHeap;let mut heap = BinaryHeap::new(); // 创建一个空的最大堆
heap.push(1);
heap.push(5);
heap.push(2);

也可以通过数组初始化：

let heap = BinaryHeap::from([1, 5, 2]); // 从数组创建

常见操作

插入元素

heap.push(10); // 向堆中插入一个元素

获取堆顶元素

if let Some(&max) = heap.peek() {println!("堆顶元素是：{}", max); // 输出堆顶元素，不移除
}

移除堆顶元素

if let Some(max) = heap.pop() {println!("移除的堆顶元素是：{}", max); // 移除并返回堆顶元素
}

检查堆的大小和是否为空

println!("堆的大小：{}", heap.len()); // 获取堆的大小
println!("堆是否为空：{}", heap.is_empty()); // 检查堆是否为空

遍历堆

for &value in &heap {println!("{}", value); // 遍历堆中的元素，但顺序不保证
}

最小堆的实现

可以通过 std::cmp::Reverse 将 BinaryHeap 转换为最小堆：

use std::cmp::Reverse;let mut min_heap = BinaryHeap::new();
min_heap.push(Reverse(1));
min_heap.push(Reverse(5));
min_heap.push(Reverse(2));if let Some(Reverse(min)) = min_heap.pop() {println!("最小堆的堆顶元素是：{}", min); // 输出最小值
}

高级特性

• peek_mut：可以获取堆顶元素的可变引用，并修改它。
• into_sorted_vec：将堆转换为有序的向量。
• drain_sorted：以堆序移除所有元素（需要启用 nightly 特性）。
• retain：根据条件保留某些元素。

示例代码

以下是一个完整的示例代码，展示了 BinaryHeap 的常见用法：

use std::collections::BinaryHeap;fn main() {let mut heap = BinaryHeap::new();heap.push(1);heap.push(5);heap.push(2);println!("堆顶元素是：{:?}", heap.peek()); // 输出：Some(5)println!("堆的大小是：{}", heap.len()); // 输出：3while let Some(max) = heap.pop() {println!("移除的元素是：{}", max); // 按从大到小的顺序移除}// 最小堆示例use std::cmp::Reverse;let mut min_heap = BinaryHeap::new();min_heap.push(Reverse(1));min_heap.push(Reverse(5));min_heap.push(Reverse(2));while let Some(Reverse(min)) = min_heap.pop() {println!("最小堆移除的元素是：{}", min); // 按从小到大的顺序移除}
}

注意事项

• 元素顺序：BinaryHeap 的迭代器返回的元素顺序是任意的，只有通过 pop 方法才能保证顺序。
• 性能：虽然 BinaryHeap 的插入和删除操作平均时间复杂度为 O(log n)，但在某些情况下（如连续插入有序数据）可能会退化到 O(n)。
• 自定义排序：如果需要自定义排序逻辑，可以通过实现 Ord 特性或使用 Reverse 来调整行为。

通过合理使用 BinaryHeap，可以高效地实现优先队列功能，同时利用 Rust 的内存安全特性。

五、字符串（String）

单独学习。

六、其他容器类型

Rust 还提供了其他一些容器类型，例如：

• LinkedList：双向链表，支持在链表的任意位置高效地插入和删除元素。
• HashSet：无序的集合，存储唯一的元素。
• BTreeMap 和 BTreeSet：基于 B 树实现的有序映射和集合，支持有序遍历。

每种容器类型都有其特定的用途和性能特点，选择合适的容器类型可以提高代码的效率和可读性。

七、综合示例

以下是一个综合示例代码，全面展示了 Rust 中各种容器数据类型的定义和应用：

use std::collections::{HashMap, VecDeque, BinaryHeap, LinkedList, HashSet, BTreeMap, BTreeSet};fn main() {// Vec 的使用vec_example();// HashMap 的使用hash_map_example();// VecDeque 的使用vec_deque_example();// BinaryHeap 的使用binary_heap_example();// LinkedList 的使用linked_list_example();// HashSet 的使用hash_set_example();// BTreeMap 和 BTreeSet 的使用b_tree_example();
}fn vec_example() {println!("--- Vec 示例 ---");// 创建一个空向量let mut vec: Vec<i32> = Vec::new();// 添加元素vec.push(1);vec.push(2);vec.push(3);println!("向量内容：{:?}", vec);// 访问元素println!("第二个元素是：{}", vec[1]);// 安全访问元素if let Some(value) = vec.get(2) {println!("第三个元素是：{}", value);} else {println!("索引超出范围");}// 遍历向量for value in &vec {println!("{}", value);}// 修改向量vec[1] = 20;println!("修改后的向量：{:?}", vec);// 移除元素if let Some(last) = vec.pop() {println!("移除的元素是：{}", last);}println!("移除后的向量：{:?}", vec);
}fn hash_map_example() {println!("\n--- HashMap 示例 ---");let mut book_reviews = HashMap::new();book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");if let Some(review) = book_reviews.get("Pride and Prejudice") {println!("Review: {}", review);} else {println!("No review found.");}for (book, review) in &book_reviews {println!("{}: {}", book, review);}
}fn vec_deque_example() {println!("\n--- VecDeque 示例 ---");let mut deque = VecDeque::new();deque.push_back(1);deque.push_back(2);deque.push_front(0);println!("队列内容：{:?}", deque);println!("队列长度：{}", deque.len());if let Some(front) = deque.pop_front() {println!("从头部移除的元素：{}", front);}if let Some(back) = deque.pop_back() {println!("从尾部移除的元素：{}", back);}println!("队列内容：{:?}", deque);
}fn binary_heap_example() {println!("\n--- BinaryHeap 示例 ---");let mut heap = BinaryHeap::new();heap.push(1);heap.push(5);heap.push(2);println!("堆顶元素是：{:?}", heap.peek());println!("堆的大小是：{}", heap.len());while let Some(max) = heap.pop() {println!("移除的元素是：{}", max);}// 最小堆示例use std::cmp::Reverse;let mut min_heap = BinaryHeap::new();min_heap.push(Reverse(1));min_heap.push(Reverse(5));min_heap.push(Reverse(2));while let Some(Reverse(min)) = min_heap.pop() {println!("最小堆移除的元素是：{}", min);}
}fn linked_list_example() {println!("\n--- LinkedList 示例 ---");let mut list = LinkedList::new();list.push_back(1);list.push_back(2);list.push_front(0);println!("链表内容：{:?}", list);println!("链表长度：{}", list.len());if let Some(front) = list.pop_front() {println!("从头部移除的元素：{}", front);}if let Some(back) = list.pop_back() {println!("从尾部移除的元素：{}", back);}println!("链表内容：{:?}", list);
}fn hash_set_example() {println!("\n--- HashSet 示例 ---");let mut set = HashSet::new();set.insert(1);set.insert(2);set.insert(3);println!("集合内容：{:?}", set);if set.contains(&2) {println!("集合中包含元素 2");}set.remove(&2);println!("移除元素 2 后的集合内容：{:?}", set);
}fn b_tree_example() {println!("\n--- BTreeMap 和 BTreeSet 示例 ---");let mut btree_map = BTreeMap::new();btree_map.insert(1, "one");btree_map.insert(2, "two");btree_map.insert(3, "three");println!("BTreeMap 内容：{:?}", btree_map);for (key, value) in &btree_map {println!("{}: {}", key, value);}let mut btree_set = BTreeSet::new();btree_set.insert(1);btree_set.insert(2);btree_set.insert(3);println!("BTreeSet 内容：{:?}", btree_set);if btree_set.contains(&2) {println!("BTreeSet 中包含元素 2");}btree_set.remove(&2);println!("移除元素 2 后的 BTreeSet 内容：{:?}", btree_set);
}

运行结果

--- Vec 示例 ---
向量内容：[1, 2, 3]
第二个元素是：2
第三个元素是：3
1
2
3
修改后的向量：[1, 20, 3]
移除的元素是：3
--- HashMap 示例 ---]
No review found.
Grimms' Fairy Tales: Masterpiece.
--- VecDeque 示例 ---erry Finn: My favorite book.
队列内容：[0, 1, 2]
队列长度：3
从头部移除的元素：0
从尾部移除的元素：2
队列内容：[1]--- BinaryHeap 示例 ---
堆顶元素是：Some(5)
堆的大小是：3
移除的元素是：5
移除的元素是：2
移除的元素是：1
最小堆移除的元素是：1
最小堆移除的元素是：2
最小堆移除的元素是：5--- LinkedList 示例 ---
链表内容：[0, 1, 2]
链表长度：3
从头部移除的元素：0
从尾部移除的元素：2
链表内容：[1]--- HashSet 示例 ---
集合内容：{3, 1, 2}
集合中包含元素 2
移除元素 2 后的集合内容：{3, 1}--- BTreeMap 和 BTreeSet 示例 ---
BTreeMap 内容：{1: "one", 2: "two", 3: "three"}
1: one
2: two
3: three
BTreeSet 内容：{1, 2, 3}
BTreeSet 中包含元素 2
移除元素 2 后的 BTreeSet 内容：{1, 3}

示例代码说明

1. Vec 示例：
   • 创建空向量、添加元素、访问元素、安全访问、遍历、修改和移除元素。
2. HashMap 示例：
   • 创建哈希表、插入键值对、查询键值对、遍历哈希表。
3. VecDeque 示例：
   • 创建双端队列、在两端添加和移除元素、访问元素。
4. BinaryHeap 示例：
   • 创建二叉堆、插入元素、获取堆顶元素、移除堆顶元素、最小堆的实现。
5. LinkedList 示例：
   • 创建双向链表、在两端添加和移除元素、访问元素。
6. HashSet 示例：
   • 创建集合、插入元素、检查元素是否存在、移除元素。
7. BTreeMap 和 BTreeSet 示例：
   • 创建有序映射和有序集合、插入元素、遍历、检查元素是否存在、移除元素。

总结

Rust 提供了多种容器类型，每种都有其独特用途和性能特点。Vec 是动态数组，支持高效随机访问和动态扩展，适用于存储连续元素序列。String 是动态字符串，支持 UTF-8 编码文本的高效操作。HashMap 是键值对集合，通过哈希函数实现快速查找，适用于需要快速检索的场景。VecDeque 是双端队列，支持在两端高效插入和删除元素，适合实现队列和栈。BinaryHeap 是基于二叉堆的优先队列，默认为最大堆，支持高效插入和删除最大元素，可通过 Reverse 转换为最小堆。此外，还有 LinkedList、HashSet、BTreeMap 和 BTreeSet 等，分别适用于特定场景，如有序存储或快速集合操作。选择合适的容器类型可以提高代码效率和可读性，同时充分利用 Rust 的内存安全特性。