Rust中如何不复制数据实现Vec按多种规则排序

符合Rust惯用法的实现方案 #

你遇到的核心矛盾是Rust的BTreeSet要求Ord实现必须是类型自包含的，不能依赖集合外部的上下文（比如外层的Vec引用），这是和C++std::set的设计差异：C++允许比较器持有外部指针，把生命周期安全的责任交给开发者，而Rust在编译期就禁止了这类可能触发悬空引用、比较逻辑不一致的不安全模式。

以下两种方案完全不需要Rc<>、没有unsafe代码、符合安全规则，你可以根据业务场景选择：

方案1：预计算排序键（推荐，支持动态插入、零运行时开销） #

这是Rust生态中处理多规则排序最常用的模式，完全规避自引用问题：

• 基础存储直接用Vec<MyType>即可，不需要Box包装，也不需要智能指针。我们全程用索引访问元素，只要你只在末尾追加元素、不删除/移动已有元素，索引和元素的对应关系永久有效——哪怕Vec扩容触发元素内存移动，索引也不会失效，比引用/指针更安全。
• 为每种排序规则定义轻量的排序键类型，提前从MyType中提取比较需要的字段，和原始Vec同索引存在单独的键列表中。
• BTreeSet中存储(排序键, 索引)元组，Rust会自动为实现了Ord的元组提供排序逻辑，比较时完全不需要访问外层Vec。

示例实现：

use std::collections::BTreeSet;
use std::cmp::Reverse;

#[derive(Debug)]
struct MyType {
    id: u64,
    score: f64,
    timestamp: u64,
    // 其他大体积字段不需要复制，直接存在原始Vec中即可
}

// 第一种替代排序键：按score降序，同score按timestamp升序
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
struct Alt1Key {
    // 注意：f64没有实现Ord，如果需要排序浮点数可以自行处理NaN，或用现成的OrderedFloat包装
    score: Reverse<u64>, // 示例中假设score是可以转成有序整数类型的数值
    timestamp: u64,
}

// 第二种替代排序键：按id升序
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
struct Alt2Key {
    id: u64,
}

struct MyCollection {
    /// 按插入顺序存储原始元素
    basis: Vec<MyType>,
    /// 存储alt1规则的排序键，和basis索引一一对应
    alt1_keys: Vec<Alt1Key>,
    alt1_ordering: BTreeSet<(Alt1Key, usize)>,
    /// 存储alt2规则的排序键，和basis索引一一对应
    alt2_keys: Vec<Alt2Key>,
    alt2_ordering: BTreeSet<(Alt2Key, usize)>,
}

impl MyCollection {
    fn new() -> Self {
        Self {
            basis: Vec::new(),
            alt1_keys: Vec::new(),
            alt1_ordering: BTreeSet::new(),
            alt2_keys: Vec::new(),
            alt2_ordering: BTreeSet::new(),
        }
    }

    fn push(&mut self, item: MyType) {
        let idx = self.basis.len();
        // 插入时预计算两种排序的键
        let alt1_key = Alt1Key {
            score: Reverse((item.score * 100.0) as u64), // 示例转换逻辑
            timestamp: item.timestamp,
        };
        let alt2_key = Alt2Key { id: item.id };
        
        self.basis.push(item);
        self.alt1_keys.push(alt1_key);
        self.alt2_keys.push(alt2_key);
        self.alt1_ordering.insert((alt1_key, idx));
        self.alt2_ordering.insert((alt2_key, idx));
    }

    /// 按插入顺序遍历
    fn iter_insert_order(&self) -> impl Iterator<Item = &MyType> {
        self.basis.iter()
    }

    /// 按alt1规则遍历
    fn iter_alt1(&self) -> impl Iterator<Item = &MyType> {
        self.alt1_ordering.iter().map(move |&(_, idx)| &self.basis[idx])
    }

    /// 按alt2规则遍历
    fn iter_alt2(&self) -> impl Iterator<Item = &MyType> {
        self.alt2_ordering.iter().map(move |&(_, idx)| &self.basis[idx])
    }
}

这个方案的插入性能和原生BTreeSet一致，都是O(log n)，遍历没有额外间接访问开销，如果排序键是数值、枚举这类Copy类型，额外内存开销可以忽略不计。

方案2：一次性生成排序索引列表（适合批量插入后读取的场景） #

如果你不需要在插入过程中随时读取有序结果，而是所有元素插入完成后才做遍历访问，完全不需要BTreeSet，直接生成排序后的索引Vec即可，性能远好于BTreeSet：

struct MyCollection {
    basis: Vec<MyType>,
    alt1_ordering: Vec<usize>,
    alt2_ordering: Vec<usize>,
}

impl MyCollection {
    fn new() -> Self {
        Self {
            basis: Vec::new(),
            alt1_ordering: Vec::new(),
            alt2_ordering: Vec::new(),
        }
    }

    fn push(&mut self, item: MyType) {
        self.basis.push(item);
    }

    /// 所有元素插入完成后调用，生成各规则的有序索引
    fn build_orderings(&mut self) {
        self.alt1_ordering = (0..self.basis.len()).collect();
        self.alt1_ordering.sort_by(|&a, &b| {
            // 在这里写任意自定义比较逻辑，直接访问basis元素即可
            self.basis[a].score.partial_cmp(&self.basis[b].score).unwrap().reverse()
                .then(self.basis[a].timestamp.cmp(&self.basis[b].timestamp))
        });

        self.alt2_ordering = (0..self.basis.len()).collect();
        self.alt2_ordering.sort_by(|&a, &b| self.basis[a].id.cmp(&self.basis[b].id));
    }

    // 遍历方法和方案1一致
}

这个方案实现最简单，没有任何额外依赖，排序过程的缓存局部性远优于BTreeSet，遍历速度快很多，缺点是增量插入后需要重新排序，不适合频繁插入+频繁读取有序结果的场景。

不推荐其他方案的原因 #

• 尝试在BTreeSet的元素中存Vec引用、或者用&MyType做BTreeSet元素，本质都是构造自引用结构体，Rust借用检查器无法验证这类结构的生命周期安全，哪怕逻辑上不会失效，编译也无法通过。
• 用Rc<MyType>虽然可以解决生命周期问题，但会带来额外的引用计数运行时开销，不符合你的需求。
• 用第三方自引用库（比如ouroboros）虽然可以实现零开销的自引用结构，但会引入额外依赖，代码复杂度也高于以上两种方案。

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