Jan 2023 Language Update ライブラリ案

このページは誰でも編集できます。

2023年環境に要望するクレート
- ac-library-rs
- once_cell
- static_assertions
- varisat
- memoise
- argio
- bitvec
- counter
- hashbag
- pathfinding
- recur-fn
- indexing
- ~~index_vec~~
- ~~with_locals~~
- amplify
- ~~ouroboros~~
- easy-ext
- multimap
- btreemultimap
- bstr
- az
- glidesort
- tap
- omniswap
2020年環境のクレート
- num
  - num-bigint
  - num-complex
  - num-integer
  - num-iter
  - num-rational
  - num-traits
- num-derive
- ndarray
- nalgebra
  - alga
- libm
- rand
  - getrandom
  - rand_chacha
  - rand_core
  - rand_hc
  - rand_pcg
- rand_distr
- petgraph
- indexmap
- regex
- lazy_static
- ordered-float
- ascii
- permutohedron
- superslice
- itertools
- itertools-num
- maplit
- either
- im-rc
- fixedbitset
- bitset-fixed
- proconio
- text_io
- ~~whiteread~~
- rustc-hash
- smallvec

2023年環境に要望するクレート

ac-library-rs

Version

c03e2cab25a5997ed00674fee5f821e5a5433b42 (Crates.ioにまだアップロードしていない)

Comment

ac-libraryのRust実装。 (@qryxip)
このままでもライブラリとしては機能するとはいえ、Crates.ioへのアップロードを含めまだ色々やることがあるため、急いでやっていく。 (@qryxip)

once_cell

Version

v1.17.1

Comment

lazy_staticと同じく、グローバル変数を定義できる。 (@qryxip)

use std::{collections::HashSet, sync::Mutex};

use once_cell::sync::Lazy;

static SET: Lazy<Mutex<HashSet<i32>>> = Lazy::new(|| Mutex::new([0, 1, 2].into()));

lazy_staticよりも今はこちらの方が使われているはず。また今標準ライブラリに入りかけている。 (@qryxip)

とはいえ今はMutexがconst文脈で用意できたりするので、利用する機会は減ってるかもしれない。 (@qryxip)

use std::{collections::BTreeSet, sync::Mutex};

// 中身を入れるのは非const文脈じゃないと無理
SET.lock().unwrap().extend([0, 1, 2]);

static SET: Mutex<BTreeSet<i32>> = Mutex::new(BTreeSet::new());

static_assertions

Version

v1.1.0

Comment

型の性質やconst文脈での真偽値を、コンパイル時にassertできる。 (@qryxip)

use static_assertions::{assert_impl_all, const_assert_eq};

// u16はusizeに変換可能である
assert_impl_all!(u16: Into<usize>);

// 1+1=2である
const_assert_eq!(1 + 1, 2);

その性質上手元でさえ動けばいいので、AtCoder側に入れなくてもこうすればいいのでは?と思わなくもない。 (@qryxip)

// 手元のコードエディタではエラーがちゃんと出て、かつAtCoder側でcargo buildするときは無視される
#[cfg(test)]
const _: () = {
    use static_assertions::{assert_impl_all, const_assert_eq};

    // u16はusizeに変換可能である
    assert_impl_all!(u16: Into<usize>);

    // 1+1=2である
    const_assert_eq!(1 + 1, 2);
};

varisat

Version

v0.2.2

Comment

SATソルバー。 (@qryxip)
まあ一応提案するだけした方がいいかもしれない? (@qryxip)

memoise

Version

v0.3.2

Comment

@tanakh氏製の、競プロ用途に特化したメモ化ライブラリ。 (@qryxip)
- 氏のブログ記事
cachedがよくメンテされているようだが、上記のブログの通りAtCoderには向かないかもしれない。 (@qryxip)

argio

Version

v0.2.0

Comment

@tanakh氏製の、競プロ用標準入出力ライブラリ。 (@qryxip)
- 氏のブログ記事
今のRust Analyzerならproconioの補完も十分にできるため、相対的な重要性は下がっている気はする。 (@qryxip)

bitvec

Version

v1.0.1

Comments

fixedbitsetやbitset-fixedと比べてGitHubのStarが多く、機能も充実している。(@falrnd)
fixedbitsetを置き換えるものではないと思う。bitvecはVec<bool>のように振る舞い、fixedbitsetはBTreeSet<usize>のように振る舞う。(@qryxip)

