跳到主要内容

集合类型

Rust 标准库提供了多种集合类型，用于存储多个值。与内置的数组和元组不同，集合类型的数据存储在堆上，可以在运行时动态增长或缩小。本章将介绍三种最常用的集合类型：Vector、String 和 HashMap。

集合概述​

集合类型是 Rust 标准库中非常重要的数据结构。与数组不同，集合的大小不需要在编译时确定，可以根据需要动态调整。

常用集合类型对比​

集合类型特点用途
Vec<T>动态数组，存储相同类型元素有序列表，索引访问
StringUTF-8 编码的可变字符串文本处理
HashMap<K, V>键值对映射快速查找，缓存
HashSet<T>无重复元素集合去重，集合运算
BTreeMap<K, V>有序键值对映射需要按键排序
VecDeque<T>双端队列高效的头尾操作

Vector 动态数组​

Vector（Vec<T>）是一种动态数组，可以存储多个相同类型的值，且大小可以动态变化。Vector 将数据存储在堆上，因此可以在运行时增长或缩小。

创建 Vector​

fn main() {
    // 创建空的 Vector（需要类型注解）
    let v: Vec<i32> = Vec::new();
    
    // 使用 vec! 宏创建带初始值的 Vector
    let v = vec![1, 2, 3, 4, 5];
    
    // 使用 with_capacity 预分配容量（提高性能）
    let v: Vec<i32> = Vec::with_capacity(100);
    
    println!("Vector: {:?}", v);
}

解释：

  • Vec::new() 创建空的 Vector，需要显式指定类型
  • vec! 宏可以方便地创建带初始值的 Vector，类型会自动推断
  • with_capacity 可以预分配内存，避免频繁重新分配。当你知道大概需要存储多少元素时，使用这个方法可以显著提升性能

更新 Vector​

fn main() {
    let mut v = Vec::new();
    
    // 使用 push 添加元素
    v.push(1);
    v.push(2);
    v.push(3);
    
    println!("Vector: {:?}", v);
    
    // 在指定位置插入
    v.insert(1, 10);  // 在索引 1 处插入 10
    println!("插入后: {:?}", v);
    
    // 删除最后一个元素
    let last = v.pop();
    println!("弹出: {:?}, 剩余: {:?}", last, v);
    
    // 删除指定位置的元素
    let removed = v.remove(0);
    println!("删除: {}, 剩余: {:?}", removed, v);
}

关键点：push 和 pop 操作的时间复杂度通常是 O(1)O(1)（摊销），而 insert 和 remove 的时间复杂度是 O(n)O(n)，因为需要移动元素。

读取元素​

Vector 提供两种方式读取元素：索引访问和 get 方法。

fn main() {
    let v = vec![1, 2, 3, 4, 5];
    
    // 方式一：索引访问（越界会 panic）
    let third = &v[2];
    println!("第三个元素: {}", third);
    
    // 方式二：get 方法（返回 Option）
    match v.get(2) {
        Some(value) => println!("第三个元素: {}", value),
        None => println!("没有第三个元素"),
    }
    
    // 越界访问对比
    // let does_not_exist = &v[100];  // panic!
    let does_not_exist = v.get(100);  // 返回 None
    println!("越界访问: {:?}", does_not_exist);
}

两种方式的区别：

方式越界行为返回类型适用场景
&v[i]panic&T确信索引有效时
v.get(i)返回 NoneOption<&T>索引可能无效时

所有权和借用规则​

Vector 遵循 Rust 的所有权和借用规则。

fn main() {
    let mut v = vec![1, 2, 3, 4, 5];
    
    // 获取第一个元素的引用
    let first = &v[0];
    
    // 错误！不能同时存在可变和不可变引用
    // v.push(6);  // 编译错误
    // println!("第一个元素: {}", first);
    
    // 正确做法：先使用引用，再修改
    println!("第一个元素: {}", first);
    v.push(6);
    println!("添加后: {:?}", v);
}

