How to override ordering of vectors to be by length and not lexicographic?

Question

I am trying to write a Rust program that puts integer vectors into a priority queue. The problem is, the default ordering of vectors is lexicographic, and I have to order vectors by their lengths. An ugly solution is to create a new vector struct called VEC, implement Ord by length, and just work with VEC instead. But if possible I'd prefer to override the default Ord by lex order.

//ugly solution

#[derive(Eq)]
pub struct VEC<T: Eq> {
    data: Vec<T>,
}

impl<T: Eq> Ord for VEC<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        let x = self.data.len();
        let y = other.data.len();
        y.cmp(&x)
    }
}

impl<T: Eq> PartialOrd for VEC<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T: Eq> PartialEq for VEC<T> {
    fn eq(&self, other: &Self) -> bool {
        self.data.len() == other.data.len()
    }
}

The newtype pattern is already idiomatic for overriding an ordering implementation, so it's hard to follow up on the question. Can you show a concrete example of how you intend to use this type? See also: https://stackoverflow.com/questions/68223317/how-to-create-a-custom-ordering https://stackoverflow.com/questions/26836488/how-to-sort-a-vector-in-rust — E_net4, Aug 12 '22 at 15:14
What data structure are you using for your priority queue? A `BTree`? — isaactfa, Aug 12 '22 at 15:15
@isaactfa I was thinking a `BinaryHeap`, but it does not really matter. — suwa, Aug 12 '22 at 15:43

score 1 · Answer 1 · answered Aug 12 '22 at 18:59

The ordering of a collection is solely determined by the collection and the contents. So, to customize the ordering, you must either have a custom collection or a custom element type. You've already implemented a custom wrapper element type, which is a perfectly good solution.

Another possibility, good for one-off problems, is to use a tuple. Tuples of (A, B) are ordered by comparing A and then comparing B if the As are equal. Then, notice that if you make a tuple of specifically (vec.len(), vec), then the elements will in fact be ordered by length of the vector.

This isn't as elegant as your wrapper since it would be possible to have an element with the wrong stored length, and it takes an extra usize of memory, but it's less code to write, and you don't have to worry about the correctness and consistency of your Eq, Ord, PartialEq, PartialOrd implementations since the tuple provides them all generically.

How to override ordering of vectors to be by length and not lexicographic?

1 Answers1