How to sort a Vec of structs by 2 or multiple fields?

user_7573706 0
Viewed 1330

example

struct MyStruct{
    row: u8,
    column: u8
}

let my_vector = a Vec<MyStruct> with like 100 items in it

Lets say I have a simple setup like this ^. I want to sort my_vector list of say 100 items by row AND THEN by column so I get my vector looking like sample 1 instead of sample 2.

sample 1

my_vector = vec![
MyStruct { row: 10, column: 1 },
MyStruct { row: 10, column: 2 },
MyStruct { row: 10, column: 3 }, ]

sample 2

my_vector = vec![
MyStruct { row: 10, column: 3 },
MyStruct { row: 10, column: 1 },
MyStruct { row: 10, column: 2 }, ]

Currently I've been working off this post which describes how to sort by a single key with the sort_by_key() function, but the issue i'm having with that is that I can only sort by a single key, and not by two or multiple keys. This results in problems like sample 2, where I get my rows sorted but then my columns in a random order.

I want both my rows and columns to be ordered. How can I do this?, Thanks

rust
5 Answers

Since tuples in Rust impl PartialOrd with lexicographic comparison, you can use the sort_by_key() methods:

my_vector.sort_unstable_by_key(|item| (item.row, item.column));

Playground.

user_78843050

You can also implement PartialOrd or Ord for MyStruct <module std::CMP>

use core::cmp::Ordering;

#[derive(Debug, Eq, PartialEq, Ord)]
struct MyStruct {
    row: u8,
    column: u8,
}

impl PartialOrd for MyStruct {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        if self.row == other.row {
            return Some(self.column.cmp(&other.column));
        }
        Some(self.row.cmp(&other.row))
    }
}

fn main() {
    let mut my_vector = vec![
        MyStruct { row: 10, column: 3 },
        MyStruct { row: 10, column: 1 },
        MyStruct { row: 10, column: 2 },
    ];
    my_vector.sort();
    println!("{:?}", my_vector);
}

playground

user_46031500

Working Solution!

By collating the information of the previous two solutions and the help of GitHub Copilot, here is a working solution for a sort by two keys

core algorithm

    my_vector.sort_by(|a, b| {
        if a.row == b.row {
            a.column.partial_cmp(&b.column).unwrap()
        } else {
            a.row.partial_cmp(&b.row).unwrap()
        }
    });

output

    // println!("{:#?}", locations);

    // let mut locations = vec![
    //     Location {
    //         row: 1,
    //         column: 1,
    //     },
    //     Location {
    //         row: 1,
    //         column: 2,
    //     },
    //     Location {
    //         row: 2,
    //         column: 1,
    //     },
    //     Location {
    //         row: 2,
    //         column: 2,
    //     },
    // ];
user_75737060

u can use sort_by()

my_vector.sort_by(|a, b| ...);

with a and b, u can make condition to return true for sort link

user_175179470

I think using match is a better alternative because it compares each pair only once. Using sort_unstable_by might be a bit better because unstable is faster, and because it is possible to make any comparison go in reverse (descending order) -- simply switch a and b for that cmp() call.

struct MyStruct{
    row: u8,
    column: u8
}

fn sort(items: &mut [MyStruct]) {
    items.sort_unstable_by(|a, b| {
        match a.row.cmp(&b.row) {
            Ordering::Equal => { a.column.cmp(&b.column) }
            v => { v }
        }
    });
}
user_1772750
Related