为什么这个规则很重要？

Vector 在内存中连续存储元素。当添加新元素时，如果当前空间不足，Vector 会重新分配更大的内存空间并移动所有元素。此时，旧的引用将指向已释放的内存，导致悬垂引用。Rust 的借用规则在编译时防止了这种问题。

遍历 Vector​

fn main() {
    let v = vec![100, 32, 57];
    
    // 不可变遍历
    println!("遍历元素:");
    for i in &v {
        println!("{}", i);
    }
    
    // 可变遍历
    let mut v2 = vec![100, 32, 57];
    for i in &mut v2 {
        *i += 50;  // 使用解引用修改值
    }
    println!("修改后: {:?}", v2);
    
    // 消费遍历（获取所有权）
    let v3 = vec![1, 2, 3];
    for i in v3 {
        println!("消费: {}", i);
    }
    // v3 不再可用
}

使用枚举存储多种类型​

Vector 只能存储相同类型的元素，但可以通过枚举来存储不同类型：

#[derive(Debug)]
enum SpreadsheetCell {
    Int(i32),
    Float(f64),
    Text(String),
}

fn main() {
    let row = vec![
        SpreadsheetCell::Int(3),
        SpreadsheetCell::Text(String::from("蓝色")),
        SpreadsheetCell::Float(10.12),
    ];
    
    for cell in &row {
        match cell {
            SpreadsheetCell::Int(i) => println!("整数: {}", i),
            SpreadsheetCell::Float(f) => println!("浮点数: {}", f),
            SpreadsheetCell::Text(s) => println!("文本: {}", s),
        }
    }
}

这种模式让你可以在需要存储不同类型的场景下，依然保持类型安全。

常用方法​

fn main() {
    let mut v = vec![1, 2, 3, 4, 5];
    
    // 长度和容量
    println!("长度: {}, 容量: {}", v.len(), v.capacity());
    
    // 判断是否为空
    println!("是否为空: {}", v.is_empty());
    
    // 是否包含某个元素
    println!("包含 3: {}", v.contains(&3));
    
    // 清空
    v.clear();
    println!("清空后: {:?}", v);
    
    // 扩展
    v.extend([1, 2, 3]);
    println!("扩展后: {:?}", v);
    
    // 追加另一个 Vector
    let mut v2 = vec![4, 5, 6];
    v.append(&mut v2);
    println!("追加后: v: {:?}, v2: {:?}", v, v2);
    
    // 截断
    v.truncate(3);
    println!("截断后: {:?}", v);
    
    // 排序
    let mut nums = vec![3, 1, 4, 1, 5, 9];
    nums.sort();
    println!("排序后: {:?}", nums);
    
    // 反转
    nums.reverse();
    println!("反转后: {:?}", nums);
}

String 字符串​

String 是一种 UTF-8 编码的可增长字符串类型。Rust 中的字符串比其他语言更复杂，但这也带来了更好的安全性和国际化支持。

String 与 &str 的区别​

fn main() {
    // &str：字符串切片（不可变，通常是借用）
    let s1: &str = "hello";  // 字符串字面量
    
    // String：堆分配的可增长字符串
    let s2: String = String::from("hello");
    
    println!("&str: {}", s1);
    println!("String: {}", s2);
}

对比：

特性&strString
内存位置栈或二进制文件堆
可变性不可变可变
大小固定可增长
所有权借用拥有

&str 是对一段 UTF-8 数据的引用，而 String 是拥有堆上数据所有权的类型。在函数参数中，推荐使用 &str，因为它可以同时接受 &String 和字符串字面量。

创建 String​

fn main() {
    // 从字面量创建
    let s1 = String::from("hello");
    
    // 使用 to_string 方法
    let s2 = "world".to_string();
    
    // 创建空字符串
    let s3 = String::new();
    
    // 从字符创建
    let s4: String = ['h', 'e', 'l', 'l', 'o'].iter().collect();
    
    // 使用 with_capacity 预分配
    let s5 = String::with_capacity(100);
    
    println!("s1: {}, s2: {}, s3: '{}', s4: {}", s1, s2, s3, s4);
}

