How to define an ordered Map/Set with a runtime-defined comparator?

This is similar to How do I use a custom comparator function with BTreeSet? however in my case I won't know the sorting criteria until runtime. The possible criteria are extensive and can't be hard-coded (think something like sort by distance to target or sort by specific bytes in a payload or combination thereof). The sorting criteria won't change after the map/set is created.

The only alternatives I see are:

use a Vec, but log(n) inserts and deletes are crucial
wrap each of the elements with the sorting criteria (directly or indirectly), but that seems wasteful

This is possible with standard C++ containers std::map/std::set but doesn't seem possible with Rust's BTreeMap/BTreeSet. Is there an alternative in the standard library or in another crate that can do this? Or will I have to implement this myself?

My use-case is a database-like system where elements in the set are defined by a schema, like:

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

    ORDERBY z
}

But since the schema is user-defined at runtime, the elements are stored in a set of bytes (BTreeSet<Vec<u8>>). Likewise the order of the elements is user-defined. So the comparator I would give to BTreeSet would look like |a, b| schema.cmp(a, b). Hard-coded, the above example may look something like:

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)
}

Solution

There is the copse¹ crate written by @eggyal which provides BTreeSet, BTreeMap, and BinaryHeap types mimicking the standard library but which allow a ordering to be specified separately.

Here is an example BTreeSet of Points that are ordered by a distance to a fixed 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);
    }
}

(3, 3)
(2, 5)
(0, 0)

^{1. "Copse" is a word meaning "a small group of trees" which I find very fitting.}