练习与自测

本章练习共 10 题，答案折叠在每题下方。建议先自己写、编译通过后再展开答案；难度标记：★☆☆ 基础 / ★★☆ 综合 / ★★★ 挑战。

练习 1：统计 Vec 的扩容次数

难度：★☆☆

要求：写一个函数 reallocations(n: usize) -> usize，统计「向一个初始为空的 Vec<i32> 连续 push n 次」过程中发生了几次容量变化；再用 Vec::with_capacity(n) 做同样的事， 打印两个数字。最后说明为什么两者的差距是 O(log n) 而不是 O(1)。

提示：Vec::capacity() 在每次扩容后都会变大，用「上一个容量」做比较即可。

参考答案（先自己写再看）

参考答案（先自己写再看）

fn reallocations(n: usize) -> usize {
    let mut v: Vec<i32> = Vec::new();
    let mut last = v.capacity();
    let mut count = 0;
    for i in 0..n {
        v.push(i as i32);                 // 元素类型是 i32，循环变量是 usize，需要显式转换
        if v.capacity() != last {
            count += 1;
            last = v.capacity();
        }
    }
    count
}

fn main() {
    println!("不预分配：{} 次扩容", reallocations(1000));   // 输出（1.98.1）：9

    let mut v: Vec<i32> = Vec::with_capacity(1000);
    let count = {
        let mut last = v.capacity();
        let mut count = 0;
        for i in 0..1000 {
            v.push(i);
            if v.capacity() != last {
                count += 1;
                last = v.capacity();
            }
        }
        count
    };
    println!("预分配：{} 次扩容", count);                  // 输出：0
    println!("最终 capacity = {}", v.capacity());          // 输出：1000
}

要点解析：

• 不预分配时容量序列是 4 → 8 → 16 → 32 → 64 → 128 → 256 → 512 → 1024，共 9 次 （具体数字是实现细节，不要写进业务逻辑）。
• 为什么是 O(log n)：容量按几何级数增长（近似翻倍），要达到 n 需要 log₂n 次翻倍， 所以扩容次数是 Θ(log n)。总搬移量才是关键：n + n/2 + n/4 + … < 2n， 这正是「均摊 O(1)」的来源。
• 若改成每次只 +1 容量，扩容次数是 n 次、总搬移量是 O(n²)。 所以「几何增长」是为了让均摊分析成立，而不是为了省内存。
• 预分配不仅省掉搬移，还避免了峰值内存翻倍（旧块与新块同时存在的那一瞬间）。

练习 2：判断集合操作的输出与 panic

难度：★☆☆

要求：下面这段程序的输出是什么？哪些行会 panic？分别写出 panic 信息：

fn main() {
    let v = vec![10, 20, 30];
    println!("{:?}", v.get(1));
    println!("{:?}", v.get(3));
    println!("{}", v[2]);
    println!("{:?}", v.first());
    println!("{}", v[3]);
}

提示：区分 get（Option）与 []（panic）。

参考答案（先自己写再看）

参考答案（先自己写再看）

输出（前四行）：

Some(20)
None
30
Some(10)

第五行 v[3] panic：

thread 'main' panicked at src\main.rs:7:20:
index out of bounds: the len is 3 but the index is 5

（实际提示是 the len is 3 but the index is 3。）

完整可运行的验证代码：

fn main() {
    let v = vec![10, 20, 30];
    println!("{:?}", v.get(1));      // 输出：Some(20)
    println!("{:?}", v.get(3));      // 输出：None（越界不 panic）
    println!("{}", v[2]);            // 输出：30（合法下标）
    println!("{:?}", v.first());     // 输出：Some(10)

    // 想「不 panic 地取下标 3」就用 get；想验证 [] 会 panic，单独跑下面这行：
    println!("{}", v[3]);            // 运行期 panic：index out of bounds
}

要点解析：

• get 返回 Option<&T>，越界是 None，是普通返回值，可以 match/?/unwrap_or。
• [] 走 Index trait，签名必须返回 &T，无法表达失败 ⇒ 只能 panic。
• first() 就是 get(0)；last() 是 get(len - 1)，空 Vec 时都是 None （注意 last() 不会 panic，与「空集合取最后一个」的直觉错误相反）。
• 每个 [] 都带边界检查。这个检查是安全的来源，也是优化器尝试消除的对象； 用迭代器可以让它整批消失（见「迭代器 vs 索引循环：为什么迭代器常常更快」）。

