如何使用运行时定义的比较器定义有序映射/集？

Question

这类似于How do I use a custom comparator function with BTreeSet? 但就我而言，直到运行时我才会知道排序标准。可能的标准很广泛，并且不能进行硬编码（想想像按到目标的距离排序或按有效负载中的特定字节或其组合排序）。创建地图/集合后，排序标准不会更改。

我看到的唯一替代方案是：

• 使用 a Vec，但 log(n) 插入和删除至关重要
• 用排序标准（直接或间接）包装每个元素，但这似乎很浪费

这对于标准 C++ 容器std::map/是可能的，但对于 Rust 的/std::set似乎不可能。标准库或其他板条箱中是否有替代方案可以做到这一点？或者我必须自己实施这个？BTreeMapBTreeSet

---

我的用例是一个类似数据库的系统，其中集合中的元素由模式定义，例如：

Element {
    FIELD x: f32
    FIELD y: f32
    FIELD z: i64

    ORDERBY z
}

但由于模式是用户在运行时定义的，因此元素存储在一组字节 ( BTreeSet<Vec<u8>>) 中。同样，元素的顺序是用户定义的。所以我会给的比较器BTreeSet看起来像|a, b| schema.cmp(a, b)。硬编码后，上面的示例可能类似于：

fn cmp(a: &Vec<u8>, b: &Vec<u8>) -> Ordering {
    let a_field = self.get_field(a, 2).as_i64();
    let b_field = self.get_field(b, 2).as_i64();
    a_field.cmp(b_field)
}

Answer 1

@eggyal 编写了 copse 1 板条箱，它提供了模仿标准^库BTreeSet的、BTreeMap和BinaryHeap类型，但允许单独指定顺序。

下面是按到固定点的距离排序的 sBTreeSet的示例：Point

use copse::{BTreeSet, SortableBy, TotalOrder};

struct Point {
    x: f64,
    y: f64,
}

impl Point {
    fn distance(&self, other: &Point) -> f64 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        (dx * dx + dy * dy).sqrt()
    }
}

struct PointTotalOrder(Point);

impl TotalOrder for PointTotalOrder {
    type OrderedType = Point;

    fn cmp(&self, this: &Point, that: &Point) -> std::cmp::Ordering {
        let this_dist = self.0.distance(this);
        let that_dist = self.0.distance(that);
        f64::total_cmp(&this_dist, &that_dist)
    }
}

impl SortableBy<PointTotalOrder> for Point {
    fn sort_key(&self) -> &Point {
        self
    }
}

fn main() {
    let fixed = Point { x: 2.0, y: 3.0 };

    let mut set = BTreeSet::new(PointTotalOrder(fixed));
    set.insert(Point { x: 0.0, y: 0.0 });
    set.insert(Point { x: 3.0, y: 3.0 });
    set.insert(Point { x: 2.0, y: 5.0 });

    for point in set {
        println!("({}, {})", point.x, point.y);
    }
}

use copse::{BTreeSet, SortableBy, TotalOrder};

struct Point {
    x: f64,
    y: f64,
}

impl Point {
    fn distance(&self, other: &Point) -> f64 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        (dx * dx + dy * dy).sqrt()
    }
}

struct PointTotalOrder(Point);

impl TotalOrder for PointTotalOrder {
    type OrderedType = Point;

    fn cmp(&self, this: &Point, that: &Point) -> std::cmp::Ordering {
        let this_dist = self.0.distance(this);
        let that_dist = self.0.distance(that);
        f64::total_cmp(&this_dist, &that_dist)
    }
}

impl SortableBy<PointTotalOrder> for Point {
    fn sort_key(&self) -> &Point {
        self
    }
}

fn main() {
    let fixed = Point { x: 2.0, y: 3.0 };

    let mut set = BTreeSet::new(PointTotalOrder(fixed));
    set.insert(Point { x: 0.0, y: 0.0 });
    set.insert(Point { x: 3.0, y: 3.0 });
    set.insert(Point { x: 2.0, y: 5.0 });

    for point in set {
        println!("({}, {})", point.x, point.y);
    }
}

^{1.“Copse”这个词的意思是“一小群树木”，我觉得很贴切。}