====== 第八章 集合类型 ======

===== 8.1 概览 =====

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

**主要集合类型：**

| 集合 | 描述 | 使用场景 |
|------|------|----------|
| Vec<T> | 可变长度的数组 | 需要按顺序存储同类型元素 |
| HashMap<K, V> | 键值对存储 | 需要通过键查找值 |
| HashSet<T> | 无序不重复集合 | 需要去重或检查成员资格 |
| VecDeque<T> | 双端队列 | 需要在两端添加/删除元素 |
| BTreeMap<K, V> | 有序键值对 | 需要按键排序遍历 |
| BTreeSet<T> | 有序不重复集合 | 需要有序且去重 |

===== 8.2 Vector（Vec<T>）=====

==== 创建Vector ====

<code 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]
</code>

==== 添加和删除元素 ====

<code rust>
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
</code>

==== 访问元素 ====

<code rust>
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
</code>

**可变引用规则：**

<code rust>
let mut v = vec![1, 2, 3, 4, 5];

let first = &v[0];  // 不可变引用
v.push(6);          // 错误！不能同时有可变和不可变引用

println!("第一个元素是：{}", first);
</code>

==== 遍历Vector ====

<code rust>
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;
}
</code>

==== 存储不同类型数据 ====

使用枚举：

<code rust>
enum SpreadsheetCell {
    Int(i32),
    Float(f64),
    Text(String),
}

let row = vec![
    SpreadsheetCell::Int(3),
    SpreadsheetCell::Text(String::from("blue")),
    SpreadsheetCell::Float(10.12),
];
</code>

===== 8.3 HashMap<K, V> =====

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

==== 创建HashMap ====

<code rust>
use std::collections::HashMap;

// 创建空HashMap
let mut scores = HashMap::new();

// 插入数据
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
</code>

**从Vector创建：**

<code rust>
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();
</code>

==== 访问值 ====

<code rust>
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);
}
</code>

==== 更新HashMap ====

**覆盖：**

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

**只在键不存在时插入：**

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

**基于旧值更新：**

<code rust>
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}
</code>

==== HashMap与所有权 ====

<code rust>
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);  // 错误！
</code>

===== 8.4 HashSet<T> =====

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

==== 创建HashSet ====

<code rust>
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();
</code>

==== 基本操作 ====

<code rust>
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();
</code>

==== 集合运算 ====

<code rust>
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}
</code>

===== 8.5 VecDeque<T> =====

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

<code rust>
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]
</code>

===== 8.6 BTreeMap和BTreeSet =====

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

<code rust>
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
</code>

===== 练习题 =====

==== 练习题8.1：统计字符频率 ====

<code rust>
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);
    }
}
</code>

==== 练习题8.2：找两数之和 ====

<code rust>
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!("未找到"),
    }
}
</code>

==== 练习题8.3：去重并排序 ====

<code rust>
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]
}
</code>

==== 练习题8.4：LRU缓存简化版 ====

<code rust>
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);
}
</code>

===== 本章小结 =====

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

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

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