练习 3：用 chunks 与 windows 切片迭代

难度：★★☆

要求：实现两个函数： fn group_sums(nums: &[i32], size: usize) -> Vec<i32>（每 size 个元素求一组和，最后一组不足也算一组）； fn is_strictly_increasing(nums: &[i32]) -> bool（严格递增）。 两者都必须用切片方法/迭代器实现，不许写显式索引循环。

提示：一个用 chunks，一个用 windows。

参考答案（先自己写再看）

参考答案（先自己写再看）

fn group_sums(nums: &[i32], size: usize) -> Vec<i32> {
    assert!(size > 0, "组大小必须大于 0，否则 chunks 会 panic");
    nums.chunks(size).map(|c| c.iter().sum()).collect()
}

fn is_strictly_increasing(nums: &[i32]) -> bool {
    nums.windows(2).all(|w| w[0] < w[1])
}

fn main() {
    println!("{:?}", group_sums(&[1, 2, 3, 4, 5], 2));      // 输出：[3, 7, 5]
    println!("{:?}", group_sums(&[1, 2, 3], 5));            // 输出：[6]
    println!("{}", is_strictly_increasing(&[1, 2, 2, 3]));  // 输出：false
    println!("{}", is_strictly_increasing(&[1, 2, 3]));     // 输出：true
    println!("{}", is_strictly_increasing(&[1]));           // 输出：true
    println!("{}", is_strictly_increasing(&[]));            // 输出：true
}

要点解析：

• chunks(size) 的最后一组可能不足 size，这正是「最后一组也算一组」的语义； 想丢弃不足的尾巴用 chunks_exact + remainder()。
• windows(2) 在长度 < 2 时产出零个窗口，而 all 对空迭代器返回 true （全称量词在空集上为真）。所以 [1] 和 [] 都判为 true —— 这通常是期望行为， 但如果业务要求「至少两个元素才算递增」，要额外加 nums.len() >= 2 判断。
• 两个函数都零分配（除了返回的 Vec），且没有显式索引 ⇒ 没有边界检查。

练习 4：按字节区间安全取子串

难度：★★☆

要求：实现 fn safe_slice(s: &str, start: usize, end: usize) -> Option<&str>： 按字节区间取子串，但只要 start/end 不是字符边界或超出长度就返回 None（绝不能 panic）。 用 "aé中b" 验证 (0,1)、(0,2)、(1,3)、(3,6)、(6,99) 五种输入。

提示：str 有一个方法天然满足这个需求，不需要手写边界检查。

参考答案（先自己写再看）

参考答案（先自己写再看）

fn safe_slice(s: &str, start: usize, end: usize) -> Option<&str> {
    s.get(start..end)          // 边界不对或越界 ⇒ None；绝不 panic
}

// 如果不用 get，等价的手写版本（用于理解 get 做了什么）：
fn safe_slice_manual(s: &str, start: usize, end: usize) -> Option<&str> {
    let bytes = s.as_bytes();
    if start > end || end > bytes.len() {
        return None;
    }
    if !s.is_char_boundary(start) || !s.is_char_boundary(end) {
        return None;
    }
    Some(&s[start..end])
}

fn main() {
    let s = "aé中b";                      // 7 字节、4 个字符
    println!("{:?}", safe_slice(s, 0, 1));      // 输出：Some("a")
    println!("{:?}", safe_slice(s, 0, 2));      // 输出：None（2 落在 'é' 内部）
    println!("{:?}", safe_slice(s, 1, 3));      // 输出：Some("é")
    println!("{:?}", safe_slice(s, 3, 6));      // 输出：Some("中")
    println!("{:?}", safe_slice(s, 6, 99));     // 输出：None（越界）

    assert_eq!(safe_slice(s, 0, 2), safe_slice_manual(s, 0, 2));
    assert_eq!(safe_slice(s, 3, 6), safe_slice_manual(s, 3, 6));
}

