A vector of `Ord` elements in a serializable structure

help
1

How to satisfy Ord and serde's Deserialize traits in the example below?

use serde::{Deserialize, Serialize};

#[derive(Deserialize, Serialize)]
pub struct Key {
    comparators: Vec<Box<dyn Ord>>, // ERROR:
}

A Comparator should be an object that implements std::cmp::Ord and because the Key is serializable it should also implement serde::Serialize and serde::Deserialize.

2

Ord can’t be made into a trait object, and it’s unclear what behavior you might want in that case: If you have two types A and B that both implement Ord, that means that there’s a natural order for A’s and a natural order for Bs. If you have a mixed collection of As and Bs, though, there’s no way to tell how they should be interleaved. And extending this from two types to all Ord types just makes the theoretical problem worse.

Can you describe at a higher level what you’re trying to accomplish?

2 Likes
3

I'd like to construct a BTreeMap where the Key would be a custom sortable key but internally it would hold a list of sortable objects. This would allow me to do a multi-index style comparison.

Comparator0(u8);
impl Ord for Comparator0 { ... }

Comparator1(u8);
impl Ord for Comparator1 { ... }

let key = Key {
   comparators: vec![Comparator0(1), Comparator1(2)],
};

let mut btree = BTreeSet::default();
btree.insert(key, value);

I was thinking about something like below (but doesn't work):

pub trait Comparable<'a>: Deserialize<'a> + Serialize {
    fn compare(&self, i: impl Ord, j: impl Ord) -> std::cmp::Ordering;
}
...
pub struct Key {
    comparators: Vec<Box<dyn Comparable>>,
}

Ow, and let me tell you that the Ord part works when not using serde's Serialize/Deserialize. I think I'll have to implement serde's traits on the Key manually :frowning:

4

Ord definitely isn't object safe. It's possible an error elsewhere in your project was preventing the Ord error from appearing, but just creating a binding of type Box<dyn Ord> causes an error immediately for me.

Serialize and Deserialize are also not object safe. You can use erased-serde to help with Serialize, but you'll have to roll your own custom Deserialize implementation because there's no way to do type erased deserialization in general. You have to add some sort of identifier to the serialization and then use that to determine what type to deserialize.

You may be better off using an enum instead of trait objects since that can do the work of adding an identifier for you. You can derive all of the traits you need on an enum as long as the types you're storing in it implement them. The derived impl may not order them exactly how you want though.

Playground

use serde::{Deserialize, Serialize};

#[derive(Deserialize, Serialize, PartialEq, Eq, PartialOrd, Ord)]
pub struct Key {
    comparators: Vec<KeyTypes>,
}

#[derive(Eq, PartialEq, PartialOrd, Ord, Serialize, Deserialize, Debug)]
enum KeyTypes {
    One(u8),
    Two(u32),
    Three(String),
}

fn main() {
    let mut list = vec![
        KeyTypes::Three("three".into()),
        KeyTypes::One(1),
        KeyTypes::Two(2),
    ];

    list.sort();

    println!("{list:?}");
}
3 Likes
5

How so?

Which of these is greater than the other? Note that you haven't defined ordering between Comparator0 and Comparator1.

    let key = Key { comparators: vec![Comparator0(1), Comparator1(2)] };
    let key = Key { comparators: vec![Comparator1(1), Comparator0(2)] };
    let key = Key { comparators: vec![Comparator0(3), Comparator1(2)] };
    let key = Key { comparators: vec![Comparator1(3), Comparator0(2)] };
6

Yeah, the enum should do the trick. Thx.

7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.