Linux Programming / お気楽 Rust プログラミング超入門

Rust の基礎知識

●ポインタの基本

Rust には *const T と *mut T という「ポインタ」がある
Rust では「生ポインタ (raw pointers)」と呼ばれている
Rust の参照 (&T, &mut T) には制約がある (借用チェッカー)
生ポインタの場合、*mut T はいくつでも作ることができ、*const T と混在させることもできる
ただし、生ポインタが指し示すデータの安全性は保証されていない
また、生ポインタ自身の値も正しいことは保証されていない

null ポインタかもしれないし、でたらめなメモリを指し示しているかもしれない
安全確認はプログラマの責任

このため、生ポインタをデリファレンスするときには unsafe が必要になる
なお、生ポインタからデータを move することはできないようだ

参照を生ポインタに型変換する操作は安全である

let x = 123; の生ポインタは let raw = &x as *const i32;
または let raw: *const i32 = &x;
let mut y = 456; の生ポインタは let raw_mut = &mut y as *mut i32;
または let raw_mut: *mut i32 = &mut y;

デリファレンスは * を使う (unsafe)

println!("{}", *raw); とか *raw_mut = 789; など

生ポインタを参照に変換することもできる (unsafe)

let ref_x = &*raw; とか let mut ref_y = &mut *raw_mut; など

リスト : ポインタの簡単な使用例

struct Foo {
    nums: i32
}

impl Drop for Foo {
    fn drop(&mut self) {
        println!("drop foo {}", self.nums);
    }
}

fn main() {
    let x = 123;
    let raw_x = &x as *const i32;
    let ref_x;
    println!("{:p}", raw_x);   // :p はポインタ (アドレス) を表示する
    unsafe {
        ref_x = &*raw_x;
        println!("{}", *raw_x);
    }
    println!("{}", ref_x);

    let mut y = 456;
    let raw_y = &y as *const i32;
    let raw_mut_y = &mut y as *mut i32;
    let raw_mut_y1 = &mut y as *mut i32;
    println!("{:p}", raw_y);
    println!("{:p}", raw_mut_y);
    println!("{:p}", raw_mut_y1);
    let ref_mut_y;                 // let mut ... とするとワーニング (mut は不要)
    unsafe {
        println!("{}", *raw_y);
        *raw_mut_y = 999;
        println!("{}", *raw_y);
        *raw_mut_y1 = 9999;
        println!("{}", *raw_y);
        ref_mut_y = &mut *raw_mut_y;
    }
    *ref_mut_y = 10000;
    println!("{}", y);

    let mut z = Foo { nums: 1000 };
    let raw_z = &z as *const Foo;
    let raw_mut_z = &mut z as *mut Foo;
    unsafe {
        println!("{}", (*raw_z).nums);
        // let a = *raw_z; raw pointer から move はできない
        // println!("{}", a.nums);
        *raw_mut_z = Foo { nums: 2000 };
        println!("{}", (*raw_z).nums);
    }
}

0x7fffc32f49d8
123
123
0x7fffc32f49dc
0x7fffc32f49dc
0x7fffc32f49dc
456
999
9999
10000
1000
drop foo 1000
2000
drop foo 2000

生ポインタはメソッド offset() で位置 (アドレス) を変更することができる

unsafe fn offset(self, cnt: isize) -> *const T
unsafe fn offset(self, cnt: isize) -> *mut T

cnt は要素の個数を表す (バイト数ではない, Ｃ言語のポインタと同じ)
Rust の場合、配列やベクタの要素は連続したメモリ領域に配置される
先頭要素の参照を生ポインタに型変換すると、それはメモリ領域の先頭アドレスを指し示す
offset() を使えば各要素にアクセスすることができる

リスト : offset() の簡単な使用例

fn main() {
    let a = [1, 2, 3, 4, 5, 6, 7, 8];
    let raw_a = &a[0] as *const i32;
    println!("{:p}", raw_a);
    unsafe {
        for i in 0 .. 8 {
            print!("{} ", *raw_a.offset(i));
        }
        println!("");
    }
    let mut b = vec![1, 2, 3, 4, 5, 6, 7, 8];
    let mut raw_b = &mut b[0] as *mut i32;
    println!("{:p}", raw_b);
    unsafe {
        for _ in 0 .. 8 {
            *raw_b *= 10;
            print!("{} ", *raw_b);
            raw_b = raw_b.offset(1)
        }
        println!("");
    }
}

