10.1 章节概述
集合类型是编程中最常用的数据结构之一，Rust标准库提供了丰富而高效的集合类型。本章将深入学习Rust的各种集合类型，包括它们的特性、使用场景和性能特点。
🎯 学习目标
- 掌握Rust标准库中的主要集合类型
- 理解不同集合类型的性能特点和适用场景
- 学会选择合适的集合类型解决实际问题
- 掌握集合的常用操作和迭代器模式
- 了解集合的内存管理和优化技巧
📋 本章内容
- 向量（Vec） - 动态数组的使用和优化
- 哈希映射（HashMap） - 键值对存储和查找
- 哈希集合（HashSet） - 唯一值的集合操作
- 其他集合类型 - VecDeque、BTreeMap、BTreeSet等
- 集合的选择和性能 - 不同场景下的最佳选择
- 综合示例 - 实际应用中的集合使用
10.2 向量（Vec）
向量是Rust中最常用的集合类型，它是一个可增长的数组，所有元素必须是相同类型。
10.2.1 向量基础
fn main() {
println!("📊 向量基础操作");
println!("===============");
demonstrate_vector_creation();
demonstrate_vector_operations();
demonstrate_vector_access();
demonstrate_vector_iteration();
}
fn demonstrate_vector_creation() {
println!("\n向量创建:");
// 创建空向量
let mut v1: Vec<i32> = Vec::new();
println!("空向量: {:?}", v1);
// 使用vec!宏创建
let v2 = vec![1, 2, 3, 4, 5];
println!("使用宏创建: {:?}", v2);
// 创建指定容量的向量
let mut v3 = Vec::with_capacity(10);
println!("指定容量向量，容量: {}, 长度: {}", v3.capacity(), v3.len());
// 从迭代器创建
let v4: Vec<i32> = (1..=5).collect();
println!("从迭代器创建: {:?}", v4);
// 创建重复元素的向量
let v5 = vec![0; 5]; // 5个0
println!("重复元素向量: {:?}", v5);
// 从数组创建
let arr = [1, 2, 3, 4, 5];
let v6 = Vec::from(arr);
println!("从数组创建: {:?}", v6);
// 从切片创建
let slice = &[1, 2, 3];
let v7 = slice.to_vec();
println!("从切片创建: {:?}", v7);
}
fn demonstrate_vector_operations() {
println!("\n向量操作:");
let mut v = Vec::new();
// 添加元素
v.push(1);
v.push(2);
v.push(3);
println!("添加元素后: {:?}", v);
// 弹出元素
if let Some(last) = v.pop() {
println!("弹出的元素: {}", last);
}
println!("弹出后: {:?}", v);
// 插入元素
v.insert(1, 10);
println!("在索引1插入10: {:?}", v);
// 移除元素
let removed = v.remove(1);
println!("移除索引1的元素: {}, 结果: {:?}", removed, v);
// 扩展向量
v.extend(vec![4, 5, 6]);
println!("扩展后: {:?}", v);
// 追加另一个向量
let mut other = vec![7, 8, 9];
v.append(&mut other);
println!("追加后: {:?}", v);
println!("被追加的向量: {:?}", other); // 现在为空
// 清空向量
let mut temp = v.clone();
temp.clear();
println!("清空后: {:?}", temp);
// 截断向量
let mut truncated = v.clone();
truncated.truncate(3);
println!("截断到3个元素: {:?}", truncated);
// 保留满足条件的元素
let mut filtered = v.clone();
filtered.retain(|&x| x % 2 == 0);
println!("保留偶数: {:?}", filtered);
// 去重（需要先排序）
let mut with_duplicates = vec![1, 2, 2, 3, 3, 3, 4];
with_duplicates.sort();
with_duplicates.dedup();
println!("去重后: {:?}", with_duplicates);
}
fn demonstrate_vector_access() {
println!("\n向量访问:");
let v = vec![1, 2, 3, 4, 5];
// 索引访问（可能panic）
println!("索引2的元素: {}", v[2]);
// 安全访问
match v.get(2) {
Some(value) => println!("安全访问索引2: {}", value),
None => println!("索引2不存在"),
}
// 访问不存在的索引
match v.get(10) {
Some(value) => println!("索引10的值: {}", value),
None => println!("索引10不存在"),
}
// 获取第一个和最后一个元素
if let Some(first) = v.first() {
println!("第一个元素: {}", first);
}
if let Some(last) = v.last() {
println!("最后一个元素: {}", last);
}
// 切片访问
let slice = &v[1..4];
println!("切片[1..4]: {:?}", slice);
// 可变访问
let mut v_mut = vec![1, 2, 3, 4, 5];
v_mut[0] = 10;
println!("修改后: {:?}", v_mut);
if let Some(first_mut) = v_mut.first_mut() {
*first_mut = 100;
}
println!("修改第一个元素后: {:?}", v_mut);
}
fn demonstrate_vector_iteration() {
println!("\n向量迭代:");
let v = vec![1, 2, 3, 4, 5];
// 不可变迭代
println!("不可变迭代:");
for item in &v {
print!("{} ", item);
}
println!();
// 可变迭代
let mut v_mut = vec![1, 2, 3, 4, 5];
println!("可变迭代（每个元素乘以2）:");
for item in &mut v_mut {
*item *= 2;
}
println!("{:?}", v_mut);
// 拥有所有权的迭代
println!("拥有所有权的迭代:");
for item in v {
print!("{} ", item);
}
println!();
// 使用迭代器方法
let v2 = vec![1, 2, 3, 4, 5];
let sum: i32 = v2.iter().sum();
println!("元素和: {}", sum);
let doubled: Vec<i32> = v2.iter().map(|x| x * 2).collect();
println!("每个元素乘以2: {:?}", doubled);
let even_count = v2.iter().filter(|&&x| x % 2 == 0).count();
println!("偶数个数: {}", even_count);
let first_even = v2.iter().find(|&&x| x % 2 == 0);
println!("第一个偶数: {:?}", first_even);
// 枚举迭代
println!("枚举迭代:");
for (index, value) in v2.iter().enumerate() {
println!("索引{}: 值{}", index, value);
}
}
rustc vector_basics.rs && ./vector_basics
10.2.2 向量性能优化
fn main() {
println!("⚡ 向量性能优化");
println!("===============");
demonstrate_capacity_management();
demonstrate_memory_layout();
demonstrate_performance_tips();
}
fn demonstrate_capacity_management() {
println!("\n容量管理:");
// 容量和长度的区别
let mut v = Vec::new();
println!("初始 - 长度: {}, 容量: {}", v.len(), v.capacity());
// 添加元素观察容量变化
for i in 1..=10 {
v.push(i);
println!("添加{} - 长度: {}, 容量: {}", i, v.len(), v.capacity());
}
// 预分配容量
println!("\n预分配容量:");
let mut v_with_capacity = Vec::with_capacity(10);
println!("预分配 - 长度: {}, 容量: {}", v_with_capacity.len(), v_with_capacity.capacity());
for i in 1..=10 {
v_with_capacity.push(i);
if i <= 3 || i == 10 {
println!("添加{} - 长度: {}, 容量: {}", i, v_with_capacity.len(), v_with_capacity.capacity());
}
}
// 手动调整容量
let mut v_reserve = vec![1, 2, 3];
println!("\n手动调整容量:");
println!("调整前 - 长度: {}, 容量: {}", v_reserve.len(), v_reserve.capacity());
v_reserve.reserve(10); // 至少保证额外10个元素的容量
println!("reserve(10)后 - 长度: {}, 容量: {}", v_reserve.len(), v_reserve.capacity());
v_reserve.reserve_exact(5); // 精确保证额外5个元素的容量
println!("reserve_exact(5)后 - 长度: {}, 容量: {}", v_reserve.len(), v_reserve.capacity());
// 收缩容量
v_reserve.shrink_to_fit();
println!("shrink_to_fit()后 - 长度: {}, 容量: {}", v_reserve.len(), v_reserve.capacity());
}
fn demonstrate_memory_layout() {
println!("\n内存布局:");
let v = vec![1, 2, 3, 4, 5];
// 获取原始指针
let ptr = v.as_ptr();
println!("向量指针: {:p}", ptr);
println!("向量长度: {}", v.len());
println!("向量容量: {}", v.capacity());
// 元素地址
for (i, item) in v.iter().enumerate() {
println!("元素{}地址: {:p}, 值: {}", i, item, item);
}
// 切片和向量的关系
let slice: &[i32] = &v;
println!("\n切片指针: {:p}", slice.as_ptr());
println!("切片长度: {}", slice.len());
// 从原始部分创建向量（不安全操作）
unsafe {
let reconstructed = Vec::from_raw_parts(ptr as *mut i32, v.len(), v.capacity());
println!("重构的向量: {:?}", reconstructed);
// 注意：这里会导致双重释放，实际代码中不要这样做
std::mem::forget(reconstructed); // 防止双重释放
}
// 向量的内存占用
println!("\n内存占用:");
println!("Vec<i32>大小: {} 字节", std::mem::size_of::<Vec<i32>>());
println!("i32大小: {} 字节", std::mem::size_of::<i32>());
println!("5个i32的向量堆内存: {} 字节", v.capacity() * std::mem::size_of::<i32>());
}
fn demonstrate_performance_tips() {
println!("\n性能技巧:");
// 技巧1：预分配容量
println!("1. 预分配容量的重要性:");
let start = std::time::Instant::now();
let mut v1 = Vec::new();
for i in 0..100000 {
v1.push(i);
}
let duration1 = start.elapsed();
println!("不预分配耗时: {:?}", duration1);
let start = std::time::Instant::now();
let mut v2 = Vec::with_capacity(100000);
for i in 0..100000 {
v2.push(i);
}
let duration2 = start.elapsed();
println!("预分配耗时: {:?}", duration2);
// 技巧2：批量操作
println!("\n2. 批量操作vs单个操作:");
let data: Vec<i32> = (0..10000).collect();
let start = std::time::Instant::now();
let mut v3 = Vec::new();
for &item in &data {
v3.push(item);
}
let duration3 = start.elapsed();
println!("逐个push耗时: {:?}", duration3);
let start = std::time::Instant::now();
let mut v4 = Vec::new();
v4.extend(&data);
let duration4 = start.elapsed();
println!("extend耗时: {:?}", duration4);
// 技巧3：避免不必要的克隆
println!("\n3. 避免不必要的克隆:");
let large_vec: Vec<String> = (0..1000)
.map(|i| format!("字符串{}", i))
.collect();
// 不好的做法：克隆整个向量
let start = std::time::Instant::now();
let _cloned = large_vec.clone();
let clone_duration = start.elapsed();
println!("克隆向量耗时: {:?}", clone_duration);
// 好的做法：使用引用
let start = std::time::Instant::now();
let _referenced = &large_vec;
let ref_duration = start.elapsed();
println!("引用向量耗时: {:?}", ref_duration);
// 技巧4：选择合适的迭代方式
println!("\n4. 迭代方式的性能差异:");
let numbers: Vec<i32> = (0..100000).collect();
// 索引访问
let start = std::time::Instant::now();
let mut sum1 = 0;
for i in 0..numbers.len() {
sum1 += numbers[i];
}
let index_duration = start.elapsed();
println!("索引访问耗时: {:?}, 和: {}", index_duration, sum1);
// 迭代器
let start = std::time::Instant::now();
let sum2: i32 = numbers.iter().sum();
let iter_duration = start.elapsed();
println!("迭代器耗时: {:?}, 和: {}", iter_duration, sum2);
// for循环
let start = std::time::Instant::now();
let mut sum3 = 0;
for &num in &numbers {
sum3 += num;
}
let for_duration = start.elapsed();
println!("for循环耗时: {:?}, 和: {}", for_duration, sum3);
}
rustc vector_performance.rs && ./vector_performance
10.3 哈希映射（HashMap）
哈希映射是一种键值对集合，提供快速的查找、插入和删除操作。
10.3.1 HashMap基础
use std::collections::HashMap;
fn main() {
println!("🗂️ HashMap基础操作");
println!("==================");
demonstrate_hashmap_creation();
demonstrate_hashmap_operations();
demonstrate_hashmap_access();
demonstrate_hashmap_iteration();
}
fn demonstrate_hashmap_creation() {
println!("\nHashMap创建:");
// 创建空HashMap
let mut map1: HashMap<String, i32> = HashMap::new();
println!("空HashMap: {:?}", map1);
// 使用with_capacity创建
let mut map2 = HashMap::with_capacity(10);
map2.insert("key1".to_string(), 100);
println!("指定容量HashMap: {:?}", map2);
// 从迭代器创建
let map3: HashMap<i32, String> = (1..=5)
.map(|i| (i, format!("值{}", i)))
.collect();
println!("从迭代器创建: {:?}", map3);
// 从数组创建
let pairs = [("a", 1), ("b", 2), ("c", 3)];
let map4: HashMap<&str, i32> = pairs.iter().cloned().collect();
println!("从数组创建: {:?}", map4);
// 使用宏创建（需要外部crate）
// 这里展示手动创建的方式
let mut map5 = HashMap::new();
map5.insert("红色", "#FF0000");
map5.insert("绿色", "#00FF00");
map5.insert("蓝色", "#0000FF");
println!("颜色映射: {:?}", map5);
}
fn demonstrate_hashmap_operations() {
println!("\nHashMap操作:");
let mut scores = HashMap::new();
// 插入键值对
scores.insert("Alice".to_string(), 95);
scores.insert("Bob".to_string(), 87);
scores.insert("Charlie".to_string(), 92);
println!("插入后: {:?}", scores);
// 更新值
scores.insert("Alice".to_string(), 98); // 覆盖原值
println!("更新Alice的分数: {:?}", scores);
// 只在键不存在时插入
scores.entry("David".to_string()).or_insert(85);
scores.entry("Alice".to_string()).or_insert(80); // 不会覆盖
println!("使用entry插入: {:?}", scores);
// 基于现有值更新
let alice_score = scores.entry("Alice".to_string()).or_insert(0);
*alice_score += 2; // Alice的分数+2
println!("更新Alice分数+2: {:?}", scores);
// 移除键值对
if let Some(removed) = scores.remove("Bob") {
println!("移除Bob，分数为: {}", removed);
}
println!("移除Bob后: {:?}", scores);
// 清空HashMap
let mut temp = scores.clone();
temp.clear();
println!("清空后: {:?}", temp);
// 保留满足条件的元素
scores.retain(|_, &mut score| score >= 90);
println!("保留分数>=90的学生: {:?}", scores);
}
fn demonstrate_hashmap_access() {
println!("\nHashMap访问:");
let mut scores = HashMap::new();
scores.insert("Alice", 95);
scores.insert("Bob", 87);
scores.insert("Charlie", 92);
// 获取值
match scores.get("Alice") {
Some(score) => println!("Alice的分数: {}", score),
None => println!("Alice不存在"),
}
// 获取不存在的键
match scores.get("David") {
Some(score) => println!("David的分数: {}", score),
None => println!("David不存在"),
}
// 获取可变引用
if let Some(score) = scores.get_mut("Bob") {
*score += 5;
println!("Bob分数+5后: {}", score);
}
// 检查键是否存在
println!("包含Alice: {}", scores.contains_key("Alice"));
println!("包含David: {}", scores.contains_key("David"));
// 获取键值对的数量
println!("HashMap大小: {}", scores.len());
println!("HashMap是否为空: {}", scores.is_empty());
// 使用entry API
let charlie_score = scores.entry("Charlie").or_insert(0);
println!("Charlie的分数: {}", charlie_score);
// entry的高级用法
scores.entry("Eve").and_modify(|score| *score += 10).or_insert(75);
println!("添加Eve或修改Eve的分数: {:?}", scores);
scores.entry("Alice").and_modify(|score| *score += 10).or_insert(75);
println!("修改Alice的分数+10: {:?}", scores);
}
fn demonstrate_hashmap_iteration() {
println!("\nHashMap迭代:");
let mut scores = HashMap::new();
scores.insert("Alice", 95);
scores.insert("Bob", 87);
scores.insert("Charlie", 92);
scores.insert("David", 88);
// 迭代键值对
println!("迭代键值对:");
for (name, score) in &scores {
println!("{}: {}", name, score);
}
// 只迭代键
println!("\n只迭代键:");
for name in scores.keys() {
println!("{}", name);
}
// 只迭代值
println!("\n只迭代值:");
for score in scores.values() {
println!("{}", score);
}
// 可变迭代值
println!("\n可变迭代值（所有分数+5）:");
for score in scores.values_mut() {
*score += 5;
}
for (name, score) in &scores {
println!("{}: {}", name, score);
}
// 拥有所有权的迭代
println!("\n拥有所有权的迭代:");
let scores_clone = scores.clone();
for (name, score) in scores_clone {
println!("{}: {}", name, score);
}
// 使用迭代器方法
let total_score: i32 = scores.values().sum();
println!("\n总分: {}", total_score);
let high_scores: Vec<(&str, &i32)> = scores
.iter()
.filter(|(_, &score)| score >= 95)
.collect();
println!("高分学生: {:?}", high_scores);
let names: Vec<&str> = scores.keys().cloned().collect();
println!("所有学生姓名: {:?}", names);
// 查找最高分
if let Some((name, score)) = scores.iter().max_by_key(|(_, score)| *score) {
println!("最高分: {} - {}", name, score);
}
// 查找最低分
if let Some((name, score)) = scores.iter().min_by_key(|(_, score)| *score) {
println!("最低分: {} - {}", name, score);
}
}
rustc hashmap_basics.rs && ./hashmap_basics
10.3.2 HashMap高级用法
use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;
fn main() {
println!("🔧 HashMap高级用法");
println!("==================");
demonstrate_custom_types();
demonstrate_hash_function();
demonstrate_entry_api();
demonstrate_performance_tips();
}
fn demonstrate_custom_types() {
println!("\n自定义类型作为键:");
// 自定义结构体作为键
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Person {
name: String,
age: u32,
}
impl Person {
fn new(name: &str, age: u32) -> Self {
Person {
name: name.to_string(),
age,
}
}
}
let mut person_scores = HashMap::new();
let alice = Person::new("Alice", 25);
let bob = Person::new("Bob", 30);
let charlie = Person::new("Charlie", 28);
person_scores.insert(alice.clone(), 95);
person_scores.insert(bob.clone(), 87);
person_scores.insert(charlie.clone(), 92);
println!("人员分数映射:");
for (person, score) in &person_scores {
println!("{:?}: {}", person, score);
}
// 查找特定人员
let search_person = Person::new("Alice", 25);
if let Some(score) = person_scores.get(&search_person) {
println!("找到Alice的分数: {}", score);
}
// 枚举作为键
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum Color {
Red,
Green,
Blue,
RGB(u8, u8, u8),
}
let mut color_names = HashMap::new();
color_names.insert(Color::Red, "红色");
color_names.insert(Color::Green, "绿色");
color_names.insert(Color::Blue, "蓝色");
color_names.insert(Color::RGB(255, 165, 0), "橙色");
println!("\n颜色名称映射:");
for (color, name) in &color_names {
println!("{:?}: {}", color, name);
}
}
fn demonstrate_hash_function() {
println!("\n哈希函数:");
// 查看不同值的哈希值
fn calculate_hash<T: Hash>(t: &T) -> u64 {
let mut hasher = DefaultHasher::new();
t.hash(&mut hasher);
hasher.finish()
}
let strings = vec!["hello", "world", "rust", "programming"];
println!("字符串哈希值:");
for s in &strings {
println!("{}: {}", s, calculate_hash(s));
}
let numbers = vec![1, 2, 3, 100, 1000];
println!("\n数字哈希值:");
for n in &numbers {
println!("{}: {}", n, calculate_hash(n));
}
// 自定义哈希实现
#[derive(Debug, PartialEq, Eq)]
struct CustomKey {
id: u32,
name: String,
}
impl Hash for CustomKey {
fn hash<H: Hasher>(&self, state: &mut H) {
// 只基于id进行哈希，忽略name
self.id.hash(state);
}
}
let mut custom_map = HashMap::new();
let key1 = CustomKey { id: 1, name: "Alice".to_string() };
let key2 = CustomKey { id: 1, name: "Bob".to_string() }; // 相同的id
custom_map.insert(key1, "值1");
println!("\n自定义哈希 - 插入key1后: {:?}", custom_map);
// 由于哈希值相同且PartialEq基于结构体所有字段，这会被视为不同的键
custom_map.insert(key2, "值2");
println!("插入key2后: {:?}", custom_map);
// 展示哈希冲突处理
println!("\n哈希冲突演示:");
let mut collision_map = HashMap::new();
// 这些字符串可能产生哈希冲突（在某些哈希函数下）
let test_strings = vec!["a", "b", "c", "aa", "bb", "cc"];
for (i, s) in test_strings.iter().enumerate() {
collision_map.insert(*s, i);
println!("插入'{}': 哈希值={}, 映射大小={}", s, calculate_hash(s), collision_map.len());
}
}
fn demonstrate_entry_api() {
println!("\nEntry API高级用法:");
let mut word_count = HashMap::new();
let text = "hello world hello rust world programming rust";
// 统计单词出现次数
for word in text.split_whitespace() {
*word_count.entry(word).or_insert(0) += 1;
}
println!("单词计数: {:?}", word_count);
// 使用entry进行复杂操作
let mut student_grades = HashMap::new();
// 为学生添加成绩
fn add_grade(grades: &mut HashMap<String, Vec<i32>>, student: &str, grade: i32) {
grades.entry(student.to_string())
.or_insert_with(Vec::new)
.push(grade);
}
add_grade(&mut student_grades, "Alice", 95);
add_grade(&mut student_grades, "Alice", 87);
add_grade(&mut student_grades, "Bob", 92);
add_grade(&mut student_grades, "Alice", 91);
add_grade(&mut student_grades, "Bob", 88);
println!("\n学生成绩: {:?}", student_grades);
// 计算平均分
let mut averages = HashMap::new();
for (student, grades) in &student_grades {
let average = grades.iter().sum::<i32>() as f64 / grades.len() as f64;
averages.insert(student.clone(), average);
}
println!("平均分: {:?}", averages);
// 使用entry进行条件更新
let mut cache = HashMap::new();
// 模拟缓存操作
fn get_or_compute(cache: &mut HashMap<String, i32>, key: &str) -> i32 {
*cache.entry(key.to_string()).or_insert_with(|| {
println!("计算{}的值", key);
key.len() as i32 * 10 // 模拟复杂计算
})
}
println!("\n缓存操作:");
println!("第一次获取'hello': {}", get_or_compute(&mut cache, "hello"));
println!("第二次获取'hello': {}", get_or_compute(&mut cache, "hello"));
println!("获取'world': {}", get_or_compute(&mut cache, "world"));
println!("缓存内容: {:?}", cache);
}
fn demonstrate_performance_tips() {
println!("\n性能优化技巧:");
// 技巧1：预分配容量
println!("1. 预分配容量:");
let start = std::time::Instant::now();
let mut map1 = HashMap::new();
for i in 0..10000 {
map1.insert(i, i * 2);
}
let duration1 = start.elapsed();
println!("不预分配耗时: {:?}", duration1);
let start = std::time::Instant::now();
let mut map2 = HashMap::with_capacity(10000);
for i in 0..10000 {
map2.insert(i, i * 2);
}
let duration2 = start.elapsed();
println!("预分配耗时: {:?}", duration2);
// 技巧2：避免不必要的字符串分配
println!("\n2. 字符串键的优化:");
// 不好的做法：每次都创建新字符串
let start = std::time::Instant::now();
let mut map3 = HashMap::new();
for i in 0..1000 {
let key = format!("key{}", i);
map3.insert(key, i);
}
let duration3 = start.elapsed();
println!("创建字符串键耗时: {:?}", duration3);
// 好的做法：使用&str或预先创建字符串
let keys: Vec<String> = (0..1000).map(|i| format!("key{}", i)).collect();
let start = std::time::Instant::now();
let mut map4 = HashMap::new();
for (i, key) in keys.iter().enumerate() {
map4.insert(key, i);
}
let duration4 = start.elapsed();
println!("使用预创建字符串键耗时: {:?}", duration4);
// 技巧3：批量操作
println!("\n3. 批量操作:");
let data: Vec<(i32, i32)> = (0..5000).map(|i| (i, i * 2)).collect();
let start = std::time::Instant::now();
let mut map5 = HashMap::new();
for (k, v) in &data {
map5.insert(*k, *v);
}
let duration5 = start.elapsed();
println!("逐个插入耗时: {:?}", duration5);
let start = std::time::Instant::now();
let map6: HashMap<i32, i32> = data.iter().cloned().collect();
let duration6 = start.elapsed();
println!("批量创建耗时: {:?}", duration6);
// 技巧4：选择合适的键类型
println!("\n4. 键类型的选择:");
// 使用整数键
let start = std::time::Instant::now();
let mut int_map = HashMap::new();
for i in 0..10000 {
int_map.insert(i, i.to_string());
}
let int_duration = start.elapsed();
println!("整数键耗时: {:?}", int_duration);
// 使用字符串键
let start = std::time::Instant::now();
let mut string_map = HashMap::new();
for i in 0..10000 {
string_map.insert(i.to_string(), i);
}
let string_duration = start.elapsed();
println!("字符串键耗时: {:?}", string_duration);
println!("\n容量信息:");
println!("map1容量: {}, 长度: {}", map1.capacity(), map1.len());
println!("map2容量: {}, 长度: {}", map2.capacity(), map2.len());
}
rustc hashmap_advanced.rs && ./hashmap_advanced
10.4 哈希集合（HashSet）
HashSet是一个无序的唯一值集合，基于HashMap实现，提供快速的插入、删除和查找操作。
10.4.1 HashSet基础
use std::collections::HashSet;
fn main() {
println!("📚 HashSet基础操作");
println!("==================");
demonstrate_hashset_creation();
demonstrate_hashset_operations();
demonstrate_set_operations();
demonstrate_hashset_iteration();
}
fn demonstrate_hashset_creation() {
println!("\nHashSet创建:");
// 创建空HashSet
let mut set1: HashSet<i32> = HashSet::new();
println!("空HashSet: {:?}", set1);
// 使用with_capacity创建
let mut set2 = HashSet::with_capacity(10);
set2.insert(1);
println!("指定容量HashSet: {:?}", set2);
// 从迭代器创建
let set3: HashSet<i32> = (1..=5).collect();
println!("从迭代器创建: {:?}", set3);
// 从数组创建
let arr = [1, 2, 3, 4, 5, 3, 2, 1]; // 包含重复元素
let set4: HashSet<i32> = arr.iter().cloned().collect();
println!("从数组创建（自动去重）: {:?}", set4);
// 从向量创建
let vec = vec!["apple", "banana", "cherry", "apple"];
let set5: HashSet<&str> = vec.into_iter().collect();
println!("从向量创建: {:?}", set5);
// 手动构建
let mut colors = HashSet::new();
colors.insert("红色");
colors.insert("绿色");
colors.insert("蓝色");
println!("手动构建: {:?}", colors);
}
fn demonstrate_hashset_operations() {
println!("\nHashSet操作:");
let mut numbers = HashSet::new();
// 插入元素
println!("插入元素:");
println!("插入1: {}", numbers.insert(1)); // true，新元素
println!("插入2: {}", numbers.insert(2)); // true，新元素
println!("插入1: {}", numbers.insert(1)); // false，已存在
println!("当前集合: {:?}", numbers);
// 检查元素是否存在
println!("\n检查元素:");
println!("包含1: {}", numbers.contains(&1));
println!("包含3: {}", numbers.contains(&3));
// 移除元素
println!("\n移除元素:");
println!("移除1: {}", numbers.remove(&1)); // true，存在并移除
println!("移除3: {}", numbers.remove(&3)); // false，不存在
println!("移除后: {:?}", numbers);
// 添加更多元素
numbers.extend(vec![3, 4, 5, 6]);
println!("扩展后: {:?}", numbers);
// 获取集合大小
println!("\n集合信息:");
println!("大小: {}", numbers.len());
println!("是否为空: {}", numbers.is_empty());
// 保留满足条件的元素
numbers.retain(|&x| x % 2 == 0);
println!("保留偶数: {:?}", numbers);
// 清空集合
let mut temp = numbers.clone();
temp.clear();
println!("清空后: {:?}", temp);
println!("清空后是否为空: {}", temp.is_empty());
}
fn demonstrate_set_operations() {
println!("\n集合运算:");
let set_a: HashSet<i32> = [1, 2, 3, 4, 5].iter().cloned().collect();
let set_b: HashSet<i32> = [4, 5, 6, 7, 8].iter().cloned().collect();
let set_c: HashSet<i32> = [1, 2, 3].iter().cloned().collect();
println!("集合A: {:?}", set_a);
println!("集合B: {:?}", set_b);
println!("集合C: {:?}", set_c);
// 并集
let union: HashSet<i32> = set_a.union(&set_b).cloned().collect();
println!("\nA ∪ B (并集): {:?}", union);
// 交集
let intersection: HashSet<i32> = set_a.intersection(&set_b).cloned().collect();
println!("A ∩ B (交集): {:?}", intersection);
// 差集
let difference: HashSet<i32> = set_a.difference(&set_b).cloned().collect();
println!("A - B (差集): {:?}", difference);
// 对称差集
let symmetric_difference: HashSet<i32> = set_a.symmetric_difference(&set_b).cloned().collect();
println!("A △ B (对称差集): {:?}", symmetric_difference);
// 子集和超集检查
println!("\n集合关系:");
println!("C是A的子集: {}", set_c.is_subset(&set_a));
println!("A是C的超集: {}", set_a.is_superset(&set_c));
println!("A和B是否不相交: {}", set_a.is_disjoint(&set_b));
let set_d: HashSet<i32> = [10, 11, 12].iter().cloned().collect();
println!("A和D是否不相交: {}", set_a.is_disjoint(&set_d));
// 使用操作符进行集合运算
println!("\n使用操作符:");
let mut result = set_a.clone();
// 并集（修改原集合）
for item in &set_b {
result.insert(*item);
}
println!("A ∪ B (修改原集合): {:?}", result);
// 交集（修改原集合）
result.retain(|item| set_a.contains(item) && set_b.contains(item));
println!("(A ∪ B) ∩ (A ∩ B): {:?}", result);
}
fn demonstrate_hashset_iteration() {
println!("\nHashSet迭代:");
let fruits: HashSet<&str> = ["apple", "banana", "cherry", "date", "elderberry"]
.iter().cloned().collect();
// 基本迭代
println!("所有水果:");
for fruit in &fruits {
println!(" {}", fruit);
}
// 拥有所有权的迭代
let fruits_clone = fruits.clone();
println!("\n拥有所有权的迭代:");
for fruit in fruits_clone {
println!(" {}", fruit);
}
// 使用迭代器方法
let long_names: Vec<&str> = fruits
.iter()
.filter(|name| name.len() > 5)
.cloned()
.collect();
println!("\n长名称水果: {:?}", long_names);
let total_chars: usize = fruits.iter().map(|name| name.len()).sum();
println!("所有水果名称总字符数: {}", total_chars);
let has_apple = fruits.iter().any(|&fruit| fruit == "apple");
println!("是否包含apple: {}", has_apple);
let all_lowercase = fruits.iter().all(|name| name.chars().all(|c| c.is_lowercase()));
println!("是否都是小写: {}", all_lowercase);
// 查找特定元素
let found = fruits.iter().find(|&&name| name.starts_with('c'));
println!("第一个以c开头的水果: {:?}", found);
// 转换为向量并排序（HashSet本身是无序的）
let mut sorted_fruits: Vec<&str> = fruits.iter().cloned().collect();
sorted_fruits.sort();
println!("排序后的水果: {:?}", sorted_fruits);
}
rustc hashset_basics.rs && ./hashset_basics
10.4.2 HashSet实际应用
use std::collections::HashSet;
fn main() {
println!("🎯 HashSet实际应用");
println!("==================");
demonstrate_deduplication();
demonstrate_membership_testing();
demonstrate_data_analysis();
demonstrate_caching();
}
fn demonstrate_deduplication() {
println!("\n数据去重:");
// 去重数字列表
let numbers = vec![1, 2, 3, 2, 4, 3, 5, 1, 6, 4];
println!("原始数字: {:?}", numbers);
let unique_numbers: HashSet<i32> = numbers.into_iter().collect();
let mut sorted_unique: Vec<i32> = unique_numbers.into_iter().collect();
sorted_unique.sort();
println!("去重后: {:?}", sorted_unique);
// 去重字符串列表
let words = vec![
"apple", "banana", "apple", "cherry", "banana", "date", "apple"
];
println!("\n原始单词: {:?}", words);
let unique_words: HashSet<&str> = words.into_iter().collect();
println!("去重后: {:?}", unique_words);
// 去重自定义结构体
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Person {
name: String,
email: String,
}
let people = vec![
Person { name: "Alice".to_string(), email: "alice@example.com".to_string() },
Person { name: "Bob".to_string(), email: "bob@example.com".to_string() },
Person { name: "Alice".to_string(), email: "alice@example.com".to_string() }, // 重复
Person { name: "Charlie".to_string(), email: "charlie@example.com".to_string() },
Person { name: "Bob".to_string(), email: "bob@example.com".to_string() }, // 重复
];
println!("\n原始人员数量: {}", people.len());
let unique_people: HashSet<Person> = people.into_iter().collect();
println!("去重后人员数量: {}", unique_people.len());
for person in &unique_people {
println!(" {:?}", person);
}
}
fn demonstrate_membership_testing() {
println!("\n成员资格测试:");
// 权限检查系统
let admin_users: HashSet<&str> = ["alice", "bob", "admin"].iter().cloned().collect();
let regular_users: HashSet<&str> = ["charlie", "david", "eve"].iter().cloned().collect();
fn check_permission(user: &str, admins: &HashSet<&str>, regulars: &HashSet<&str>) {
if admins.contains(user) {
println!("{} 是管理员，拥有所有权限", user);
} else if regulars.contains(user) {
println!("{} 是普通用户，拥有基本权限", user);
} else {
println!("{} 不是系统用户，无权限", user);
}
}
let test_users = ["alice", "charlie", "frank", "admin"];
for user in &test_users {
check_permission(user, &admin_users, ®ular_users);
}
// 黑名单检查
let blacklist: HashSet<&str> = ["spam@example.com", "fake@test.com", "bad@domain.com"]
.iter().cloned().collect();
let emails = ["user@example.com", "spam@example.com", "valid@test.com", "bad@domain.com"];
println!("\n邮箱黑名单检查:");
for email in &emails {
if blacklist.contains(email) {
println!("{} 在黑名单中，拒绝", email);
} else {
println!("{} 不在黑名单中，允许", email);
}
}
// 标签系统
let post_tags: HashSet<&str> = ["rust", "programming", "tutorial", "beginner"]
.iter().cloned().collect();
let search_queries = [
vec!["rust", "tutorial"],
vec!["python", "programming"],
vec!["rust", "advanced"],
vec!["programming", "beginner"],
];
println!("\n标签匹配检查:");
for (i, query) in search_queries.iter().enumerate() {
let query_set: HashSet<&str> = query.iter().cloned().collect();
let matches = post_tags.intersection(&query_set).count();
let match_ratio = matches as f64 / query.len() as f64;
println!("查询{}: {:?}", i + 1, query);
println!(" 匹配标签数: {}/{}", matches, query.len());
println!(" 匹配率: {:.1}%", match_ratio * 100.0);
if match_ratio >= 0.5 {
println!(" 结果: 相关");
} else {
println!(" 结果: 不相关");
}
}
}
fn demonstrate_data_analysis() {
println!("\n数据分析:");
// 分析两个数据集的关系
let dataset_a: HashSet<i32> = (1..=100).filter(|x| x % 2 == 0).collect(); // 偶数
let dataset_b: HashSet<i32> = (1..=100).filter(|x| x % 3 == 0).collect(); // 3的倍数
let dataset_c: HashSet<i32> = (1..=100).filter(|x| x % 5 == 0).collect(); // 5的倍数
println!("数据集A (偶数): {} 个元素", dataset_a.len());
println!("数据集B (3的倍数): {} 个元素", dataset_b.len());
println!("数据集C (5的倍数): {} 个元素", dataset_c.len());
// 交集分析
let a_and_b: HashSet<i32> = dataset_a.intersection(&dataset_b).cloned().collect();
let a_and_c: HashSet<i32> = dataset_a.intersection(&dataset_c).cloned().collect();
let b_and_c: HashSet<i32> = dataset_b.intersection(&dataset_c).cloned().collect();
let all_three: HashSet<i32> = a_and_b.intersection(&dataset_c).cloned().collect();
println!("\n交集分析:");
println!("A ∩ B (偶数且是3的倍数): {} 个", a_and_b.len());
println!("A ∩ C (偶数且是5的倍数): {} 个", a_and_c.len());
println!("B ∩ C (3的倍数且是5的倍数): {} 个", b_and_c.len());
println!("A ∩ B ∩ C (偶数且是3和5的倍数): {} 个", all_three.len());
// 显示具体的交集元素
println!("\nA ∩ B ∩ C 的元素: {:?}", {
let mut sorted: Vec<i32> = all_three.into_iter().collect();
sorted.sort();
sorted
});
// 唯一性分析
let only_a: HashSet<i32> = dataset_a.difference(&dataset_b).cloned()
.collect::<HashSet<i32>>().difference(&dataset_c).cloned().collect();
let only_b: HashSet<i32> = dataset_b.difference(&dataset_a).cloned()
.collect::<HashSet<i32>>().difference(&dataset_c).cloned().collect();
let only_c: HashSet<i32> = dataset_c.difference(&dataset_a).cloned()
.collect::<HashSet<i32>>().difference(&dataset_b).cloned().collect();
println!("\n唯一性分析:");
println!("只在A中: {} 个", only_a.len());
println!("只在B中: {} 个", only_b.len());
println!("只在C中: {} 个", only_c.len());
// 覆盖率分析
let union_all: HashSet<i32> = dataset_a.union(&dataset_b)
.cloned().collect::<HashSet<i32>>()
.union(&dataset_c).cloned().collect();
println!("\n覆盖率分析:");
println!("总覆盖: {} 个数字 (1-100中的 {:.1}%)", union_all.len(), union_all.len() as f64);
}
fn demonstrate_caching() {
println!("\n缓存应用:");
// 简单的访问记录缓存
struct AccessTracker {
visited_pages: HashSet<String>,
unique_visitors: HashSet<String>,
}
impl AccessTracker {
fn new() -> Self {
AccessTracker {
visited_pages: HashSet::new(),
unique_visitors: HashSet::new(),
}
}
fn record_visit(&mut self, user_id: &str, page: &str) {
self.visited_pages.insert(page.to_string());
self.unique_visitors.insert(user_id.to_string());
println!("用户 {} 访问了页面 {}", user_id, page);
}
fn get_stats(&self) -> (usize, usize) {
(self.unique_visitors.len(), self.visited_pages.len())
}
fn has_visited_page(&self, page: &str) -> bool {
self.visited_pages.contains(page)
}
fn is_returning_visitor(&self, user_id: &str) -> bool {
self.unique_visitors.contains(user_id)
}
}
let mut tracker = AccessTracker::new();
// 模拟访问记录
let visits = [
("user1", "/home"),
("user2", "/about"),
("user1", "/products"), // 回访用户
("user3", "/home"), // 重复页面
("user2", "/contact"), // 回访用户
("user4", "/home"), // 新用户，重复页面
];
for (user, page) in &visits {
let is_returning = tracker.is_returning_visitor(user);
let page_visited_before = tracker.has_visited_page(page);
tracker.record_visit(user, page);
println!(" 回访用户: {}, 页面已访问过: {}", is_returning, page_visited_before);
}
let (unique_users, unique_pages) = tracker.get_stats();
println!("\n统计结果:");
println!("独立访客: {}", unique_users);
println!("访问页面: {}", unique_pages);
// 计算缓存
struct ComputationCache {
computed_values: HashSet<i32>,
results: std::collections::HashMap<i32, i32>,
}
impl ComputationCache {
fn new() -> Self {
ComputationCache {
computed_values: HashSet::new(),
results: std::collections::HashMap::new(),
}
}
fn expensive_computation(&mut self, input: i32) -> i32 {
if self.computed_values.contains(&input) {
println!("缓存命中: {}", input);
*self.results.get(&input).unwrap()
} else {
println!("计算中: {}", input);
// 模拟昂贵的计算
let result = input * input + input * 2 + 1;
self.computed_values.insert(input);
self.results.insert(input, result);
result
}
}
fn cache_size(&self) -> usize {
self.computed_values.len()
}
}
println!("\n计算缓存演示:");
let mut cache = ComputationCache::new();
let inputs = [5, 3, 8, 5, 3, 10, 8, 5]; // 包含重复值
for input in &inputs {
let result = cache.expensive_computation(*input);
println!(" f({}) = {}", input, result);
}
println!("\n缓存大小: {}", cache.cache_size());
}
rustc hashset_applications.rs && ./hashset_applications
10.5 其他集合类型
Rust标准库还提供了其他有用的集合类型，每种都有其特定的用途和性能特点。
10.5.1 VecDeque（双端队列）
use std::collections::VecDeque;
fn main() {
println!("🔄 VecDeque双端队列");
println!("==================");
demonstrate_vecdeque_basics();
demonstrate_queue_operations();
demonstrate_performance_comparison();
}
fn demonstrate_vecdeque_basics() {
println!("\nVecDeque基础操作:");
// 创建VecDeque
let mut deque = VecDeque::new();
println!("空双端队列: {:?}", deque);
// 从向量创建
let mut deque2 = VecDeque::from(vec![1, 2, 3, 4, 5]);
println!("从向量创建: {:?}", deque2);
// 前端操作
deque.push_front(1);
deque.push_front(2);
deque.push_front(3);
println!("前端添加后: {:?}", deque);
// 后端操作
deque.push_back(4);
deque.push_back(5);
deque.push_back(6);
println!("后端添加后: {:?}", deque);
// 前端移除
if let Some(front) = deque.pop_front() {
println!("前端移除: {}", front);
}
println!("前端移除后: {:?}", deque);
// 后端移除
if let Some(back) = deque.pop_back() {
println!("后端移除: {}", back);
}
println!("后端移除后: {:?}", deque);
// 访问元素
if let Some(front) = deque.front() {
println!("前端元素: {}", front);
}
if let Some(back) = deque.back() {
println!("后端元素: {}", back);
}
// 索引访问
if let Some(element) = deque.get(1) {
println!("索引1的元素: {}", element);
}
// 长度和容量
println!("长度: {}", deque.len());
println!("是否为空: {}", deque.is_empty());
// 插入和移除
deque.insert(2, 100);
println!("在索引2插入100: {:?}", deque);
if let Some(removed) = deque.remove(2) {
println!("移除索引2的元素: {}", removed);
}
println!("移除后: {:?}", deque);
}
fn demonstrate_queue_operations() {
println!("\n队列操作演示:");
// FIFO队列（先进先出）
println!("FIFO队列:");
let mut fifo_queue = VecDeque::new();
// 入队
for i in 1..=5 {
fifo_queue.push_back(i);
println!("入队: {}, 队列: {:?}", i, fifo_queue);
}
// 出队
while let Some(item) = fifo_queue.pop_front() {
println!("出队: {}, 剩余: {:?}", item, fifo_queue);
}
// LIFO栈（后进先出）
println!("\nLIFO栈:");
let mut lifo_stack = VecDeque::new();
// 入栈
for i in 1..=5 {
lifo_stack.push_back(i);
println!("入栈: {}, 栈: {:?}", i, lifo_stack);
}
// 出栈
while let Some(item) = lifo_stack.pop_back() {
println!("出栈: {}, 剩余: {:?}", item, lifo_stack);
}
// 双端操作
println!("\n双端操作:");
let mut deque = VecDeque::new();
// 交替从两端添加
for i in 1..=10 {
if i % 2 == 0 {
deque.push_front(i);
println!("前端添加{}: {:?}", i, deque);
} else {
deque.push_back(i);
println!("后端添加{}: {:?}", i, deque);
}
}
// 交替从两端移除
let mut count = 0;
while !deque.is_empty() {
count += 1;
if count % 2 == 0 {
if let Some(item) = deque.pop_front() {
println!("前端移除{}: {:?}", item, deque);
}
} else {
if let Some(item) = deque.pop_back() {
println!("后端移除{}: {:?}", item, deque);
}
}
}
}
fn demonstrate_performance_comparison() {
println!("\n性能比较:");
let size = 100000;
// VecDeque前端插入性能
let start = std::time::Instant::now();
let mut deque = VecDeque::new();
for i in 0..size {
deque.push_front(i);
}
let deque_front_duration = start.elapsed();
println!("VecDeque前端插入{}个元素耗时: {:?}", size, deque_front_duration);
// Vec前端插入性能（使用insert(0, item)）
let start = std::time::Instant::now();
let mut vec = Vec::new();
for i in 0..1000 { // 减少数量，因为Vec前端插入很慢
vec.insert(0, i);
}
let vec_front_duration = start.elapsed();
println!("Vec前端插入1000个元素耗时: {:?}", vec_front_duration);
// VecDeque后端插入性能
let start = std::time::Instant::now();
let mut deque2 = VecDeque::new();
for i in 0..size {
deque2.push_back(i);
}
let deque_back_duration = start.elapsed();
println!("VecDeque后端插入{}个元素耗时: {:?}", size, deque_back_duration);
// Vec后端插入性能
let start = std::time::Instant::now();
let mut vec2 = Vec::new();
for i in 0..size {
vec2.push(i);
}
let vec_back_duration = start.elapsed();
println!("Vec后端插入{}个元素耗时: {:?}", size, vec_back_duration);
// 随机访问性能比较
let start = std::time::Instant::now();
let mut sum1 = 0;
for i in 0..deque.len() {
sum1 += deque[i];
}
let deque_access_duration = start.elapsed();
println!("VecDeque随机访问耗时: {:?}, 和: {}", deque_access_duration, sum1);
let start = std::time::Instant::now();
let mut sum2 = 0;
for i in 0..vec2.len() {
sum2 += vec2[i];
}
let vec_access_duration = start.elapsed();
println!("Vec随机访问耗时: {:?}, 和: {}", vec_access_duration, sum2);
println!("\n总结:");
println!("- VecDeque在前端操作上比Vec快得多");
println!("- VecDeque和Vec在后端操作上性能相近");
println!("- Vec在随机访问上可能略快于VecDeque");
println!("- VecDeque适合需要双端操作的场景");
}
rustc vecdeque_demo.rs && ./vecdeque_demo
10.5.2 BTreeMap和BTreeSet（有序集合）
use std::collections::{BTreeMap, BTreeSet};
fn main() {
println!("🌳 BTree集合类型");
println!("================");
demonstrate_btreemap();
demonstrate_btreeset();
demonstrate_ordering_benefits();
demonstrate_range_operations();
}
fn demonstrate_btreemap() {
println!("\nBTreeMap演示:");
// 创建BTreeMap
let mut scores = BTreeMap::new();
// 插入数据（注意插入顺序）
scores.insert("Charlie", 92);
scores.insert("Alice", 95);
scores.insert("Bob", 87);
scores.insert("David", 88);
scores.insert("Eve", 91);
println!("BTreeMap（自动按键排序）: {:?}", scores);
// 基本操作
println!("\n基本操作:");
if let Some(score) = scores.get("Alice") {
println!("Alice的分数: {}", score);
}
scores.insert("Frank", 89);
println!("添加Frank后: {:?}", scores);
if let Some(removed) = scores.remove("Bob") {
println!("移除Bob，分数: {}", removed);
}
println!("移除Bob后: {:?}", scores);
// 有序迭代
println!("\n有序迭代:");
for (name, score) in &scores {
println!("{}: {}", name, score);
}
// 第一个和最后一个元素
if let Some((first_name, first_score)) = scores.first_key_value() {
println!("\n第一个元素: {} - {}", first_name, first_score);
}
if let Some((last_name, last_score)) = scores.last_key_value() {
println!("最后一个元素: {} - {}", last_name, last_score);
}
// entry API
scores.entry("Grace").or_insert(93);
scores.entry("Alice").and_modify(|score| *score += 2).or_insert(0);
println!("\n使用entry API后: {:?}", scores);
}
fn demonstrate_btreeset() {
println!("\nBTreeSet演示:");
// 创建BTreeSet
let mut numbers = BTreeSet::new();
// 插入数据（注意插入顺序）
let insert_order = [5, 2, 8, 1, 9, 3, 7, 4, 6];
for num in &insert_order {
numbers.insert(*num);
}
println!("插入顺序: {:?}", insert_order);
println!("BTreeSet（自动排序）: {:?}", numbers);
// 集合操作
let set_a: BTreeSet<i32> = [1, 2, 3, 4, 5].iter().cloned().collect();
let set_b: BTreeSet<i32> = [4, 5, 6, 7, 8].iter().cloned().collect();
println!("\n集合运算:");
println!("集合A: {:?}", set_a);
println!("集合B: {:?}", set_b);
// 并集（结果也是有序的）
let union: BTreeSet<i32> = set_a.union(&set_b).cloned().collect();
println!("A ∪ B: {:?}", union);
// 交集
let intersection: BTreeSet<i32> = set_a.intersection(&set_b).cloned().collect();
println!("A ∩ B: {:?}", intersection);
// 差集
let difference: BTreeSet<i32> = set_a.difference(&set_b).cloned().collect();
println!("A - B: {:?}", difference);
// 对称差集
let symmetric_diff: BTreeSet<i32> = set_a.symmetric_difference(&set_b).cloned().collect();
println!("A △ B: {:?}", symmetric_diff);
// 子集检查
let subset: BTreeSet<i32> = [2, 3, 4].iter().cloned().collect();
println!("\n{:?} 是 {:?} 的子集: {}", subset, set_a, subset.is_subset(&set_a));
// 有序迭代
println!("\n有序迭代:");
for num in &numbers {
print!("{} ", num);
}
println!();
// 反向迭代
println!("反向迭代:");
for num in numbers.iter().rev() {
print!("{} ", num);
}
println!();
}
fn demonstrate_ordering_benefits() {
println!("\n有序性的好处:");
// 时间序列数据
let mut time_series = BTreeMap::new();
// 模拟时间戳和值（插入顺序是乱的）
let data = [
(1640995200, 100), // 2022-01-01 00:00:00
(1640995800, 105), // 2022-01-01 00:10:00
(1640995500, 102), // 2022-01-01 00:05:00
(1640996100, 108), // 2022-01-01 00:15:00
(1640995300, 101), // 2022-01-01 00:02:30
];
for (timestamp, value) in &data {
time_series.insert(*timestamp, *value);
}
println!("时间序列数据（自动按时间排序）:");
for (timestamp, value) in &time_series {
println!("时间戳 {}: 值 {}", timestamp, value);
}
// 排行榜系统
let mut leaderboard = BTreeMap::new();
// 使用负分数作为键来实现降序排列
let players = [
("Alice", 1500),
("Bob", 1200),
("Charlie", 1800),
("David", 1350),
("Eve", 1650),
];
for (name, score) in &players {
leaderboard.insert(-score, name); // 负分数实现降序
}
println!("\n排行榜（按分数降序）:");
for (rank, (neg_score, name)) in leaderboard.iter().enumerate() {
println!("第{}名: {} - {} 分", rank + 1, name, -neg_score);
}
// 字典序排序
let mut dictionary = BTreeSet::new();
let words = ["zebra", "apple", "banana", "cherry", "date", "elderberry"];
for word in &words {
dictionary.insert(*word);
}
println!("\n字典（按字母顺序）:");
for (i, word) in dictionary.iter().enumerate() {
println!("{}: {}", i + 1, word);
}
}
fn demonstrate_range_operations() {
println!("\n范围操作:");
// 创建一个包含1-20的BTreeSet
let numbers: BTreeSet<i32> = (1..=20).collect();
println!("完整集合: {:?}", numbers);
// 范围查询
println!("\n范围查询:");
// 大于等于10的元素
let ge_10: Vec<&i32> = numbers.range(10..).collect();
println!(">= 10: {:?}", ge_10);
// 小于15的元素
let lt_15: Vec<&i32> = numbers.range(..15).collect();
println!("< 15: {:?}", lt_15);
// 5到15之间的元素（包含5，不包含15）
let range_5_15: Vec<&i32> = numbers.range(5..15).collect();
println!("[5, 15): {:?}", range_5_15);
// 5到15之间的元素（都包含）
let range_5_15_inclusive: Vec<&i32> = numbers.range(5..=15).collect();
println!("[5, 15]: {:?}", range_5_15_inclusive);
// BTreeMap的范围操作
let mut scores = BTreeMap::new();
for i in 1..=10 {
scores.insert(i, i * 10);
}
println!("\nBTreeMap范围操作:");
println!("完整映射: {:?}", scores);
// 键在3到7之间的元素
let range_3_7: Vec<(&i32, &i32)> = scores.range(3..=7).collect();
println!("键在[3, 7]: {:?}", range_3_7);
// 分割操作
let mut split_set = BTreeSet::from([1, 3, 5, 7, 9, 11, 13, 15]);
println!("\n分割操作:");
println!("原集合: {:?}", split_set);
// 分割出大于等于8的元素
let split_off = split_set.split_off(&8);
println!("分割后原集合: {:?}", split_set);
println!("分割出的集合: {:?}", split_off);
// 查找操作
let test_set: BTreeSet<i32> = (1..=20).filter(|x| x % 2 == 0).collect();
println!("\n查找操作（偶数集合）: {:?}", test_set);
// 查找第一个大于等于7的元素
if let Some(found) = test_set.range(7..).next() {
println!("第一个 >= 7 的元素: {}", found);
}
// 查找最后一个小于15的元素
if let Some(found) = test_set.range(..15).next_back() {
println!("最后一个 < 15 的元素: {}", found);
}
// 二分查找的优势
println!("\n二分查找性能演示:");
let large_set: BTreeSet<i32> = (0..100000).collect();
let start = std::time::Instant::now();
let contains_50000 = large_set.contains(&50000);
let btree_duration = start.elapsed();
println!("BTreeSet查找50000: {} (耗时: {:?})", contains_50000, btree_duration);
// 与Vec的线性查找比较
let large_vec: Vec<i32> = (0..100000).collect();
let start = std::time::Instant::now();
let contains_50000_vec = large_vec.contains(&50000);
let vec_duration = start.elapsed();
println!("Vec查找50000: {} (耗时: {:?})", contains_50000_vec, vec_duration);
println!("BTreeSet查找比Vec快约 {:.1} 倍",
vec_duration.as_nanos() as f64 / btree_duration.as_nanos() as f64);
}
rustc btree_collections.rs && ./btree_collections