更新 String​

fn main() {
    let mut s = String::from("hello");
    
    // 追加字符串
    s.push_str(" world");
    println!("追加后: {}", s);
    
    // 追加单个字符
    s.push('!');
    println!("添加字符后: {}", s);
    
    // 使用 + 运算符拼接（会转移所有权）
    let s1 = String::from("Hello, ");
    let s2 = String::from("world!");
    let s3 = s1 + &s2;  // s1 被移动，s2 被借用
    println!("拼接结果: {}", s3);
    // println!("{}", s1);  // 错误！s1 已被移动
    println!("s2 仍可用: {}", s2);
    
    // 使用 format! 宏拼接（不会转移所有权）
    let s1 = String::from("tic");
    let s2 = String::from("tac");
    let s3 = String::from("toe");
    let s = format!("{}-{}-{}", s1, s2, s3);
    println!("format 结果: {}", s);
    println!("s1, s2, s3 仍可用: {}, {}, {}", s1, s2, s3);
}

+ 运算符的内部实现：

当你执行 s1 + &s2 时，Rust 实际上调用的是 add 方法，它的签名大致是 fn add(self, s: &str) -> String。因为 s2 的类型是 &String，Rust 会自动进行解引用强制转换（deref coercion），将其转换为 &str。这个过程会获取 s1 的所有权，所以 s1 之后不能再使用。

索引字符串​

Rust 不支持直接使用索引访问字符串，因为 UTF-8 编码的字符可能占用多个字节。

fn main() {
    let s = String::from("hello");
    
    // 错误！Rust 不支持字符串索引
    // let h = s[0];  // 编译错误
    
    // 正确方式：使用切片
    let hello = &s[0..5];  // 获取字节范围
    println!("切片: {}", hello);
    
    // 注意：切片是按字节而非字符
    let chinese = String::from("你好");
    // let slice = &chinese[0..1];  // 危险！可能破坏 UTF-8 字符
    let slice = &chinese[0..3];  // "你"占 3 个字节
    println!("中文切片: {}", slice);
}

为什么不支持索引：

Rust 字符串是 UTF-8 编码的。对于英文字符，每个字符占用 1 个字节；对于中文字符，每个字符通常占用 3 个字节。如果允许通过索引访问，可能会得到一个不完整的字符，这是不安全的。

遍历字符串​

fn main() {
    let s = String::from("你好世界");
    
    // 遍历字符
    println!("遍历字符:");
    for c in s.chars() {
        println!("{}", c);
    }
    
    // 遍历字节
    println!("\n遍历字节:");
    for b in s.bytes() {
        println!("{}", b);
    }
    
    // 遍历字符及其索引
    println!("\n遍历字符和索引:");
    for (i, c) in s.char_indices() {
        println!("索引 {}: 字符 {}", i, c);
    }
}

常用方法​

fn main() {
    let mut s = String::from("Hello, World!");
    
    // 长度（字节数）
    println!("字节长度: {}", s.len());
    
    // 字符数
    println!("字符数: {}", s.chars().count());
    
    // 判断是否为空
    println!("是否为空: {}", s.is_empty());
    
    // 分割
    let parts: Vec<&str> = s.split(", ").collect();
    println!("分割: {:?}", parts);
    
    // 替换
    let replaced = s.replace("World", "Rust");
    println!("替换后: {}", replaced);
    
    // 大小写转换
    println!("小写: {}", s.to_lowercase());
    println!("大写: {}", s.to_uppercase());
    
    // 去除空白
    let s2 = "  hello  ";
    println!("去除两端空白: '{}'", s2.trim());
    
    // 判断开头和结尾
    println!("以 Hello 开头: {}", s.starts_with("Hello"));
    println!("以 ! 结尾: {}", s.ends_with("!"));
    
    // 包含
    println!("包含 World: {}", s.contains("World"));
}