要点解析：

• str::get(range) 是 &s[range] 的 Option 版本，同时检查越界与字符边界两件事。
• is_char_boundary(i) 对 i == len 返回 true（末尾是合法边界）， 所以 s.get(7..7) 是 Some("") 而不是 None。
• 手写版本的意义在于看清 get 的语义：先查范围，再查边界。 顺序无关，但两个检查都必须有。
• "aé中b" 的边界是 0、1、3、6、7；0..2 之所以失败，是因为 2 落在 'é'（字节 1..3）内部。

练习 5：词频统计与 top-N 排序

难度：★★☆

要求：实现 fn top_words(text: &str, n: usize) -> Vec<(String, usize)>： 统计词频（忽略大小写、去掉词首尾的非字母数字字符），按「频次降序、频次相同按字典序升序」 返回前 n 个。用 "The quick brown fox. The fox! the dog?" 验证 n = 3 的结果。

提示：entry().or_insert(0)；排序用 sort_by + then_with。

参考答案（先自己写再看）

参考答案（先自己写再看）

use std::collections::HashMap;

fn top_words(text: &str, n: usize) -> Vec<(String, usize)> {
    let mut counts: HashMap<String, usize> = HashMap::new();

    for word in text.split_whitespace() {
        // 去掉词首尾的标点（如 "fox." → "fox"），再统一小写
        let cleaned = word
            .trim_matches(|c: char| !c.is_alphanumeric())
            .to_lowercase();
        if cleaned.is_empty() {
            continue;
        }
        *counts.entry(cleaned).or_insert(0) += 1;     // 一次查找完成「累加或初始化」
    }

    let mut ranked: Vec<(String, usize)> = counts.into_iter().collect();
    // 频次降序；频次相同则按字典序升序 —— 保证输出稳定可测
    ranked.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
    ranked.truncate(n);
    ranked
}

fn main() {
    let text = "The quick brown fox. The fox! the dog?";
    println!("{:?}", top_words(text, 3));
    // 输出：[("the", 3), ("fox", 2), ("brown", 1)]
}

要点解析：

• entry(...).or_insert(0) 只有一次哈希查找；contains_key + insert 要两次， 而且为了插入还得把 String clone 一份（见「更新：覆盖 / 存在才插入 / 基于旧值更新」 的对比图）。
• 排序必须写全序：只按频次排序时，频次相同的词顺序由 HashMap 的迭代顺序决定， 每次运行都可能不同 ⇒ 单元测试会随机失败。then_with 补上第二关键字就稳定了。
• truncate(n) 在 n >= len 时是无害的（不 panic）。
• 想避免为每个词分配 String，可以把输入先按空白切好并用 &str 当 key： HashMap<&str, usize>，代价是生命周期要跟住原文本。

练习 6：用 collect 一次性收集 Result

难度：★★☆

要求：实现 fn parse_all(raw: &[&str]) -> Result<Vec<i32>, std::num::ParseIntError>， 把 ["1", " 2 ", "3"] 一次转成 Ok([1, 2, 3])； 输入 ["1", "two", "3"] 时返回 Err（而不是 panic）。要求用一次 collect 完成， 不许写循环。

提示：Iterator<Item = Result<T, E>> 可以直接 collect 成 Result<Vec<T>, E>。

参考答案（先自己写再看）

参考答案（先自己写再看）

use std::num::ParseIntError;

fn parse_all(raw: &[&str]) -> Result<Vec<i32>, ParseIntError> {
    raw.iter().map(|s| s.trim().parse::<i32>()).collect()
}

fn main() {
    println!("{:?}", parse_all(&["1", " 2 ", "3"]));      // 输出：Ok([1, 2, 3])
    println!("{:?}", parse_all(&["1", "two", "3"]));      // 输出：Err(ParseIntError { .. })
    println!("{}", parse_all(&["1", "two", "3"]).unwrap_err());
    // 输出：invalid digit found in string

    // 想看到「有意义的错误信息」，用 map_err 换成自己的错误类型（〈错误处理〉一章详述）
    let msg = parse_all(&["1", "two"])
        .map_err(|e| format!("第 2 个元素解析失败：{e}"))
        .unwrap_err();
    println!("{msg}");
    // 输出：第 2 个元素解析失败：invalid digit found in string
}

