Rust中如何定义依赖标准值排序且避免无效比较的结构体？

你的思路方向是对的，但原实现确实存在冗余引用和无效比较的风险。这里提供一种更符合Rust惯用写法的方案，既能消除冗余，又能通过类型系统在编译时阻止无效比较：

核心思路 #

1. 预先计算距离：在创建Submission时就计算好提交位置到正确位置的距离并存储，避免重复计算和持有冗余引用。
2. 类型标记确保安全：用一个零大小的泛型标记类型，确保只有针对同一游戏轮次（或同一正确位置）的Submission才能被比较，编译器直接拦截跨轮次的无效操作。

完整代码实现 #

// 定义一个零大小的标记类型，用来区分不同的游戏轮次
// 你可以为每一轮游戏创建不同的标记类型，比如GameRound1、GameRound2，或者用UUID作为关联类型
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct CurrentGameRound;

// 假设你的Location结构体是这样的（如果已有可以忽略）
#[derive(Clone, Copy, Debug)]
struct Location {
    lat: f64,
    lng: f64,
}

impl Location {
    fn distance(&self, other: Location) -> f64 {
        // 这里实现你的距离计算逻辑，比如Haversine公式
        let d_lat = (other.lat - self.lat).to_radians();
        let d_lng = (other.lng - self.lng).to_radians();
        let a = (d_lat / 2.0).sin().powi(2)
            + self.lat.to_radians().cos() * other.lat.to_radians().cos()
            * (d_lng / 2.0).sin().powi(2);
        let c = 2.0 * a.sqrt().atan2((1.0 - a).sqrt());
        6371.0 * c // 地球半径，单位公里
    }
}

// Submission结构体：存储提交位置、预先计算的距离，以及类型标记
struct Submission<R> {
    submitted: Location,
    distance: f64,
    // 零大小标记，不占用内存，仅用于类型区分
    _marker: std::marker::PhantomData<R>,
}

impl<R> Submission<R> {
    // 构造函数：必须传入正确位置，在这里一次性计算距离
    // 外部无法绕过这个逻辑创建错误的Submission
    pub fn new(submitted: Location, correct: &Location) -> Self {
        let distance = submitted.distance(*correct);
        Self {
            submitted,
            distance,
            _marker: std::marker::PhantomData,
        }
    }

    // 提供获取距离的方法（可选）
    pub fn distance(&self) -> f64 {
        self.distance
    }

    // 提供获取提交位置的方法（可选）
    pub fn submitted_location(&self) -> Location {
        self.submitted
    }
}

// 仅允许同一标记类型R的Submission进行相等比较
impl<R> PartialEq for Submission<R> {
    fn eq(&self, other: &Self) -> bool {
        self.distance.eq(&other.distance)
    }
}

// 实现Eq trait（因为PartialEq已经覆盖了所有情况，且距离相等是完全等价的）
impl<R> Eq for Submission<R> {}

// 实现PartialOrd，基于距离排序（距离越小排名越靠前）
impl<R> PartialOrd for Submission<R> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        // 因为f64的partial_cmp可能返回None（比如NaN），但我们的构造函数确保distance是有效的数值
        // 所以这里可以安全地unwrap，或者处理NaN情况（如果你的distance计算可能产生NaN）
        self.distance.partial_cmp(&other.distance)
    }
}

// 实现Ord trait，让Submission可以被用于OrderedSkipList这类需要全序的容器
impl<R> Ord for Submission<R> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.partial_cmp(other)
            .unwrap_or(std::cmp::Ordering::Equal)
    }
}

方案优势 #

• 消除冗余：不再每个Submission都持有correct的引用，内存占用更低，也避免了生命周期的困扰。
• 编译时安全：如果尝试比较不同标记类型的Submission（比如Submission<CurrentGameRound>和Submission<AnotherGameRound>），编译器会直接报错，彻底避免无效比较。
• 性能提升：距离只在创建时计算一次，后续比较和排序无需重复计算，效率更高。
• 惯用写法：利用Rust的类型系统和零大小类型实现安全约束，符合Rust的"安全优先"设计理念。

使用示例 #

use skiplist::ordered_skiplist::OrderedSkipList;

fn main() {
    let correct_location = Location { lat: 51.5074, lng: -0.1278 }; // 伦敦大本钟

    // 创建当前轮次的提交列表
    let mut submissions: OrderedSkipList<Submission<CurrentGameRound>> = OrderedSkipList::new();

    // 添加玩家提交
    submissions.insert(Submission::new(Location { lat: 51.5073, lng: -0.1277 }, &correct_location));
    submissions.insert(Submission::new(Location { lat: 51.5100, lng: -0.1300 }, &correct_location));

    // 遍历排序后的提交（距离从小到大）
    for submission in submissions.iter() {
        println!("距离: {:.2} km", submission.distance());
    }
}

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