Rustでmultisetを使う

Rustでmultisetを使う

C++のmultiset相当のものはRustの標準ライブラリにないが、いい代用方法を見つけたのでメモ

AtCoderの提出一覧から頭のいいコードを見つけたのでパクる

multisetとは

multiset は連想コンテナの一種であり、要素自身がキーとなる。

連想コンテナは特にそれらキーによる要素アクセスが効率的になるよう設計されたコンテナである（要素への相対位置または絶対位置によるアクセスが効率的であるシーケンシャルコンテナとは異なる）。

内部的には、multiset 内の要素は、コンテナの構築時に設定された狭義の弱順序基準に従って小さいものから大きいものへとソートされる。

setが重複キーを許可しないのに対し、multisetは重複キーを許可する。

cpprefjp.github.io

代用方法

方針

BTreeSetを使用し、要素に重複しないものをタプルで持たせることで重複キーを許可する

multisetとの対応

使ったもの・わかりにくかったものを書く

説明	C++	Rust
型	multiset	BTreeSet
挿入	insert(x)	&self.insert((x, 重複しない値))
与えられた値より大きいもの	upper_bound(x)	&self.range((x, 十分小さい値)..)
与えられた値より小さいもの	lower_bound(x)	&self.range(..=(x, 十分大きい値))

他もBTreeSetのメソッド、Rustのiterを使っていい感じに書けると思う

使用例

atcoder.jp

use std::collections::BTreeSet;
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        query: usize
    };

    let mut a = BTreeSet::new();
    let inf = std::usize::MAX;
    for i in 0..query {
        input! { q: usize, x: usize };
        match q {
            1 => {
                a.insert((x, i));
            },
            2 => {
                input! { k: usize };
                if let Some((x, _)) = a.range(..=(x, inf)).rev().nth(k - 1) {
                    println!("{}", x);
                } else {
                    println!("-1");
                }
            },
            3 => {
                input! { k: usize };
                if let Some((x, _)) = a.range((x, 0)..).nth(k - 1) {
                    println!("{}", x);
                } else {
                    println!("-1");
                }
            },
            _ => unreachable!()
        }
    }
}