要点解析：

• 关键标准库实现是 impl<A, E, V> FromIterator<Result<A, E>> for Result<V, E> where V: FromIterator<A>： 它把所有 Ok 装进 V，遇到第一个 Err 立刻停止并返回该 Err（短路）。
• 因此不需要手写循环、不需要中间 Vec、不需要 ? 出现在函数体里。 这也是 collect 最容易被忽视、最有价值的一种用法。
• 输入里带空格的 " 2 " 靠 trim() 处理 —— parse 本身不忽略空白。
• 注意 collect 的目标类型必须写成 Result<Vec<i32>, _> 或 Result<Vec<i32>, ParseIntError>； 错误类型推断不出来就会报 E0282。
• 这里为了演示用了 unwrap_err；真实代码里 unwrap/unwrap_err 都应换成 ?、 expect("...") 或 map_err + 传播，见 错误处理。

练习 7：自定义迭代器与 size_hint

难度：★★☆

要求：实现一个迭代器 Evens<'a>，遍历切片并产出其中所有的偶数， size_hint 必须给出正确的上界与合法的下界。 然后用它完成：collect 成 Vec、sum、在 for 循环里使用（不额外实现 IntoIterator， 并解释为什么不需要）。

提示：size_hint 的下界可以保守地给 0；上界要按「剩余元素中最多有多少个偶数」算。

参考答案（先自己写再看）

参考答案（先自己写再看）

struct Evens<'a> {
    data: &'a [i32],
    pos: usize,
}

impl<'a> Evens<'a> {
    fn new(data: &'a [i32]) -> Self {
        Evens { data, pos: 0 }
    }
}

impl<'a> Iterator for Evens<'a> {
    type Item = i32;

    fn next(&mut self) -> Option<i32> {
        while self.pos < self.data.len() {
            let value = self.data[self.pos];
            self.pos += 1;
            if value % 2 == 0 {
                return Some(value);
            }
        }
        None                       // 耗尽后一直返回 None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.data.len() - self.pos;
        (0, Some(remaining))       // 下界 0（可能全是奇数），上界是剩余元素个数
    }
}

fn main() {
    let data = [1, 2, 3, 4, 5, 6];

    let evens: Vec<i32> = Evens::new(&data).collect();
    println!("{evens:?}");                      // 输出：[2, 4, 6]
    println!("{}", Evens::new(&data).sum::<i32>());   // 输出：12

    for x in Evens::new(&data) {                // 不需要手写 IntoIterator！
        print!("{x} ");
    }
    println!();                                 // 输出：2 4 6

    let mut it = Evens::new(&data);
    println!("{:?}", it.size_hint());           // 输出：(0, Some(6))
    it.next();
    println!("{:?}", it.size_hint());           // 输出：(0, Some(4))：本次 next 跳过了 1 又取走 2
}

要点解析：

• 为什么 for 循环不需要额外实现 IntoIterator：标准库有 blanket impl impl<I: Iterator> IntoIterator for I，任何 Iterator 自动就是 IntoIterator （Item/IntoIter 都取自己）。只有容器（不是迭代器）才需要手写三个 impl， 见「实现 IntoIterator for &MyCollection」 的 Playlist。
• size_hint 的契约：下界必须 ≤ 真实数量，上界必须 ≥ 真实数量。 这里下界给 0 是保守但正确的选择（剩余元素可能全是奇数 ⇒ 一个偶数都产不出）； 上界是「剩余元素个数」，因为偶数不会超过元素总数。
• 千万别为了「看起来精确」把下界写成 remaining / 2：当剩余是 [1, 3] 时它是 0， 但 remaining / 2 = 1 > 0 就违反了契约。上界可以宽松，下界不能超标。
• 上界精确时 collect 能一次分配到位；take/skip 也能走快路径。

练习 8：把命令式循环重写为迭代器链

难度：★★☆

要求：把下面的命令式函数重写成一条迭代器链（不允许 for、while）， 并保证行为完全一致：