boolのスライスやVecのように振る舞う型を提供する。 (@qryxip)

整数をビット列として挿入することもできる。

use bitvec::prelude::*;

let mut bits = bitvec![u8, Msb0;];

bits.extend(0b00010101u8.view_bits::<Lsb0>());
bits.push(true);

assert_eq!(
    bits.into_iter().map(u8::from).collect::<Vec<_>>(),
    [1, 0, 1, 0, 1, 0, 0, 0, 1],
);
//   ^^^^^^^^^^^^^^^^^^^^^^  ^
//   0b00010101              true

counter

Version

v0.5.7

Comments

Pythonのcollections.Counterのようなものを提供する。 (@qryxip)

use counter::Counter;

let mut counts = Counter::<_>::new();

counts += *b"abbccc";
counts[&b'd'] += 4;

assert_eq!(counts[&b'a'], 1);
assert_eq!(counts[&b'b'], 2);
assert_eq!(counts[&b'c'], 3);
assert_eq!(counts[&b'd'], 4);

assert_eq!(
    counts.most_common_ordered(),
    [(b'd', 4), (b'c', 3), (b'b', 2), (b'a', 1)],
);

use counter::Counter;

let counts1 = b"abc".iter().copied().collect::<Counter<_>>();
let counts2 = b"cde".iter().copied().collect::<Counter<_>>();

assert_eq!(
    (counts1.clone() + counts2.clone()).into_map(),
    [(b'a', 1), (b'b', 1), (b'c', 2), (b'd', 1), (b'e', 1)].into(),
);
assert_eq!(
    (counts1 - counts2).into_map(),
    [(b'a', 1), (b'b', 1)].into(),
);

2020年の時は__getitem__/__setitem__にあたる操作ができない、それほど有名ではないという2つの理由で提案から外したが、前者は私が実装し、後者についてはいつの間にかめちゃくちゃ使われるようになっていた。 (@qryxip)

hashbag

Version

v0.1.11

Comments

C++のstd::unordered_multisetにあたるものを提供する。 (@qryxip)

use hashbag::HashBag;

let mut bag = HashBag::new();

bag.insert(b'a');
bag.insert(b'b');
bag.insert(b'b');

BTreeMap<T, usize>などで頑張ることもできるが、結構手間であるためコンテスト後によく悲鳴が聞こえた記憶がある。 (@qryxip)

pathfinding

Version

v4.2.1

Comments

グラフ関係のアルゴリズムを提供する。 (@qryxip)

petgraphと比べてAPIが簡略化されており、こちらであればアルゴリズムコンテストでの利用に耐えるのではないか。

#[rustfmt::skip]
let maze = [
    b"...##",
    b".#...",
    b".#.##",
    b".#.##",
    b".#...",
];

let h = maze.len();
let w = maze[0].len();

let (path, cost) = pathfinding::directed::dijkstra::dijkstra::<(usize, usize), _, _, _, _>(
    &(0, 0),
    |&(i, j)| {
        [
            (i.wrapping_sub(1), j),
            (i + 1, j),
            (i, j.wrapping_sub(1)),
            (i, j + 1),
        ]
        .into_iter()
        .filter(|&(i, j)| i < h && j < w && maze[i][j] == b'.')
        .map(|p| (p, 1))
    },
    |&p| p == (h - 1, w - 1),
)
.unwrap();

assert_eq!(
    path,
    [
        (0, 0),
        (0, 1),
        (0, 2),
        (1, 2),
        (2, 2),
        (3, 2),
        (4, 2),
        (4, 3),
        (4, 4),
    ],
);
assert_eq!(path.len() - 1, cost);

recur-fn

Version

v2.2.0

Comments

Rustでは自己再帰するクロージャを書くのに一手間要るが、その一手間をやってくれる。 (@qryxip)

use proconio::input;
use recur_fn::RecurFn as _;

input! {
    f0: u32,
    f1: u32,
    n: [u32],
}

let fib = recur_fn::recur_fn(|fib, n| match n {
    0 => f0,
    1 => f1,
    n => fib(n - 2) + fib(n - 1),
});
let fib = |n| fib.call(n);

for n in n {
    println!("{}", fib(n));
}

上記の例を書いているときに気付いたが、rust-analyzerがハングしてしまう。 (@qryxip)

indexing

Version

v0.4.1

Comments

[T]への境界チェックを先に行うことで、「特定の[T]にチェック無しで何度でもアクセスできる添字型/範囲型」を作れる。 (@qryxip)

