はじめに
競技プログラミングにおいてPythonでよく使用する関数やクラスについて、それらとRustのメソッドやデータ構造との対応をまとめました。
競技プログラミングでPythonからRustへ移行しようとしている人の参考になれば幸いです。
なお、本記事のRustのバージョンは1.15.1を想定しています(2019/09/07時点でのAtCoderのRustのバージョン)。
標準入出力
標準入力
Rustでは std::io::Stdin のread_lineメソッドを用いて標準入力を1行単位で受け取ることができます（これはPythonのinput関数と同じですね）。
標準入力のパターンに応じて、受け取った文字列をsplitしたりparseしたりします。
Pythonと比べて、全体にしんどいのでスニペット／テンプレート化しておくとよいでしょう。
なお、高速に標準入力したい場合、StdinLock構造体を使うとよいようです。
参考: Rust の標準入出力は(何も考えないで使うと)遅い - Qiita
ideoneでの実行結果
単一の整数を標準入力する
例: 標準入力から単一の整数を受け取り、 n に束縛する。
n = int(input())
let n: i64 = {
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
line.trim().parse().unwrap()
};
単一の文字列を標準入力する
例: 標準入力から単一の文字列を受け取り、 s に束縛する。
s = input()
let s: Vec<char> = {
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
line.trim().chars().collect()
};
Rustでは、文字のVecとして s に文字列を束縛しています（イテレートする際に便利なので）。
定数個の整数を標準入力する
例: 標準入力から空白区切りで3個の整数を受け取り、 それぞれ a, b, c に束縛する。
a, b, c = map(int, input().split())
let (a, b, c): (i64, i64, i64) = {
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
let mut iter = line.split_whitespace();
(
iter.next().unwrap().parse().unwrap(),
iter.next().unwrap().parse().unwrap(),
iter.next().unwrap().parse().unwrap()
)
};
整数の個数が3でない場合、Rustコードの右辺の iter.next().unwrap().parse().unwrap() の個数を整数の個数に合わせる必要があります。
可変個の整数（空白区切り）を標準入力する
例: 標準入力から空白区切りの整数のリストを受け取り、 xs に束縛する。
xs = list(map(int, input().split()))
let xs: Vec<i64> = {
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
line.split_whitespace()
.map(|x| x.parse().unwrap())
.collect()
};
n個の整数（改行区切り）を標準入力する
例: 標準入力から改行区切りの n 個の整数のリストを受け取り、 ys に束縛する。
ys = [int(input()) for _ in range(n)]
let ys: Vec<i64> = (0..n)
.map(|_| {
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
line.trim().parse().unwrap()
})
.collect();
n行の定数個の整数を標準入力する
例: 標準入力からn行の整数ペアを受け取り、 pairs に（タプルのリストとして）束縛する。
pairs = [tuple(map(int, input().split())) for _ in range(n)]
let pairs: Vec<(i64, i64)> = (0..n)
.map(|_| {
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
let mut iter = line.split_whitespace();
(
iter.next().unwrap().parse().unwrap(),
iter.next().unwrap().parse().unwrap()
)
})
.collect();
整数の個数が2でない場合、Rustコードの右辺の iter.next().unwrap().parse().unwrap() の個数を整数の個数に合わせる必要があります。
整数の二次元リストを標準入力する
例: 標準入力から二次元整数リストを受け取り、 mat に（リストのリストとして）束縛する。
mat = [list(map(int, input().split())) for _ in range(n)]
let mat: Vec<Vec<i64>> = (0..n)
.map(|_| {
let mut line: String = String::new();
std::io::stdin().read_line(&mut line).unwrap();
line.split_whitespace()
.map(|x| x.parse().unwrap())
.collect()
})
.collect();
Python, Rust ともにi行目j列目の要素には mat[i][j] でアクセスできます。
標準出力
Rustではprintlnマクロを用いて標準出力します。
ideoneでの実行結果
単一の整数／文字列を標準出力する
例1: 整数 x を標準出力する（末尾に改行文字を含む）。
print(x)
println!("{}", x);
例2: 文字列 s を標準出力する（末尾に改行文字を含む）。
print(s)
println!("{}", s);
Rustの s は String または &str 型とします。
整数の場合と同一の文です。
文字リストを連結して標準出力する
例: 文字リスト char_list の各文字を連結した文字列を標準出力する（末尾に改行文字を含む）。
print(''.join(char_list))
println!("{}", char_list.iter().collect::<String>());
Rustの char_list は Vec<char> 型とします。
定数個の整数／文字列を標準出力する
例: 整数 x, y, z を空白区切りで標準出力する（末尾に改行文字を含む）。
print(x, y, z)
println!("{} {} {}", x, y, z);
println! の文字列フォーマットを利用します。 文字列を標準出力する場合も同様です。
n個の整数／文字列を空白区切りで標準出力する
例: 整数のリスト xs を空白区切りで標準出力する（末尾に改行文字を含む）。
print(*xs)
println!(
"{}",
xs.iter()
.map(std::string::ToString::to_string)
.collect::<Vec<_>>()
.join(" ")
);
.map(std::string::ToString::to_string) は .map(|&x| x.to_string()) でも構いません。
xs の要素が文字列ならば .map(std::string::ToString::to_string) は不要です。
n個の整数／文字列を改行白区切りで標準出力する
例: 整数のリスト xs を改行区切りで標準出力する（最終行末尾に改行文字を含む）。
print('\n'.join(map(str, xs)))
println!(
"{}",
xs.iter()
.map(std::string::ToString::to_string)
.collect::<Vec<_>>()
.join("\n")
);
forループで println! をn回呼んでもよいでしょう（ただし、nが大きい場合、実行時間はおよそ10倍になります。この差はPyPyと比べて顕著なので注意してください）。
データ構造
list
Rustではstd::vec::Vecをlistして使う方法を紹介します。
ideoneでの実行結果
listを生成する
例1: 3, 3, 4を要素とするlist a を生成する。
a = [3, 3, 4]
let mut a = vec![3, 3, 4];
a に対して破壊的操作を行わない場合、 mut は不要です。
例2: 0以上10以下の偶数を2乗したlist b を生成する。
b = [i**2 for i in range(10 + 1) if i % 2 == 0]
let mut b: Vec<_> = (0..(10_i64 + 1))
.filter(|&i| i % 2 == 0)
.map(|i| i.pow(2))
.collect();
残念ながらRustではリストの内包表記は使えません（サードパーティの cute を使うとリストの内包表記のような記法でvecを作成できるようですが）。
例3: 空のlist c を作成する。
c = []
let mut empty_list = vec![];
listの要素数を求める
例: list a の要素数を cardinality に束縛する。
cardinality = len(a)
let cardinality = a.len();
listのi番目の要素を求める
例: list a の2番目(0-indexed)の要素を second_element に束縛する。
second_element = a[2]
let second_element = a[2];
listをイテレートする
例: list a の要素を先頭から順に1行ずつ標準出力する。
for x in a:
print(x)
for &x in &a {
println!("{}", x);
}
Rustのコードの a は Vec<i64> 型とします。
Rust で for x in a と書いた場合、所有権が移動してしまい、以降 a を参照できないので注意してください。
また、 for x in &a と書いた場合、 x には a の要素への参照が束縛されることに注意してください（a の要素がプリミティブでないならば、参照を束縛させることになります）。
listに含まれる指定した要素の個数を求める
例: list a に含まれる3の個数を num_of_three に束縛する。
num_of_three = a.count(3)
let num_of_three = a.iter()
.filter(|&&x| x == 3)
.count();
Rustだと少々面倒です。
とはいえ、指定した述語にマッチする要素の個数を求める場合はPythonでも同様のコードになるので、そこまで気にならないと思います。
listのi番目の要素を更新する
例: list a の2番目の要素を3に更新する。
a[2] = 3
a[2] = 3;
Rust では a は mut 修飾子付きで宣言されている必要があることに注意です。
listの末尾に要素を追加する
例: list c に 42 を追加する。
c.append(42)
c.push(42);
listの末尾要素を削除する
例: list b の末尾の要素を削除し、削除した要素を tail に束縛する。
tail = b.pop()
let tail = b.pop().unwrap();
Rust では unwrap する必要があることに注意です（他のデータ構造も同様）。
dict
Rustではstd::collections::HashMapを使います。
ideoneでの実行結果
dictを生成する
例1: 空のdict scovilles を生成する。
scovilles = {}
let mut scovilles = std::collections::HashMap::new();
あらかじめ、 use std::collections::HashMap; を宣言すると、 let mut scovilles = HashMap::new(); と書くことができます。
例2: 'a'から'z'をキーとし、それらのアスキーコードを項目とするdict asciicodes を生成する。
asciicodes = {
chr(ord('a') + i): ord('a') + i
for i in range(26)
}
let asciicodes: std::collections::HashMap<_, _> = (0..26)
.map(|i| {
let ascii_code = ('a' as u8) + i;
(ascii_code as char, ascii_code as i64)
})
.collect();
Rustではキーと項目のタプルをcollectさせることで、宣言的にdictを作成できます。
dictに項目を設定する
例: dict scovilles に 'habanero' から 100,000 へのマッピングを設定（既に存在する場合は項目を上書き）する。
scovilles['habanero'] = 100_000
scovilles.insert("habanero", 100_000);
Rustでは scovilles["habanero"] = 100_000; とは書けないです。
dictの要素数を求める
例: dict scovilles の項目数を cardinality に束縛する。
cardinality = len(scovilles)
let cardinality = scovilles.len();
ある要素がdictのキーとして存在するか判定する
例: dict scovilles のキーに 'reaper' が含まれるならば真、そうでなければ偽を has_reaper に束縛する。
has_reaper = 'reaper' in scovilles
let has_reaper = scovilles.contains_key(&"reaper");
Rustでは引数は参照型であることに注意してください(strの場合は & 付けなくてもよいですが）。
dictの指定したキーの項目を求める
例1: dict scovilles のキー 'habanero' の項目を habanero に束縛する。
habanero = scovilles['habanero']
let habanero = scovilles[&"habanero"];
例2: dict scovilles の 'reaper' の項目を reaper に束縛する。ただし、 scovilles のキーに 'reaper' が含まれないならば 0 を束縛する。
reaper = scovilles.get('reaper', 0)
let reaper = *scovilles.get("reaper").unwrap_or(&0);
キーが存在しない可能性がある場合、Rustでもgetメソッドを使います。getメソッドはOptionを返すのでunwrap_orメソッドを用いるとよいです。
dictをイテレートする
例: dict scovilles のキーと項目のペアを空白区切りで1行ずつ出力する。
for k, v in scovilles.items():
print(k, v)
for (&k, &v) in &scovilles {
println!("{} {}", k, v);
}
dictから項目を削除する
例: dict scovilles からキー 'habanero' とそれに対応する項目を削除する。
scovilles.pop('habanero')
scovilles.remove(&"habanero");
set
Rustではstd::collections::HashSetを使います。
setとHashSetの関係はdictとHashMapの関係とほぼ同じです。
ideoneでの実行結果
setを生成する
例1: 空のset s を生成する。
s = set()
let mut s = std::collections::HashSet::new();
例2: 0以上10未満の偶数のset evens を生成する。
s = set()
let evens: std::collections::HashSet<_> = (0..10)
.filter(|&i| i % 2 == 0)
.collect();
setに要素を追加する
例: set s に 8 を追加する。
s.add(8)
s.insert(8);
setの要素数を求める
例: set s の要素数を cardinality に束縛する。
cardinality = len(s)
let cardinality = s.len();
ある要素がsetに含まれるか判定する
例: set s に 1 が含まれるならば真、そうでなければ偽を has_one に束縛する。
has_one = 1 in s
let has_one = s.contains(&1)
setをイテレートする
例: set s の要素を空白区切りで1行ずつ出力する。
for x in s:
print(x)
for &x in &s {
println!("{}", x);
}
setから要素を削除する
例: set s から 8 を削除する。
s.remove(8)
s.remove(&8);
ヒープ
ここでは、（Pythonの heapq に合わせて）Minヒープとして扱う方法を説明します。Rustではstd::collections::BinaryHeapを使います。
ideoneでの実行結果
空のヒープを生成する
例: 空のヒープ q を生成する。
import heapq
q = []
let mut q = std::collections::BinaryHeap::new();
ヒープに要素を追加する
例: ヒープ q に3, 1, 4 をこの順で追加する。
heapq.heappush(q, 3)
heapq.heappush(q, 1)
heapq.heappush(q, 4)
q.push(-3);
q.push(-1);
q.push(-4);
BinaryHeapはMaxヒープなので、符号を反転しています。
タプルを要素する場合でも、辞書式順序で比較するので、適宜符号を反転すればよいです
（Rust 1.15.1(2019/09/07時点でのAtCoderのRustのバージョン)では、std::cmp::Reverse
は使用できないので注意してください）。
ヒープの最小要素を求める
例: ヒープ q の最小要素を top に束縛する。
top = q[0]
let top = -(*q.peek().unwrap());
Rustの方は符号を反転した要素を追加しているので、符号を反転して元に戻しています。
ヒープが空か判定する
例: ヒープ q が空ならば真、そうでなければ偽を is_empty に束縛する。
has_element = q == []
let is_empty = q.is_empty();
ヒープの最小要素を取り出す
例: ヒープ q の最小要素を削除し、削除した要素を popped に束縛する。
popped = heapq.heappop(q)
let popped = -q.pop().unwrap();
popメソッドが返す値は参照型ではないので、参照外しは不要であることに注意してください。
defaultdict
Rustではstd::collections::HashMapをdefaultdictとして使います。
HashMapからstd::collections::hash_map::Entryを取得し、Entryのor_insertメソッドを用いてデフォルト値を得られるようにします。
ideoneでの実行結果
defaultdictを生成する
例: デフォルト値が0であるdefaultdict scovilles を生成する。
import collections
scovilles = defaultdict(int)
let mut scovilles = std::collections::HashMap::new();
scovilles はただのHashMapなのでdefaultdictではないですが、項目を取得する際に工夫することでdefaultdictのように扱えます。
defaultdictに項目を設定する
例: defaultdict scovilles に 'reaper' から 2,000,000 へのマッピングを設定（既に存在する場合は項目を上書き）する。
scovilles['reaper'] = 2_000_000
scovilles.insert("reaper", 2_000_000);
defaultdictの指定したキーの項目を求める
例: defaultdict scovilles のキー 'habanero' の項目を habanero に束縛する。ただし、 scovilles にキー 'habanero' が存在しない場合、
scovilles に 'habanero' から 0(デフォルト値) へのマッピングを設定した上で habanero にはデフォルト値である0を束縛する。
habanero = scovilles['habanero']
let habanero = *scovilles.entry("habanero").or_insert(0);
Counter
defaultdict同様、Rustではstd::collections::HashMapをCounterとして使います。残念ながらPythonのように楽はできないです。
ideoneでの実行結果
Counterを生成する
例: リスト [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] の各整数に関するCounter c を生成する。
import collections
c = collections.Counter([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
let mut c = std::collections::HashMap::new();
for &i in &vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] {
*(c.entry(i).or_insert(0)) += 1;
}
ここでもEntryの or_insert が役立ちます。
指定したキーのカウントを求める
例: Counter c の5のカウントを num_of_five に束縛する。
num_of_five = c[5]
let num_of_five = *c.get(&5).unwrap_or(&0);
dictと同様です。
指定したキーのカウントを増やす
例: Counter c の3のカウントを57増やす
c[3] += 57
*(c.entry(&3).or_insert(0)) += 57;
or_insert を用いることで加算代入できます。
deque
Rustではstd::collections::VecDequeを使います。
ideoneでの実行結果
空のdequeを生成する
例: 空のdeque d を生成する。
import collections
d = collections.deque()
let mut d = std::collections::VecDeque::new();
dequeの先頭に要素を追加する
例: deque d の先頭に 4 を追加する。
d.appendleft(4)
d.push_front(4);
dequeの末尾に要素を追加する
例: deque d の末尾に 2 を追加する。
d.append(2)
d.push_back(2);
dequeの要素数を求める
deque dの要素数を cardinality に束縛する
cardinality = len(d)
let cardinality = d.len();
dequeの先頭要素を求める
例: deque d の先頭要素を head に束縛する。
head = d[0]
let head = *d.front().unwrap();
dequeの末尾要素を求める
例: deque d の末尾要素を tail に束縛する。
tail = d[-1]
let tail = *d.back().unwrap();
dequeの先頭要素を削除する
例: deque d の先頭要素を削除し、削除した要素を popped_head に束縛する。
popped_head = d.popleft()
let popped_head = d.pop_front().unwrap();
dequeの末尾要素を削除する
例: deque d の末尾要素を削除し、削除した要素を popped_tail に束縛する。
popped_tail = d.pop()
let popped_tail = d.pop_back().unwrap();
イテレート
Pythonのコードではitertoolsモジュールとfunctoolsモジュールがインポートされているとして説明します。
import itertools
import functools
ideoneでの実行結果
reversed
例: 整数リスト xs の順序を逆転したリストを rev_xs に束縛する。
rev_xs = list(reversed(xs))
let rev_xs: Vec<i64> = xs.iter().map(|&x| x).rev().collect();
.map(|&x| x) は .copied() の代用です（Rust 1.15.1(2019/09/07時点でのAtCoderのRustのバージョン)では、Iteratorにcopiedメソッドがないため）。
accumulate
例: 整数リスト xs の累積和のリストを acc に束縛する。
acc = list(itertools.accumulate(xs))
let acc: Vec<_> = xs.iter()
.scan(0, |state, &x| { *state += x; Some(*state) })
.collect();
zip
例: 整数リスト xs と ys から要素を集めたリストを xys に束縛する。
xys = list(zip(xs, ys))
let xys: Vec<_> = xs.iter().map(|&x| x).zip(ys.iter().map(|&x| x)).collect();
map
例: 整数リスト xs の各要素を2乗したリストを sqs に束縛する。
sqs = list(map(lambda x: x**2, xs))
let sqs: Vec<_> = xs.iter().map(|&x| x.pow(2)).collect();
filter
例: 整数リスト xs から奇数の要素を抽出したリストを odds に束縛する。
odds = list(filter(lambda x: x % 2 == 1, xs))
let odds: Vec<_> = xs.iter().filter(|&&x| x % 2 == 1).map(|&x| x).collect();
reduce
例: フィボナッチ数列 [0, 1, 1, 2, 3, 5, 8, ...] の第5項（0-indexed）を fib5 に束縛する。
fib5, _ = functools.reduce(
lambda p, _: (p[0] + p[1], p[0]),
range(4),
(1, 0)
)
let (fib5, _) = (0..4).fold(
(1, 0),
|(p, pp), _| (p + pp, p)
);
Pythonではlambda関数の引数に対してアンパック代入を適用できませんが、Rustではそれが可能です。添字アクセスしなくて済むのは嬉しいですね。
max/min
例1: 整数リスト xs の最大値を x_max に束縛する。
x_max = max(xs)
let x_max = *xs.iter().max().unwrap();
例2: 整数リスト zs の最小値を z_min に束縛する。ただし、 zs が空ならば0を z_min に束縛する。
z_min = min(zs, default=0)
let z_min = *zs.iter().max().unwrap_or(&0);
例3: 整数リスト xs に含まれる要素のうち、2で割った余りが最小となる要素を x_argmin に束縛する。ただし、そのような要素が複数存在する場合、リストの先頭に近い要素を x_argmin に束縛する。
x_argmin = min(xs, key=lambda x: x % 2)
let x_argmin = *xs.iter().min_by_key(|&&x| x % 2).unwrap();
sum
例: 整数リスト xs の各要素の和を s に束縛する。
s = sum(xs)
let s: i64 = xs.iter().sum();
all/any
例1: 整数リスト xs の要素がすべて奇数ならば真、そうでなければ偽を is_all_odd に束縛する。
is_all_odd = all(x % 2 == 1 for x in xs)
let is_all_odd = xs.iter().all(|&x| x % 2 == 1);
例2: 整数リスト xs の要素に偶数が存在するならば真、そうでなければ偽を does_exist_even に束縛する。
does_exist_even = any(x % 2 == 0 for x in xs)
let does_exist_even = xs.iter().any(|&x| x % 2 == 0);
enumerate
例: 整数リスト xs から各要素のインデックス(0-indexed)とその要素をペアにしたリストを indexed_xs に束縛する。
indexed_xs = [(i, x) for i, x in enumerate(xs)]
let indexed_xs: Vec<_> = xs.iter().map(|&x| x).enumerate().collect();
Rustではインデックスの開始番号を指定できないことに注意してください。例えば、1-indexedにしたい場合は、1スタートのrangeオブジェクトとzipさせればよいです。
sorted
例: 整数リスト xs を昇順ソートしたリストを sorted_xs に束縛する。
sorted_xs = sorted(xs)
let sorted_xs: Vec<_> = {
let mut tmp_xs = xs.clone();
tmp_xs.sort();
tmp_xs
};
Rustの標準ライブラリには非破壊的なソートメソッドは存在しません。
range
例1: 0以上10未満の整数のリストを ps に束縛する。
ps = list(range(10))
let ps: Vec<_> = (0..10).collect();
例2: 1以上10未満の整数のリストを qs に束縛する。
qs = list(range(1, 10))
let qs: Vec<_> = (1..10).collect();
なお、 Rust 1.15.1(2019/09/07時点でのAtCoderのRustのバージョン)では、rangeのstepをカスタムするのは（スマートには）できないです。
スライス
例1: 整数リスト xs の先頭から3番目まで(0-indexed, exclusive)の要素から成るリストを heads に束縛する。
heads = xs[:3]
let heads = xs[..3].to_vec();
例2: 整数リスト xs の3番目から(0-indexed, inclusive)末尾までの要素から成るリストを tails に束縛する。
tails = xs[3:]
let tails = xs[3..].to_vec();
文字列
標準入出力でも述べた通り、Rustでは文字列を Vec<char> として扱うと使い勝手がよいです。
Vec<char> として扱えば、listで述べた操作が可能なので、i文字目の取得や特定の文字のカウントが可能です。
ここでは、数字の文字を整数に変換する方法と整数を文字列に変換する方法についてのみ述べます。
ideoneでの実行結果
int
例: 文字 '1' を整数1として x に束縛する。
x = int('1')
let x = '1'.to_digit(10).unwrap() as i64;
'1' as i64 だと x は49（'1'のASCIIコード）になることに注意してください。
str
例: 整数42を文字列として s に束縛する。
s = str(42)
let y: Vec<_> = 42.to_string().chars().collect();
Rustでは文字のリストとして s に束縛しています。
String型として束縛したいならば、単に let y = 42.to_string(); でよいです。
数学
ideoneでの実行結果
abs
例: 整数 x の絶対値を a に束縛する。
a = abs(x)
let a = x.abs();
gcd
例: 整数 p, q の最大公約数を g に束縛する。
import fractions
p = 12
q = 18
g = fractions.gcd(p, q)
AtCoderのPythonバージョンは3.4.3なので、math.gcdではなくfractions.gcdを用いています。
let g = {
fn gcd(x: i64, y: i64) -> i64 {
if y == 0 {
x
} else {
gcd(y, x % y)
}
}
gcd(p, q)
};
残念ながら、Rustの標準ライブラリにはgcdはありません。
pow
例1: 正の整数 q, n について、 q の n 乗を z に束縛する。
z = q**n
let z = q.pow(n);
例2: 整数 q の $10^9 + 5$ 乗に対する $10^9 + 7$ の剰余を r に束縛する。
r = pow(q, 10**9 + 5, 10**9 + 7)
let r = {
fn mod_pow(x: i64, y: i64, z: i64) -> i64 {
if y == 0 {
1
} else {
let h = mod_pow(x, y / 2, z);
let res = (h * h) % z;
if y % 2 == 0 {
res
} else {
(res * x) % z
}
}
}
mod_pow(q, 1_000_000_005, 1_000_000_007)
};
Rustのpowは剰余をとるべき乗を求められないので、自力でダブリングしています。
sqrt
例: 正の整数 q の平方根を s に束縛する。
import math
s = math.sqrt(q)
let s = (q as f64).sqrt();
i64にはsqrtメソッドはないので、f64にキャストします。
bisect
RustのVecにはbinary_searchメソッドがありますが、同一の要素が複数存在する場合、得られるインデックスは不定なので、競技プログラミングにおいて使うのは厳しいです。
仕方ないので、自力で二分探索します。
ideoneでの実行結果
bisect_left
例: 昇順ソートされている整数のリスト x から、5以上の要素のうち、最小のインデックスを i に束縛する。
i = bisect.bisect_left(x, 5)
fn bis<P>(ok: i64, ng: i64, p: P) -> i64
where P: Fn(i64) -> bool {
let mid = (ok + ng) / 2;
if (ok - ng).abs() == 1 {
ok
} else if p(mid) {
bis(mid, ng, p)
} else {
bis(ok, mid, p)
}
}
let i = bis(x.len() as i64, -1, |i| x[i as usize] >= 5);
println!("i = {}", i);
Rustの bis は二分探索を行う関数です（所謂めぐる式）。
i64に対して二分探索を行うので、Vecの要素にアクセスする際はusizeにキャストしています。
bisect
例: 昇順ソートされている整数のリスト x から、5より大きい要素のうち、最小のインデックスを j に束縛する。
j = bisect.bisect(x, 5)
fn bis<P>(ok: i64, ng: i64, p: P) -> i64
where P: Fn(i64) -> bool {
let mid = (ok + ng) / 2;
if (ok - ng).abs() == 1 {
ok
} else if p(mid) {
bis(mid, ng, p)
} else {
bis(ok, mid, p)
}
}
let j = bis(x.len() as i64, -1, |i| x[i as usize] > 5);
println!("j = {}", j);
Rustのコードは bis のクロージャの不等号から等号が外れています。
おわりに
比較してみると、やはりPythonの方がコーディングは楽ですが、Rustもそれほど悪くないかなと感じます
（標準ライブラリがやや貧弱なのがつらいですが）。
個人的には、Rustのクロージャのパターンマッチがお気に入りです。