字符串和所有权​

fn main() {
    let s1 = String::from("hello");
    
    // 函数参数：建议使用 &str
    fn print_str(s: &str) {
        println!("{}", s);
    }
    
    // 可以接受 &String（自动解引用为 &str）
    print_str(&s1);
    
    // 也可以接受 &str
    print_str("world");
    
    // 函数返回 String
    fn create_string() -> String {
        String::from("new string")
    }
    
    let s2 = create_string();
    println!("返回的字符串: {}", s2);
}

最佳实践：函数参数使用 &str 而不是 &String，这样函数可以同时接受 String 的引用和字符串字面量。

HashMap 哈希映射​

HashMap 存储键值对，通过键快速查找对应的值。它使用哈希函数来决定如何在内存中存储这些键值对。

创建 HashMap​

use std::collections::HashMap;

fn main() {
    // 创建空的 HashMap
    let mut scores: HashMap<String, i32> = HashMap::new();
    
    // 插入键值对
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
    
    println!("分数: {:?}", scores);
    
    // 从两个 Vector 创建
    let teams = vec![String::from("Blue"), String::from("Yellow")];
    let initial_scores = vec![10, 50];
    let scores: HashMap<_, _> = teams.into_iter().zip(initial_scores.into_iter()).collect();
    println!("从 Vector 创建: {:?}", scores);
}

访问值​

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
    
    // 使用 get 方法（返回 Option）
    let team_name = String::from("Blue");
    match scores.get(&team_name) {
        Some(score) => println!("Blue 队分数: {}", score),
        None => println!("队伍不存在"),
    }
    
    // 使用 unwrap_or 提供默认值
    let score = scores.get(&String::from("Red")).unwrap_or(&0);
    println!("Red 队分数: {}", score);
    
    // 遍历
    for (key, value) in &scores {
        println!("{}: {}", key, value);
    }
}

更新 HashMap​

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    
    // 覆盖旧值
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25);  // 覆盖
    println!("覆盖后: {:?}", scores);
    
    // 只在键不存在时插入
    scores.entry(String::from("Yellow")).or_insert(50);
    scores.entry(String::from("Blue")).or_insert(100);  // 不会插入
    println!("entry 后: {:?}", scores);
    
    // 基于旧值更新
    let text = "hello world wonderful world";
    let mut map = HashMap::new();
    
    for word in text.split_whitespace() {
        let count = map.entry(word).or_insert(0);
        *count += 1;
    }
    
    println!("词频统计: {:?}", map);
}

entry API 的优势：entry 方法返回一个 Entry 枚举，表示键可能存在也可能不存在。or_insert 方法在键不存在时插入默认值，并返回一个可变引用。这种模式避免了先检查再插入的两步操作。

删除元素​

use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
    
    // 删除键值对
    scores.remove(&String::from("Blue"));
    println!("删除后: {:?}", scores);
    
    // 清空
    scores.clear();
    println!("清空后: {:?}", scores);
}

所有权​

HashMap 对于实现了 Copy trait 的类型会复制值，对于拥有所有权的类型（如 String）会移动所有权。

use std::collections::HashMap;

fn main() {
    let field_name = String::from("Favorite color");
    let field_value = String::from("Blue");
    
    let mut map = HashMap::new();
    map.insert(field_name, field_value);
    
    // field_name 和 field_value 已被移动
    // println!("{}", field_name);  // 错误！
    
    // 使用引用（需要确保引用有效）
    let name = String::from("Alice");
    let age = 30;
    
    let mut map2 = HashMap::new();
    map2.insert(&name, age);  // name 被借用，age 被复制
    
    println!("name 仍可用: {}", name);
    println!("map2: {:?}", map2);
}