0x7fffdc93fef8
1 2 3 4 5 6 7 8
0x7fffd43b4510
10 20 30 40 50 60 70 80

Box<T> などに格納されている要素の参照を生ポインタに変換することもできる
Box::into_raw(box) を使っても、生ポインタ *mut T を取得することができる
このとき、Box は消費 (破棄) されるので、ポインタが剥き出しの状態になる
メモリ領域の解法はプログラマの責任になる

関数 unsafe Box::from_raw(ptr) で生ポインタを Box に包み直す
関数 drop() でその Box を解放する
もしくは std::ptr::drop_in_place(ptr) を使う

リスト : Box と生ポインタの使用例

struct Foo {
    nums: i32
}

impl Drop for Foo {
    fn drop(&mut self) {
        println!("drop foo {}", self.nums);
    }
}

fn main() {
    let a = Box::new(Foo { nums: 123 });
    let raw_a = &*a as *const Foo;
    unsafe {
        println!("{}", (*raw_a).nums);
    }
    let mut b = Box::new(Foo { nums: 456 });
    let raw_mut_b = &mut *b as *mut Foo;
    unsafe {
        println!("{}", (*raw_mut_b).nums);
        *raw_mut_b = Foo { nums: 789 };
        println!("{}", (*raw_mut_b).nums);
    }
    let c = Box::new(Foo { nums: 1000 });
    let raw_mut_c = Box::into_raw(c);
    unsafe {
        println!("{}", (*raw_mut_c).nums);
        drop(Box::from_raw(raw_mut_c));
        // drop(raw_mut_c);  NG
        // std::ptr::drop_in_place(raw_mut_c);  OK
    }
}

123
456
drop foo 456
789
1000
drop foo 1000
drop foo 789
drop foo 123

このほかにもモジュール std::ptr には生ポインタ用の関数がいくつか用意されている

●マクロの基本

Rust のマクロは Scheme の「健全なマクロ (hygienic macro)」と同様の機能である
マクロは Rust のプログラムにコンパイルされ、それがソースコード中に展開される
それを再度コンパイルすることで実行ファイルを生成する
Rust のマクロは macro_rules! というマクロを使って記述する
マクロの記述には独自のパターン言語を使う

macro_rules! マクロ名 {
    (pattern1) => (template1);
    (pattern2) => (template2);
        ...,
    (patternN) => (templateN);
}

pattern はマクロの入力パターン (引数) を表す (Rust ではマッチャーと呼ぶようだ)
引数がパターンとマッチングする場合、それに対応するテンプレート template に変換する
パターンの基本は $名前:識別子で、$名前はパターン変数を表す
識別子はマッチさせるデータ型を表す

block, expr, ident, item, pat, path, stmt, tt, ty

マッチングしたデータはパターン変数に格納され、テンプレートで使用することができる

リスト : マクロの簡単な使用例 (1)

macro_rules! foo {
    ($a:expr) => (println!("{:?} = {:?}", stringify!($a), $a));
}

macro_rules! bar {
    () => (println!("[]"));
    ($a:expr) => (println!("{:?}", [$a]));
    ($a:expr, $b:expr) => (println!("{:?}", [$a, $b]));
    ($a:expr, $b:expr, $c:expr) => (println!("{:?}", [$a, $b, $c]));
}

fn main() {
    foo!(1 + 2);
    foo![11 * 12];
    foo!{100 - 200};
    // foo!(); コンパイルエラー
    bar!();
    bar!(1);
    bar!(1,2);
    bar!(1,2,3);
}

"1 + 2" = 3
"11 * 12" = 132
"100 - 200" = -100
[]
[1]
[1, 2]
[1, 2, 3]

expr は式を指定する識別子
foo! の引数 (式) はパターン変数 $a に格納される
stringify! は引数を文字列に変換するマクロ
foo! は println!() に展開され、そのあとコンパイルされる
マクロの呼び出しは () だけではなく、[] でも {} でもよい
パターン言語で使用する識別子や記号などを除いて、任意の文字列はそれ自身とマッチングする
たとえば、bar! のパターンはカンマで区切られているので、カンマとマッチングする
カンマ以外のトークンで区切ることもできるが、識別子によって次に受け付けるトークンにルールがある

たとえば expr の場合、, ; => のどれかひとつだけが許される

