Ch 13: BTreeMap与BTreeSet

1. 引言

BTreeMap和BTreeSet是基于B树实现的有序映射和集合类型。相比HashMap和HashSet，它们的主要优势是：

• 有序性：元素按键的顺序排列，支持按范围查询
• 稳定迭代：迭代顺序始终与键顺序一致
• 范围操作：支持高效的range、split等范围操作

今天我们学习BTreeMap和BTreeSet的核心方法。

2. BTreeMap基本操作

BTreeMap是键值对的有序映射，键必须实现Ord trait。

2.1 创建与插入

use std::collections::BTreeMap;

fn main() {
    let mut map: BTreeMap<&str, i32> = BTreeMap::new();

    // insert 插入键值对
    map.insert("apple", 3);
    map.insert("banana", 2);
    map.insert("orange", 5);

    println!("{:?}", map);
    // 输出: {"apple": 3, "banana": 2, "orange": 5}

    // 键已存在则更新值
    map.insert("apple", 10);
    println!("{:?}", map);
    // 输出: {"apple": 10, "banana": 2, "orange": 5}
}

注意：insert会返回Option<V>，如果键已存在，返回旧值。

2.2 pop_first与pop_last

删除并返回最小的键值对，或最大的键值对：

use std::collections::BTreeMap;

fn main() {
    let mut map: BTreeMap<i32, &str> = BTreeMap::new();
    map.insert(3, "three");
    map.insert(1, "one");
    map.insert(2, "two");

    // pop_first 删除并返回最小的键值对
    if let Some((key, value)) = map.pop_first() {
        println!("pop_first: ({}, {})", key, value);
        // 输出: pop_first: (1, "one")
    }

    // pop_last 删除并返回最大的键值对
    if let Some((key, value)) = map.pop_last() {
        println!("pop_last: ({}, {})", key, value);
        // 输出: pop_last: (3, "three")
    }

    println!("剩余元素: {:?}", map);
    // 输出: 剩余元素: {2: "two"}
}

3. range范围操作

range允许按键的范围进行迭代，这是BTreeMap最强大的特性之一。

3.1 基本range用法

use std::collections::BTreeMap;

fn main() {
    let mut map: BTreeMap<i32, &str> = BTreeMap::new();
    map.insert(1, "one");
    map.insert(2, "two");
    map.insert(3, "three");
    map.insert(4, "four");
    map.insert(5, "five");

    // 迭代键在 [2, 4) 范围内的键值对（左闭右开）
    let range = map.range(2..4);
    for (key, value) in range {
        println!("({}, {})", key, value);
    }
    // 输出: (2, "two") 和 (3, "three")

    // 使用Bound可以更灵活地控制边界
    use std::collections::Bound;

    // 包括下界
    let range_inclusive = map.range((Bound::Included(2), Bound::Unbounded));
    println!("从2到末尾: {:?}", range_inclusive.count());
    // 输出: 从2到末尾: 4
}

3.2 range实战：排行榜

use std::collections::BTreeMap;

fn main() {
    // 模拟游戏排行榜：分数 -> 玩家名
    let mut leaderboard: BTreeMap<i32, Vec<&str>> = BTreeMap::new();
    leaderboard.insert(100, vec!["Alice", "Bob"]);
    leaderboard.insert(95, vec!["Charlie"]);
    leaderboard.insert(90, vec!["Diana", "Eve"]);

    // 查询90-100分之间的玩家
    let top_players: Vec<_> = leaderboard
        .range(90..=100)
        .flat_map(|(score, names)| names.iter().map(|n| (*score, *n)))
        .collect();

    println!("90-100分玩家: {:?}", top_players);
    // 输出: [(90, "Diana"), (90, "Eve"), (95, "Charlie"), (100, "Alice"), (100, "Bob")]
}

4. split分割操作

split将一个BTreeMap按指定键分割成两个：

use std::collections::BTreeMap;

fn main() {
    let mut map: BTreeMap<i32, &str> = BTreeMap::new();
    map.insert(1, "one");
    map.insert(2, "two");
    map.insert(3, "three");
    map.insert(4, "four");
    map.insert(5, "five");

    // 按键3分割，返回 (<3, >=3) 的两个map
    let (left, right) = map.split(&3);

    println!("左侧 (<3): {:?}", left);
    // 输出: 左侧 (<3): {1: "one", 2: "two"}

    println!("右侧 (>=3): {:?}", right);
    // 输出: 右侧 (>=3): {3: "three", 4: "four", 5: "five"}
}

注意：split会消耗原Map，如果需要保留原Map，先用clone。

5. BTreeSet核心操作

BTreeSet是只有键的集合，底层使用BTree实现。

5.1 基本操作

use std::collections::BTreeSet;

fn main() {
    let mut set: BTreeSet<i32> = BTreeSet::new();
    set.insert(3);
    set.insert(1);
    set.insert(2);

    println!("{:?}", set);
    // 输出: {1, 2, 3}

    // pop_first/pop_last
    if let Some(first) = set.pop_first() {
        println!("pop_first: {}", first);
        // 输出: pop_first: 1
    }

    // range操作
    let subset: Vec<_> = set.range(1..3).collect();
    println!("range 1..3: {:?}", subset);
    // 输出: range 1..3: [2]
}

5.2 集合运算

use std::collections::BTreeSet;

fn main() {
    let a: BTreeSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let b: BTreeSet<i32> = [3, 4, 5, 6].into_iter().collect();

    // 并集
    println!("并集: {:?}", a.union(&b).collect::<Vec<_>>());
    // 输出: 并集: [1, 2, 3, 4, 5, 6]

    // 交集
    println!("交集: {:?}", a.intersection(&b).collect::<Vec<_>>());
    // 输出: 交集: [3, 4]

    // 差集
    println!("差集 (a-b): {:?}", a.difference(&b).collect::<Vec<_>>());
    // 输出: 差集 (a-b): [1, 2]

    // 对称差集
    println!("对称差集: {:?}", a.symmetric_difference(&b).collect::<Vec<_>>());
    // 输出: 对称差集: [1, 2, 5, 6]
}

6. 性能注意事项

操作	时间复杂度
insert	O(log n)
get	O(log n)
pop_first/pop_last	O(log n)
range	O(log n + k) k为返回元素数

BTreeMap和BTreeSet适用于：

• 需要有序遍历的场景
• 范围查询频繁的场景
• 键需要比较而非仅需要哈希的场景

7. 总结

今天我们学习了BTreeMap和BTreeSet的核心操作：

1. insert - 插入键值对或元素
2. pop_first/pop_last - 删除并返回最小/最大的键值对
3. range - 按键范围迭代，是有序映射的杀手级特性
4. split - 将一个Map按指定键分割成两个
5. 集合运算 - union、intersection、difference等（仅Set）

相比HashMap/BHashSet，BTreeMap/BTreeSet在有序操作和范围查询上有明显优势，是需要保持数据有序时的首选。