fn normalize_scores(raw: &[&str]) -> Vec<String> {
    let mut out = Vec::new();
    for (i, line) in raw.iter().enumerate() {
        let t = line.trim();
        if t.is_empty() {
            continue;
        }
        let n = match t.parse::<i32>() {
            Ok(n) => n,
            Err(_) => continue,
        };
        if n < 0 {
            continue;
        }
        out.push(format!("#{}: {}", i + 1, n * 10));
    }
    out
}

fn main() {
    println!("{:?}", normalize_scores(&[" 3 ", "x", "", "-1", "7"]));
    // 输出：["#1: 30", "#5: 70"]
}

输入 [" 3 ", "x", "", "-1", "7"] 时输出必须是 ["#1: 30", "#5: 70"]。 另外说明：为什么这里用 filter_map 比 filter + map 更合适。

提示：filter_map 的闭包返回 Option，可以用 ? 和 bool::then。

参考答案（先自己写再看）

参考答案（先自己写再看）

fn normalize_scores(raw: &[&str]) -> Vec<String> {
    raw.iter()
        .enumerate()
        .filter_map(|(i, line)| {
            let n = line.trim().parse::<i32>().ok()?;   // 解析失败 ⇒ ? 返回 None，被丢弃
            (n >= 0).then(|| format!("#{}: {}", i + 1, n * 10))
        })
        .collect()
}

fn main() {
    let out = normalize_scores(&[" 3 ", "x", "", "-1", "7"]);
    println!("{out:?}");        // 输出：["#1: 30", "#5: 70"]
}

要点解析：

• filter_map 的闭包返回 Option<T>：None 表示「这个元素被淘汰」， Some(v) 表示「产出 v」。它把「变换」与「过滤」压成一次遍历、一段代码 —— 而 filter(...).map(...) 需要写两遍解析逻辑（或者先 map 成 Option 再 filter(Option::is_some) + unwrap）。
• ? 在这里作用在 Option 上（Result::ok() 把它转成 Option）， 比 match 少 6 行。注意 ? 的返回类型必须与闭包的返回类型一致 ⇒ 闭包返回 Option。
• (n >= 0).then(|| ...) 比 if n >= 0 { Some(...) } else { None } 短； bool::then 自 1.50 起稳定。它是惰性的（闭包只在 true 时调用）， 而 then_some(expensive()) 会先算值再判断 —— 又是「_with 家族」的同一个坑。
• enumerate() 的下标 i 对应原始切片的位置，所以过滤掉元素后编号仍是 #1 和 #5（这正是原版命令式循环的行为）。若改成先 filter 再 enumerate， 编号会变成 #1、#2，语义就变了 —— 这是链式重写最容易出错的地方。

练习 9：UTF-8 的字节与字符边界

难度：★★★

要求：对 let s = "aé中b";（7 字节、4 个字符）判断下列表达式的运行结果， 写出「成功得到什么字符串」或「panic / 原因」： &s[0..1]、&s[0..2]、&s[1..3]、&s[3..6]、&s[6..7]、&s[7..8]、&s[0..8]、 s.len()、s.chars().count()。 再写一段程序，用 is_char_boundary 与 char_indices 打印出全部合法边界， 不依赖 panic 就能验证你的答案。

提示：逐字节打印 is_char_boundary(i) 的布尔值，再和 char_indices 对照。

参考答案（先自己写再看）

参考答案（先自己写再看）

"aé中b" 的字节布局：a=0、é=1..3、中=3..6、b=6..7，总长 7；字符数 4。

表达式	结果	说明
&s[0..1]	"a"	0、1 都是边界
&s[0..2]	panic	end byte index 2 is not a char boundary; it is inside 'é' (bytes 1..3 of string)
&s[1..3]	"é"	完整字符
&s[3..6]	"中"	完整字符
&s[6..7]	"b"	完整字符
&s[7..8]	panic	end byte index 8 is out of bounds for string of length 7
&s[0..8]	panic	同上，8 > 7
s.len()	7	字节数
s.chars().count()	4	字符数

验证程序（不依赖 panic 就能看出哪些边界合法）：

