Defining Comparable Structs in Rust: A Practical Guide

When working with data structures in Rust, especially when you need to sort or compare custom structs, understanding how to define comparability is crucial. This guide will explore how to make your Rust structs comparable, focusing on implementing the necessary traits for ordering and equality, particularly when dealing with complex fields like HashMap. We’ll address a common scenario: defining a custom order for a User struct based on surname, name, and a HashMap of interests.

In Rust, the standard library provides several traits that enable comparison: PartialEq, Eq, PartialOrd, and Ord. These traits are essential for using structs with data structures like BTreeSet or when you need to perform sorting operations. Let’s break down why each of these traits is important.

PartialEq and Eq are for equality comparisons. PartialEq allows for partial equality, meaning that not all values of a type can be compared for equality (think floating-point numbers and NaN). Eq is for types where equality is total and reflexive (if a == b and b == c, then a == c). For most structs where all fields are comparable, you’ll want to derive or implement both.

PartialOrd and Ord are for ordering comparisons. PartialOrd allows for partial ordering, where some pairs of values might not be comparable. Ord represents a total ordering; for any two values, it’s always possible to determine if one is less than, equal to, or greater than the other. If you want to use your struct in a BTreeSet or sort a vector of your structs, you need to implement Ord. Implementing Ord also requires implementing PartialOrd, Eq, and PartialEq.

Let’s consider the User struct from the original example:

#[derive(Eq, Debug)]
pub struct User {
    name: String,
    surname: String,
    interests: HashMap<String, String>,
}

To make User comparable, we need to implement Ord. The desired ordering is first by surname, then by name, and finally by the interests HashMap. Here’s how you can implement Ord for this User struct:

use std::cmp::Ordering;
use std::collections::HashMap;

#[derive(Eq, Debug, PartialEq)]
pub struct User {
    name: String,
    surname: String,
    interests: HashMap<String, String>,
}

impl User {
    pub fn create(
        name: String,
        surname: String,
        interests: HashMap<String, String>,
    ) -> User {
        User { name, surname, interests }
    }
}

impl Ord for User {
    fn cmp(&self, other: &Self) -> Ordering {
        self.surname.cmp(&other.surname)
            .then_with(|| self.name.cmp(&other.name))
            .then_with(|| {
                let mut self_interests_sorted: Vec<_> = self.interests.iter().collect();
                let mut other_interests_sorted: Vec<_> = other.interests.iter().collect();
                self_interests_sorted.sort_by_key(|(k, _)| *k);
                other_interests_sorted.sort_by_key(|(k, _)| *k);

                for i in 0..std::cmp::min(self_interests_sorted.len(), other_interests_sorted.len()) {
                    let key_cmp = self_interests_sorted[i].0.cmp(&other_interests_sorted[i].0);
                    if key_cmp != Ordering::Equal {
                        return key_cmp;
                    }
                    let value_cmp = self_interests_sorted[i].1.cmp(&other_interests_sorted[i].1);
                    if value_cmp != Ordering::Equal {
                        return value_cmp;
                    }
                }
                self.interests.len().cmp(&other.interests.len())
            })
    }
}

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

impl PartialEq for User {
    fn eq(&self, other: &Self) -> bool {
        self.surname == other.surname && self.name == other.name && self.interests == other.interests
    }
}

In the cmp function, we first compare surnames. If surnames are equal, we then compare names. If names are also equal, we proceed to compare the interests HashMap. The HashMap comparison logic involves:

1. Sorting the key-value pairs by keys to ensure consistent comparison order.
2. Iterating through the sorted key-value pairs of both HashMaps up to the length of the shorter HashMap.
3. Comparing keys and then values for each pair. If a difference is found, we return the corresponding Ordering.
4. If all compared pairs are equal, the HashMap with fewer entries is considered smaller.

This implementation ensures a deterministic and consistent ordering for User structs, even with the complexity of the interests HashMap. The use of then_with elegantly chains the comparison logic for surname and name before moving to the more complex HashMap comparison.

For testing, you can use BTreeSet to verify the ordering:

#[cfg(test)]
mod test {
    use super::*;
    use std::collections::BTreeSet;

    #[test]
    fn it_orders_with_surname_first() {
        let first_user = User::create(
            String::from("name1"),
            String::from("surname0"),
            HashMap::new(),
        );
        let second_user = User::create(
            String::from("name0"),
            String::from("surname1"),
            HashMap::new(),
        );
        let mut users = BTreeSet::new();
        users.insert(second_user);
        users.insert(first_user);
        let first = users.into_iter().next().unwrap();
        assert_eq!(first.surname, "surname0");
    }

    #[test]
    fn it_orders_with_same_surname_but_different_name() {
        let first_user = User::create(
            String::from("name0"),
            String::from("surname0"),
            HashMap::new(),
        );
        let second_user = User::create(
            String::from("name1"),
            String::from("surname0"),
            HashMap::new(),
        );
        let mut users = BTreeSet::new();
        users.insert(second_user);
        users.insert(first_user);
        let first = users.into_iter().next().unwrap();
        assert_eq!(first.name, "name0");
    }
}

By implementing Ord, PartialOrd, Eq, and PartialEq, you make your custom structs fully comparable in Rust, enabling their use in sorted collections and comparison operations, making your code more robust and versatile. Understanding these traits is fundamental to leveraging Rust’s powerful type system for effective data management.