How is ordering defined for tuples in Rust?

Question

I was looking at the documentation and found an example code that looked unfamiliar.

std::cmp::Reverse - Rust

use std::cmp::Reverse;

let mut v = vec![1, 2, 3, 4, 5, 6];
v.sort_by_key(|&num| (num > 3, Reverse(num)));
assert_eq!(v, vec![3, 2, 1, 6, 5, 4]);

How does (num > 3, Reverse(num)) define ordering between themselves?

I had a look into documentation for tuple, and it said

The sequential nature of the tuple applies to its implementations of various traits. For example, in PartialOrd and Ord, the elements are compared sequentially until the first non-equal set is found.

That makes sense for equality checks, but it seems to me that it does not give explanation for how > and < acts on tuples.

I did some experiments, but understood nothing.

    println!("{}", (5, 5) > (3, 4)); // true
    println!("{}", (2, 2) > (3, 4)); // false
    println!("{}", (2, 5) > (3, 4)); // false
    println!("{}", (3, 5) > (3, 4)); // true
    println!("{}", (5, 2) > (3, 4)); // true

Aphonic

Answer 1

As what you quoted notes, tuples are compared lexicographically.

That is, the first elements of each tuple are compared, then if they're equal the second elements are, then the third, etc.. until a non-equal pair is found and provides the ordering of the tuples. If all pairs are equal then the tuples are, obviously, equal.

println!("{}", (5, 5) > (3, 4)); // true

5 > 3, therefore (5, _) > (3, _)

println!("{}", (2, 2) > (3, 4)); // false

2 < 3, therefore (2, _) < (3, _)

println!("{}", (2, 5) > (3, 4)); // false

see above

println!("{}", (3, 5) > (3, 4)); // true

3 == 3, 5 > 4, therefore (3, 5) > (3, 4)

println!("{}", (5, 2) > (3, 4)); // true

see first case

How does (num > 3, Reverse(num)) define ordering between themselves?

booleans sort false < true, therefore it first orders the elements in two broad categories (numbers below 3 then numbers above 3) then within each category items are ordered based on their reverse natural order (that is, largest-first). Though it obviously does that in a single pass.

Bottali

Answer 2

You can read the source code of tuple:

impl<$($T:PartialOrd + PartialEq),+> PartialOrd for ($($T,)+)
    where last_type!($($T,)+): ?Sized {
    #[inline]
    fn partial_cmp(&self, other: &($($T,)+)) -> Option<Ordering> {
        lexical_partial_cmp!($(self.$idx, other.$idx),+)
    }
    // ...
    #[inline]
    fn gt(&self, other: &($($T,)+)) -> bool {
        lexical_ord!(gt, $(self.$idx, other.$idx),+)
    }
}

And the lexical_ord macro:

// Constructs an expression that performs a lexical ordering using method $rel.
// The values are interleaved, so the macro invocation for
// `(a1, a2, a3) < (b1, b2, b3)` would be `lexical_ord!(lt, a1, b1, a2, b2,
// a3, b3)` (and similarly for `lexical_cmp`)
macro_rules! lexical_ord {
    ($rel: ident, $a:expr, $b:expr, $($rest_a:expr, $rest_b:expr),+) => {
        if $a != $b { lexical_ord!($rel, $a, $b) }
        else { lexical_ord!($rel, $($rest_a, $rest_b),+) }
    };
    ($rel: ident, $a:expr, $b:expr) => { ($a) . $rel (& $b) };
}

So (a, b) > (c, d) will call (a, b).gt(&(c, d)), which will use the lexical_ord macro like this (see comment in the code):

lexical_ord(gt, a, c, b, d)

(Actually, it should be something like lexical_ord(gt, (a, b).0, (c, d).0, (a, b).1, (c, d).1), if I'm reading the macro correctly, but I've simplified it here.)

Which will be translated (at compile-time) to this:

if a != c {
    (a).gt(&c)
} else {
    (b).gt(&d)
}

So the actual code that will be called for (a, b) > (c, d) will be:

fn gt(&self, other: &($T, $T)) -> bool {
    if self.0 != other.0 {
        (self.0).gt(&other.0)  // self.0 > other.0
    } else {
        (self.1).gt(&other.1)  // self.1 > other.1
    }
}

So it's comparing the values in each tuple one-by-one in pairs.

Allain

Answer 3

That makes sense for equality checks, but it seems to me that it does not give explanation for how > and < acts on tuples.

It does, consider the examples you gave:

println!("{}", (5, 5) > (3, 4)); // 5 > 3 is true
println!("{}", (2, 2) > (3, 4)); // 2 > 3 is false
println!("{}", (2, 5) > (3, 4)); // 2 > 3 is false
println!("{}", (3, 5) > (3, 4)); // 3 == 3, then: 5 > 4 is true
println!("{}", (5, 2) > (3, 4)); // 5 > 3 is true

It returns the result of </> of the first non-equal element of the tuple.

Highflown