[T]からは[0, n-1]の範囲のindexing::Rangeが取れ、そこから「より小さな」indexing::{Index, Range}が取れる。そこから境界チェック無しのアクセスが何度でもできる。

let mut xs = vec![0, 1, 2, 3, 4];

indexing::scope(&mut xs, |xs| {
    let range = xs.range();

    // 境界チェックをスキップしてアクセス
    for &x in &xs[range] {
        println!("{x}");
    }

    // 空ではないことをチェック
    let range = range.nonempty().unwrap();

    // そうすると「最初の要素」と「最後の要素」に境界チェック無しでアクセスできる
    println!("{}", xs[range.first()]);
    println!("{}", xs[range.last()]);
});

// これはコンパイルエラーになる
fn f(xs: &[i32], ys: &[i32]) {
    indexing::scope(xs, |xs| {
        indexing::scope(ys, |ys| {
            let index_of_xs = xs.vet(0).unwrap();
            let _ = ys[index_of_xs];
        });
    });
}

上記のrecur-fnもそうだが、原理がわかってしまえば手作りできる類のものではある。 (@qryxip)

index_vec

Version

~~v0.1.3~~

Comments

[T]/Vec<T>の添字をusize以外にできるライブラリ。 (@qryxip)

use index_vec::{index_vec, IndexVec};

index_vec::define_index_type! {
    pub struct Idx = u8;
}

let items: IndexVec<Idx, u8> = index_vec![b'a', b'b', b'c'];

let mut i = Idx::new(0);
i += 1usize;

assert_eq!(items[i], b'b');

冷静に考えるとアルゴリズムコンテストには使いにくい。私の提案だが、freezeするからといって入れるべきではなかったかもしれない。 (@qryxip)

with_locals

Version

~~v0.1.3~~

Comments

参照の継続(名前がわからない)を簡易にする。 (@qryxip)

次のようなことをやりたいときwith_modulusはネストする必要があり、視認性が悪い。

use proconio::input;

fn main() {
    input! {
        m1: u32,
        m2: u32,
        m3: u32,
    }

    with_modulus(m1, |m1| {
        with_modulus(m2, |m2| {
            with_modulus(m3, |m3| {
                let x = m1.mk(0);
                let y = m2.mk(0);
                let z = m3.mk(0);
            });
        });
    });
}

fn with_modulus<F, O>(modulus: u32, f: F) -> O
where
    F: for<'modulus> FnOnce(&'modulus DynamicModulus) -> O,
{
    f(&DynamicModulus(modulus))
}

struct DynamicModulus(u32);

impl DynamicModulus {
    fn mk(&self, value: u32) -> DynamicModInt<'_> {
        DynamicModInt {
            value: value % self.0,
            modulus: &self.0,
        }
    }
}

struct DynamicModInt<'modulus> {
    value: u32,
    modulus: &'modulus u32,
}

そこでこのライブラリを使えばフラットにできる。またwith_modulusの定義も簡単にできる。

use with_locals::with;

#[with]
fn main() {
    input! {
        m1: u32,
        m2: u32,
        m3: u32,
    }

    #[with]
    let m1 = modulus(m1);
    #[with]
    let m2 = modulus(m2);
    #[with]
    let m3 = modulus(m3);

    let x = m1.mk(0);
    let y = m2.mk(0);
    let z = m3.mk(0);
}

#[with('local)]
fn modulus(modulus: u32) -> &'local DynamicModulus {
    &DynamicModulus(modulus)
}

また上記で紹介したindexingに(無理矢理)使うこともできる。

fn f(xs: &[i32], ys: &[i32], zs: &[i32]) {
    indexing::scope(xs, |xs| {
        indexing::scope(ys, |ys| {
            indexing::scope(zs, |zs| {
                todo!();
            })
        })
    })
}

↓

use with_locals::with;

#[with]
fn f(xs: &[i32], ys: &[i32], zs: &[i32]) {
    use indexing::scope as with_indexing;

    #[with]
    let xs = indexing(xs);
    #[with]
    let ys = indexing(ys);
    #[with]
    let zs = indexing(zs);

    todo!();
}

多分使い所は限られる。 (@qryxip)
私の提案だが、こっちも早まったかもしれない。 (@qryxip)

amplify

Version

v3.14.2

Comments