1 回以上の繰り返しは $(...),+ で、0 回以上の繰り返しは $(...),+ で表すことができる
カンマは区切り文字
繰り返しはパターンとテンプレートの両方で使用する
繰り返しを入れ子にすることもできる

リスト : マクロの簡単な使用例 (2)

macro_rules! sum {
    () => (0);
    ($($x:expr),+) => ({
        let mut acc = 0;
        $( acc += $x; )+
        acc
    });
}

fn main() {
    println!("{}", sum!());
    println!("{}", sum!(1));
    println!("{}", sum!(1, 2, 3, 4, 5));
}

0
1
15

このほかにも、再帰的なマクロや健全性などの話があるが、本稿では立ち入らない
最後に、マクロの簡単な例題として遅延評価のプログラムを示す
遅延評価の説明は拙作のページ遅延評価を参照

リスト : マクロの簡単な例題

use std::cell::RefCell;

// 遅延評価
struct Delay<'a, T: 'a> {
    value: RefCell<Option<T>>,
    func: Box<dyn Fn() -> T + 'a>
}

impl<'a, T: 'a> Delay<'a, T> {
    fn new<F: 'a>(f: F) -> Delay<'a, T> where F: Fn() -> T {
        Delay { func: Box::new(f), value: RefCell::new(None) }
    }
    fn force(&self) -> &T {
        let mut val = self.value.borrow_mut();
        if val.is_none() {
            *val = Some((self.func)());
        }
        match unsafe { self.value.as_ptr().as_ref().unwrap() } {
            &Some(ref x) => x,
            _ => unreachable!()
        }
    }
}

// Delay を生成するマクロ
// delay! を定義することで使いやすくなる
macro_rules! delay {
    ($e:expr) => (Delay::new(move || $e));
}

// たらいまわし関数
fn tarai(x: i32, y: i32, z: Delay<i32>) -> i32 {
    if x <= y {
        y
    } else {
        let zz = *z.force();
        tarai(tarai(x - 1, y, z),
              tarai(y - 1, zz, delay!(x)),
              delay!(tarai(zz - 1, x, delay!(y))))
    }
}

fn main() {
    let a = delay!({println!("oops"); 1 + 2});  // ブロックも式
    println!("{}", a.force()); 
    println!("{}", a.force());
    println!("{}", tarai(14, 7, delay!(0)));
    println!("{}", tarai(140, 70, delay!(0)));
}

oops
3
3
14
140

●ライフタイム境界

Rust は型パラメータの境界にライフタイムを指定することができる
Rust では「ライフタイム境界」と呼んでいるようだ

T: 'a
T 内の全ての参照は 'a よりも長生きでなくてはならない
T: Trait + 'a
1 に加えてTはTraitという名のトレイトを実装してなくてはならない

リスト : ライフタイム境界の簡単な例 (1)

struct Foo<'a, T: 'a> {
    value: &'a T
}

impl<'a, T> Foo<'a, T> {
    fn new(val: &'a T) -> Foo<'a, T> {
        Foo { value: val }
    }
}

fn main() {
    let x = 10;
    let a = Foo::new(&x);
    println!("{}", a.value);

    //let b: Foo<i32>;
    //{
    //    let y = 20;  コンパイルエラー `y` does not live long enough
    //    b = Foo::new(&y);
    //}
}

構造体 Foo のフィールド value は参照を格納するのでライフタイムパラメータ 'a の指定が必要
value の参照先 (T の値) が Foo よりも先に解放されてはいけない
つまり、T の参照 (&T) のライフタイムは Foo よりも短くなることはない
この条件を T の境界にライフタイムパラメータ 'a を指定することで表す
Foo にライフタイムパラメータが必要なので、impl でもライフタイムパラメータを指定する
変数 b は変数 y よりもライフタイムが長い
したがって、y の参照を格納した Foo を変数 b にセットすることはできない (コンパイルエラー)

リスト : ライフタイム境界の簡単な例 (2)

use std::cell::RefCell;

// 遅延評価
struct Delay<'a, T: 'a> {
    value: RefCell<Option<T>>,
    func: Box<dyn Fn() -> T + 'a>
}

impl<'a, T: 'a> Delay<'a, T> {
    fn new<F: 'a>(f: F) -> Delay<'a, T> where F: Fn() -> T {
        Delay { func: Box::new(f), value: RefCell::new(None) }
    }
    fn force(&self) -> &T {
        let mut val = self.value.borrow_mut();
        if val.is_none() {
            *val = Some((self.func)());
        }
        match unsafe { self.value.as_ptr().as_ref().unwrap() } {
            &Some(ref x) => x,
            _ => unreachable!()
        }
    }
}

