Rust 初心者の AtCoder でよく使う言語機能とライブラリー覚え書き

# はじめに
* [AtCoder 緑になったのでパズル好きな人に競プロを紹介してみる](https://qiita.com/hossie/items/a86d66d658a1d22111a7)
* [Rust 初心者の AtCoder 用開発環境設定と、解く流れの例](https://qiita.com/hossie/items/0f85f2054b875e9fb013)

色変記事の続きです。Rust 初心者が良く使う言語機能とライブラリーをまとめて、コードをコピーペーストできるようにしよう、という目的です。今回も比較用に C++ を書きます。

## 想定読者
* Rust で AtCoder に参加しようとしている
* Rust の経験がある、または Rust 以外の何かのプログラミング言語を使える

## 本記事で行うこと
* Rust 1.42 で競技プログラミングに参加するときによく使いそうな言語機能・標準ライブラリー
    * Rust 1.42 は AtCoder 2022年7月時点の実行環境
* [2020 Update · rust\-lang\-ja/atcoder\-rust\-resources Wiki](https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/2020-Update) で使える AtCoder 用ライブラリーのうち、よく使いそうなもの
* [レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa) で触れられている C++ 標準ライブラリーのうち、Rust で直接対応があるもの

## 本記事で行わないこと
* 競技プログラミングで使わないもの、ほかの方法で書けるもの
    * たとえば構造体は、タイムアタック内ではタプルでさっと書けば良いですから、扱いません
* 各コレクションの意味・使いどころの紹介
    * C++ set, map など他の言語にありますし、解説記事も多数あります
* Rust 1.43 以降の機能

# Rust のよく使う言語機能とライブラリー覚え書き

適宜こちらにリンクします:

* [The Rust Programming Language 日本語版](https://doc.rust-jp.rs/book-ja/)
* [Rust by Example 日本語版](https://doc.rust-jp.rs/rust-by-example-ja/)
* [The Rust Standard Library](https://doc.rust-lang.org/std/)


## 言語機能
### 整数 i64 (C++: long long)
* [データ型 \- The Rust Programming Language 日本語版](https://doc.rust-jp.rs/book-ja/ch03-02-data-types.html)
* [i64 \- Rust](https://doc.rust-lang.org/std/primitive.i64.html)

型指定しないと `i32` になります。競技プログラミングでは途中計算でオーバーフローしがちですので、基本 `i64` がおすすめです。以下の例は `i32` も混ざっています。

```rust
#[test]
fn test() {
    let i = 1i64; // 1i64 でも 1_i64 でもいい
    assert_eq!(i, 1);

    // 四則演算
    let j: i32 = 2;
    // assert_eq!(i + j, 3); // 異なる型同士は演算できない
    assert_eq!(i + j as i64, 3); // キャストすれば OK

    // 商・余り・切り上げ (両方正の場合)
    assert_eq!(19 / 4, 4);
    assert_eq!(19 % 4, 3);
    assert_eq!((19 + 4 - 1) / 4, 5);

    // 商・余り (負の場合)
    assert_eq!(-7 / 4, -1); // ゼロ方向への切り捨て (C++11 と同じ)
    assert_eq!(-7 % 4, -3);
    assert_eq!((-7i64).div_euclid(4), -2);
    assert_eq!((-7i64).rem_euclid(4), 1); // 余りを非負にする

    // べき乗
    assert_eq!(10_i64.pow(4), 10000);

    // min, max (C++: min, max)
    let i: i64 = 1;
    assert_eq!(i.max(2), 2);
    assert_eq!(i.min(2), 1);

    // abs (C++: abs)
    assert_eq!((-i).abs(), 1);

    // シフト演算
    assert_eq!(0b11 << 4, 0b110000);
    assert_eq!(0xff >> 1, 0x7f);

    // ビット演算 (C++: popcount)
    assert_eq!(0b10100000_i64.count_ones(), 2);

    let i64_max = ((1u64 << 63) - 1) as i64;
    assert_eq!(i64_max, 0x7fff_ffff_ffff_ffff);

    // 型の最大値
    // assert_eq!(i64::MAX, 0x7fff_ffff_ffff_ffff); // Rust 1.43 以降
}
```

複数の値の中で最大値を調べるときに、 `if i < j { i = j; }` の代わりに `i = i.max(j);` のようにも書けます。


### 整数 usize (C++: size_t)
* [usize \- Rust](https://doc.rust-lang.org/std/primitive.usize.html)

`i64` と同じく整数です。同じような計算ができます。CPU のアーキテクチャ依存 実行環境は 64bit ばかりですので、競技プログラミングの世界では 'u64' (C++: unsigned long long) のつもりで使えます。

```rust
#[test]
fn test() {
    let i = 1usize; // 1usize でも 1_usize でもいい
    assert_eq!(i, 1);
    
    // 配列に添字でアクセス
    let j = 0i64;
    let a = [10, 20, 30];
    assert_eq!(a[i], 20);
    // assert_eq!(a[j], 10); // 型が違うのでダメ
    assert_eq!(a[j as usize], 10);
}
```

### 実数 f64 (C++: double)
* [f64 \- Rust](https://doc.rust-lang.org/std/primitive.f64.html)

```rust
use std::f64::consts::PI;

#[test]
fn test() {
    let i = 1.0_f64;
    assert_eq!(i, 1.0);

    // ルート, べき乗
    assert_eq!(16.0_f64.sqrt(), 4.0);
    assert_eq!(16.0_f64.powi(2), 256.0);
    assert_eq!(16.0_f64.powf(0.25), 2.0);

    // min, max (C++: min, max)
    assert_eq!(i.max(2.0), 2.0);
    assert_eq!(i.min(2.0), 1.0);

    // abs (C++: abs)
    assert_eq!((-i).abs(), 1.0);

    // 三角関数 (計算誤差のため、比較を閾値付きで行う)
    assert!(((PI / 3.0).cos() - 0.5).abs() < 1e-6);
    assert!(((PI / 2.0).sin() - 1.0).abs() < 1e-6);
    assert!(((PI / 4.0).tan() - 1.0).abs() < 1e-6);
}
```

### タプル (C++: pair, tuple)
* [タプル \- Rust By Example 日本語版](https://doc.rust-jp.rs/rust-by-example-ja/primitives/tuples.html)
* [tuple \- Rust](https://doc.rust-lang.org/std/primitive.tuple.html)

```rust
#[test]
fn test() {
    // 代入 (複数の型の値を入れられる)
    let t = (0, '1', "t.2");
    assert_eq!(t.0, 0);
    assert_eq!(t.1, '1');
    assert_eq!(t.2, "t.2");

    // 分割代入
    let (a, b, c) = t;
    assert_eq!(a, 0);
    assert_eq!(b, '1');
    assert_eq!(c, "t.2");

    // 分割代入: 入力 x1, y1, x2, y2, ... をループで回す
    let a = vec![(1, 2), (3, 4), (5, 6)];
    for (x, y) in a {
        assert_eq!(x, 1);
        assert_eq!(y, 2);
        break;
    }

    // 入れ子
    let t = ((0, 1), (2, 3, 4));
    assert_eq!((t.1).2, 4);

    // デバッグ表示
    println!("{:?}", t);

    // 順序関係
    assert_eq((1, 2), (1, 2));
    assert!((1, 2) < (2, 1)); // 左の大小関係が優先
    assert!((1, 2) > (1, 1));
    // assert_ne!((1, 1), (1, 1, 1)); // 異なる型は比較できない
    // assert_ne!((1_i64), (1_u64)); // 異なる型は比較できない
}
```

`(x, y)` のようにセットで扱う値があるときに、構造体のように使えます。名前を付けなくて良く、比較演算子やデバッグ表示が標準で組み込まれています。汎用構造。

可読性を上げるなら構造体やタプル構造体を使うこともできます。でもコードが長くなります。 20行程度で解ける問題に対してはオーバースペックです。`BinaryHeap` に、標準ライブラリーの `Reverse` を使って比較する例を載せました。 

* [構造体を定義し、インスタンス化する \- The Rust Programming Language 日本語版](https://doc.rust-jp.rs/book-ja/ch05-01-defining-structs.html)
* [構造体 \- Rust By Example 日本語版](https://doc.rust-jp.rs/rust-by-example-ja/custom_types/structs.html)
* [高度な型 \- The Rust Programming Language 日本語版](https://doc.rust-jp.rs/book-ja/ch19-04-advanced-types.html)
* [Reverse in std::cmp \- Rust](https://doc.rust-lang.org/std/cmp/struct.Reverse.html)


## 標準ライブラリー

### Vec (C++: vector)

* [ベクタ型 \- Rust By Example 日本語版](https://doc.rust-jp.rs/rust-by-example-ja/std/vec.html)
* [Vec in std::vec \- Rust](https://doc.rust-lang.org/std/vec/struct.Vec.html)

使いたくなる操作がたくさんあります。その都度 API マニュアルを確認しています。

#### 基本
```rust
#[test]
fn test() {
    // 生成
    let v = vec![0, 1, 2];
    assert_eq!(v, [0, 1, 2]);

    let v = vec![(0, 1); 3];
    assert_eq!(v, [(0, 1), (0, 1), (0, 1)]); // タプルのベクトル

    let v = vec![vec![0, 1]; 3];
    assert_eq!(v, [[0, 1], [0, 1], [0, 1]]); // ベクトルのベクトル

    // アクセス
    let v = vec![0, 1, 2];
    assert_eq!(v[0], 0); // 0開始
    // assert_eq!(v[-1], 2); // 負数: コンパイルエラー
    // assert_eq!(v[3], 2); // 範囲外: panic!

    // 基本操作
    let mut v = vec![0, 1, 2];
    v.push(3); // 末尾に追加
    v.insert(0, -1); // 先頭などに追加 (とても遅い)
    assert_eq!(v, [-1, 0, 1, 2, 3]);
    assert_eq!(v[0], -1);

    // 入れ替え
    let mut v = vec![0, -1, -2, -3];
    v.swap(0, 2); // index 指定
    assert_eq!(v, [-2, -1, 0, -3]);
    
    // 反転
    let mut v = vec![3, 1, 4, 1, 6];
    v.reverse();
    assert_eq!(v, [6, 1, 4, 1, 3]);

    // 長さ
    let v = vec![0, 1, 2];
    assert_eq!(v.len(), 3);

    // 前の値と組にする (2つの値の差を取るときなど)
    let v = vec![0, 1, 2, 3];
    for x in v.windows(2) {
        assert_eq!(x, [0, 1]); // [[0, 1], [1, 2], [2, 3]]
        break;
    }
}
```

#### ソート、二分探索
```rust
#[test]
fn test() {
    // ソート 昇順 (C++: sort)
    let mut v = vec![1_i32, 2, 3, 2, 2, 3];
    v.sort();
    assert_eq!(v, [1, 2, 2, 2, 3, 3]);

    // ソート 特殊な順番
    let mut v: Vec<i64> = vec![-5, 4, 1, -3, 2];
    v.sort_by_key(|x| x.abs());
    assert_eq!(v, [1, 2, -3, 4, -5]);

    // ソート 実数
    let mut v = vec![2.0, 7.0, 1.0, 8.0];
    // v.sort(); // 実数は NaN があり全順序でないため、ソート不可
    v.sort_by(|a, b| a.partial_cmp(b).unwrap()); // NaN がないと明示する
    assert_eq!(v, [1.0, 2.0, 7.0, 8.0]);

    // 二分探索
    let v = vec![2, 4, 6, 6, 6];
    assert_eq!(v.binary_search(&2), Ok(0)); // 1つだけ一致
    assert_eq!(v.binary_search(&4), Ok(1));

    assert_eq!(v.binary_search(&1), Err(0)); // 一致しない
    assert_eq!(v.binary_search(&3), Err(1));
    assert_eq!(v.binary_search(&8), Err(5));

    assert!(match v.binary_search(&6) {
        Ok(2..=4) => true, // 2, 3, 4 いずれか
        _ => false,
    });

    let i = v.binary_search(&5).unwrap_or_else(|x| x);
    assert_eq!(i, 2); // 一致かどうかを区別しない場合
}
```


二分探索に癖があります。一致かどうかを区別しないときにひと工夫必要です [^1] 。

[^1]: `Result<T, T>` から値を取り出す方法について、[Tracking Issue for \`Result::into\_ok\_or\_err\` / \`feature\(result\_into\_ok\_or\_err\)\` · Issue \#82223 · rust\-lang/rust](https://github.com/rust-lang/rust/issues/82223) で議論されています。最新の Rust では `let (Ok(i) | Err(i)) = v.binary_search(&num);` と書けます。ラムダ式よりは自然です。

#### Iterator (C++: iterator)
* [Iterator in std::iter \- Rust](https://doc.rust-lang.org/std/iter/trait.Iterator.html)

コレクションの要素をたどって処理します。 `Vec` 以外でもできます。

```rust
#[test]
fn test() {
    // 合計
    let v = vec![0, 1, 2, 3];
    let sum: i64 = v.iter().sum();
    assert_eq!(sum, 6);

    // 数え上げ (C++: count)
    let v = vec![3, 1, 4, 1, 6];
    let count = v.iter().filter(|&&x| x == 1).count();
    assert_eq!(count, 2);
}
```    

### String (C++: string)

* [文字列 \- Rust By Example 日本語版](https://doc.rust-jp.rs/rust-by-example-ja/std/str.html)
* [String in std::string \- Rust](https://doc.rust-lang.org/std/string/struct.String.html)
。
競技プログラミングでは文字単位での操作が中心です。`String` 型より `Vec<char>` として扱うのが楽です。 proconio でできます。

```rust
#[test]
fn test() {
    // 文字操作
    let c = 'a' as char;
    assert_eq!(c, 'a');

    let c = (b'A' + 1) as char; // u8 型経由で計算
    assert_eq!(c, 'B');

    // 文字列操作
    let str = "abc"; // &str 型
    // let str = str + "def"; // &str 型のままでは操作できない。VS Code では下にする修正ヒントが出る
    let str = str.to_owned() + "def"; // String 型
    assert_eq!(str, "abcdef");
}
```

### HashMap, BTreeMap (C++: unordered_map, map)

* [ハッシュマップ \- Rust By Example 日本語版](https://doc.rust-jp.rs/rust-by-example-ja/std/hash.html?highlight=hashmap#%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%9E%E3%83%83%E3%83%97)
* [HashMap in std::collections::hash\_map \- Rust](https://doc.rust-lang.org/std/collections/hash_map/struct.HashMap.html)
* [BTreeMap in std::collections \- Rust](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html)

連想配列。`HashMap`, `BTreeMap` どちらも同じように使えます。速度優先ならハッシュ側、キーの順番が大事なら二分木 (Binary Tree) 側がより向いています。軽い計算の問題を解くときはどちらでも良いです。

```rust
use std::collections::BTreeMap;

#[test]
fn test() {
    // 生成
    let mut map = BTreeMap::<i64, &str>::new();
    map.insert(3, "Three");
    map.insert(1, "One");
    map.insert(4, "Four");
    // let m = BTreeMap::from([(3, "Three"), (1, "One"), (4, "Four")]); // Rust 1.56-
    // let m: BTreeMap<i64, _> = [(3, "Three"), (1, "One"), (4, "Four")].iter().cloned().collect();

    // 要素数
    assert_eq!(map.is_empty(), false);
    assert_eq!(map.len(), 3);

    // 存在チェック
    assert_eq!(map.contains_key(&3), true);
    assert_eq!(map.contains_key(&2), false);

    // アクセス
    assert_eq!(map[&3], "Three");
    // assert_eq!(m[&2], "Two"); // 存在しないキーを使うと panic!

    assert_eq!(map.get(&3), Some(&"Three"));
    assert_eq!(map.get(&2), None); // より安全

    // 書き換え
    // m[&3] = "three"; // コンパイルエラー
    map.insert(3, "three"); // 同じキーで新しい値を挿入する
    assert_eq!(map[&3], "three");
    
    if let Some(x) = map.get_mut(&3) {
        *x = "3"; // get_mut() で取れた値を書き換えることで map を更新
    }
    assert_eq!(map[&3], "3");

    // for
    for (n, s) in map {
        assert_eq!(n, 1); // BTreeMap の場合、[1, 3, 4] の順に取れる
        assert_eq!(s, "One");
        break;
    }

   // 数え上げ
    let mut map = BTreeMap::new();
    let ary = [3, 1, 4, 1, 6];
    for x in ary {
        *map.entry(x).or_insert(0) += 1; // C++: map[x] += 1 のようにキーなしでできる
    }
    assert_eq!(map[&1], 2);
}
```

### HashSet, BTreeSet (C++: unordered_set, set)

* [ハッシュ集合 \- Rust By Example 日本語版](https://doc.rust-jp.rs/rust-by-example-ja/std/hash/hashset.html)
* [HashSet in std::collections \- Rust](https://doc.rust-lang.org/std/collections/struct.HashSet.html)
* [BTreeSet in std::collections \- Rust](https://doc.rust-lang.org/std/collections/struct.BTreeSet.html)

map の値なし版。

```rust
use std::collections::HashSet;

#[test]
fn test() {
    // 作成
    let mut set = HashSet::<i64>::new();
    set.insert(3);
    set.insert(1);
    set.insert(4);
    // let m = HashSet::from([3, 1, 4]); // Rust 1.56-
    // let a: HashSet<i64> = [3, 1, 4].iter().cloned().collect();

    // 要素数
    assert_eq!(set.is_empty(), false);
    assert_eq!(set.len(), 3);

    set.insert(1); // 登録済みの値を入れても要素数は変わらない
    assert_eq!(set.len(), 3);

    // 存在チェック
    assert_eq!(set.contains(&3), true);
    assert_eq!(set.contains(&2), false);

    // for
    for x in set {
        assert!(match x {
            3 | 1 | 4 => true, // Hash では 3, 1, 4 が順不同で現れる
            _ => false,
        });
    }
    
    // 集合 (HashSet::from(): Rust 1.56-)
    let set2 = HashSet::from([2, 4, 6]);
    let set3 = HashSet::from([3, 6]);
    let union: HashSet<i64> = set2.union(&set3).cloned().collect();
    let intersection: HashSet<i64> = set2.intersection(&set3).cloned().collect();
    let difference: HashSet<i64> = set2.difference(&set3).cloned().collect();
    assert_eq!(union, HashSet::from([2, 3, 4, 6])); // 和集合
    assert_eq!(intersection, HashSet::from([6])); // 積集合
    assert_eq!(difference, HashSet::from([2, 4])); // 差集合
}
```

### スタック, キュー (C++: stack, queue)

* [std::collections \- Rust](https://doc.rust-lang.org/std/collections/)
* [Vec in std::vec \- Rust](https://doc.rust-lang.org/std/vec/struct.Vec.html)
* [VecDeque in std::collections \- Rust](https://doc.rust-lang.org/std/collections/struct.VecDeque.html)

LIFO 後入れ先出しのスタック、FIFO 先入れ先出しのキューはどちらも Rust 標準ライブラリーにありません。代わりに `Vec` (C++: vector) や `VecDeque` (C++: deque) を使います。多機能すぎて内側への直接アクセスなどスタック・キューでは行わないこともできてしまいますが、意識して使わないようにします。 [^2]

[^2]: C++ の stack, queue はコンテナーアダプターです。deque などのより高機能なコンテナーを内部に持ち、stack, queue として使用する機能だけを公開しています。

```rust
use std::collections::VecDeque;

#[test]
fn test() {
    // stack
    let mut stack = Vec::<i64>::new();
    stack.push(3);
    stack.push(1);
    stack.push(4);
    assert_eq!(stack.last(), Some(&4)); // Last-in First-out

    // 順に値を取り出す
    while let Some(x) = stack.pop() {
        assert_eq!(x, 4);
        break;
    }
    assert_eq!(stack.pop().unwrap(), 1);
    assert_eq!(stack.pop().unwrap(), 3);
    assert!(stack.is_empty());

    // queue
    let mut queue = VecDeque::<i64>::new();
    queue.push_back(3);
    queue.push_back(1);
    queue.push_back(4);
    assert_eq!(queue.front(), Some(&3)); // First-in First-out

    // 順に値を取り出す
    while let Some(x) = queue.pop_front() {
        assert_eq!(x, 3);
        break;
    }
    assert_eq!(queue.pop_front().unwrap(), 1);
    assert_eq!(queue.pop_front().unwrap(), 4);
    assert!(queue.is_empty());
}
```

### BinaryHeap (C++: priority_queue)

* [BinaryHeap in std::collections \- Rust](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html)

重み付きのキュー。ダイクストラ法などで使います。

```rust
use std::{collections::BinaryHeap, cmp::Reverse};

#[test]
fn test() {
    // binary heap
    let mut heap = BinaryHeap::<i64>::new();
    heap.push(3);
    heap.push(1);
    heap.push(4);
    heap.push(1);
    assert_eq!(heap.len(), 4);

    // 順に値を取り出す
    while let Some(x) = heap.pop() {
        assert_eq!(x, 4); // 一番大きな値
        break;
    }
    assert_eq!(heap.pop().unwrap(), 3);
    assert_eq!(heap.pop().unwrap(), 1);
    assert_eq!(heap.pop().unwrap(), 1); // Set と異なり、同じ値を入れられる
    assert!(heap.is_empty());

    // binary heap (逆順)
    let mut heap = BinaryHeap::new();
    heap.push(Reverse(3_i64));
    heap.push(Reverse(1));
    assert_eq!(heap.pop().unwrap().0, 1); // 小さな 1 が先
    assert_eq!(heap.pop().unwrap().0, 3);
    assert!(heap.is_empty());

    // binary heap (sort_by_key みたいなこと)
    let mut heap = BinaryHeap::new();
    heap.push((0, "foo"));
    heap.push((0, "bar"));
    heap.push((1, "baz"));
    assert_eq!(heap.pop().unwrap().1, "baz"); // タプル先頭要素が一番大きい
    assert_eq!(heap.pop().unwrap().1, "foo");
    assert_eq!(heap.pop().unwrap().1, "bar");
    assert!(heap.is_empty());
}
```

`sort_by_key` みたいなことをしようとすると、`Reverse` のように構造体を作成して比較演算子を定義するのが正攻法だと思います。ニュータイプパターン。でも時間制限優先で手を抜きたいところです。 [^3]

[^3]: [Since 1\.15\.1 · rust\-lang\-ja/atcoder\-rust\-resources Wiki](https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/Since-1.15.1#stdcmpreverse) `Reverse` の説明に、「`BinaryHeap`のようなデータ構造は`(f(x), x)` (ただし`f`が単射または`x`が一意)のような要素にすることで自由にキーを設定できますが、`Reverse`のようなラッパーなら簡潔かつ効率的になります。」と書いていました。タプルの第一要素を使うことは不自然ではないようです。

* [高度な型 \- The Rust Programming Language 日本語版](https://doc.rust-jp.rs/book-ja/ch19-04-advanced-types.html)
* [Reverse in std::cmp \- Rust](https://doc.rust-lang.org/std/cmp/struct.Reverse.html)

### time (C++: chrono)
* [std::time \- Rust](https://doc.rust-lang.org/std/time/index.html)

まだ使ったことがありませんのでリンクだけ貼っておきます。

### assert (C++: assert)
* [テストの記述法 \- The Rust Programming Language 日本語版](https://doc.rust-jp.rs/book-ja/ch11-01-writing-tests.html)
* [Testing \- Rust By Example 日本語版](https://doc.rust-jp.rs/rust-by-example-ja/testing.html)

本記事内ですでにたくさん使っています。省略します。

## 他の AtCoder で使えるライブラリー

[2020 Update · rust\-lang\-ja/atcoder\-rust\-resources Wiki](https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/2020-Update) より。

### superslice (C++: lower_bound, next_permutation など)
* [superslice \- Rust](https://docs.rs/superslice/1.0.0/superslice/)

スライスに便利なメソッドを追加します。Vec でも使えます。

```rust
use superslice::Ext;

#[test]
fn test() {
    // lower_bound, upper_bound (二分探索の先頭)
    let a = [1, 3, 3, 5]; // 昇順に並べておく
    assert_eq!(a.lower_bound(&2), 1); // 値が2以上の最初の位置。
    assert_eq!(a.lower_bound(&3), 1); // 値が3以上の最初の位置。binary_search と違い、場所が一意に決まる
    assert_eq!(a.lower_bound(&4), 3); // 値が4以上の最初の位置。

    assert_eq!(a.upper_bound(&4), 3); // 値が4より上の最後の位置。
    assert_eq!(a.upper_bound(&5), 4); // 値が5より上の最後の位置。4要素なら 4が現れうる。

    assert_eq!(a.lower_bound(&5) - a.lower_bound(&3), 2); // 3以上5未満の個数
    assert_eq!(a.upper_bound(&5) - a.lower_bound(&3), 3); // 3以上5以下の個数

    // next_permutation
    let mut a = [1, 2, 3];
    a.next_permutation();
    assert_eq!(a, [1, 3, 2]); // 次の順列
    a.next_permutation();
    assert_eq!(a, [2, 1, 3]); // 次の順列

    let mut a = [3, 1, 2, 4];
    let mut count = 1; // [3, 1, 2, 4] から [4, 3, 2, 1] までの個数を調べる
    while a.next_permutation() {
        count += 1;
    }
    assert_eq!(count, 2 * 3 * 2 * 1);
}
```

### permutohedron (C++: lower_bound など)
* [permutohedron \- Rust](https://docs.rs/permutohedron/0.2.4/permutohedron/)

同じように使えます。

```rust
use permutohedron::LexicalPermutation;

#[test]
fn test() {
    let mut a = [3, 1, 2, 4];
    let mut count = 1; // [3, 1, 2, 4] から [4, 3, 2, 1] までの個数を調べる
    while a.next_permutation() {
        count += 1;
    }
    assert_eq!(count, 2 * 3 * 2 * 1);
}
```


### petgraph (C++: UnionFind など)

* [petgraph \- Rust](https://docs.rs/petgraph/0.5.1/petgraph/#modules)

グラフアルゴリズムを広く提供します。ダイクストラ法など、このライブラリーに当てはめれば解けてしまうものもあります。ここでは同じ集合に属するかの高速判定 UnionFind だけ取り上げます。

```rust
use petgraph::unionfind::UnionFind;

#[test]
fn test() {
    // UnionFind 
    let mut uf = UnionFind::<usize>::new(8);
    uf.union(0, 2); // 集合 [0, 2]
    uf.union(2, 4); // 集合 [0, 2, 4]
    uf.union(5, 6); // 集合 [5, 6]
    uf.union(0, 6); // 集合 [0, 2, 4, 5, 6]

    uf.union(1, 3); // 集合 [1, 3]

    assert_eq!(uf.find(4), uf.find(6)); // [4, 6] は同じ集合に属する
    assert_ne!(uf.find(3), uf.find(4)); // [3, 4] は異なる集合に属する
}
```

### FixedBitSet, BitSet (C++: bitset)
* [fixedbitset::FixedBitSet \- Rust](https://docs.rs/fixedbitset/0.2.0/fixedbitset/struct.FixedBitSet.html)
* [bitset\_fixed::BitSet \- Rust](https://docs.rs/bitset-fixed/0.1.0/bitset_fixed/struct.BitSet.html)

まだ使ったことがありませんのでリンクだけ貼っておきます。集合演算したいときは前者、ビットシフト演算したいときは後者のようです。

### rand (C++: random)
* [rand \- Rust](https://docs.rs/rand/latest/rand/)

まだ使ったことがありませんのでリンクだけ貼っておきます。


### その他

[2020 Update · rust\-lang\-ja/atcoder\-rust\-resources Wiki](https://github.com/rust-lang-ja/atcoder-rust-resources/wiki/2020-Update) にはほかにもいろいろライブラリーが入っています。

* `Vec<f64>` を「実数は `NaN` があり全順序でないため、ソート不可」ではなく、ソートしたい [^4]
* 行列計算したい

などよくありそうな問題は、ライブラリーを探すと解決方法が見つかるかもしれません。

[^4]: [付録C：導出可能なトレイト \- The Rust Programming Language 日本語版](https://doc.rust-jp.rs/book-ja/appendix-03-derivable-traits.html) に詳細が書かれています。分かりますが、けっこうはまりポイントです……。

# その他のコードを使う

言語機能とライブラリーで行えれば良いですが、残念ながらそれでは不十分なことがあります。

たとえば Rust 標準ライブラリーには最大公約数 gcd (C++: gcd) がありません。ユークリッドの互除法を使って数行で書けるものだとしても、タイムロスになります。動作実績のあるコードを貼り付けたいです。

## スニペット

* [Rustで競技プログラミングをするときの"スニペット管理"をまじめに考える\(cargo\-snippetの紹介\) \- Qiita](https://qiita.com/hatoo@github/items/5c6814e72ddd2ecaf48f)

このように VSCode に設定してみました。gcd, lcm がサンプルとしてそのまま使えます。便利。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/118172/119eadd1-109d-49d3-2c66-b9b99888f024.png)

## 提出したコードを検索

* [hossy3/atcoder\-solutions: AtCoder solutions \(mainly ABC A\-E\) by rust](https://github.com/hossy3/atcoder-solutions/)

以前に自分が提出したコードを置いています。書いたことがあるものはコピーペーストできます。提出した問題数が増えるほど便利になっていきます。 [^5]

[^5]: [AtCoder Problems](https://kenkoooo.com/atcoder/#/user/hossie) を見ると投稿時点で 68問提出でした。「まだ使ったことがありませんのでリンクだけ貼っておきます。」を多用したあたりからも、全然足りないと思っています。

## Rust の記事から参考になるコードを探す

この記事がその一つになれば良いなと思います。

この記事を書きながら [AtCoder Beginner Contest 259 \- AtCoder](https://atcoder.jp/contests/abc259) に参加しました。ちょうど三角関数と `BinaryHeap` をはじめて使いました。