Rust: Rust 常用集合：VecDeque、BTreeMap 与性能对比

let mut queue = Vec::new();
queue.push("Customer A");   // A 取号，排在队尾
queue.push("Customer B");   // B 取号，排在队尾
queue.push("Customer C");   // C 取号，排在队尾

// 叫号入座：从队头移除
let first = queue.remove(0);  // O(n) —— 后面的所有元素都要前移！
println!("{} 入座", first);

use std::collections::VecDeque;
use std::collections::BTreeMap;

fn main() {
    // VecDeque：前后都能进出
    let mut queue = VecDeque::new();
    queue.push_back("Customer A");   // 队尾进入
    queue.push_back("Customer B");
    queue.push_front("VIP");         // VIP 从队首插队！

    println!("下一个入座: {}", queue.pop_front().unwrap());  // VIP
    println!("再下一个: {}", queue.pop_front().unwrap());    // Customer A

    // BTreeMap：有序键值存储
    let mut customers = BTreeMap::new();
    customers.insert(1001, "Alice");
    customers.insert(1003, "Bob");
    customers.insert(1002, "Charlie");

    // 自动按键排序输出
    for (id, name) in &customers {
        println!("取号 #{}: {}", id, name);
    }
    // 输出: #1001: Alice, #1002: Charlie, #1003: Bob
}

// ============================================
// VecDeque：双端队列的基本操作
// ============================================

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque<&str> = VecDeque::new();

    // 普通顾客从队尾进入
    queue.push_back("Alice");
    queue.push_back("Bob");
    queue.push_back("Charlie");

    // VIP 顾客从队首插队
    queue.push_front("VIP-David");
    queue.push_front("VIP-Eve");

    println!("当前排队人数: {}", queue.len());
    println!("队首: {:?}, 队尾: {:?}", queue.front(), queue.back());

    // 叫号入座：从队首移除
    println!("\n叫号顺序:");
    while let Some(customer) = queue.pop_front() {
        println!("  {} 入座", customer);
    }
}

当前排队人数: 5
队首: Some("VIP-Eve"), 队尾: Some("Charlie")

叫号顺序:
  VIP-Eve 入座
  VIP-David 入座
  Alice 入座
  Bob 入座
  Charlie 入座

// ============================================
// BTreeMap：按键自动排序
// ============================================

use std::collections::BTreeMap;

fn main() {
    let mut scores = BTreeMap::new();

    scores.insert("Charlie", 87);
    scores.insert("Alice", 95);
    scores.insert("Bob", 72);
    scores.insert("David", 91);

    // BTreeMap 按键（字母顺序）自动排序
    println!("=== 成绩单（按姓名排序）===");
    for (name, score) in &scores {
        println!("  {}: {}", name, score);
    }

    // 按键查找
    println!("\nAlice 的成绩: {}", scores.get("Alice").unwrap());

    // 检查是否存在
    if scores.contains_key("Eve") {
        println!("Eve 的成绩存在");
    } else {
        println!("Eve 还没有成绩");
    }

    // 获取第一个和最后一个条目
    println!("\n第一个: {:?}", scores.first_key_value());
    println!("最后一个: {:?}", scores.last_key_value());
}

=== 成绩单（按姓名排序）===
  Alice: 95
  Bob: 72
  Charlie: 87
  David: 91

Alice 的成绩: 95
Eve 还没有成绩

第一个: Some(("Alice", 95))
最后一个: Some(("David", 91))

// ============================================
// BTreeMap 范围查询：range 方法
// ============================================

use std::collections::BTreeMap;

fn main() {
    // 模拟订单系统：日期 -> 订单金额
    let mut orders = BTreeMap::new();

    orders.insert("2026-07-01", 120);
    orders.insert("2026-07-03", 85);
    orders.insert("2026-07-05", 200);
    orders.insert("2026-07-07", 150);
    orders.insert("2026-07-10", 95);

    // 查询 7 月 3 日到 7 月 7 日之间的订单（包含两端）
    println!("=== 7月3日 ~ 7月7日 订单 ===");
    for (date, amount) in orders.range("2026-07-03"..="2026-07-07") {
        println!("  {}: ${}", date, amount);
    }

    // 查询所有 >= 7月5日的订单
    println!("\n=== 7月5日及之后 订单 ===");
    for (date, amount) in orders.range("2026-07-05"..) {
        println!("  {}: ${}", date, amount);
    }

    // 汇总金额
    let total: i32 = orders.range("2026-07-03"..="2026-07-07")
        .map(|(_, amount)| amount)
        .sum();
    println!("\n7月3日~7月7日总金额: ${}", total);
}

=== 7月3日 ~ 7月7日 订单 ===
  2026-07-03: $85
  2026-07-05: $200
  2026-07-07: $150

