Как определяется порядок для кортежей в Rust? - PullRequest
Новая
       18

Как определяется порядок для кортежей в Rust?

4 голосов
/ 20 апреля 2020

Я просматривал документацию и нашел пример кода, который выглядел незнакомым.

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]);

Каким образом (num > 3, Reverse(num)) определить порядок между собой?

Я посмотрел документацию для кортеж , и там было сказано

Последовательный характер кортежа относится к его реализации различных черт. Например, в PartialOrd и Ord элементы сравниваются последовательно, пока не будет найден первый неравный набор.

Это имеет смысл для проверок на равенство, но мне кажется, что оно не дает объяснения как > и < действуют на кортежи.

Я провел несколько экспериментов, но ничего не понял. 

    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

Ответы [ 3 ]

4 голосов
/ 20 апреля 2020

Как вы указали в заметках, кортежи сравниваются лексикографически.

То есть, сравниваются первые элементы каждого кортежа, затем, если они равны, вторые элементы, то третий, и т. Д. c .. до тех пор, пока не будет найдена неравная пара и не упорядочен набор кортежей. Если все пары равны, то кортежи, очевидно, равны. 

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

5> 3, поэтому (5, _)> (3, _) 

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

2 <3, поэтому (2, _) <(3, _) </p> 

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

см. Выше 

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

3 == 3, 5> 4, поэтому (3, 5)> (3, 4) 

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

см. Первый случай

Как (num > 3, Reverse(num)) определяет порядок между собой?

booleans sort false < true, поэтому сначала он упорядочивает элементы в двух широких категориях (числа ниже 3, затем числа выше 3) затем в пределах каждой категории элементы упорядочены на основе их обратного естественного порядка (то есть, по величине сначала). Хотя это, очевидно, делает это за один проход.

3 голосов
/ 20 апреля 2020

Вы можете прочитать исходный код 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),+)
    }
}

И макрос lexical_ord : 

// 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) };
}

Так (a, b) > (c, d) будет вызывать (a, b).gt(&(c, d)), который будет использовать макрос lexical_ord, как это (см. Комментарий в коде): 

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

(На самом деле, это должно быть что-то вроде lexical_ord(gt, (a, b).0, (c, d).0, (a, b).1, (c, d).1), если я правильно читаю макрос, но я упростил его здесь.)

Что будет переведено (во время компиляции) в это: 

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

Итак, фактический код то, что будет вызвано для (a, b) > (c, d), будет: 

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
    }
}

Таким образом, он сравнивает значения в каждом кортеже попарно.

0 голосов
/ 20 апреля 2020

Это имеет смысл для проверок на равенство, но мне кажется, что оно не дает объяснения того, как > и < действуют на кортежи.

Это делает, рассмотрим примеры, которые вы привели: 

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

Возвращает результат < / > первого неравного элемента кортежа.

...