64、BTreeMap（B树表）

概述

通过从Vec迁移到HashMap，我们提高了票务管理系统的性能，并在此过程中简化了代码。

不过，这并不意味着万事大吉。在迭代Vec的存储结构时，我们可以确保ticket按照添加的顺序返回。

HashMap的情况并非如此：我们可以迭代tickets，但是顺序是随机的。

我们可以从HashMap切换到BTreeMap来恢复一致的顺序。

BTreeMap

BTreeMap保证条目按照他们的键进行排序。

当我们需要按照特定顺序迭代条目的时候，或者需要执行范围查询的时候（比如查询id在10-20的所有的ticket）时，这就很有用了。

就像HashMap一样，我们不会在BTreeMap的定义上找到trait约束。但是我们可以发现它的方法上的trait约束，让我们看一下insert方法：

// `K` and `V` stand for the key and value types, respectively,
// just like in `HashMap`.
// K 和 V 分别代表键类型和值类型，
// 就像在 HashMap 中一样。
impl<K, V> BTreeMap<K, V> {
    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        // implementation
    }
}

我们不再需要Hash trait。相反，键类型必须实现Ord trait。

Ord

Ordtrait被用来比较值。对比来看，PartialEq用于比较相等性，而Ord用于比较可排序性。

Ord被定义在std::cmp：

pub trait Ord: Eq + PartialOrd {
    fn cmp(&self, other: &Self) -> Ordering;
}

cmp方法返回一个Ordering枚举，这个枚举可以是Less，Equal或Greater。

Ord需要实现两个其他的trait：Eq和PratialOrd。

PartialOrd

PartialOrd是Ord的弱版本，就像PartialEq是Eq的弱版本一样。看定义就知道为什么了：

pub trait PartialOrd: PartialEq {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering>;
}

PartialOrd::partial_cmp返回一个Option——不保证两个值可以进行比较。

例如，f32没有实现Ord，因为NaN值不具有可比性，这与f32不实现Eq的原因相同。

实现Ord和PartialOrd

Ord和PartialEq都可以为我们的类型派生：

// You need to add `Eq` and `PartialEq` too,
// since `Ord` requires them.
#[derive(Eq, PartialEq, Ord, PartialOrd)]
struct TicketId(u64);

如果我们选择（或需要——手动实现它们，需要小心以下两点：

• Ord和PartialEq必须与Eq和PartialEq一致。
• Ord和PartialOrd必须彼此一致。

练习

这一节的练习和上一节的其实差别不大，补充内容都差不多，我就直接跳过了，关键在于一个地方……

原题：

// TODO: Replace `todo!()`s with the correct implementation.
//  Implement `IntoIterator` for `&TicketStore`. The iterator should yield immutable
//  references to the tickets, ordered by their `TicketId`.
//  Implement additional traits on `TicketId` if needed.
// TODO：将 todo!() 替换为正确的实现。
//  为 &TicketStore 实现 IntoIterator。该迭代器应按 TicketId 的顺序，生成对票证的不可变引用。
//  如有必要，在 TicketId 上实现额外的 trait。
use std::collections::{hash_map, BTreeMap};
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};

#[derive(Clone)]
pub struct TicketStore {
    tickets: BTreeMap<TicketId, Ticket>,
    counter: u64,
}

#[derive(Clone, Copy, Debug, PartialEq, Ord, PartialOrd, Eq)]
pub struct TicketId(u64);

#[derive(Clone, Debug, PartialEq)]
pub struct Ticket {
    pub id: TicketId,
    pub title: TicketTitle,
    pub description: TicketDescription,
    pub status: Status,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TicketDraft {
    pub title: TicketTitle,
    pub description: TicketDescription,
}

#[derive(Clone, Debug, Copy, PartialEq, Eq)]
pub enum Status {
    ToDo,
    InProgress,
    Done,
}

impl TicketStore {
    pub fn new() -> Self {
        Self {
            tickets: BTreeMap::new(),
            counter: 0,
        }
    }

    pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
        let id = TicketId(self.counter);
        self.counter += 1;
        let ticket = Ticket {
            id,
            title: ticket.title,
            description: ticket.description,
            status: Status::ToDo,
        };
        self.tickets.insert(id, ticket);
        id
    }

    pub fn get(&self, id: TicketId) -> Option<&Ticket> {
        self.tickets.get(&id)
    }

    pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
        self.tickets.get_mut(&id)
    }
}

impl Index<TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: TicketId) -> &Self::Output {
        self.get(index).unwrap()
    }
}

impl Index<&TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: &TicketId) -> &Self::Output {
        &self[*index]
    }
}

impl IndexMut<TicketId> for TicketStore {
    fn index_mut(&mut self, index: TicketId) -> &mut Self::Output {
        self.get_mut(index).unwrap()
    }
}

impl IndexMut<&TicketId> for TicketStore {
    fn index_mut(&mut self, index: &TicketId) -> &mut Self::Output {
        &mut self[*index]
    }
}
/* TODO */

我们要做的是为TicketStore实现IntoIteratortrait。我一开始鼓捣了半天没鼓捣出来：

impl IntoIterator for TicketStore {
    type Item = (TicketId, Ticket);
    type IntoIter = std::collections::hash_map::IntoIter<TicketId, Ticket>;
    fn into_iter(self) -> Self::IntoIter {
        self.tickets.into_iter()
    }
}

后来看了一下答案，发现是：

impl<'a> IntoIterator for &'a TicketStore {
    type Item = &'a Ticket;
    type IntoIter = std::collections::btree_map::Values<'a, TicketId, Ticket>;

    fn into_iter(self) -> Self::IntoIter {
        self.tickets.values()
    }
}

问题就在于生命周期。

因为这是一个迭代器，所以我们必须确保迭代的元素的生命周期和TicketStore的生命周期保持一致，避免发生悬空引用的情况。

今天的学习就先到这里了。