CODEWITHSUNDEEP
rusttuples
vbstb
vbstb

Reputation: 1451

How is ordering defined for tuples in Rust?

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

Upvotes: 15

Views: 7757

Answers (3)

Masklinn
Masklinn

Reputation: 42492

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 3 or below 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.

Upvotes: 19

ForceBru
ForceBru

Reputation: 44888

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.

Upvotes: 3

Acorn
Acorn

Reputation: 26166

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.

Upvotes: 1

Related Questions