常用方法​

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // 长度
    println!("长度: {}", map.len());
    
    // 判断是否为空
    println!("是否为空: {}", map.is_empty());
    
    // 判断是否包含某个键
    println!("包含 a: {}", map.contains_key("a"));
    
    // 获取键和值的集合
    println!("所有键: {:?}", map.keys().collect::<Vec<_>>());
    println!("所有值: {:?}", map.values().collect::<Vec<_>>());
    
    // 遍历
    for (k, v) in &map {
        println!("{}: {}", k, v);
    }
    
    // 保留满足条件的元素
    map.retain(|&k, &mut _v| k != "b");
    println!("retain 后: {:?}", map);
}

HashSet 哈希集合​

HashSet 是存储唯一值的集合，基于哈希表实现，提供 O(1)O(1) 平均时间复杂度的插入、删除和查找操作。

创建 HashSet​

use std::collections::HashSet;

fn main() {
    // 创建空的 HashSet（需要类型注解）
    let set: HashSet<i32> = HashSet::new();
    
    // 从数组创建
    let set: HashSet<i32> = [1, 2, 3, 4, 5].into_iter().collect();
    
    // 从 Vec 创建
    let vec = vec![1, 2, 3, 4, 5];
    let set: HashSet<i32> = vec.into_iter().collect();
    
    println!("集合: {:?}", set);
}

基本操作​

use std::collections::HashSet;

fn main() {
    let mut set = HashSet::new();
    
    // 插入元素（返回是否成功插入）
    set.insert(1);
    set.insert(2);
    set.insert(3);
    let inserted = set.insert(2);  // false，已存在
    println!("插入 2: {}", inserted);
    
    // 检查是否存在
    println!("包含 2: {}", set.contains(&2));
    
    // 删除元素
    set.remove(&2);
    println!("删除后: {:?}", set);
    
    // 长度
    println!("长度: {}", set.len());
    
    // 判断是否为空
    println!("是否为空: {}", set.is_empty());
    
    // 清空
    set.clear();
}

集合运算​

HashSet 最强大的特性是支持集合运算：

use std::collections::HashSet;

fn main() {
    let a: HashSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let b: HashSet<i32> = [3, 4, 5, 6].into_iter().collect();
    
    // 并集：两个集合的所有元素
    let union: HashSet<i32> = a.union(&b).cloned().collect();
    println!("并集: {:?}", union);  // {1, 2, 3, 4, 5, 6}
    
    // 交集：两个集合共有的元素
    let intersection: HashSet<i32> = a.intersection(&b).cloned().collect();
    println!("交集: {:?}", intersection);  // {3, 4}
    
    // 差集：a 中有但 b 中没有的元素
    let difference: HashSet<i32> = a.difference(&b).cloned().collect();
    println!("差集 (a - b): {:?}", difference);  // {1, 2}
    
    // 对称差集：只在一个集合中的元素
    let symmetric_difference: HashSet<i32> = a.symmetric_difference(&b).cloned().collect();
    println!("对称差集: {:?}", symmetric_difference);  // {1, 2, 5, 6}
    
    // 子集判断
    let c: HashSet<i32> = [1, 2].into_iter().collect();
    println!("c 是 a 的子集: {}", c.is_subset(&a));  // true
    
    // 超集判断
    println!("a 是 c 的超集: {}", a.is_superset(&c));  // true
    
    // 不相交判断（没有共同元素）
    let d: HashSet<i32> = [7, 8].into_iter().collect();
    println!("a 和 d 不相交: {}", a.is_disjoint(&d));  // true
}

实际应用示例​

去重：

use std::collections::HashSet;