Delay のメソッド new() はクロージャ F を Box に包んで func にセットする
F は Delay よりも先に解放されてはいけない
F のライフタイムが Delay より短くないことを表すため、Delay にライフタイムパラメータ 'a を指定する
そして、メソッド new() の型パラメータ F の境界に 'a を指定する
なお、Delay<'a, T: 'a> とするだけではコンパイルエラー (parameter `'a` is never used) になる
クロージャの型を Fn() -> T + 'a とするとコンパイルが通る

●Copy と Clone

構造体に Copy トレイトを実装すると、他の変数 (引数) に代入するとき値がコピーされる
このとき「所有権」は移動しない
実際には、Clone トレイトのメソッド clone() でコピーが行われる
したがって、Copy だけではなく Clone トレイトの実装も必要になる
Copy, Clone トレイトは derive を使うと簡単に実装できる

リスト : Copy と Clone トレイト

#[derive(Debug)]
struct Foo {
    num: i32
}

#[derive(Debug, Copy, Clone)]
struct Bar {
    num: i32
}

#[derive(Debug, Copy, Clone)]
struct Baz<T> {
    item: T
}

fn main() {
    let a = Foo { num: 123 };
    let mut b = a;            // 所有権の移動
    b.num += 1000;
    // println!("{:?}", a);      コンパイルエラー
    println!("{:?}", b);
    let c = Bar { num: 456 };
    let mut d = c;            // コピー
    d.num += 1000; 
    println!("{:?}", c);      // 所有権は移動しないのでアクセスできる
    println!("{:?}", d);

    let e = Baz { item: Foo { num: 123 } };
    let f = e;      // 所有権の移動
    // println!("{:?}", e);   コンパイルエラー
    println!("{:?}", f);
    println!("{}", f.item.num);

    let g = Baz { item: Bar { num: 456 } };
    let h = g;      // コピー
    println!("{:?}", g);
    println!("{:?}", h);
}

Foo { num: 1123 }
Bar { num: 456 }
Bar { num: 1456 }
Baz { item: Foo { num: 123 } }
123
Baz { item: Bar { num: 456 } }
Baz { item: Bar { num: 456 } }

derive はトレイトの実装に必ず成功するわけではない
Baz<T> の場合、型 T に Copy トレイトが実装されていないと、値はコピーされずに所有権が移動することになる
必ずコピーしたい場合は、型パラメータ T の境界に Copy を指定するとよい
T に Copy が実装されていないとコンパイルエラー

●トランスミュート (transmute)

関数 std::mem::taransumute() は unsafe な型変換を行う

pub unsafe extern "rust-intrinsic" fn transmute<T, U>(e: T) -> U

引数 e (型 T) を型 U に変換する
双方の型がサイズとメモリ上への配置の仕方において同じであること
整数と浮動小数点数の変換もできるが、値ではなくビットパターンでの変換になる
サイズが合わないとコンパイルエラー

リスト : transmute() の簡単な使用例

use std::mem::transmute;

fn main() {
    unsafe {
        // transmute() はビットパターンでの変換になる
        println!("{:X}", transmute::<f64, u64>(1.2345));
        println!("{:X}", transmute::<f32, u32>(1.2345));

        // u8 の配列を数値に変換するときはエンディアンに注意
        let a: [u8; 4] = [0x19, 0x04, 0x9e, 0x3f];
        println!("{:X}", transmute::<[u8; 4], u32>(a));
        println!("{}", transmute::<[u8; 4], f32>(a));
        println!("{:?}", transmute::<i32, [u8; 4]>(0x12345678));
    }
}

3FF3C083126E978D
3F9E0419
3F9E0419
1.2345
[120, 86, 52, 18]

transmute() はライフタイムも変換することができるようだ
詳細は Function std::mem::transmute を参照

●Hash

構造体を HashMap (HashSet) のキーとして使用する場合は Hash トレイトを実装する
Hash トレイトは derive を使うと簡単に実装できる
実際には PartialEq と Eq の実装も必要になる
Rust の場合、ハッシュ値の計算は Hasher トレイトを実装したオブジェクトで行う
Hash のメソッド hash() は Hasher にデータを渡すだけ

