はじめに

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

想定読者

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

本記事で行うこと

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

本記事で行わないこと

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

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

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

言語機能

整数 i64 (C++: long long)

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

#[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

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

#[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

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)

#[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 を使って比較する例を載せました。

標準ライブラリー

Vec (C++: vector)

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

基本

#[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;
    }
}

ソート、二分探索

#[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); // 一致かどうかを区別しない場合
}

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

Iterator (C++: iterator)

Iterator in std::iter - Rust

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

#[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 日本語版
String in std::string - Rust
。
競技プログラミングでは文字単位での操作が中心です。String 型より Vec<char> として扱うのが楽です。 proconio でできます。

#[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)

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

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)

map の値なし版。

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)

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

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

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

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 のように構造体を作成して比較演算子を定義するのが正攻法だと思います。ニュータイプパターン。でも時間制限優先で手を抜きたいところです。 ³

time (C++: chrono)

std::time - Rust

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

assert (C++: assert)

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

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

2020 Update · rust-lang-ja/atcoder-rust-resources Wiki より。

superslice (C++: lower_bound, next_permutation など)

superslice - Rust

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

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

同じように使えます。

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

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

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)

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

rand (C++: random)

rand - Rust

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

その他

2020 Update · rust-lang-ja/atcoder-rust-resources Wiki にはほかにもいろいろライブラリーが入っています。

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

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

その他のコードを使う

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

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

スニペット

Rustで競技プログラミングをするときの"スニペット管理"をまじめに考える(cargo-snippetの紹介) - Qiita

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

提出したコードを検索

hossy3/atcoder-solutions: AtCoder solutions (mainly ABC A-E) by rust

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

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

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

この記事を書きながら AtCoder Beginner Contest 259 - AtCoder に参加しました。ちょうど三角関数と BinaryHeap をはじめて使いました。

Result<T, T> から値を取り出す方法について、Tracking Issue for `Result::into_ok_or_err` / `feature(result_into_ok_or_err)` · Issue #82223 · rust-lang/rust で議論されています。最新の Rust では let (Ok(i) | Err(i)) = v.binary_search(&num); と書けます。ラムダ式よりは自然です。 ↩
C++ の stack, queue はコンテナーアダプターです。deque などのより高機能なコンテナーを内部に持ち、stack, queue として使用する機能だけを公開しています。 ↩
Since 1.15.1 · rust-lang-ja/atcoder-rust-resources Wiki Reverse の説明に、「BinaryHeapのようなデータ構造は(f(x), x) (ただしfが単射またはxが一意)のような要素にすることで自由にキーを設定できますが、Reverseのようなラッパーなら簡潔かつ効率的になります。」と書いていました。タプルの第一要素を使うことは不自然ではないようです。 ↩
付録C：導出可能なトレイト - The Rust Programming Language 日本語版に詳細が書かれています。分かりますが、けっこうはまりポイントです……。 ↩
AtCoder Problems を見ると投稿時点で 68問提出でした。「まだ使ったことがありませんのでリンクだけ貼っておきます。」を多用したあたりからも、全然足りないと思っています。 ↩