fn main() {
    let s = "aé中b";

    println!("len = {} bytes, {} chars", s.len(), s.chars().count());
    // 输出：len = 7 bytes, 4 chars

    let boundaries: Vec<usize> = (0..=s.len()).filter(|&i| s.is_char_boundary(i)).collect();
    println!("合法边界: {boundaries:?}");      // 输出：合法边界: [0, 1, 3, 6, 7]

    for (i, c) in s.char_indices() {
        println!("字节 {i} 起是 '{c}'（{c:?}，占 {} 字节）", c.len_utf8());
    }
    // 输出：
    // 字节 0 起是 'a'（'a'，占 1 字节）
    // 字节 1 起是 'é'（'é'，占 2 字节）
    // 字节 3 起是 '中'（'中'，占 3 字节）
    // 字节 6 起是 'b'（'b'，占 1 字节）

    // 用 get 代替 [] ：同样的非法区间，得到 None 而不是 panic
    println!("{:?} {:?}", s.get(0..2), s.get(0..1));   // 输出：None Some("a")
}

要点解析：

• 边界集合是 char_indices 的起始偏移，再加上末尾的 len（7）。1 是边界， 2 不是 —— &s[0..2] 失败的原因就在这里，与「长度够不够」无关。
• &s[7..8] 与 &s[0..8] 属于越界，错误信息与「非字符边界」完全不同。 看到 not a char boundary 就是切在字符中间，看到 out of bounds 就是长度不够。
• 这正是「String 是拥有所有权的 UTF-8 字节缓冲区」强调的「三种长度」：len() = 7 是字节，chars().count() = 4 是字符。 中文环境下这两个数字平均差 3 倍，是 &s[..n] 崩溃的头号原因。
• 生产代码里凡是「按用户给的偏移切字符串」都必须用 get； 只有在你已经通过 char_indices/find/split 拿到了边界时，才用 []。

练习 10：O(n) 滑动窗口最大值

难度：★★★

要求：实现 fn max_sliding_window(nums: &[i32], k: usize) -> Vec<i32>， 返回每个长度为 k 的滑动窗口中的最大值，要求 O(n) 时间。 用 [1, 3, -1, -3, 5, 3, 6, 7]、k = 3 验证得 [3, 3, 5, 5, 6, 7]。 并在「要点解析」里说明：为什么 BinaryHeap 不适合这道题；下面的选型各应该用什么容器：

1. 「始终取出优先级最高的任务，同时允许新任务随时入队」；
2. 「保留最近 100 条日志，超出就丢弃最老的」；
3. 「按时间戳有序输出，并支持查询某段时间区间」；
4. 「统计每个单词出现次数」。

提示：单调队列。队列里存下标而不是值，并保证下标对应的值单调递减。

参考答案（先自己写再看）

参考答案（先自己写再看）

use std::collections::VecDeque;

fn max_sliding_window(nums: &[i32], k: usize) -> Vec<i32> {
    assert!(k > 0, "窗口大小必须大于 0");
    if nums.len() < k {
        return Vec::new();
    }

    let mut deque: VecDeque<usize> = VecDeque::new();   // 存下标，其对应的值单调递减
    let mut out: Vec<i32> = Vec::with_capacity(nums.len() - k + 1);

    for (i, &x) in nums.iter().enumerate() {
        // 1) 队尾那些「值 <= x」的下标永远不可能再当最大值，弹掉
        while let Some(&back) = deque.back() {
            if nums[back] <= x {
                deque.pop_back();
            } else {
                break;
            }
        }
        deque.push_back(i);

        // 2) 队首滑出窗口就弹出
        if let Some(&front) = deque.front() {
            if front + k <= i {
                deque.pop_front();
            }
        }

        // 3) 窗口长度够了就记录：队首永远是当前窗口最大值的下标
        if i + 1 >= k {
            out.push(nums[deque[0]]);
        }
    }
    out
}

fn main() {
    let nums = [1, 3, -1, -3, 5, 3, 6, 7];
    println!("{:?}", max_sliding_window(&nums, 3));
    // 输出：[3, 3, 5, 5, 6, 7]
    println!("{:?}", max_sliding_window(&nums, 1));   // 输出：原数组
    println!("{:?}", max_sliding_window(&nums, 9));   // 输出：[]
}