fn hash<H>(&self, state: &mut H) where H: Hasher,

hash() を何度も呼び出すことで複数のデータを渡すこともできる
Hasher のメソッド finish() でハッシュ値を求める (返り値は u64)
std::collections::hash_map::DefaultHasher にデフォルトの Hasher が用意されている

リスト : トレイト Hash の簡単な使用例

use std::collections::HashSet;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

#[derive(Hash, PartialEq, Eq)]
struct Foo {
    num: i32
}

fn main() {
    let mut h: HashSet<Foo> = HashSet::new();
    for i in 0 .. 10 {
        h.insert(Foo { num: i });
    }
    println!("{}", h.contains(&Foo { num: 0 }));
    println!("{}", h.contains(&Foo { num: 9 }));
    println!("{}", h.contains(&Foo { num: 10 }));

    for i in 0 .. 10 {
        let mut hasher: DefaultHasher = DefaultHasher::new();
        let a = Foo { num: i };
        a.hash(&mut hasher);
        println!("{}", hasher.finish());
    }
}

true
true
false
14709398186846620400
1742378985846435984
16336925911988107921
568126464209439262
15565210526001683492
14828406784900857967
2748490571820495779
13916993215237271530
17499417595158719687
16856616568243533183

●Default

Default はデータ型のデフォルト値を規定するトレイト

pub trait Default {
    fn default() -> Self;
}

Default::default() でデータ型のデフォルト値を取得することができる
Default トレイトは derive で簡単に実装できる
この場合、Rust で標準的なデフォルト値になる
独自のデフォルト値を指定したい場合はメソッド default() を実装する

リスト : Default トレイトの簡単な使用例

#[derive(Debug, Default)]
struct Foo {
    x: i32,
    y: f64
}

#[derive(Debug)]
struct Bar {
    x: i32,
    y: f64
}

impl Default for Bar {
    fn default() -> Bar {
        Bar { x: 12345, y: 1.2345}
    }
}

fn main() {
    let a: i32 = Default::default();
    let b: f64 = Default::default();
    let c: Foo = Default::default();
    let d: Bar = Default::default();
    println!("{}", a);
    println!("{}", b);
    println!("{}", c.x);
    println!("{}", c.y);
    println!("{}", d.x);
    println!("{}", d.y);
}

●UnsafeCell<T>

UnsafeCell<T> は Cell<T> や RefCell<T> と同様のデータ構造だが、生ポインタを使ってデータを操作するところが異なる
UnsafeCell の生成はメソッド new() で行う

fn new(value: T) -> UnsafeCell<T>

生ポインタの取得はメソッド get() を使う

fn get(&self) -> *mut T

データを取り出す (move する) ときはメソッド into_inner() を使う

unsafe fn into_inner(self) -> T

リスト : UnsafeCell の簡単な使用例

use std::cell::UnsafeCell;

#[derive(Debug)]
struct Foo {
    x: i32, y: i32
}

fn main() {
    let a = UnsafeCell::new(123);
    let p = a.get();
    unsafe {
        println!("{}", *p);
        *p = 456;
        println!("{}", *p);
    }

    let b = UnsafeCell::new(Foo { x: 10, y: 20 });
    let q = b.get();
    unsafe {
        println!("{}", (*q).x);
        println!("{}", (*q).y);
        (*q).x = 123;
        (*q).y = 456;
        println!("{}", (*q).x);
        println!("{}", (*q).y);
        let b1 = b.into_inner();
        println!("{:?}", b1);
    }

    let c = UnsafeCell::new(Box::new(Foo { x: 10, y: 20 }));
    let r = c.get();
    unsafe {
        println!("{}", (*r).x);
        println!("{}", (*r).y);
        (*r).x = 123;
        (*r).y = 456;
        println!("{}", (*r).x);
        println!("{}", (*r).y);
        let c1 = c.into_inner();
        println!("{:?}", c1);
    }
}

123
456
10
20
123
456
Foo { x: 123, y: 456 }
10
20
123
456
Foo { x: 123, y: 456 }

●Ref<T> と RefMut<T>

RefCell<T> のメソッド borrow() は Ref<T> を返す
メソッド borrow_mut() は RefMut<T> を返す
Ref と RefMut にはメソッド Ref::map(), RefMut::map() が用意されている