手書きで書くにはだるいが、ライブラリとして持つほどでも無いようなショートハンドを多数提供する。 (@qryxip)

maplit風のマクロや、i1024型やu7型とかもある。

use std::collections::BTreeMap;

use amplify::{
    bmap,
    num::{i1024, u7},
    s,
};

let _: String = s!("foo");
let _: BTreeMap<i32, i32> = bmap!(0 => 1);
let _ = u7::try_from(42).unwrap();
let _ = i1024::from(1) << 1000;

ouroboros

Version

~~v0.15.5~~

Comments

「自己参照」をする構造体を、健全性(soundness)を保ったまま定義する機能を提供する。 (@qryxip)

ライブラリの設計をやらかしたときに、利用側でリカバリする用途に使える。

use std::mem;

use ouroboros::self_referencing;

let mut stack = ResettableStack::from([0, 1, 2, 3, 4]);
assert_eq!(*stack.borrow_remaining(), [0, 1, 2, 3, 4]);

assert_eq!(stack.pop(), Some(4));
assert_eq!(*stack.borrow_remaining(), [0, 1, 2, 3]);

stack.reset();
assert_eq!(*stack.borrow_remaining(), [0, 1, 2, 3, 4]);

#[self_referencing]
struct ResettableStack {
    buf: Vec<i32>,

    #[borrows(buf)]
    remaining: &'this [i32],
}

impl ResettableStack {
    fn pop(&mut self) -> Option<i32> {
        self.with_remaining_mut(|remaining| {
            let popped = remaining.last().copied();
            *remaining = &remaining[..remaining.len() - 1];
            popped
        })
    }

    fn reset(&mut self) {
        *self = mem::replace(self, [].into()).into_heads().buf.into()
    }
}

impl<B: Into<Vec<i32>>> From<B> for ResettableStack {
    fn from(buf: B) -> Self {
        ResettableStackBuilder {
            buf: buf.into(),
            remaining_builder: |buf| buf,
        }
        .build()
    }
}

私の提案だが、こっちも早まったかもしれない。 (@qryxip)

easy-ext

Version

v1.0.1

Comments

extension trait patternのショートハンドを提供する。 (@qryxip)

use easy_ext::ext;
use proconio::input;

input! {
    n: usize,
}

n.times(|| println!("Yes"));

#[ext]
impl usize {
    fn times(self, mut f: impl FnMut()) {
        for _ in 0..self {
            f();
        }
    }
}

あまり利用機会は無さそうな上、数行分省略できる程度ではある。 (@qryxip)
私の提案だが、こっちも早まったかもしれない。 (@qryxip)

multimap

Version

v0.9.0

Comments

btreemultimap

Version

v0.1.1

Comments

bstr

Version

v1.4.0

Comments

A string type that is not required to be valid UTF-8.

az

Version

v1.2.1

Comments

Casts and checked casts

glidesort

Version

v0.1.2

Comments

Glidesort sorting algorithm
Pattern-defeating quicksort (pdqsort) (pdqsortをもとにした実装は、 Rust 1.20.0 以降の sort_unstable、 Go 1.19 など) の作者によって、 2023-02 の FOSDEM'23 にて発表された、安定な比較ソート(stable comparison sort)の実装。 (@mizar)

tap

Version

v1.0.1

Comments

Generic extensions for tapping values in Rust

omniswap

Version

v0.1.0

Comments

swap values between possibly-overlapping references

2020年環境のクレート

AtCoder 2020

num

Version

v0.2.1 → v0.4.0

Sub-crates

num-bigint v0.2.6 -> v0.4.3
num-complex v0.2.4 -> v0.4.3
num-integer v0.1.42 -> v0.1.45
num-iter v0.1.40 -> v0.1.43
num-rational v0.2.4 -> v0.4.1
num-traits v0.2.11 -> v0.2.15

Comments

なんだかんだでみんな使っていた印象。(@qryxip)
色々機能が追加されたと思うが未調査。(@qryxip)

ndarray

Version

v0.13.0 → v0.15.6

Comments

色々機能が追加されたと思うが未調査。(@qryxip)

nalgebra

Version

v0.20.0 → v0.32.1

Sub-crates

alga v0.9.3 → v0.9.3

Comments

色々機能が追加されたと思うが未調査。(@qryxip)

libm

Version

v0.2.1 → v0.2.6

Comments

rand

Version

v0.7.3 → v0.8.5

Sub-crates