=== 7月5日及之后 订单 ===
  2026-07-05: $200
  2026-07-07: $150
  2026-07-10: $95

7月3日~7月7日总金额: $435

// ============================================
// 四种集合性能对比：插入 10000 个元素
// ============================================

use std::collections::{BTreeMap, HashMap, VecDeque};
use std::time::Instant;

fn main() {
    let n = 10_000;

    // Vec 尾部插入
    let start = Instant::now();
    let mut vec = Vec::new();
    for i in 0..n {
        vec.push(i);
    }
    println!("Vec 尾部插入: {:?}", start.elapsed());

    // VecDeque 尾部插入
    let start = Instant::now();
    let mut deque = VecDeque::new();
    for i in 0..n {
        deque.push_back(i);
    }
    println!("VecDeque 尾部插入: {:?}", start.elapsed());

    // HashMap 插入
    let start = Instant::now();
    let mut hmap = HashMap::new();
    for i in 0..n {
        hmap.insert(i, i);
    }
    println!("HashMap 插入: {:?}", start.elapsed());

    // BTreeMap 插入
    let start = Instant::now();
    let mut bmap = BTreeMap::new();
    for i in 0..n {
        bmap.insert(i, i);
    }
    println!("BTreeMap 插入: {:?}", start.elapsed());

    // 查找性能对比
    println!("\n--- 查找性能 ---");

    let start = Instant::now();
    let _ = vec.contains(&9999);
    println!("Vec 线性查找: {:?}", start.elapsed());

    let start = Instant::now();
    let _ = hmap.get(&9999);
    println!("HashMap 查找: {:?}", start.elapsed());

    let start = Instant::now();
    let _ = bmap.get(&9999);
    println!("BTreeMap 查找: {:?}", start.elapsed());
}

Vec 尾部插入: 78.2µs
VecDeque 尾部插入: 82.1µs
HashMap 插入: 1.2ms
BTreeMap 插入: 2.8ms

--- 查找性能 ---
Vec 线性查找: 42.5µs
HashMap 查找: 138ns
BTreeMap 查找: 312ns

// ============================================
// 综合示例：VecDeque 队列 + BTreeMap 优先级
// ============================================

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

#[derive(Debug, Clone)]
struct Task {
    id: u32,
    name: String,
    priority: u8,
}

fn main() {
    let mut queue: VecDeque<Task> = VecDeque::new();
    queue.push_back(Task { id: 1, name: "Check email".into(), priority: 3 });
    queue.push_back(Task { id: 2, name: "Fix bug #42".into(), priority: 1 });
    queue.push_back(Task { id: 3, name: "Write report".into(), priority: 2 });
    queue.push_back(Task { id: 4, name: "Urgent deploy".into(), priority: 0 });

    println!("=== FIFO 队列处理 ===");
    while let Some(task) = queue.pop_front() {
        println!("[P{}] #{}: {}", task.priority, task.id, task.name);
    }

    let mut priority_map: BTreeMap<u8, Vec<String>> = BTreeMap::new();
    let tasks = vec![
        ("Check email", 3u8), ("Fix bug #42", 1), ("Write report", 2),
        ("Urgent deploy", 0), ("Code review", 1), ("Team meeting", 3),
        ("Security patch", 0), ("Update docs", 2),
    ];

    for (name, pri) in tasks {
        priority_map.entry(pri).or_insert_with(Vec::new).push(name.to_string());
    }

    println!("\n=== 按优先级排序 ===");
    for (pri, task_list) in &priority_map {
        println!("P{}: {:?}", pri, task_list);
    }

    println!("\n=== 高优先级任务 (P0-P1) ===");
    for (pri, task_list) in priority_map.range(0..=1) {
        println!("P{}: {:?}", pri, task_list);
    }

    let mut history: VecDeque<String> = VecDeque::with_capacity(3);
    for i in 0..5 {
        history.push_back(format!("task_{}", i));
        if history.len() > 3 {
            history.pop_front();
        }
    }
    println!("\n最近 3 条历史: {:?}", history);
}

=== FIFO 队列处理 ===
[P3] #1: Check email
[P1] #2: Fix bug #42
[P2] #3: Write report
[P0] #4: Urgent deploy

=== 按优先级排序 ===
P0: ["Urgent deploy", "Security patch"]
P1: ["Fix bug #42", "Code review"]
P2: ["Write report", "Update docs"]
P3: ["Check email", "Team meeting"]

=== 高优先级任务 (P0-P1) ===
P0: ["Urgent deploy", "Security patch"]
P1: ["Fix bug #42", "Code review"]

最近 3 条历史: ["task_2", "task_3", "task_4"]