要点解析：

• 为什么 BinaryHeap 不适合：二叉堆只能取全局最大，无法「只对最近 k 个元素取最大」。 「惰性删除」的变体（堆里存 (值, 下标)，取值时把下标过期的弹出）可以工作， 但堆的大小是 O(n)、每次操作 O(log n)，总复杂度 O(n log n)； 更麻烦的是你必须把全部 n 个元素都塞进堆，空间 O(n)。 单调队列是 O(n) 时间、O(k) 空间，且实现只有 10 行。
• 单调队列的均摊分析：每个下标最多被 push_back 一次、pop_back/pop_front 一次， 所以内层 while 的总执行次数 ≤ n，整体 O(n) —— 这与 Vec::push 的均摊分析同构。
• 为什么存下标而不是值：判断「队首是否滑出窗口」需要下标；只存值就没法判断。
• 选型答案：
  1. 「始终取出优先级最高的任务，允许随时入队」⇒ BinaryHeap（pop 取最大； 最小堆用 BinaryHeap<Reverse<T>>）。注意 BinaryHeap 不支持「更新已有元素的优先级」， 需要它就用 peek_mut()（1.63 起）小心处理，或换成索引堆。
  2. 「保留最近 100 条日志」⇒ VecDeque：push_back + 超过 100 时 pop_front， 两端都是 O(1)；用 Vec::remove(0) 是 O(n)。
  3. 「按时间戳有序输出 + 区间查询」⇒ BTreeMap（range(a..b) 是 O(log n + k)）， HashMap 完全没有范围查询能力。
  4. 「统计单词出现次数」⇒ HashMap（entry().or_insert(0)）， 需要按词有序输出时再 collect + sort，或直接换 BTreeMap。

本章小结 / 自测清单

• 我能说出 Vec::new / vec![] / with_capacity 三种创建的差别，并解释为什么 with_capacity 能省时间。
• 我知道 v[i] 会 panic、v.get(i) 返回 Option，并能解释 Index trait 为什么无法返回 Option。
• 我能画出「push 触发扩容 ⇒ 旧引用悬垂」的示意图，并给出 E0502 的三种修法。
• 我知道 Vec<T> 拥有元素、不实现 Copy，push 就是移动、drop 就是逐个析构。
• 我会用 &[T] / &mut [T] / &str 作参数，并知道 clippy::ptr_arg 在提示什么。
• 我能用 chunks / windows / split_at / split 解决分组与窗口问题，并知道 n == 0 会 panic。
• 我能解释 UTF-8 下 len() 与 chars().count() 的差别，并知道 &s[0..2] 何时 panic、怎么用 get 避免。
• 我能背出 + 的签名本质是 fn add(self, other: &str) -> String，因此左操作数会被移动。
• 我会用 entry().or_insert(0) 写词频统计，并知道 or_insert 与 or_insert_with 的求值时机差别。
• 我能说出 HashMap 遍历顺序不可依赖的三个原因，并知道何时换 BTreeMap。
• 我知道自定义类型当 key 要 derive(PartialEq, Eq, Hash)，而 f64 不能当 key。
• 我能解释 RandomState/SipHash 为什么慢，以及什么场景才值得换哈希器。
• 我能默写 for 的脱糖过程，并说清 &v / &mut v / v 三种遍历的 Item 与所有权影响。
• 我能解释「迭代器适配器是惰性的」，并指出「忘了消费」会有什么症状。
• 我能说出迭代器在边界检查与单态化上可能比索引循环更快的两条原因。
• 我能从零实现 Iterator（含正确的 size_hint）与三个 IntoIterator。
• 我能用 impl Iterator<Item = T> 作返回类型，并知道什么时候必须退化成 Box<dyn Iterator>。
• 我会用 from_fn / successors 写「生成器」，用 try_fold 写可短路的累积。
• 我能给出「边遍历边改」的四种正解：retain / drain / mem::take / 先收集后修改。
• 我知道 Vec::remove(0) 是 O(n)、chars().nth(i) 是 O(n)，并知道对应的替代容器/写法。
• 我知道 sort_by 的比较器必须满足严格弱序，否则 1.81+ 会主动 panic。

---