第八章 集合类型

Rust标准库提供了几种有用的集合类型，存储在堆上，大小可以动态增长。

主要集合类型：

// 创建空Vec
let v: Vec<i32> = Vec::new();
 
// 使用vec!宏
let v = vec![1, 2, 3];
 
// 创建并填充
let v = vec![0; 5];  // [0, 0, 0, 0, 0]

let mut v = Vec::new();
 
// 添加元素
v.push(5);
v.push(6);
v.push(7);
 
// 删除并返回最后一个元素
let last = v.pop();  // Some(7)
 
// 在指定位置插入
v.insert(0, 10);  // [10, 5, 6]
 
// 删除指定位置元素
let removed = v.remove(0);  // 10

let v = vec![1, 2, 3, 4, 5];
 
// 索引访问（越界会panic）
let third: &i32 = &v[2];
println!("第三个元素是{}", third);
 
// get方法（安全）
match v.get(2) {
    Some(third) => println!("第三个元素是{}", third),
    None => println!("没有这个元素"),
}
 
// 越界不会panic
let does_not_exist = v.get(100);  // None

可变引用规则：

let mut v = vec![1, 2, 3, 4, 5];
 
let first = &v[0];  // 不可变引用
v.push(6);          // 错误！不能同时有可变和不可变引用
 
println!("第一个元素是：{}", first);

let v = vec![100, 32, 57];
 
// 不可变遍历
for i in &v {
    println!("{}", i);
}
 
// 可变遍历
let mut v = vec![100, 32, 57];
for i in &mut v {
    *i += 50;
}

使用枚举：

enum SpreadsheetCell {
    Int(i32),
    Float(f64),
    Text(String),
}
 
let row = vec![
    SpreadsheetCell::Int(3),
    SpreadsheetCell::Text(String::from("blue")),
    SpreadsheetCell::Float(10.12),
];

HashMap存储键值对，通过键查找值，平均时间复杂度O(1)。

use std::collections::HashMap;
 
// 创建空HashMap
let mut scores = HashMap::new();
 
// 插入数据
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

从Vector创建：

use std::collections::HashMap;
 
let teams = vec![String::from("Blue"), String::from("Yellow")];
let initial_scores = vec![10, 50];
 
let scores: HashMap<_, _> = teams.iter()
    .zip(initial_scores.iter())
    .collect();

use std::collections::HashMap;
 
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
 
// get方法
let team_name = String::from("Blue");
let score = scores.get(&team_name);  // Some(&10)
 
// 遍历
for (key, value) in &scores {
    println!("{}: {}", key, value);
}

覆盖：

scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Blue"), 25);  // 覆盖

只在键不存在时插入：

scores.entry(String::from("Yellow")).or_insert(50);
scores.entry(String::from("Blue")).or_insert(50);  // Blue已存在，不会插入

基于旧值更新：

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);
// {"world": 2, "hello": 1, "wonderful": 1}

use std::collections::HashMap;
 
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);  // 错误！

HashSet是不允许重复值的无序集合。

use std::collections::HashSet;
 
// 创建空Set
let mut set = HashSet::new();
 
// 从Vector创建
let numbers = vec![1, 2, 3, 4, 5, 3, 2];
let unique: HashSet<_> = numbers.into_iter().collect();

use std::collections::HashSet;
 
let mut set = HashSet::new();
 
// 插入
set.insert(1);
set.insert(2);
set.insert(3);
 
// 重复插入无效
set.insert(2);  // 无效
 
// 检查存在
if set.contains(&1) {
    println!("包含1");
}
 
// 删除
set.remove(&1);
 
// 长度
println!("长度：{}", set.len());
 
// 清空
set.clear();

use std::collections::HashSet;
 
let a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
let b: HashSet<_> = [2, 3, 4].iter().cloned().collect();
 
// 交集
let intersection: HashSet<_> = a.intersection(&b).collect();
println!("交集：{:?}", intersection);  // {2, 3}
 
// 并集
let union: HashSet<_> = a.union(&b).collect();
println!("并集：{:?}", union);  // {1, 2, 3, 4}
 
// 差集
let difference: HashSet<_> = a.difference(&b).collect();
println!("差集：{:?}", difference);  // {1}
 