getrandom v0.1.14 → v0.2.8
rand_chacha v0.2.2 → v0.3.1
rand_core v0.5.1 → v0.6.4
rand_hc v0.2.0 → v0.3.1
rand_pcg v0.2.1 → v0.3.1

Comments

色々機能が追加されたと思うが未調査。(@qryxip)

rand_distr

Version

v0.2.2 → 0.4.3

Comments

色々機能が追加されたと思うが未調査。(@qryxip)

petgraph

Version

v0.5.0 → v0.6.2

Comments

色々機能が追加されたと思うが未調査。(@qryxip)

indexmap

Version

v1.3.2 → v1.9.2

Comments

regex

Version

v1.3.6 → v1.7.1

Comments

lazy_static

Version

v1.4.0 → v1.4.0

Comments

ordered-float

Version

v1.0.2 → v3.4.0

Comments

色々機能が追加されたと思うが未調査。(@qryxip)

ascii

Version

v1.0.0 → v1.1.0

Comments

個人的には使い道が見出せなかったが、そこそこ使われていた印象。(@qryxip)

permutohedron

Version

v0.2.4 → v0.2.4

Comments

superslice

Version

v1.0.0 → v1.0.0

Comments

itertools

Version

v0.9.0 → v0.10.5

Comments

使い道は多分結構多い。使っていた人も多いのではないか。(@qryxip)
色々機能が追加されたと思うが未調査。(@qryxip)

itertools-num

Version

v0.1.3 → v0.1.3

Comments

使っていた人はいるのか。(@qryxip)

maplit

Version

v1.0.2 → v1.0.2

Comments

今のRustだとHashSet::from([1, 2, 3])のように書けるとはいえ、maplitの書き方に慣れている人も多いのではないか。(@qryxip)

either

Version

v1.5.3 → v1.8.1

Comments

itertoolsがこれを返すことがあるので、それで使っていた人もいるのではないか。(@qryxip)

im-rc

Version

v14.3.0 → v15.1.0

Comments

なんか遅いらしいし、実用していた人はいるのか。(@qryxip)

fixedbitset

Version

v0.2.0 → v0.4.2

Comments

まあまあ手軽に使えたはずだし、使っていた人もいたかも。(@qryxip)

bitset-fixed

Version

v0.1.0 → v0.1.0

Comments

proconio

Version

v0.3.6 → v0.4.3

Comments

RustでAtCoderに参加している人にとっては、言わずと知れたライブラリ。 (@qryxip)
v0.3からの変更として致命的なバグの修正と、APIの追加がある(後で書く)。 (@qryxip)

text_io

Version

v0.1.8 → v0.1.12

Comments

The MIT non-military non-spy Licenseというライセンスだったのが純粋なMIT OR Apache-2.0に変わった。 (@qryxip)
その他の変更点は特に無いはず。read!時にstdoutをflushするようになったことくらい?(text_ioでやるべきことか?という気もする) (@qryxip)

whiteread

Version

v0.5.0 → ~~v0.5.0~~ 削除

Comments

つい最近気付いたが、ライセンスはMITといいつつThe MIT non-military non-spy License。罠でしょこれは (@qryxip)

rustc-hash

Version

v1.1.0 → v1.1.0

Comments

smallvec

Version

v1.2.0 → v1.10.0

Comments

AtCoder Rust Uncyclo
AtCoder言語アップデート (2019年7月)
AtCoder言語アップデート (2023年1月)
- Jan 2023 Language Update ライブラリ案
AtCoder言語アップデート (2024年11月)
- Nov 2024 Language Update ライブラリ案

Jan 2023 Language Update ライブラリ案

目次

2023年環境に要望するクレート

ac-library-rs

Version

Comment

once_cell

Version

Comment

static_assertions

Version

Comment

varisat

Version

Comment

memoise

Version

Comment

argio

Version

Comment

bitvec

Version

Comments

counter

Version

Comments

hashbag

Version

Comments

pathfinding

Version

Comments

recur-fn

Version

Comments

indexing

Version

Comments

index_vec

Version

Comments

with_locals

Version

Comments

amplify

Version

Comments

ouroboros

Version

Comments

easy-ext

Version

Comments

multimap

Version

Comments

btreemultimap

Version

Comments

bstr

Version

Comments

az

Version

Comments

glidesort

Version

Comments

tap

Version

Comments

omniswap

Version

Comments

2020年環境のクレート

num

Version

Sub-crates

Comments