fn main() {
    let numbers = vec![1, 2, 2, 3, 3, 3, 4, 5];
    
    // 方法一：转换为 HashSet 再转回 Vec
    let unique: HashSet<i32> = numbers.into_iter().collect();
    let unique_vec: Vec<i32> = unique.into_iter().collect();
    println!("去重后: {:?}", unique_vec);
    
    // 方法二：保持顺序的去重
    let numbers = vec![1, 2, 2, 3, 3, 3, 4, 5];
    let mut seen = HashSet::new();
    let unique_ordered: Vec<i32> = numbers
        .into_iter()
        .filter(|x| seen.insert(*x))  // insert 返回 true 表示是新元素
        .collect();
    println!("保持顺序去重: {:?}", unique_ordered);
}

查找重复元素：

use std::collections::HashSet;

fn find_duplicates(items: &[i32]) -> Vec<i32> {
    let mut seen = HashSet::new();
    let mut duplicates = HashSet::new();
    
    for &item in items {
        if !seen.insert(item) {
            duplicates.insert(item);
        }
    }
    
    duplicates.into_iter().collect()
}

fn main() {
    let numbers = vec![1, 2, 3, 2, 4, 5, 3, 6, 3];
    let dups = find_duplicates(&numbers);
    println!("重复元素: {:?}", dups);
}

VecDeque 双端队列​

VecDeque 是双端队列，支持在两端高效地添加和删除元素。与 Vec 相比，VecDeque 在头部操作的时间复杂度是 O(1)O(1)，而 Vec 是 O(n)O(n)。

创建 VecDeque​

use std::collections::VecDeque;

fn main() {
    // 创建空的 VecDeque
    let mut deque: VecDeque<i32> = VecDeque::new();
    
    // 指定初始容量
    let deque: VecDeque<i32> = VecDeque::with_capacity(10);
    
    // 从迭代器创建
    let deque: VecDeque<i32> = (1..=5).collect();
    
    println!("双端队列: {:?}", deque);
}

基本操作​

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    
    // 尾部添加
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
    println!("push_back 后: {:?}", deque);  // [1, 2, 3]
    
    // 头部添加
    deque.push_front(0);
    println!("push_front 后: {:?}", deque);  // [0, 1, 2, 3]
    
    // 尾部删除
    let back = deque.pop_back();
    println!("pop_back: {:?}, 剩余: {:?}", back, deque);  // Some(3), [0, 1, 2]
    
    // 头部删除
    let front = deque.pop_front();
    println!("pop_front: {:?}, 剩余: {:?}", front, deque);  // Some(0), [1, 2]
    
    // 查看头部和尾部（不移除）
    println!("头部: {:?}", deque.front());  // Some(&1)
    println!("尾部: {:?}", deque.back());   // Some(&2)
    
    // 长度和容量
    println!("长度: {}, 容量: {}", deque.len(), deque.capacity());
}

作为队列使用（FIFO）​

use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::new();
    
    // 入队
    queue.push_back("任务1");
    queue.push_back("任务2");
    queue.push_back("任务3");
    
    println!("队列: {:?}", queue);
    
    // 出队
    while let Some(task) = queue.pop_front() {
        println!("处理: {}", task);
    }
}

作为栈使用（LIFO）​

use std::collections::VecDeque;

fn main() {
    let mut stack = VecDeque::new();
    
    // 入栈
    stack.push_back("元素1");
    stack.push_back("元素2");
    stack.push_back("元素3");
    
    println!("栈: {:?}", stack);
    
    // 出栈
    while let Some(element) = stack.pop_back() {
        println!("弹出: {}", element);
    }
}

滑动窗口示例​

VecDeque 非常适合实现滑动窗口算法：

use std::collections::VecDeque;

fn moving_average(data: &[i32], window_size: usize) -> Vec<f64> {
    let mut result = Vec::new();
    let mut window = VecDeque::with_capacity(window_size);
    let mut sum = 0;
    
    for &value in data {
        // 添加新值
        window.push_back(value);
        sum += value;
        
        // 如果窗口超过大小，移除最老的值
        if window.len() > window_size {
            if let Some(old) = window.pop_front() {
                sum -= old;
            }
        }
        
        // 计算平均值
        if window.len() == window_size {
            result.push(sum as f64 / window_size as f64);
        }
    }
    
    result
}

