(2021/11/27 更新)

私は今までC++で競プロをしていたのですが、パソコンをM1 Macに変えてC++の環境を構築するのが面倒になっていました。せっかくなら流行りのRustでやろうという気持ちが湧いてきました。しかしまだまだ慣れていないのでC++のSTLなどと同等のものをどうやってRustで記述するかをメモしていきたいと思います。

std

collections

collectionsについて

全然ドキュメント読んでなかったのですが、こういうのがあtたんですね、すごい。

BTreeSet

C++ の set に当たります。

// initialize
let mut set = BTreeSet::new();
let mut set = BTreeSet::from([1, 2, 3]);
let mut set = (0..10).collect::<BTreeSet<_>>();

set.insert(10);
set.remove(2);

set.contains(3);
set.range(3..) // equivalent to lower_bound in C++

集合演算は割愛。

doc 練習問題

BTreeMap

C++ の map に当たります。

キーの順序を考慮しなくていい場合は HashMap でも良さそうです。

// initialize
let mut mp = BTreeMap::new();
mp.insert("hoge", 1);
mp.insert("fuga", 2);

mp.contains_key("hoge");
mp.remove("fuga");

match mp.get("hoge") {
    Some(value) => println!("{} is contained", value),
    None => println!("Not found"),
}

// update
*mp.entry("fuga").or_insert(0) += 10; // using Entry API

doc

VecDeque

C++ の queue あるいは deque として使えます。

let mut q = VecDeque::new();
q.push_back(1);
q.push_back(2);
q.push_back(3);

while !q.is_empty() {
    if let Some(x) = q.pop_front() {
        // code
    }
}

doc

BinaryHeap

C++ の priority_queue に相当する。

let mut pq = BinaryHeap::new();

heap.push(1);
heap.push(3);
heap.push(2);

heap.peek(); // Some(&3);

heap.pop(); // Some(&3);
heap.pop(); // Some(&2);

大きい順に並んでいるみたいです。

数値系であれば-1をかけて逆順にすることができますが一般にはそうではないので、std::cmp::Reverse を使うみたいです。

doc

よくある処理

別記事にした方がいいかもしれない

bit全探索

unimplemented!();

DP

unimplemented!();

グラフ

unimplemented!();

  • {in,pre,post} order fashion
  • dijkstra
  • floyd-warshall

累積和

unimplemented!();

浮動小数点数の扱い

unimplemented!();