Rust BTreeSet插入ID唯一、rank可重复元素异常问题排查

问题场景 #

使用BTreeSet作为有序集合，定义包含唯一id字段和可重复rank字段的Item结构体，期望仅以id判断元素唯一性，按rank字段排序。手动实现PartialEq、PartialOrd和Ord trait后，插入id=2、rank=1的元素未出现在集合中。

代码示例 #

use std::cmp::Ordering;
use std::collections::BTreeSet;

#[allow(dead_code)]
fn main() {
    let mut set = BTreeSet::new();
    set.insert(Item {
        id: 0,
        rank: 0,
    });
    set.insert(Item {
        id: 1,
        rank: 1,
    });
    set.insert(Item {
        id: 2,
        rank: 1,
    });
    for item in set.iter() {
        println!("{:?}", item);
    }

}

#[derive(Debug, Eq)]
struct Item {
    id: u32,
    rank: u32,
}

impl PartialEq for Item {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        self.rank.cmp(&other.rank)
    }
}

实际输出 #

Item { id: 0, rank: 0 }
Item { id: 1, rank: 1 }

预期输出 #

Item { id: 0, rank: 0 }
Item { id: 1, rank: 1 }
Item { id: 2, rank: 1 }

问题原因 #

Rust的BTreeSet不直接通过PartialEq判断元素是否重复，而是依赖Ord trait的实现逻辑。对于BTreeSet来说，只要两个元素通过cmp方法返回Ordering::Equal，就会被判定为同一个元素，后续插入操作会被忽略。

当前Ord仅比较rank字段，导致id=1和id=2的Item比较结果为Equal，因此BTreeSet将后者判定为重复元素，未执行插入。

解决方法 #

修改Ord trait的实现，优先按rank排序，当rank相等时，再通过唯一的id字段区分元素。这样既保证集合按rank有序，又能避免不同id元素被误判为重复。

修改后的Ord实现代码：

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        self.rank.cmp(&other.rank).then_with(|| self.id.cmp(&other.id))
    }
}

运行修改后的代码，集合会包含三个元素，输出与预期一致。

内容的提问来源于stack exchange，提问作者mepmerp