fn main() {
    let data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    let averages = moving_average(&data, 3);
    println!("移动平均: {:?}", averages);
    // [2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0]
}

BTreeMap 和 BTreeSet​

当需要有序的键值对或有序集合时，使用 BTreeMap 和 BTreeSet：

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    // BTreeMap：键有序排列
    let mut map = BTreeMap::new();
    map.insert(3, "c");
    map.insert(1, "a");
    map.insert(2, "b");
    
    // 遍历时按键的顺序输出
    for (k, v) in &map {
        println!("{}: {}", k, v);  // 1: a, 2: b, 3: c
    }
    
    // 获取范围内的键值对
    for (k, v) in map.range(1..=2) {
        println!("范围内: {}: {}", k, v);
    }
    
    // BTreeSet：元素有序排列
    let mut set = BTreeSet::new();
    set.insert(3);
    set.insert(1);
    set.insert(2);
    
    for item in &set {
        println!("{}", item);  // 1, 2, 3
    }
    
    // 获取范围内的元素
    for item in set.range(2..) {
        println!(">=2: {}", item);
    }
}

HashMap vs BTreeMap：

特性HashMapBTreeMap
查找时间O(1)O(1) 平均O(log⁡n)O(\log n)
顺序无序按键排序
内存使用较高较低
范围查询不支持支持

LinkedList 链表​

Rust 的 LinkedList 是双向链表。虽然支持 O(1)O(1) 的任意位置插入删除，但由于缓存不友好，通常不推荐使用，除非有特殊需求。

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::new();
    
    // 添加元素
    list.push_back(1);
    list.push_back(2);
    list.push_front(0);
    
    // 遍历
    for elem in &list {
        println!("{}", elem);
    }
    
    // 通常推荐使用 Vec 或 VecDeque 代替
}

集合类型选择指南​

场景推荐类型说明
存储有序列表Vec<T>索引访问快，末尾添加快
存储字符串StringUTF-8 编码，可增长
键值对映射HashMap<K, V>快速查找
需要有序键值对BTreeMap<K, V>键有序排列，支持范围查询
双端队列VecDeque<T>头尾都高效添加删除
去重集合HashSet<T>快速判断元素是否存在
有序去重集合BTreeSet<T>元素有序排列
队列（FIFO）VecDeque<T>先进先出
栈（LIFO）Vec<T> 或 VecDeque<T>后进先出

性能考虑​

Vector 性能优化​

  1. 预分配容量：使用 with_capacity 可以避免多次重新分配
  2. 批量操作：使用 extend 而不是多次 push
  3. 避免中间分配：使用迭代器链代替创建中间集合
fn main() {
    // 不好的做法：可能多次重新分配
    let mut v = Vec::new();
    for i in 0..1000 {
        v.push(i);
    }
    
    // 好的做法：预分配容量
    let mut v = Vec::with_capacity(1000);
    for i in 0..1000 {
        v.push(i);
    }
}

HashMap 性能优化​

  1. 预分配容量：使用 with_capacity
  2. 选择合适的哈希函数：默认的 SipHash 安全但不是最快的，可以根据需要选择其他实现
  3. 使用引用作为键：减少所有权转移

小结​

本章我们学习了：

  1. Vector：动态数组，存储多个相同类型的值
  2. String：UTF-8 编码的可增长字符串
  3. HashMap：键值对存储，快速查找

这些集合类型是 Rust 编程中最常用的数据结构，掌握它们对于编写高效的 Rust 程序至关重要。

练习​

  1. 创建一个 Vector，存储 1 到 10 的整数，计算平均值
  2. 给定一个字符串，统计每个字符出现的次数
  3. 使用 HashMap 实现一个简单的通讯录（姓名 -> 电话号码）
  4. 实现一个函数，接受字符串并返回第一个单词

参考资料​