// 对称差集
let symmetric_diff: HashSet<_> = a.symmetric_difference(&b).collect();
println!("对称差集：{:?}", symmetric_diff);  // {1, 4}

VecDeque是双端队列，在两端添加/删除元素都是O(1)。

use std::collections::VecDeque;
 
let mut deque = VecDeque::new();
 
// 在前端添加
deque.push_front(1);
deque.push_front(2);
 
// 在后端添加
deque.push_back(3);
deque.push_back(4);
 
// 前端弹出
let front = deque.pop_front();  // Some(2)
 
// 后端弹出
let back = deque.pop_back();    // Some(4)
 
// 访问
println!("{:?}", deque);  // [1, 3]

BTreeMap和BTreeSet是有序版本，基于B树实现。

use std::collections::BTreeMap;
 
let mut map = BTreeMap::new();
map.insert(3, "c");
map.insert(1, "a");
map.insert(2, "b");
 
// 遍历时按键排序
for (key, value) in &map {
    println!("{}: {}", key, value);
}
// 输出：
// 1: a
// 2: b
// 3: c

use std::collections::HashMap;
 
fn char_frequency(text: &str) -> HashMap<char, usize> {
    let mut map = HashMap::new();
 
    for c in text.chars() {
        *map.entry(c).or_insert(0) += 1;
    }
 
    map
}
 
fn main() {
    let text = "hello world";
    let freq = char_frequency(text);
 
    for (c, count) in &freq {
        println!("'{}': {}", c, count);
    }
}

use std::collections::HashMap;
 
fn two_sum(nums: Vec<i32>, target: i32) -> Option<(usize, usize)> {
    let mut map = HashMap::new();
 
    for (i, &num) in nums.iter().enumerate() {
        let complement = target - num;
        if let Some(&j) = map.get(&complement) {
            return Some((j, i));
        }
        map.insert(num, i);
    }
 
    None
}
 
fn main() {
    let nums = vec![2, 7, 11, 15];
    let target = 9;
 
    match two_sum(nums, target) {
        Some((i, j)) => println!("索引 {} 和 {} 的值相加为{}", i, j, target),
        None => println!("未找到"),
    }
}

use std::collections::BTreeSet;
 
fn unique_sorted(nums: Vec<i32>) -> Vec<i32> {
    let set: BTreeSet<_> = nums.into_iter().collect();
    set.into_iter().collect()
}
 
fn main() {
    let nums = vec![5, 3, 5, 2, 3, 1, 4, 2];
    let result = unique_sorted(nums);
    println!("{:?}", result);  // [1, 2, 3, 4, 5]
}

use std::collections::VecDeque;
 
struct SimpleCache {
    items: VecDeque<i32>,
    capacity: usize,
}
 
impl SimpleCache {
    fn new(capacity: usize) -> Self {
        SimpleCache {
            items: VecDeque::new(),
            capacity,
        }
    }
 
    fn get(&mut self, val: i32) -> bool {
        if let Some(pos) = self.items.iter().position(|&x| x == val) {
            // 移动到前端
            self.items.remove(pos);
            self.items.push_front(val);
            true
        } else {
            false
        }
    }
 
    fn put(&mut self, val: i32) {
        if self.items.contains(&val) {
            return;
        }
 
        if self.items.len() >= self.capacity {
            self.items.pop_back();
        }
 
        self.items.push_front(val);
    }
}
 
fn main() {
    let mut cache = SimpleCache::new(3);
    cache.put(1);
    cache.put(2);
    cache.put(3);
    println!("缓存：{:?}", cache.items);
 
    cache.put(4);  // 移除1
    println!("加入4后：{:?}", cache.items);
 
    println!("查找2：{}", cache.get(2));
    println!("查找后：{:?}", cache.items);
}

本章介绍了Rust的主要集合类型：

• Vec<T>：动态数组，支持push/pop/insert/remove
• HashMap<K, V>：哈希表，键值对存储
• HashSet<T>：不重复元素集合
• VecDeque<T>：双端队列
• BTreeMap/BTreeSet：有序版本

这些集合类型都存储在堆上，所有权规则适用。选择合适的集合类型对于程序性能很重要。