fn map<U, F>(orig: Ref<'b, T>, f: F) -> Ref<'b, U> 
where
    F: FnOnce(&T) -> &U,
    U: ?Sized,

fn map<U, F>(orig: RefMut<'b, T>, f: F) -> RefMut<'b, U> 
where
    F: FnOnce(&mut T) -> &mut U,
    U: ?Sized,

map() は RefCell に格納されているデータ構造 (構造体やタプルなど) の要素の参照を取得するのに便利
このほかに、Ref にはメソッド Ref::clone() がある (RefMut にはない)

fn clone(orig: &Ref<'b, T>) -> Ref<'b, T>

リスト : Ref と RefMut の簡単な使用例

use std::cell::{RefCell, Ref, RefMut};

#[derive(Debug)]
struct Foo {
    x: i32, y: f64
}

fn main() {
    let a = RefCell::new(Foo { x: 100, y: 1.2345 });
    {
        let p = Ref::map(a.borrow(), |foo| &foo.x);
        let q = Ref::clone(&p);
        println!("{}", *p);
        println!("{}", *q);
    }
    {
        let mut r = RefMut::map(a.borrow_mut(), |foo| &mut foo.y);
        *r *= 10.0;
    }
    println!("{:?}", a); 
}

100
100
RefCell { value: Foo { x: 100, y: 12.344999999999999 } }

●BinaryHeap<T>

BinaryHeap<T> は「二分ヒープ (binary heap)」を使ったプライオリティキュー
データ型 T はトレイト Ord を実装していること
BinaryHeap<T> は大きな値ほど優先順位が高い
これを「最大ヒープ (max heap)」という
逆に、小さな値ほど優先順位が高いヒープを「最小ヒープ (min heap)」という
自分で Ord を定義することで最小ヒープを実現することができる
主なメソッド

fn new() -> BinaryHeap<T>, BinaryHeap の生成
fn peek(&self) -> Option<&T>, 最大要素の参照を取得
fn pop(&mut self) -> Option<T>, 最大要素の取得
fn push(&mut self, item: T), 要素の追加
fn len(&self) -> usize, 要素数を返す
fn is_empty(&self) -> bool, ヒープが空ならば true を返す
fn clear(&mut self), ヒープを空にする

リスト : BinaryHeap の簡単な使用例

use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq)]
struct Foo {
    num: i32
}

impl Ord for Foo {
    fn cmp(&self, other: &Foo) -> Ordering {
        self.num.cmp(&other.num).reverse()
    }
}

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

fn main() {
    let a = [5,6,4,3,7,8,2,1,9];
    let mut q1 = BinaryHeap::new();
    let mut q2 = BinaryHeap::new();
    for x in &a {
        q1.push(*x);
        q2.push( Foo { num: *x });
    }
    while !q1.is_empty() {
        println!("{:?}", q1.pop());
    }
    while !q2.is_empty() {
        println!("{:?}", q2.pop());
    }
}

Some(9)
Some(8)
Some(7)
Some(6)
Some(5)
Some(4)
Some(3)
Some(2)
Some(1)
Some(Foo { num: 1 })
Some(Foo { num: 2 })
Some(Foo { num: 3 })
Some(Foo { num: 4 })
Some(Foo { num: 5 })
Some(Foo { num: 6 })
Some(Foo { num: 7 })
Some(Foo { num: 8 })
Some(Foo { num: 9 })

Ord を定義するときは PartialOrd の定義も必要になる
PartialOrd を定義するときは Eq の定義も必要になる
Eq を定義するときは PartialEq の定義も必要になる
けっきょく、Ord, PartialOrd, Eq, PartialEq の 4 つを定義しないとダメ
等値関係が標準のままでよければ、Eq と PartialEq は derive で OK
Ord で必要なメソッドは cmp() だけ

fn cmp(&self, other: &Self) -> Ordering

std::cmp::Ordering は次のように定義されている

pub enum Ordering { Less, Equal, Greater }

メソッド reverse() は Less を Greater に、Greater を Less に変換する
Foo の場合、フィールド変数 num (整数値) を cmp() で比較し、結果を reverse() で変換すれば最小ヒープになる
PartialOrd で必要なメソッドは partial_cmp() だけ

fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>

partial_cmp() は Ord のメソッド cmp() の返り値を Some() に包んで返すだけ

初版 2017 年 9 - 12 月
改訂 2022 年 7 月 30 日